# Proof verification : Theorem on finite sets - Bartle's Introduction to real analysis, Section 1.3, Page 17

I would like to know, if my proof to the below theorem is correct.

Theorem.

(a) If $A$ is a set with $m$ elements and $B$ is a set with $n$ elements and if ${A}\cap{B}=\phi$, then ${A}\cup{B}$ has $m+n$ elements.

(b) If $A$ is a set with $m\in\mathbb{N}$ elements and ${C}\subseteq{A}$ is a set with $1$ element, then ${A}\backslash{C}$ is a set with $m-1$ elements.

(c) If $C$ is an infinite set and $B$ is a finite set, then ${C}\backslash{B}$ is an infinite set.

Proof.

(a) Let $f$ be a bijection from $N_{m}:=\{1,2,\ldots,m\}$ onto $A$ and $g$ be a bijection from $N_{n}$ onto $B$.

We define a new function $h$ from $N_{m+n}$ onto ${A}\cup{B}$ such that,

$$h(i)=\begin{cases} f(i) & i=1,2,\ldots,m\\ g(i-m) & i=m+1,\ldots,m+n \end{cases}$$

Further, let us prove that $h$ is a bijection.

(i) $h$ is injective.

Firstly, $f$ and $g$ are injections. Let $x_{1},x_{2}$ be two distinct elements in the set $N_{m+n}$.

We always have ${f(x_{1})\neq{f(x_{2})}}$, if $x_{1}\neq{x_{2}}$.

Similarly, ${g(x_{1})\neq{g(x_{2})}}$, if $x_{1}\neq{x_{2}}$.

Since, ${A}\cap{B}=\phi$, we always have $f(x_{1})\neq{g(x_{2})}$, if $x_{1}\neq{x_{2}}$.

Thus, $h(x_{1})\neq{h(x_{2})}$, if $x_{1}\neq{x_{2}}$

(ii) $h$ is a surjection.

Clearly, for any $y\in({A}\cup{B})$, there exists atleast one $x\in{N_{m+n}}$, such that $h(x)=y$.

Thus, $h$ is a bijection.

(b) Suppose $y_{k}\in{C}$ and $f(k)=y_{k}$.

We define a new function $h$ from $N_{m-1}$ onto $A\backslash{C}$ as follows:

$$h(i)=\begin{cases} f(i) & i=1,2,\ldots,k-1\\ f(i+1) & i=k,\ldots,m-1 \end{cases}$$

We can easily prove that $h$ is a bijection, and consequently $A\backslash{C}$ contains $m-1$ elements.

(c) Intuitively, I know that the set $N$ of natural numbers is countably infinite, and if I define $N_{m}:=\{1,2,3,\ldots,m\}$ and remove a finite number of $m$ elements from an infinite set, $N-N_{m}$, we still have an infinite set. I am not sure, how to write a proof for this in mathematical language.

• Hi, would anyone help me in checking my proof. Thanks. :) – Quasar Jan 26 '17 at 9:33

a.) seems okay, however in your map $h$ the last line should be $i = m+1, \dots, m+n$
b.) You should be more careful with the notation here. Suppose $f$ is defined as in a.). $C$ is a subset of $A$, so $C \setminus A = \emptyset$. I think you mean $A \setminus C$.
Also your map $h$ need not be well-defined, as $h(k+1) = f(k+1-1) = f(k) = y_k \notin A\setminus C$. Alternatively you could consider a map
$$h: A \setminus C \to N_{m-1}$$ $$h(x) \mapsto \begin{cases} f^{-1}(x) & \text{for } f^{-1}(x) < k\\ f^{-1}(x) -1 & \text{for } f^{-1}(x) > k \end{cases}$$
c.) $C$ need not be countably infinite. Consider e.g. $C = \mathbb{R}$. However you could assume that $C \setminus B$ is a finite. Then consider $C = (C \setminus B) \cup B$ and use a.)
• thanks for the help. Corrected my typos and my map $h$ as well. I liked the way you defined $h$. :) – Quasar Jan 26 '17 at 11:15