Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Proof.

Suppose that $A$ is a finite nonempty set, $B$ is a set, and $A\approx B\text{.}$ Since $A$ is a finite set, there exists a $k\in \mathbb{N}$ such that $A\approx {\mathbb{N}}_k\text{.}$ We also have assumed that $A\approx B$ and so by Item 2.b of Theorem 9.1 (in Beginning Activity 2), we can conclude that $B\approx A\text{.}$ Since $A\approx {\mathbb{N}}_k\text{,}$ we can use Item 2.c of Theorem 9.1 to conclude that $B\approx {\mathbb{N}}_k\text{.}$ Thus, $B$ is finite and has the same cardinality as $A\text{.}$

Proof.

Let $A$ be a finite set and assume $\text{ card}(A)=k\text{,}$ where $k=0$ or $k\in \mathbb{N}\text{.}$ Assume $x\notin A\text{.}$

If $A=\mathrm{\varnothing }\text{,}$ then $\text{ card}(A)=0$ and $A\cup \left\{x\right\}=\left\{x\right\}\text{,}$ which is equivalent to ${\mathbb{N}}_1\text{.}$ Thus, $A\cup \left\{x\right\}$ is finite with cardinality 1, which equals $\text{ card}(A)+1\text{.}$

If $A\ne \mathrm{\varnothing }\text{,}$ then $A\approx {\mathbb{N}}_k\text{,}$ for some $k\in \mathbb{N}\text{.}$ This means that $\text{ card}(A)=k\text{,}$ and there exists a bijection $f:A\to {\mathbb{N}}_k\text{.}$ We will now use this bijection to define a function $g:A\cup \left\{x\right\}\to {\mathbb{N}}_{k+1}$ and then prove that the function $g$ is a bijection. We define $g:A\cup \left\{x\right\}\to {\mathbb{N}}_{k+1}$ as follows: For each $t\in A\cup \left\{x\right\}\text{,}$

To prove that $g$ is an injection, we let $x_1,x_2\in A\cup \left\{x\right\}$ and assume $x_1\ne x_2\text{.}$

• If $x_1,x_2\in A\text{,}$ then since $f$ is a bijection, $f(x_1)\ne f(x_2)\text{,}$ and this implies that $g(x_1)\ne g(x_2)\text{.}$

• If $x_1=x\text{,}$ then since $x_2\ne x_1\text{,}$ we conclude that $x_2\ne x$ and hence $x_2\in A\text{.}$ So $g(x_1)=k+1\text{,}$ and since $f(x_2)\in {\mathbb{N}}_k$ and $g(x_2)=f(x_2)\text{,}$ we can conclude that $g(x_1)\ne g(x_2)\text{.}$

• The case where $x_2=x$ is handled similarly to the previous case.

This proves that the function $g$ is an injection. The proof that $g$ is a surjection is Exercise 1. Since $g$ is a bijection, we conclude that $A\cup \left\{x\right\}\approx {\mathbb{N}}_{k+1}\text{,}$ and

Since $\text{ card}\left(A\right)=k\text{,}$ we have proved that $\text{ card}(A\cup \left\{x\right\})=\text{ card}(A)+1\text{.}$

Proof.

We will use a proof using induction on $m\text{.}$ For each $m\in \mathbb{N}\text{,}$ let $P(m)$ be, “If $A\subseteq {\mathbb{N}}_m\text{,}$ then $A$ is finite and $\text{ card}(A)\le m\text{.}$”

We first prove that $P(1)$ is true. If $A\subseteq {\mathbb{N}}_1\text{,}$ then $A=\mathrm{\varnothing }$ or $A=\left\{1\right\}\text{,}$ both of which are finite and have cardinality less than or equal to the cardinality of ${\mathbb{N}}_1\text{.}$ This proves that $P(1)$ is true.

For the inductive step, let $k\in \mathbb{N}$ and assume that $P(k)$ is true. That is, assume that if $B\subseteq {\mathbb{N}}_k\text{,}$ then $B$ is a finite set and $\text{ card}(B)\le k\text{.}$ We need to prove that $P(k+1)$ is true.

