Show that for each $k\in\Bbb{N}$, $\Bbb{N}_k$ is finite

Question

So, I'm studying mathematics on my own and I took a book about Proofs in Abstract Mathematics with the following exercise:

For each $k\in\Bbb{N}$ we have that $\Bbb{N}_k$ is finite

Just to give some context on what theorems and definitions we can use:

1. Definition: $\Bbb{N}_k = \{1, 2, ..., k \} $
2. Definition: A set $S$ is infinite iff there exists a one-to-one but not onto $\ f:S\to S$
3. Definition: $A\sim B$ means $A$ is equipotent to (or same cardinality of) $B$
4. Theorem: if $A$ is infinite and $A\sim B$, then $B$ is infinite
5. Theorem: if $A$ is infinite and $f:A\to B$ is one-to-one, then $B$ is infinite
6. Theorem: Let $\ f:A \to B$ be one-to-one and $C\subseteq A$ then $\ g:C \to B$, $\ g(x)=f(x)\ $ for any $\ x\in C$, is also one-to-one
7. Lemma: Let $k\in\Bbb{N}$, then $\Bbb{N}_k- \{x\} \sim \Bbb{N}_{k-1}$ for any $x\in \Bbb{N}_k$

What I did was:

Suppose that $\Bbb{N}_K$ is not finite for every $k\in\Bbb{N}$, then by the Well-Ordering Principle, there is a smallest element $k\in\Bbb{N}$ such that $\Bbb{N}_k$ is infinite. Let $x_0\in\Bbb{N}_k\ $ be the smallest element of $\Bbb{N}_k$ and define $C=\Bbb{N}_k - \{x_0\}$. Let $f:\Bbb{N}_k \to C\ $ be $\ f(n)=n+1$. We will prove that $f$ is one-to-one. Let $x_1,x_2\in\Bbb{N}_k$ such that $f(x_1)=f(x_2)$, then $x_1+1=x_2+1$. Hence $x_1=x_2$, what proves that $f$ is one-to-one. Thus we have that $C$ is infinite. Then $C\sim \Bbb{N}_{k-1}$ and thus we must have that $\Bbb{N}_{k-1}$ is infinite. However this contradicts our hypothesis that $k$ is the least element such that $\Bbb{N}_k$ is infinite. Thus it must be that for each $k\in \Bbb{N}$ we have $\Bbb{N}_k$ is finite.

My question is if the proof above, especially when creating the function $f:\Bbb{N}_k\to C$ has any flaw. The book explicitly says we should use the 6th theorem listed above, but I didn't find any explicitly use of it. Maybe is there another way to prove it?

Edited:

As some of you commented, the proof above was wrong. The function I created was not defined to $k+1$. I think this one is correct:

If $\Bbb{N}_k$ is not finite for every $k \in \Bbb{N}$, then by the Well-Ordering principle there exists a least element $k \in \Bbb{N}$ such that $\Bbb{N}_k$ is infinite. By definition, there exists $f:\Bbb{N}_k \to \Bbb{N}_k$ such that $f$ is one-to-one but not onto. Then, because $f$ is not onto, there exists $y\in\Bbb{N}_k$ such that $y\neq f(x)$ for every $x\in \Bbb{N}_k$. Pick $x_0\neq y$ and define $A=\Bbb{N}_k-\{x_0\}$. Let $g:A\to A$ be defined as: $$g(x)= \begin{cases} f(x) \ if \ f(x)\neq x_0 \\ f(x_0) \ if \ f(x) = x_0 \end{cases}$$

We will prove that $g$ is one-to-one but not onto.

First we show $g$ is one-to-one. Let $x_1,x_2 \in A$ such that $x_1\neq x_2$. Since $f$ is one-to-one, $f(x_1)\neq f(x_2)$. If $f(x_1)=x_0$, then $f(x_2)\neq x_0$. Hence $g(x_1)=f(x_0)$ and $g(x_2)=f(x_2)$. Since $x_0\neq x_2$, then $f(x_0)\neq f(x_2)$ and thus $g(x_1)\neq g(x_2)$. Without loss of generality, if $f(x_2)=x_0$, then $g(x_1)\neq g(x_2)$. If $f(x_1)\neq x_0$ and $f(x_1)\neq x_0$, then $g(x_1)=f(x_1)$ and $g(x_2)=f(x_2)$. Hence $g(x_1)\neq g(x_2)$. We have that $g$ is one-to-one.

