# Cardinality of Sets and Infinite Sets

The following are homework questions I would like assistance on. I will do what I can to work on these problems; any feedback is helpful.

In the following problems, S is an infinite set (we do not know if it is denumerable or uncountable). Question 1:

Let $k$ be in P. Define $G_k(S)$ = {$A$: $A$ is an element of $\mathcal{P}(S))$, |$A$|=$k$ } Show that |$G_k(S)$| = |$S$|.

My intuition tells me that I will need to use Cantor's Theorem and the Schroeder-Bernstein Theorem but I am having difficulty beginning the proof.

Question 2:

Let $C$ be a denumerable collection of sets and for every $T$ in C, T is equipotent to S.

Show that $|\bigcup C| = |S|$

Question 3:

Let $F(S)$ $=$ {$A$: $A$ is an element of $\mathcal{P}(S)$, $S$ \ $A$ is finite} Show that |$F(S)$| = |$S$|

-
Shouldn't question 1 be to show $|G_k(S)|=|S|$? –  coffeemath Nov 7 '12 at 2:14
Yes, you're right. Sorry about that! –  Julian Park Nov 7 '12 at 2:56

The first question is simply false without assuming the axiom of choice, so you can use that. You could also use the fact that if $S$ is infinite then $S\times S$ is equipotent with $S$. Therefore $S^k$ is equipotent with $S$. Note that in particular cases (e.g. $\mathbb N$ or $\mathbb R$) this is true even if the axiom of choice is not assumed. However for the general case this requires the axiom of choice to hold.

Now find an injection from $S$ into $G_k(S)$; and find a surjection from $S^k$ onto $G_k(S)$, from the above we know that we can now find a surjection from $S$ onto $G_k(S)$. Again, using the axiom of choice we can therefore find an injective function from $G_k(S)$ into $S$, and use Cantor-Bernstein.

For the second question you need the fact, $|S\times\mathbb N|=|S|$. Then write $C=\{T_n\mid n\in\mathbb N\}$, and use the fact that every $T_n$ has a bijection with $S$. Again, this requires the axiom of choice.

Lastly, the third question is equivalent to showing that $Fin(S)=\{A\subseteq S\mid |A|<\infty\}$ is equipotent with $S$; and this follows from the previous question. You could write $Fin(S)$ as the countable union of $G_k(S)$.

-
Would there be a way to approach the solution without using the Axiom of Choice? That is a topic I learn towards the end of my course. –  Julian Park Nov 8 '12 at 15:05
@Julian: For special sets like the natural numbers, or real numbers, or other well-orderable set it holds without choice. In the generality presented here, it is false without assuming choice. –  Asaf Karagila Nov 8 '12 at 15:25

For #1, if $S$ is infinite, then $S \times S$ is equipotent to $S$. If you can use this, you can also use that $S \times S \times \ldots \times S$ [$k$ factors] is equipotent to $S$. And the set of subsets of $S$ of size $k$ is contained in the latter product. The cardinality result applied here is that, if $A,B$ are infinite sets, then $\operatorname{card}(A \times B)=\max (\operatorname{card}(A),\operatorname{card}(B)$. This is for example on the Wiki page about "cardinal numbers". So if both $A,B$ are the infinite set $S$ we get $|S \times S|=|S|.$

EDIT: You may also need to invoke Schroeder Bernstein and well ordering. That is, you can get an injection from $G_k$ into the product $S^k$ by using the well ordering on $S$ to map a specific subset $A$ of $S$ with $k$ elements to the specific product $(a_1,...,a_n)$ with the $a_j$ in their ordering from the well ordering on $S.$ And you can get another injection from $S$ back to the product $S^k$ by mapping $s$ to $(s,s,...,s)$. Then using Schroeder Bernstein you can conclude equipotence.

Another EDIT: My method only gives an injection from $G_k$ to S by first mapping $G_k$ via injection to $S^k$ and following that by a bijection from $S^k$ back to $S$. I can't see clearly how to get an injection from $S$ back to the set $G_k$ however, so I'd need to rethink. Luckily there's another answer posted already.

-
What you say in the edit is true, but it’s not true that $G_k$ is contained in $S^k$. –  Brian M. Scott Nov 7 '12 at 9:05
$G_k$ has a "copy" in $S^k$ by mapping $A$ to $(a_1,...,a_k)$ using the well ordering assumed on $S$. So using a bijection between $S^k$ to $S$ we can get an injection from $G_k$ to $S$. But my idea doesn't work the other way from $S$ back to $G_k$. Thanks for the comment; I'll throw that in. –  coffeemath Nov 7 '12 at 11:30
Yes, given a well-ordering of $S$ you can inject $G_k$ into $S^k$, but in the first paragraph you actually said something stronger: you said that $G_k\subseteq S^k$, which isn’t true. It’s the wording to which I’m objecting, not the idea. –  Brian M. Scott Nov 7 '12 at 15:50
I see your point about the wording. Actually after I wrote the first paragraph I reconsidered and thought more specifically about "how" $G_k$ was to ber placed in $S^k$, and realized I needed well-ordering. But the "contained in" part is really in the same sense that one says the natural numbers are "contained in" the rationals, as the rationals $n/1$. I've typically blurred such distinctions, except when writing up a formal argument. –  coffeemath Nov 8 '12 at 12:16