# Every Subset of a Finite Set is Finite (understanding Cain's proof)

Firstly, I realize that there are many variations on this question already posted. My textbook, Cain's Topology gives a 2 line proof outline of Proposition 0.29 (see below) which I find quite confusing. I've tried to fill in the details, and would like someone to confirm if I understand it.

Definition. Two sets A,B are (set) equivalent if there is a bijection between them

Definition. Define $\mathbb{Z}_{n}=\{k\in\mathbb{Z}_{+}:k\leq n\}$ . A set which equivalent with a subset of some $\mathbb{Z}_{n}$ is said to be finite.

Proposition. 0.29a: (not in text): Let $g:A\rightarrow B$ be a bijection. If $B\subseteq C$ , then $f:A\rightarrow C$ defined by $\forall a\in A(f(a)=g(a))$ is an injection. (i.e, Enlarging the codomain does not affect the injectivity of a function).

Proof. Suppose $f(a_{1})=f(a_{2})$ . By the definition of $f$ , $f(a_{1})=g(a_{1})$ and $f(a_{2})=g(a_{2})$ . Thus $g(a_{1})=f(a_{1})=f(a_{2})=g(a_{2})$ , so $g(a_{1})=g(a_{2})$ . Since $g$ is an injection, this implies $a_{1}=a_{2}$ . Thus $f$ is an injection. $\square$

Proposition. 0.29: Suppose A is finite and $B\subseteq A$ . Then $B$ is finite.

Proof. Since $A$ is finite, there is a bijection between $A$ and a subset of some $\mathbb{Z}_{n}$ . By proposition 0.29a, this implies there is an injection $f:A\rightarrow\mathbb{Z}_{n}$. The restriction of $f$ to $B$, $f|B:B\rightarrow\mathbb{Z}_{n}$, defined by $f|B(b)=f(b)$ for each $b\in B$, is an injection into $\mathbb{Z}_{n}$ , since if $b_{1},b_{2}\in B$ , then:$f|B(b_{1}) = f|B(b_{2})\implies f(b_{1}) = f(b_{2}) \implies b_{1} = b_{2}$.

Therefore, setting the codomain of $f|B$ equal to $Im(f|B)$ defines a bijection $g:B \rightarrow Im(f|B)$

Now, all we need to do is show $Im(f|B)\subseteq\mathbb{Z}_{n}$ Firstly, note $Im(f|B)$ is a subset of $Im(f)$ . Recall that $Im(f|B)=\{n\in\mathbb{Z}_{n}:\exists b\in B(n=f|B(b))\}$ . Let $n\in Im(f|B)$ . Then $\exists b\in B(f|B(b)=n)$ . Since $f|B(b)=f(b)$ for $b\in B$ , we have, $\exists b\in B(f(b)=n)$ . Since $B\subseteq A$ , $b\in B$ implies $b\in A$ , and therefore $\exists b\in A(f(b)=n)$ . Thus $n\in Im(f)$ . Thus $Im(f|B)\subseteq Im(f)$ , and $Im(f)\subseteq\mathbb{Z}_{n}$ since the image is always a subset of the codomain, which in this case is $\mathbb{Z}_{n}$ .

Thus $B$ is equivalent with $Im(f|B)\subseteq\mathbb{Z}_{n}$ , and is therefore finite. $\square$

To demonstrate the idea of Proposition 0.29 I've attached the drawing below, with $A=\{a,b,c\},B =\{a,b\}$. In the first panel, we see that $A$ is finite, as there is an (unnamed) bijection between $A$ and the subset {1,2,3} of $\mathbb{Z}_4$. If we enlarge the codomain of the bijection to equal $\mathbb{Z}_4$, the bijection becomes an injection only (proposition 0.29a), which we name $f:A\rightarrow \mathbb{Z}_4$.

In the second panel, we see that the restriction of $f$ to $B$, $f|B:B \rightarrow \mathbb{Z}_4$, is also an injection.

In the last panel, we let the codomain of $f|B$ equal the image $Im(f|B)$ thus implicitly defining the bijection $g:B \rightarrow Im(f|B)$

We observe that $Im(f|B) \subseteq \mathbb{Z}_4$. Thus $B$ is equivalent with the subset of $Im(f|B) \subseteq \mathbb{Z}_4$ and is therefore finite.

• You are showing that $g$ is in bijection with a subset of $\mathbb{Z}_n$. To fulfill the definition, you thus still need to show that for every subset $A \subseteq \mathbb{Z}_n$, there exists a $k$ such that $A$ is in bijection to $\mathbb{Z}_k$... – Dirk May 24 '17 at 14:03
• This proof looks fine to me. I suspect that your "Proposition 0.29a" is something the textbook writer was taking for granted, together with other set theoretic steps in your proof of "Proposition 0.29", but it's good to work those out if you have not done so before. – Lee Mosher May 24 '17 at 14:15
• It's more common to say that a set that is equivalent (also, equipollent, equinumerous) to $\mathbb{Z}_n$ for some $n$ is finite. – Fabio Somenzi May 24 '17 at 14:16
• @Bemte: Why does that have to be shown? The definition of finiteness that is being used only requires a bijection between $B$ and a subset of some $\mathbb{Z}_n$, which is just what the proof shows. – Lee Mosher May 24 '17 at 14:16
• @FabioSomenzi I agree, the definition you gave is much more common, and intuitive. Nonetheless, I think it was important to work out the theorem in order to understand it and the material that follows. – Evan Rosica May 24 '17 at 14:28

I think its quite straightforward:

If $A$ is finite, there is some subset $A' \subseteq \mathbb{Z}_n$ for some $n$ such that we have a bijection $f:A \to A'$. ($A$ is equivalent to a subset of $\mathbb{Z}_n$).

Now if $B \subseteq A$, then $f|B$ is still injective as you rightly claim and if we take as the codomain $B' = f[B] = \{f(b): b \in B\} \subseteq A' \subseteq \mathbb{Z}_n$, we see that $f|B$ is surjective onto $B'$ by definition and it is a bijection between $B$ and a subset $B'$ of $\mathbb{Z}_n$, so $B$ is finite too.

• Nice proof. Thanks for pointing out $Im(f|B)=f(B)$. That lets me replace the entire 3rd paragraph of my proof with $f(B) \subseteq Im(f) \subseteq \mathbb{Z}_n$ – Evan Rosica May 24 '17 at 23:10

For contradiction let us suppose that some finite set have infinite subsets
Let set A be the subset of B here B is finite and A is infinite
let us suppose X be the every possible Singleton subset of A and hence X⊆A⊆B.
also ∪X⊆B
which suggest us that Set B is infinite which is not the case
hence our supposition was wrong
hence every finite set has finite subset

• Thank you for the proof, but the question was about understanding the way Prof. Cain proved it. I realize there are many (easier) alternatives. – Evan Rosica May 24 '17 at 14:19
• This is more a circular argument than a proof. – Fabio Somenzi May 24 '17 at 14:25