- #1

- 14

- 0

## Homework Statement

Proposition. Every subset of a finite set is finite.

**2. Relevant definitions**

Definition. Two sets ##X## and ##Y## have the same cardinality iff there is a bijection between ##X## and ##Y##.

A set ##X## is finite iff there is a bijection between ##X## and ##\{1, ... , n\}## for ##n \in \mathbb{N} = \{0, 1, ...\}##. In this case, we write ##\#(X) = n##.

## The Attempt at a Solution

I have one question regarding the definition. Does it matter whether one uses the bijection ##f : X \to \{1, ..., n\}## or ##f : \{1, ... , n\} \to X##? I would say no, since I have proven that a function is bijective if and only if its inverse is bijective.

Are there any benefits to using ##f : X \to \{1, ..., n\}## or ##f : \{1, ... , n\} \to X##?

Proof. Induction on ##n##. For ##n = 0## we have ##\#(X) = 0## and hence ##X = \emptyset##. Thus, the only subset ##A \subseteq X## is ##A = \emptyset##. Hence ##A## is finite. This proves the base case.

Suppose inductively that ##X## is finite and ##A \subseteq X## implies ##A## is finite. By definition this means that there is a bijection ##f : \{1, ... , n \} \to X## and there is a bijection ##g : \{1, ... , m \} \to A## such that ##m \leq n##.

We wish to show that the proposition is true for ##n + 1##. That is, if ##\#(X') = n + 1## - in other words if ##X' := X \cup \{x\}## with ##x \notin X## - and ##A' \subseteq X'## implies that ##A'## is finite. This means that there is a bijection ##f' : \{1, ... , n + 1 \} \to X'## and we must find a bijection ##g' : \{1, ... , m' \} \to A'## with ##m' \leq n + 1##.

We can assume that ##A'## is a proper subset ##A' \subset X'## since if ##A' = X'##, then we are done.

Now for the case where ##A' \subset X'## we have ##m' < n + 1##, i.e. ##m = n##. Aren't we done now by the induction hypothesis?

This is all I have for now.