| Posted on Friday, 06 February, 2004 - 05:13 pm: |
Prove:
1)Every infinite set is equivalent to a proper subset of itself.
Prove:
2)If A and B are denumerable , then A x B is denumerable.
Find:
3)Let ~ be the equivalence relation in
defined by x ~ y iff x
- y is rational. Determine the cardnality of the quotient
set /~.Can someone help me with these.....
| Posted on Friday, 06 February, 2004 - 05:27 pm: |
1) Let S be an infinite set and let B be a countable subset of S. (Prove that it exists)
Let B=a1 ,a2 ,....
Define f:S -> S-{a1 } as follows
f(x) = x if x inB
f(an ) = an+1 . This is the required bijection from S to its proper subset.
2) Do you know the "Diagonalization" method?
3)R/~ is uncountable. See that countable union of countable sets is countable.
| Posted on Saturday, 07 February, 2004 - 01:03 pm: |
Anand - for 3) it is not quite enough to show that R/~ is uncountable. We want to determine its cardinality - and there may be uncountable cardinals which are less than the cardinality of R (depending on the continuum hypothesis).
To solve 3) I think what you really need is the following:
If X is an infinite set then N x X has the same cardinality as X. (*)
Here N x X is the Cartesian product of the set of positive integers with the set X - in other words it is the set of ordered pairs (n,x) with n a positive integer and x in X.
Once you have this then the answer to your question is clear. Set X = R/~. Then there is a natural way to biject N x X and R (can you see it?) Hence X has the same cardinality as R - so R/~ has the same cardinality as R. (This cardinal is usually written 2aleph_0 - because it is the cardinality of the powerset of a countably infinite set.)
Unfortunately to prove (*) you need to know about the axiom of choice and Zorn's lemma - have you come across these Moongems?
There may be another way of approaching the question, which doesn't require the axiom of choice, but I don't currently see it.
| Posted on Saturday, 07 February, 2004 - 01:50 pm: |
Thanks for pointing that out..
| Posted on Saturday, 07 February, 2004 - 04:15 pm: |
for 2) If A and B are denumerable , then A x B is denumerable.
I'm not sure what is the "Diagonalization" method
can you give me some insite to this problem
| Posted on Tuesday, 10 February, 2004 - 11:23 pm: |
Oops, it's been pointed out to me that my message was wrong. It does not follow, without using the axiom of choice, that you can biject N x X and R.
The axiom of choice states: if you have a collection C of non-empty sets {Ai } then you can simultaneously pick an element from each of the Ai . To be more precise, there is a function f: C-> union C such that for any Ai in C, f(Ai ) is an element of Ai .
This principle seems obvious, and usually there's no problem in using it. It's usually best, however, to point out when you are using it because there are some versions of set theory (e.g. ZF) in which you cannot assume it.
Now what I had in mind was to find a bijection between N x X and R as follows. First enumerate the rationals q1 ,q2 ,... Then for any n in N and x in X, map (n,x) to x'+qn where x' is some element of the equivalent class x. Unfortunately, in defining this function, I've had to pick a representative element of each equivalence class simultaneously, and so I've needed to invoke the axiom of choice!
As it happens the rest of the argument doesn't really need AC. So I was right that AC is needed, but for the wrong reason.
It's actually probably best to forget the approach I outlined in my first message. Instead use the following theorem:
Schroeder-Bernstein Theorem: If X,Y are sets and there exists an injection from X to Y and an injection Y to X then there exists a bijection between X and Y.
This is not entirely obvious, but you can find it in any book on set theory. Note: you usually write card X < = card Y whenever there is an injection from X to Y. (Intuitively "Y is as least as large as X". It turns out card X means roughly "the size of X", although I haven't actually defined this here.) You write card X = card Y whenever there is a bijection between X and Y. So the theorem is saying that if card X < = card Y and card Y < = card X then card X = card Y. This seems reasonable enough, but it does need to be proved.
OK, so we want to prove that X = R/~ bijects with R. So by Schroeder-Bernstein it suffices to show there is an injection each way. Well it is easy to find an injection from R/~ to R using the axiom of choice. Given an equivalence class x, simply map x onto some element of the equivalence class. It is easy to then show this is an injection. We need the axiom of choice in order to make all these choices simultaneously.
What about the other way? We need an injection from R to R/~. Well it is enough to find a map f: R -> R such that if x,y are distinct then f(x)-f(y) is irrational. Because then you can simply define an injection from R to R/~ which maps any real x onto the equivalence class containing f(x) - and it is easy to show this is an injection.
So to construct f: we just need to be sure that for distinct x,y then f(x)-f(y) is a non-recurring decimal. If we ensure that for every x, the decimal expansion of f has arbitrarily long runs of zeros (let's say the 10th to 100th digits are all always zero, and the 1000th to 10000th are all always zero, and the 100000th to 1000000th decimal digits are all always zero, etc.) then f(x)-f(y) can only be irrational unless it happens to be a terminating decimal. (Can you see why?) But it's also easy to choose the other digits of f(x) in such a way that f(x)-f(y) is never non-terminiating if x,y are distinct. So we're done.