Real Numbers

[Shadow]

Hey all,

 

another post just reminded me about this, and I've been wanting to post it for quite some time. However, math syntax and me don't go together, so excuse the errors.

 

Let us have a function (I'm using different brackets so they don't get confused with part of the interval) [math]N[x][/math], where [math]x[/math] represents an interval, and [math]N[x] =[/math] the number of real numbers in the interval [math]x[/math]. I know it will always be infinity, but bear with me.

 

 

Let [math]a_n= N[ <n; n+1) ]

\Rightarrow N[ R^{+}_{0} ]=\sum_{n=0}^{\infty}a_n[/math].

 

[math]\forall x \in R: x \in <1 ; \infty)[/math]

 

[math] \Rightarrow 1/x \in (0 ; 1>[/math]

 

[math]\Rightarrow N[ (0 ; 1> ] = N[ <1 ; \infty) ][/math]

 

[math]\Rightarrow \forall z \in Z^{+}_{0}: a_z=N[ <1 ; \infty) ] \wedge a_z=N[ (0 ; 1> ][/math]

 

[math] \Rightarrow N(R^{+}_{0}) = 2a_z[/math]

 

[math] \Rightarrow \sum_{n=0}^{\infty}a_n=2a_z[/math]

 

which is not true. How is this possible?

 

Cheers,

 

Gabe

Edited December 7, 2008 by Shadow

[the tree]

The amount of entries in a set is usually called that sets cardinality and is denoted with |.| signs, so the "size" of the Reals would be [math]|\Re |=\aleph_1[/math]. Anyway, I think the relevaltion that you've stumbled across here is the two Hilbert Hotels have the same number of rooms as one Hilbert hotel, or for that matter of countably infinite Hilbert hotels.

[Shadow]

Yeah, I know, [math]2\infty = \infty[/math]. But from a logical point of view; the number of reals between 0 and 1 is x. The number of reals between 1 and 2 is also x. So the number of reals between 0 and 2 should be 2x. Thus, the number of real between any two reals a, b should be |(a-b)|x. How then can the number of reals between 1 and infinity be x?

 

Cheers,

 

Gabe

[the tree]

Two sets have the same cardinality if there exists a bijection between them and you've clearly demonstrated that there is.

 

Think of it this way: if for every element in set A you can associate it with an element in set B so that no elements are left out and no two elements are associated with the same one: then those two sets must have the same number of elements.

[D H]

But from a logical point of view; the number of reals between 0 and 1 is x. The number of reals between 1 and 2 is also x. So the number of reals between 0 and 2 should be 2x.

You are implicitly assuming that multiplication of transfinite cardinals works exactly like multiplication of finite numbers. It doesn't.

[Shadow]

I know they have the same number of elements, that's my point. I'm just not understanding how that can be. I'm not familiar with sets, so I'll use a metaphor. Say we have a house and in it an infinite amount of room. Each room takes up the same amount of space, and each room takes up the same amount of space as all the others put together. How can this be?

 

As for the multiplication thing, I don't exactly know what transfinite cardinals are, but I have an idea. Anyway, the multiplication was just illustrative. I just wanted to express what the above metaphor does.

 

Cheers,

 

Gabe

[the tree]

I know they have the same number of elements, that's my point. I'm just not understanding how that can be. I'm not familiar with sets, so I'll use a metaphor. Say we have a house and in it an infinite amount of room. Each room takes up the same amount of space, and each room takes up the same amount of space as all the others put together.

Okay, I guess that's a satisfactory metaphor. Except that no metaphor is perfect because the behaviour of the reals doesn't exactly match the physical world.

 

How can this be?

It was only about a year ago that this was introduced to me in a formal setting, I remember the day before my lecturer advised us all to get a good nights sleep and make sure we'd had enough breakfast because understanding cardinalities is not easy.

 

If you can wrap your head around the cardinality of the naturals being equal to the cardinality of the even naturals, then you're off to a good start. But really you're best off with either a textbook or a teacher. (preferably both, I guess).

[Shadow]

Well, I did a quick read on wiki (btw, I know what sets are, I just didn't know the English word) and the even/natural thing makes sense, however I don't have the proper knowledge to understand most of it (the whole ordered set thing is completely beyond me, but I didn't really try to understand ).

 

Just a quick question, why is the cardinality of R defined as [math]2^{Aleph_0}[/math]?

 

Cheers,

 

Gabe

[the tree]

Because it has the same cardinality as the Power Set of N.

 

The notation is because with finite sets, the power set of S clearly has a cardinality 2^|S|.

[Shadow]

And why does it have the same cardinality as the powerset of N? I mean, why is |R| equal to all the combinations you can make with naturals? Is there some reason or is this considered something like an axiom?

 

Just to clarify, I was giving myself a primitive test; the cardinality of odd naturals is also the same as naturals. If we add up even and odd naturals, since they're (I forgot the word, it means that they don't have anything in common) we unite them, resulting in N. It makes sense...

 

Also, how can Primes and Naturals have equal cardinality? I mean, what is the bijective function in this situation?

 

Cheers and thanks a bunch,

 

Gabe

[the tree]

And why does it have the same cardinality as the powerset of N? I mean, why is |R| equal to all the combinations you can make with naturals? Is there some reason or is this considered something like an axiom?

If two sets have the same cardinality, there is always a bijection, it's just sometimes hard to see at first. This one isn't immediately obvious because you're looking for a bijection between a set of sets and a set of numbers.

The simplest thing that comes to mind is:

[math]S \to 0.d_{1}d_{2}d_{3}\dots \quad \mbox{s.t.} \quad d_i =

\begin{cases}

1 & i \in S \\

0 & i \not\in S

\end{cases}[/math]

Which is a bijection between the power set of the naturals and (0,1), in binary notation. Finding a bijection between (0,1) and R should be easy.

 

Also, how can Primes and Naturals have equal cardinality? I mean, what is the bijective function in this situation?

In this case the best I can tell you is that if there is an injective function A->B and an injective function B<-A then there is always a bijection between A and B even if it's not easily defined/possible to write down. (there's a name for that lemma but it escapes me)

[D H]

Well, I did a quick read on wiki

A quick word of warning: Wikipedia is not a scientific source -- not to put Wikipedia down; neither is the Encyclopedia Britannica.

 

Just a quick question, why is the cardinality of R defined as [math]2^{\aleph_0}[/math]?

There is a definition involved, which is to denote the cardinality of the power set of some set [math]\mathcal S[/math] as [math]2^{|\mathcal S|}[/math]. Thus the cardinality of the power set of the natural numbers is by definition [math]2^{\aleph_0}[/math]. The real numbers can be put into a one-to-one correspondence with the power set of the natural numbers. Thus [math]|\Re|=2^{\aleph_0}[/math] is a derived identity, not a definition.

 

Also, how can Primes and Naturals have equal cardinality? I mean, what is the bijective function in this situation?

There are a countably infinite number of primes. In short, they can be indexed by the natural numbers.

[Shadow]

I know, that was what I though, but I though a bijection (ie. a bijective function) must exist between the two sets. My question is, what's the function in this case? Is something like

 

[math]f(P_n)=n[/math], where [math]P_n[/math] denotes the nth prime

 

enough? Is this considered a bijective function?

 

And how does one know the reals can be put into a one-to-one correspondence with the power set of the naturals?

[the tree]

I know, that was what I though, but I though a bijection (ie. a bijective function) must exist between the two sets. My question is, what's the function in this case? Is something like

 

[math]f(P_n)=n[/math], where [math]P_n[/math] denotes the nth prime

 

enough?

Well yes. The fact is that you know that that bijective function does exist even if you can't write it down properly.

 

 

And how does one know the reals can be put into a one-to-one correspondence with the power set of the naturals?

The function that I posted should be enough.

First take the reals into a range worth working with.

[math]\begin{array}{ccc}

\mathbb{R} & \to & (0,1) \\

x & \mapsto & \frac{2}{\pi}\arctan(x) + \frac{1}{2}

\end{array}[/math]

Then take perform the inverse of the function that I posted

[math]\begin{array}{ccc}

(0,1) & \to & \mathcal{P}(\mathbb{N}) \\

0.d_{1}d_{2}d_{3}\dots & \mapsto & \{ n : d_{n}=1 \}

\end{array}[/math]

Then the composition of those functions is a perfectly good bijection [imath]\mathbb{R} \leftrightarrow \mathcal{P}(\mathbb{N})[/imath].

Edited December 16, 2008 by the tree

[Shadow]

Okay, don't have a clue what you're talking about, so I'll just accept it's beyond my grasp for now But thank you for all your help and patience, all of you.

 

Cheers,

 

Gabe

[the tree]

Do you not understand the functions that I've posted, or do you not understand why they are bijective?

[Shadow]

Frankly, I didn't even recognize that as functions. The only functions I know and recognize are in the form [math]f(x)[/math]. All that fancy arrow/punctuation/something-that-looks-like-a-series stuff means nothing to me

[Petanquell]

I'm not sure as always, but i think we've learned it as [math] f(x) = \frac{2}{\pi}\arctan(x) + \frac{1}{2} , Df=(0;1)[/math] , toff.

Edited December 19, 2008 by Petanquell
I forgot that "I'm not sure..." phrase.

[Shadow]

Ah. Thanks for that. I still don't understand [math]\begin{array}{ccc}

(0,1) & \to & \mathcal{P}(\mathbb{N}) \\

0.d_{1}d_{2}d_{3}\dots & \mapsto & \{ n : d_{n}=1 \}

\end{array}

[/math]

[the tree]

Well rather than mapping a number x to another number y, it's mapping the binary expansion of a number 0.d₁d₂d₃... to a set defined by each digit in that expansion.

[Shadow]

I think I understand what your doing in each step, unfortunately the logic behind each step eludes me. If it's not too much trouble, could I ask you to rewrite what you posted symbolically in English?

[the tree]

Okay. So I am trying to construct a function that maps numbers in the range (0,1) to the set of subsets of the naturals. That's what the top line says. [imath](0,1) \to \mathcal{P}(\mathbb{N})[/imath], where the input comes from and where output will be.

 

Now it seems sensible that 0 should map to the empty set and 1 should map to N. For everything in between I need a way of thinking about them so that there's a similarly obvious mapping and that way of thinking about them is going to be their infinite binary expansion.

 

So I've already decided that 0.000... should map to {} and 1=0.11111 should map to {1,2,3,4...}, then I'll just try to continue the pattern.

 

0.00000... -> {}

0.10000... -> {1}

0.11000... -> {1,2}

0.11100... -> {1,2,3}

...

0.11111... -> {1,2,3,4,..}

 

Now expressing that explicitly, I take each of the digits of the binary expansion after the point and if it's a 1, then then that number maps to a set including the number of that digit.

[Shadow]

I see. Interesting, that would've never occurred to me. Thanks man )

 

Cheers,

 

Gabe