Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)$.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.