We now show that $g$ is not onto. Note that, because $x_0\neq y$, such that $y\neq f(x)$ for all $x\in\Bbb{N}_k$, we have $y\in A=\Bbb{N}_k-\{x_0\}$. Let $x\in A$. If $f(x)=x_0$, then $g(x)=f(x_0)\neq y$. If $f(x)\neq x_0$, then $g(x)=f(x)\neq y$. Hence there exists $y \in A$ such that for any $x \in A$ we have $g(x)\neq y$. Thus, $g$ is not onto.

We have demonstrated that $g:A\to A$ is one-to-one, but not onto, hence A is infinite by definition. Giving that $A=\Bbb{N}_k-\{x_0\}$ and our lemma, we have that $\Bbb{N}_{k-1}$ is also infinite. However this contradicts our hypothesis that $k$ is the smallest element such that $\Bbb{N}_k$ is infinite. Hence it must be that for every $k\in\Bbb{N}$ we have $\Bbb{N}_k$ is finite.

Sorry if my proof writing is bad in anyway. If you have any stylistic suggestion, or any suggestion at all, I would gladly read it :)

Answer 1

The proof is pretty good, but not quite there -- I would relook at two aspects of the proof:

• If $k=1$, then Lemma 7 presumably does not apply (since $\mathbb{N}_{k-1} = \mathbb{N}_0$ is undefined), and your contradiction also does not apply (if $k=1$ is the minimal element such that $\mathbb{N}_k$ is infinite, then you cannot say $\mathbb{N}_{k-1}$ is infinite because $\mathbb{N}_{k-1}$ does note exist, so there is no contradiction). To make this proof work, you would need to deal with the $k=1$ case separately as a special case.
• As you suspected, your description of the construction of $f$ needs a bit more work. I'm not convinced that $f$ is well-defined: according to your description, $f(k)=k+1$, but $k+1 \notin \mathbb{N}_k$ so $k+1 \notin C$. In constructing $f$ as you do you're implicitly relying on a reordering of $\mathbb{N}_k$ and using the fact that it is infinite, but you have to make this explicit. Or perhaps the easier route would be to instead contruct $g: C \to \mathbb{N}_k$ by $g(x)=x$ and use Theorem 6.

Answer 2

Let $x_0\in\mathbb N_k$ be the smallest element of $\mathbb N_k$

So basically, $x_0=1$ (since $1\in\mathbb N_k$).

Other than that, your proof seems fine to me. Maybe a word or two is needed to explain how you knoe that $C\sim \mathbb N_{k-1}$.

Answer 3

Here is a proof by induction on $k$:

Suppose $A_k$ is finite and $f:A_{k+1}\to A_{k+1}$ is injective ($1$-to-$1$).

(i). If $f(x)\in A_k$ for every $x\in A_k$ then $f|_{A_k}$ (the restriction of $f$ to the domain $A_k$) is injective from $A_k$ to $A_k$ so $\{f(x):x\in A_k\}=A_k$ because $A_k$ is finite. So $f(k+1)=k+1,$ otherwise $f$ would not be injective. Hence $$\{f(y):y\in A_{k+1}\}=A_k\cup \{f(k+1)\}=A_k\cup \{k+1\}=A_{k+1}.$$

(ii). If there exists $x\in A_k$ with $f(x)=k+1,$ let $g(y)=f(y)$ for $y\in A_{k+1}\setminus \{x,k+1\};$ let $g(x)=f(k+1)$ and $g(k+1)=k+1.$ Then $g:A_{k+1}\to A_{k+1}$ is injective because $f$ is injective. But $g|_{A_k}:A_k\to A_k$ is also injective so $\{g(y):y\in A_k\}=A_k$ because $A_k$ is finite. And we have $$\{f(z):z\in A_{k+1}\}=\{g(y):y\in A_k\}\cup \{f(x)\}=A_k\cup \{k+1\}=A_{k+1}.$$

(iii). To finish off the inductive proof we note that $A_1$ is finite.