1
$\begingroup$

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$|

  • 0
    Yes, you're right. Sorry about that!2012-11-07

2 Answers 2

1

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)$.

  • 0
    @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.2012-11-08
0

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.

  • 0
    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.2012-11-08