0568 number 61, cardinality

Forum for the GRE subject test in mathematics.
Post Reply
sachem
Posts: 9
Joined: Wed Oct 29, 2008 8:01 pm

0568 number 61, cardinality

Post by sachem » Fri Nov 07, 2008 1:36 am

Hey all, I have been thinking about this question and am having trouble ruling out one of the answer choices. Help on it is much appreciated!

Which of the following sets has the greatest cardinality?

A) R
B) The set of all functions from Z to Z
C) The set of all functions from R to {0,1}
D) The set of all finite subsets of R
E) The set of all polynomials with coefficients in R

Ok, so R had cardinality C. I also know the set of all sequences of real numbers has cardinality C (IE set of all functions N->R), so the choice E) has cardinality C. Since each finite subset of R can be a polynomial with coefficients of R, I think D) has cardinality C as well.

How do I rule out choice B? (The answer is C)

User avatar
lime
Posts: 129
Joined: Tue Dec 04, 2007 2:11 am

Post by lime » Fri Nov 07, 2008 3:19 am

B. B is equivalent to ZxZxZ which cardinality is aleph-null.

C. Let G(R) be the set of such functions. Consider A is any subset of R.
Let f: P(R)->G(R) be defined as

f(A) = g_A(x) = {
1, if x in A
0, if x not in A }

Apparently f is one-to-one and onto. G(R) equivalent to P(R), which cardinality is 2^C.

sachem
Posts: 9
Joined: Wed Oct 29, 2008 8:01 pm

Post by sachem » Fri Nov 07, 2008 4:08 am

Thanks for the reply, Lime.

I understand C); would you mind explaining B a bit more? I'm not sure why B) is equivalent to ZXZXZ.

I was thinking that B) has the same cardinality as all sequences of integers, because any function Z->Z can be expressed as {f(0), z(-1), f(1).....} and then I know that the set of all sequences of integers has cardinality C.



Post Reply