1. ## [SOLVED] Cardinality

Which of the following sets has the greatest cardinality?

(A) $\mathbb{R}$

A: $Card(\mathbb{R})=c$

(B) The set of all functions from $\mathbb{Z}\to\mathbb{Z}$

B: I think this is countable infinite $(\mathbb{Z}\to\mathbb{Z})\sim\mathbb{N}$

(C) The set of all functions from $\mathbb{R}\to${ $0,1$}

C: This is the answers but why?

(D) The set of all finite subsets of $\mathbb{R}$

D: Not sure how to determine cardinality here

(E) The set of all polynomials with coefficients in $\mathbb{R}$

E: I think this countable infinite too.

2. I'll write something equivalent

Originally Posted by dwsmith
Which of the following sets has the greatest cardinality?

(A) $\mathbb{R}$

A: $Card(\mathbb{R})=c$
Right.

(B) The set of all functions from $\mathbb{Z}\to\mathbb{Z}$

B: I think this is countable infinite $(\mathbb{Z}\to\mathbb{Z})\sim\mathbb{N}$
This is surely not countable. Not even $\{0,1\}^\omega$ is countable. In fact, $\mathbb{Z}^\mathbb{Z}\simeq\mathbb{R}$

(C) The set of all functions from $\mathbb{R}\to${ $0,1$}

C: This is the answers but why?
In general $\{0,1\}^A\simeq\mathcal{P}(A)$

(D) The set of all finite subsets of $\mathbb{R}$

D: Not sure how to determine cardinality here
This is equipotent to the reals. To see this let $\mathcal{R}_n=\left\{E\subseteq\mathbb{R}:\text{ca rd }E=n\right\}$ then clearly $\text{card }\mathbb{R}\leqslant \text{card }\mathcal{R}_n\leqslant\text{card }\mathbb{R}^n=\mathbb{R}$ so that $\mathcal{R}_n\simeq\mathbb{R}$. So, then your set, call it $W$, can be written as $\bigcup_{n\in\mathbb{N}}\mathcal{R}_n$ and there's a theorem which says that if the indexing set is countable and all of the sets being united have the same cardinality which is greater than $\aleph_0$ then the union has the same cardinality as each set in the union.

(E) The set of all polynomials with coefficients in $\mathbb{R}$

E: I think this countable infinite too.
Surely not isn't $f(x)=a,\text{ }a\in\mathbb{R}$ a subset of this and isn't that clearly equipotent to $\mathbb{R}$? In fact, since a polynomial is completely determined by it's coefficients this set is equipotent to that described in D)

3. The set $\mathbb{Q}$ is the set of rationals and the set $\mathcal{P}(\mathbb{Q})$ is the power set.
Define $f:\mathbb{R}\to \mathcal{P}(\mathbb{Q})$ as $a\mapsto \{x\in \mathbb{Q}:x.
Can you show that $f$ is an injection?
If so then $card(\mathcal{P}(\mathbb{N}) )= card(\mathcal{P}(\mathbb{Q}))

4. Originally Posted by dwsmith
Which of the following sets has the greatest cardinality?

All but (c) have the same cardinality $2^{\aleph_0}=c$

(A) $\mathbb{R}$

A: $Card(\mathbb{R})=c$

(B) The set of all functions from $\mathbb{Z}\to\mathbb{Z}$

B: I think this is countable infinite $(\mathbb{Z}\to\mathbb{Z})\sim\mathbb{N}$

Its cardinality is, by definition, $|\mathbb{Z}|^{|\mathbb{Z}|}=\aleph_0^{\aleph_0}=c$

(C) The set of all functions from $\mathbb{R}\to${ $0,1$}

C: This is the answers but why?

Its cardinality is $|(0,1)|^{|\mathbb{R}|}=c^c>c$

(D) The set of all finite subsets of $\mathbb{R}$

D: Not sure how to determine cardinality here

For every $n\in\mathbb{N}\,\,\exists\,c=2^{\aleph_0}$ subsets of $\mathbb{R}$ with $n$ elements, so the set we're dealing with has cardinality $c\cdot \aleph_0=c$

(E) The set of all polynomials with coefficients in $\mathbb{R}$

E: I think this countable infinite too.

This last one is very similar to the previous set so I'll let it to you

Tonio

5. Originally Posted by Drexel28
In general $\{0,1\}^A\simeq\mathcal{P}(A)$

Is the A here referring to (A) which is the reals?

6. Originally Posted by dwsmith
Is the A here referring to (A) which is the reals?
No. For any set $A$ we have that $\{0,1\}^A=\left\{f:A\to\{0,1\}\right\}$ is equipotent to $\mathcal{P}(A)$