So assume that $A$ is a subset of ${\mathbb{N}}_{k+1}\text{.}$ Then $A-\{k+1\}$ is a subset of ${\mathbb{N}}_k\text{.}$ Since $P(k)$ is true, $A-\{k+1\}$ is a finite set and

There are two cases to consider: Either $k+1\in A$ or $k+1\notin A\text{.}$

If $k+1\notin A\text{,}$ then $A=A-\{k+1\}\text{.}$ Hence, $A$ is finite and

If $k+1\in A\text{,}$ then $A=(A-\{k+1\})\cup \{k+1\}\text{.}$ Hence, by Lemma 9.4, $A$ is a finite set and

Since $\text{ card}(A-\{k+1\})\le k\text{,}$ we can conclude that $\text{ card}(A)\le k+1\text{.}$

This means that we have proved the inductive step. Hence, by mathematical induction, for each $m\in \mathbb{N}\text{,}$ if $A\subseteq {\mathbb{N}}_m\text{,}$ then $A$ is finite and $\text{ card}(A)\le m\text{.}$

Proof.

Let $S$ be a finite set and assume that $A$ is a subset of $S\text{.}$ If $A=\mathrm{\varnothing }\text{,}$ then $A$ is a finite set and $\text{ card}(A)\le \text{ card}(S)\text{.}$ So we assume that $A\ne \mathrm{\varnothing }\text{.}$

Since $S$ is finite, there exists a bijection $f:S\to {\mathbb{N}}_k$ for some $k\in \mathbb{N}\text{.}$ In this case, $\text{ card}(S)=k\text{.}$ We need to show that $A$ is equivalent to a finite set. To do this, we define $g:A\to f(A)$ by $g(x)=f(x)$ for each $x\in A\text{.}$ Since $f$ is an injection, we conclude that $g$ is an injection. Now let $y\in f(A)\text{.}$ Then there exists an $a\in A$ such that $f(a)=y\text{.}$ But by the definition of $g\text{,}$ this means that $g(a)=y\text{,}$ and hence $g$ is a surjection. This proves that $g$ is a bijection.

Hence, we have proved that $A\approx f(A)\text{.}$ Since $f(A)$ is a subset of ${\mathbb{N}}_k\text{,}$ we use Lemma 9.5 to conclude that $f(A)$ is finite and $\text{ card}(f(A))\le k\text{.}$ In addition, by Theorem 9.3, $A$ is a finite set and $\text{ card}(A)=\text{ card}(f(A))\text{.}$ This proves that $A$ is a finite set and $\text{ card}(A)\le \text{ card}(S)\text{.}$

Proof.

Let $B$ be a finite set and assume that $A$ is a proper subset of $B\text{.}$ Since $A$ is a proper subset of $B\text{,}$ there exists an element $x$ in $B-A\text{.}$ This means that $A$ is a subset of $B-\left\{x\right\}\text{.}$ Hence, by Theorem 9.6,

Also, by Corollary 9.7

Hence, we may conclude that $\text{ card}(A)\le \text{ card}(B)-1$ and that

Theorem 9.3 implies that $B\not\approx A\text{.}$ This proves that a finite set is not equivalent to any of its proper subsets.

Proof.

Let $A$ and $B$ be finite sets. We will prove the contrapositive of the theorem, which is, if there exists a function $f:A\to B$ that is an injection, then $\text{ card}(A)\le \text{ card}(B)\text{.}$

So assume that $f:A\to B$ is an injection. As in Theorem 9.6, we define a function $g:A\to f(A)$ by $g(x)=f(x)$ for each $x\in A\text{.}$ As we saw in Theorem 9.6, the function $g$ is a bijection. But then $A\approx f(A)$ and $f(A)\subseteq B\text{.}$ Hence, $\text{ card}(A)=\text{ card}(f(A))$ and $\text{ card}(f(A))\le \text{ card}(B)\text{.}$ Hence, $\text{ card}(A)\le \text{ card}(B)\text{,}$ and this proves the contrapositive. Hence, if $\text{ card}(A)>\text{ card}(B)\text{,}$ then any function $f:A\to B$ is not an injection.