1
$\begingroup$

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.

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

If you want to stick to proving this with bijections:

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.)

$\endgroup$
  • $\begingroup$ thanks for the help. Corrected my typos and my map $h$ as well. I liked the way you defined $h$. :) $\endgroup$ – Quasar Jan 26 '17 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.