| Marcos |
Can you have a set with cardinality less than the set of naturals but which is (intuitively, at least) infinite? |
||||||||||||||||||||||
| Hauke
Worpel |
No. Suppose that such a set existed. As it has infinitely many members, we can start counting them. (that is, begin the process of bringing them into one-to-one correspondence with the natural numbers) If we can start counting them, and there is no point at which they run out, then we can stop counting them any time we like. Or we can decide not to stop counting them at all. That means we can assign a number out of the naturals to all the members of our set that we have counted. Therefore, every infinite set is at least of the cardinality of the natural numbers. Aleph0 is as low of an infinity as you can get. |
||||||||||||||||||||||
| Marcos |
Thanks, I was thinking along those lines but you've explained it better... On a related note, why is it that Aleph1 = 2Aleph 0 ? I've heard this can't be proved or disproved though... Can someone give me a bit more information? Marcos |
||||||||||||||||||||||
| Chris
Tynan |
Could someone explain what Aleph is? Chris |
||||||||||||||||||||||
| Marcos |
(aleph-null) is the cardinality of the set of naturals. A set with this cardinality is called countably infinite. is the next large cardinality (after ) and you can show that such a cardinality and successive ones can exist. A set with a cardinality larger than is called uncountably infinite. It was (is?) suspected that the cardinality of the set of reals (and also the set of irrationals) is but it has been shown by Godel and Cohen that this cannot be disproved or proved (respectively) Marcos P.S. In case you're not sure what cardinality means: for a finite set, it's the number of elements in the set. You can (sort of) visualise what happens intuitively with infinite sets, but I won't go into more detail on cardinalities of infinite sets unless you want me to. |
||||||||||||||||||||||
| Yatir
Halevi |
Incidentaly Aleph is the first letter of the hebrew alphabet :-) Yatir |
||||||||||||||||||||||
| K.L. Kam |
I have some questions on this topic too. 1) why is the cardinality of the set of real, not the cardinality of the set of complex? 2) What are the defintions of , , ... ? (I know is the cardinality of the set of complex number) 3) Why is the power set of ? (same question as Marcos' one) 4) Why ? Is there a general proof? Is it still true when tends to infinity? KL Kam P.S. (aleph) is a Hebrew alphabet. |
||||||||||||||||||||||
| Marcos |
Well, for (4) I suspect is constructed so that it has cardinality larger than For (1), I always thought (guessed is more appropriate) that |
|=|
|. Can you provide a (sketch) proof why |
|> |
|?Marcos |
||||||||||||||||||||||
| Yatir
Halevi |
K.L., The cardinality of the complex numbers is Aleph-1 and the same goes for the reals numbers. and to prove that we'll need to prove that |R2 |=|R| (the cardinality of the set the reals in the same and the pairs of real numbers) To see this, it suffices to prove that the set of all pairs (x,y) o < x,y < =1 can be mapped bijectively onto (0,1]. Consider the pair (x,y) and write down their unique and unterminating decimal expansion, for example: x=0.3 01 2 007... y=0.009 2 05 1... We have seperated the digits into groups by always going to the next non-zero digit. now we associate to the pair (x,y) a number from (0,1] by writing the first group of x then the first of y and so on... thus: z=0.30090122050071... Since neither z nor y exhibit only zeros from a certain point, the decimal expansion of z doesn't terminate either. Hence we have a bijective map. Since every complex number is actualy a pair of two real numbers a+bi => (a,b), the cardinality of C is also aleph-1. |C|=|R2 |=|R| Yatir |
||||||||||||||||||||||
| Marcos |
Thanks Yatir... This idea is interesting as it seems to easily generalise for n ...More generally, can we always find a bijection f:A -> An , implying |A| = |An |? Marcos |
||||||||||||||||||||||
| Yatir
Halevi |
It has been proven that the set of the union of countably many countable sets is countable. Yatir |
||||||||||||||||||||||
| Marcos |
But is
uncountable though...
|
||||||||||||||||||||||
| K.L. Kam |
well, I believe your proof Yatir, but I've been told that set of real number is a subset of the set of complex number. Perhaps i'll check it with my math teacher tomorrow. I know a proof which needs the condition that |C| > |R|. (Perhaps I am wrong) I'll post the proof tomorrow if I still don't understand why. I need to sleep now because it's VERY late at night here, and will continue the discussion tomrrow. KL Kam |
||||||||||||||||||||||
| Marcos |
Kam, it's a "subset" in the same sense as the even numbers are a subset of the naturals. Both the evens and naturals have the same cardinality though... Marcos |
||||||||||||||||||||||
| Yatir
Halevi |
Not exactly marcos...because the complex numbers are "two-dimensional" and so the reals have no 'order' inside the complex. You can't say that 4 is bigger then 566+5i... Yatir |
||||||||||||||||||||||
| Marcos |
I never said anything was bigger/smaller than anything else... What I meant was, we can extract the reals from the complex numbers just as we can extract the naturals from the rationals or the evens from the naturals... So, the fact that such an operation is possible doesn't imply that |naturals| < |rationals| or |evens| < |naturals| or |reals| < |complex| (|A| denotes cardinality of A) Marcos P.S. Maybe I'm not getting what you're saying |
||||||||||||||||||||||
| Angelina
Lai |
From Marcos' original question, there comes one which I have always wondered: what about the set of prime numbers compared to the set of natural numbers? Both has cardinality of infinity, but would you say that there is the same number prime numbers and natural numbers? |
||||||||||||||||||||||
| Yatir
Halevi |
All I meant to say is that the connection between the evens and the naturals is not the same as between the complex and the reals. But now that I read your post again, I see that you weren't even talking about that Yatir P.s. I think I'll just confess that I wanted to show off and say that you can't say that 4 is bigger than 566+5i (and I wrote then instead of than) |
||||||||||||||||||||||
| Yatir
Halevi |
Marcos, I think I saw somewhere that aleph-0 is the smallest cardinal for infinite sets. Angelina, I'm pretty sure that it is aleph-0 because it is a subset of the naturals so it is at most alepha-0 (and if it really is the smallest then it must be aleph-0). And..I've an algorithm to count them, you have a first prime number: 2, and by checking each number after it you can find out if it is a prime or not. So you have a first an element and a deffenet way to find out the next prime number (and there is only one!). You wont have this in the reals, because for every real m and n you can always find another real (m+n)/2 between them. I hope you got what I was trying to say. Yatir |
||||||||||||||||||||||
| Vicky
Neale |
Angelina, we say that two sets have the same cardinality if there is a bijection between them (are you happy about what this means?). We can find a bijection between the primes and the naturals: just define f (pk ) = k, where pk is the kth prime. So although it seems like there ought to be a lot more natural numbers than primes, the sets of them have the same cardinality. I think this is what Yatir was trying to say. Another way of thinking about countability is to say that a set is countable if we can 'list' the elements in some way, and this is what Yatir has given you a method of doing. Vicky |
||||||||||||||||||||||
| Yatir
Halevi |
Marcos, What Godel and Cohen actually proved is that the continuum hypothesis is independent of the Zermelo-Fraenkel axiom system (the same way as the parallel axiom is independent of the other axioms of euclidian geometry). There are models were it holds and other models of set theory where it doesn't.... Yatir |
||||||||||||||||||||||
| K.L. Kam |
well i made a terrible mistake. Yes |C| = |R| ! Yatir, you wrote : Consider the pair (x,y) and write down their unique and unterminating decimal expansion, for example: x=0.3 01 2 007... y=0.009 2 05 1... We have seperated the digits into groups by always going to the next non-zero digit. now we associate to the pair (x,y) a number from (0,1] by writing the first group of x then the first of y and so on... thus: z=0.30090122050071... Why do we need to seperate the digits into groups by going to the next non-zero digit, provided that x and y don't terminate ? Can I write the proof this way : x= a.a1 a2 a3 ..... y=b.b1 b2 b3 ...... z=c.a1 b1 a2 b2 a3 b3 ..... By the way, let A be a set and the cardinality of A is non-finite. How do we proof that |power set of A| > |A| ? I remember that is a very beautiful proof by contradiction but I forget the detail. Would someone please post the proof here. KL Kam |
||||||||||||||||||||||
| Marcos |
Yatir, I know but phrasing it as "this can't be proved or disproved" sounds more spectacular as it sounds like a completely contradictory statement (Also, I
wasn't sure if the person reading the post was familiar
with the axioms of set theory)Marcos |
||||||||||||||||||||||
| David
Loeffler |
The proof that the power set P(A) has cardinality strictly bigger than A runs as follows. Suppose there was some bijection between P(A) and A. Then for each a in A, there is a subset S(a) of A corresponding, and vice versa. It may happen occasionally that a in S(a) - the bijection maps a to a set containing a itself. Let T be the set of all a in A such that a in S(a). Then T is a subset of A, so it must be S(b) for some b in A. Is b in T? If b in T , then by the definition of T, b not in T; but if b not in T, b in T. This is obviously paradoxical, so we can only conclude that our initial hypothesis was wrong, and A is not bijective with its power set. David |
||||||||||||||||||||||
| Yatir
Halevi |
Marcos,... David, I was just begining to type the proof and then I noticed that you beat me to it. The proof of this resembles the barber paradox... K.L., I remember thinking about the same thing when I first saw the proof...I remember having an answer (the answer could be: "It doens't matter"...) but I can't recall it now. I don't see any reason why it would change, maybe by grouping the digits you verify (not that it is needed) that the decimal expansion is not terminating.... (I'll have to check on that) Yatir |
||||||||||||||||||||||
| Marcos |
What's the barber paradox? Also, is the proof that aleph_1 is the cardinality of the power set of the set of naturals too advanced to understand? If not, can anyone provide a proof/starting point/website with it/some other related thing? Marcos |
||||||||||||||||||||||
| Yatir
Halevi |
Lets say that there is a barber that only shaves men that do not shave themselves. Does he shave himself? Yatir |
||||||||||||||||||||||
| Paul
Smith |
This is also known as Russell's Paradox (after Bertrand Russell, who first discovered the paradox). It can stated in terms of formal set theory: , is
?Paul |
||||||||||||||||||||||
| Marcos |
Oh ok... I knew it as Russell's Paradox. |
||||||||||||||||||||||
| Peter
Conlon |
The rationals are aleph-0 aren't they? How do you pair them off with the naturals? |
||||||||||||||||||||||
| Yatir
Halevi |
make the following table:
and start counting them as follows: 1/1,1/2,2/1,3/1,2/2,1/3,... Therefor they are countable. Yatir |
||||||||||||||||||||||
| Marcos |
Consider the following table (where the rational in the mth column, nth row is n/m): ![]() Now, following the pink line you can list the rationals without leaving any out... Hence, cardinality is Marcos P.S. You can quite easily use this very simple technique to show that has cardinality by changing into (without going into other more subtle proofs) |
||||||||||||||||||||||
| Marcos |
Sorry Yatir... |
||||||||||||||||||||||
| Demetres
Christofides |
Another way is the following: It is enough to find an injection from the rationals to the natural numbers. (See Yatir's post injections and bijections ) [There is an obvious injection from the natural numbers to the rationals] We can write every rational uniquely as a/b where a is an integer b is a strictly positive integer and (a,b)=1.Then define f(a/b) = 2|a| 3b 5sgn(a)+1 . It is an easy consequence of the F.T of arithmetic to show that f is an injection. Demetres |
||||||||||||||||||||||
| Demetres
Christofides |
Yatir, in barber's paradox, the barber shaves all men that do not shave themselves (and we assume that he is a man) Demetres |
||||||||||||||||||||||
| Demetres
Christofides |
There is a bijection between the power set of the natural and the real numbers in [0,1] For every in the power set of the naturals let where is 1 if is in and 0 if it isn't. Well actually the above is not exactly a bijection (e.g. and are both equal to 1/2 but this is not a big problem Demetres |
||||||||||||||||||||||
| Yatir
Halevi |
Demetres, Isn't f(a/b)=2a 3b enough for an injection? [Even if (a,b) is not neccesseraly 1...] Yatir |
||||||||||||||||||||||
| Yatir
Halevi |
Sorry... I understand why the 5 is needed.... But still if the cardinality of the rational is A then 2*A is still equaled to A...isn't it? Yatir |
||||||||||||||||||||||
| Demetres
Christofides |
You certainly need (a,b)=1 so that f is well defined (i.e. f(1/2)=f(2/4) e.t.c). As for multiplying by 5 it's more elegant rather than saying that the strictly positive rationals are countable hence ... Demetres |
||||||||||||||||||||||
| Yatir
Halevi |
Could you explain again why (a,b)=1 is needed...? |
||||||||||||||||||||||
| Marcos |
Thanks Demetres... |
||||||||||||||||||||||
| Demetres
Christofides |
Yatir, if we do not assume that hcf(a,b)=1, then the function I gave is NOT a function. For example f(1/2) = 2.32 .52 = 450 but f(2/4) = 22 .34 .52 = 8100. These two values should be the same. The easiest way to pick only one representative for each element of the rationals is to insist that hcf(a,b)=1 and b> 0. Demetres |
||||||||||||||||||||||
| Yatir
Halevi |
Demetres, but you can define it as a mapping between a pair of integers (a,b) to a natural number, so the cardinality will be at most countable, meaning that it is. (Or...that I made a mistake) Yatir |
||||||||||||||||||||||
| Kerwin
Hui |
Well, Demetres has defined it as a function from the rationals to the naturals, so he needs the condition hcf(a,b)=1 in order for the function to be well-defined. If instead the function is mapping to
the naturals then you don't need it, but this is not the
case above.Incidently, when you say pairs of integers (i.e. ), you will need to throw in some 7's as
well to take account of the sign of the second
integer.Kerwin |
||||||||||||||||||||||
| Yatir
Halevi |
Oh...I see what you both mean... But, in principal it doesn't matter if we prove an injection between ZxN to N or Q to N right? They both will have the same result on the cardinality...? Yatir |
||||||||||||||||||||||
| Kerwin
Hui |
That will indeed give you the same result on cardinality. But if you want to prove the rationals are countable, it makes a little more sense to construct functions from Q to N, rather than ZxN to N. Incidently, you need some version of Schroeder-Bernstein Theorem (aka Cantor-Bernstein and various other possible permutations), which says that if A injects to B and B injects to A, then A and B have the same cardinality (and the bijection is given in terms of the two injections). Kerwin |