1. ## [SOLVED] Cardinality

Which of the following sets has the greatest cardinality?

(A) $\displaystyle \mathbb{R}$

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

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

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

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

C: This is the answers but why?

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

D: Not sure how to determine cardinality here

(E) The set of all polynomials with coefficients in $\displaystyle \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) $\displaystyle \mathbb{R}$

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

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

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

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

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

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

D: Not sure how to determine cardinality here
This is equipotent to the reals. To see this let $\displaystyle \mathcal{R}_n=\left\{E\subseteq\mathbb{R}:\text{ca rd }E=n\right\}$ then clearly $\displaystyle \text{card }\mathbb{R}\leqslant \text{card }\mathcal{R}_n\leqslant\text{card }\mathbb{R}^n=\mathbb{R}$ so that $\displaystyle \mathcal{R}_n\simeq\mathbb{R}$. So, then your set, call it $\displaystyle W$, can be written as $\displaystyle \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 $\displaystyle \aleph_0$ then the union has the same cardinality as each set in the union.

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

E: I think this countable infinite too.
Surely not isn't $\displaystyle f(x)=a,\text{ }a\in\mathbb{R}$ a subset of this and isn't that clearly equipotent to $\displaystyle \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 $\displaystyle \mathbb{Q}$ is the set of rationals and the set $\displaystyle \mathcal{P}(\mathbb{Q})$ is the power set.
Define $\displaystyle f:\mathbb{R}\to \mathcal{P}(\mathbb{Q})$ as $\displaystyle a\mapsto \{x\in \mathbb{Q}:x<a,~a\in\mathbb{R}\}$.
Can you show that $\displaystyle f$ is an injection?
If so then $\displaystyle card(\mathcal{P}(\mathbb{N}) )= card(\mathcal{P}(\mathbb{Q}))<card(\mathbb{R})$

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

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

(A) $\displaystyle \mathbb{R}$

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

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

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

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

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

C: This is the answers but why?

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

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

D: Not sure how to determine cardinality here

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

(E) The set of all polynomials with coefficients in $\displaystyle \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 $\displaystyle \{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 $\displaystyle A$ we have that $\displaystyle \{0,1\}^A=\left\{f:A\to\{0,1\}\right\}$ is equipotent to $\displaystyle \mathcal{P}(A)$