Every subset of a finite set is finite

[Simpl0S]

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.

 

[member 587159]

No, it doesn't matter for the reason you told. The existence of a bijection $X \to \{1, \dots, n\}$ is equivalent with the existence of a bijection $\{1, \dots, n\} \to X$ (the inverse function indeed does the job, as you greatly explained). So both these definitions are equivalent. There isn't really an advantage.

As for the proposition "Every subset of a finite subset is finite", I really don't see the need for an induction proof (I didn't read your proof attempt).

Here is a proof sketch, and I leave the details for you.

Let $X$ be finite, and $A \subseteq X$

(1) Show that it is sufficient to find an injection $A \to \{1, \dots n\}$ for some $n \in \mathbb{N}$ (HINT: if you have an injection $A \to \{1, \dots n\}$ for some $n \in \mathbb{N}$, you also have a bijection $A \to \{1, \dots k\}$ for some $k \in \mathbb{N}$. Can you see the obvious bijection?)

(2) By assumption, there exist $m \in \mathbb{N}$ and a bijection $f: X \to \{1, \dots, m\}$. Consider the map $g: A \to X: a \mapsto a$. What can you say about $f \circ g?$