Hi! I am studying for my finals and I need some help. Thank you so much in advance.
1) Prove that the set F(S) of finite subsets of a countable set S is countable, and it is (countably) infinite if and only if S is (countably) infinite.
2) Suppose that E is an equivalence relation on a countably infinite set S, and let S/E be the associated family of eqivalence classes. Explain why S/E is countable.
1) I don't know if this the standard proof, but I think it works. WLOG we can take our countably infinite set to be the natural numbers. Now, define a function f:F(N) --> [0,1) as follows: for an element S of F(N), declare the mth binary digit of the real number f(S) to be 1 if m is a member of S, 0 otherwise. For example,
f({1,2,4,6}) = .01101010000000.....
where we have a 1 in the 1st, 2nd, 4th and 6th decimal place, 0's elsewhere (we count the place just after the decimal as the "0th" place). Notice first that this is an injective function (no two distinct finite subsets can define the same real number). And secondly, every finite subset maps to a rational number, since we always end with a tail of zeroes. Thus we have an injective function from F(N) to the rationals in [0,1), and the latter set is countable.
2) The projection map x --> [x] mapping every element of S to its own equivalence class is an onto mapping. Thus S/E is no bigger than S itself.
  |
LinkBack URL
About LinkBacks