| Posted on Tuesday, 25 November, 2003 - 07:46 am: |
Does anyone know a proof of why there are the same number of rationals and naturals, but there are more reals than naturals.Is there a bijection between rationals and naturals?
Rach
| Posted on Tuesday, 25 November, 2003 - 09:35 am: |
Rach,
Indeed there are the same number of rationals as there are naturals, a bijection between naturals and positive rationals is given below:
First, Q+ ( the set of all +ve rationals ) can be written as
Q+ = {(a,b)| a and b are naturals, b not 0 and a and b have no common factor}
Then the set N2 = {(a,b)| a , b are naturals} is a superset of Q+. Now if we show that N2 has same number of elements as Naturals have then we are done. (Fill this gap)
Lets arrange elements of N2 in an infinite array:
(1,1) (1,2) (1,3) (1,4) ,.....
(2,1) (2,2) (2,3) (2,4),...
(3,1) (3,2) (3,3) (3,4) ,.....
(4,1) (4,2) (4,3) (4,4),...
. . . .
. . . .
It is clear that if we could write all elements of a set S in a sequence in which no elements repeat then S has same number of elements as naturals. (A sequence is indeed a function from Naturals to S)
Now write all elements of array as a sequence
That is start from first element in first column and go one step right and one step up until u reach the first row.Now start from second element in first column and do the same, continue this to get a sequence. The sequence will look like this-
(1,1), (2,1) ,(1,2), (3,1), (2,2) ,(1,3), (4,1),(3,2), (2,3), (1,4)....
It is clear that it contains all the elements of array.
Now about the reals,
I show that the interval [0,1) is bigger than N.
Suppose there exists a bijection f from N to [0,1}
Write f(n) in decimal form and construct a real number r as follows,
(The digits that i refer to below are digits after decimal point)
Its first digit is different from first digit of f(1)
Its second digit is different from second digit of f(2)
.
.
Its nth digit is different from nth digit of f(n)
.
.
Now r is a real in [0,1) but it is not an image of any natural number. (can u see why?)
Thus this contradicts that f is a bijection.
| Posted on Tuesday, 25 November, 2003 - 10:00 am: |
I don't understand the reason for the reals> naturals. Please could you expand thanks.
Does this mean if a set can be arranged in some countable sequence it can be a bijection from the naturals to the terms of the sequence
| Posted on Tuesday, 25 November, 2003 - 10:01 am: |
in last message second part referred to your proof of a bijection between N2 and naturals
rach
| Posted on Tuesday, 25 November, 2003 - 10:21 am: |
Think about it, if you can count the elements (exhaustively) then you are effectively defining a bijection to the naturals.
| Posted on Tuesday, 25 November, 2003 - 01:22 pm: |
( describing Anand's idea for the reals> naturals )
Assume bijection from N to [0,1)
so i have,
f(1) = 0.a1 a2 ...
f(2) = 0.b1 b2 ...
f(3) = 0.c1 c2 ...
..
..
..
and so on
now continue with what anand explains and construct a new real 'r'.
Some questions to ponder about r,
is r in [0,1)?
is r an image of any natural number?
love arun
| Posted on Tuesday, 25 November, 2003 - 01:52 pm: |
There is another way to show that the reals and the naturals have differing cardinality, basically it involves defining a suitable bijection from the powerset of N to [0,1]. (something like
| 0.a1 a2 a3 ... |®{a1,a2.10+a3,..., |
n å k=0 | an(n+1)/2-k. 10k,...} |
should do fine I think) Then, we suppose there is a bijection from N to P(N) (its powerset), call this f. But if we look at a set A defined by {x Î N|x is not in f(x)}. Now, since f is bijective we can find an x such that f(x)=A (note that A is a subset of N). If x belongs to A then by definition of A it doesn't belong to A and vice versa. This is a contradiction, so there can exist no bijection between N and P(N). So there is no bijection between N and [0,1] by our earlier bit.
| Posted on Tuesday, 25 November, 2003 - 06:20 pm: |
Julian,
i think that number of yours should start from 0.a0 a1 .. shouldn't it?? (Sorry!if i am wrong)
Btw, nice proof!
love arun
| Posted on Tuesday, 25 November, 2003 - 07:55 pm: |
Yes, sorry. Although on re-examination, I don't think it's a bijection at all (a little tinkering could make it though).
Well, we don't actually have to explicitly find a bijection anyway. If we just find an injection from P(N) to the reals then we're done.
This should do:
| Posted on Wednesday, 26 November, 2003 - 06:32 pm: |
umm julian,
why have you taken two separate variables (a and b)??
love arun
| Posted on Wednesday, 26 November, 2003 - 07:08 pm: |
That's a map from a set of integers to a real number. The ai 's are the digits of the first number, the bi 's are the digits of the second number.
This is an injection from the powerset of the naturals to the reals.
| Posted on Thursday, 27 November, 2003 - 12:55 pm: |
:o i see!
ok! understood!
Thanks !
love arun
| Posted on Thursday, 27 November, 2003 - 04:35 pm: |
If u know about perfect sets and perfect sets of R are uncountable then the result is a corollary
| Posted on Thursday, 27 November, 2003 - 05:07 pm: |
But this still boils down to the same problem, the usual proof that non-empty perfect sets are uncountable uses a variant on Cantor's Diagonalisation argument.
| Posted on Friday, 28 November, 2003 - 05:38 am: |
I know a proof using nested sets.
Let P be a nonempty perfect set of R(k) ie RxRxR..R k times. Assume that it is countable.
Let P={P1,P2,P3....}
If x is a point in R(k) define closed neighborhood of x of radius r as the set of all points y such that |x-y|< = r. Clearly this is a closed set.
Let V1 be a neighborhood of P1 (normal open neighborhood) since P1 is a limit point, There is a point of P in V1 say x1. Let V2 be such a neighborhood of x1 such that it does not contain P1 and its correspoinding closed neighborhood lies in V1. This can certainly be done. Now since x1 is also a limit point of P, there is a point of P say x2 in V2. Let V3 be that neighborhood of x2 which does not contain P2 and its correspoinding closed neighborhood lies completely in V2. Now continue this process. That is having constructed Vn, let xn be a point in Vn. Let V(n+1) be that neighborhood of xn which does not contain Pn and whose correspoinding closed neighborhood lies completely in Vn.
Thus we get a sequence of neighborhoods
V1,V2,V3.... Such that Pn is not in V(n+1) ... (0)
Corresponding closed neighborhood (or closure) of V(n) lies in V(n+1). .... (1)
Vn's contain atleast one point of P.
Define T(n)= P intesection [Closure of V(n)]
T(n) are nonempty and closed as P and Closure of Vn are closed and also bounded. Hence T(n) are nonempty compact subsets of R(k). Property 1 implies that T(n+1) is a subset of T(n)
But intersection of all Ti's is empty since no point of P lies in all Ti's by property 0.
Hence we get a sequence of nonempty compact sets
T1 containing T2 containing T3....
But Intersection of all Ti's is empty which contradicts the theorem about such nested compact sets.
| Posted on Friday, 28 November, 2003 - 05:43 am: |
By the way, I will be very glad to hear a proof of the fact that if A and B are sets and there exists a oneone function from A to B and also a oneone function from B to A then they are equivalent. This is easy for finite sets but for infinite ...?
| Posted on Friday, 28 November, 2003 - 08:40 am: |
Is there any explicit bijection from (0,1) to [0,1]?
Partha
| Posted on Friday, 28 November, 2003 - 08:57 am: |
Anand, the theorem you talk of is called the Schroeder-Bernstein theorem (although some call it the cantor-bernstein theorem).
For a proof try here .
| Posted on Friday, 28 November, 2003 - 09:55 am: |
hi, does anyone know a proof that the cardinality of the power set is greater than the cardinality of the the set?
| Posted on Friday, 28 November, 2003 - 10:26 am: |
Rach,
Consider any set S .Let us prove that there is no surjection from S to its power set P(S). Suppose there exists such a function f. Let T be the set of all t belonging to S such that t does not belong to f(t). Since f is surjective , there exists ?a? belonging to S such that f(a)=T. Then the following question arises :
Whether a belongs to f(a)=T or not?
If a belongs to T, then by definition of T a doesn?t belong to T.
If a doesn?t belong to T , then by definition of T a must belong to T.
So existence of f is contradicted.
Since there is no surjection from S to P(S),obviously there is no bijection.
-Partha
| Posted on Friday, 28 November, 2003 - 11:38 am: |
Partha, regards your question: [0,1] and (0,1) have the same cardinality, so by definition have a bijection between them.
To find an explicit map, we have to be a bit sneaky. The trick comes by choosing a countable subset of [0,1] and first mapping 0 and 1 to numbers in this set, then we construct a map from this set into itself aiming to skip the elements which we mapped 0 and 1 to.
For example, if we chose our countable subset to be A={1/2, 1/3, 1/4, ..., 1/n, ...} then we could have
f(0)=1/2, f(1) = 1/3
Now we want to map our set to itself, let's have something like f(x) = 1/(1/x+2) for x in A, this simply maps 1/n to 1/(n+2) in general.
Now we can just say f(x) = x for x not in A and x not 0 or 1.
Then we're done, this is a bijective map.
| Posted on Friday, 28 November, 2003 - 03:25 pm: |
Thank you very much, Julian Pulman. I tried to prove it but could not do it, your proof is nice. I predicted the same lemma and could show that the lemma implies the theorem but could not prove the lemma