Cardinal Arithmetic proof issues.

Question

Let $X$ be a finite set and let $x$ be an object which is not an element of $X$. Then $X \cup \{x\}$ is finite and $|X \cup \{x\}| = |X| + 1$.

Proof. Let X be a finite set with cardinality n, denoted by #X, then there exists a bijection; $$f:X \rightarrow \{ i \in N : 1 \le i \le n\} $$. Since x is not an element of X then $$X \cup \{x\} $$ is the set of elements that contains X or {x}, then there must exist a bijection $$ g:X \cup \{x\} \rightarrow \{ i \in N : 1 \le i \le n++\} $$ By the definition of cardinality of finite sets $$X \cup \{x\} $$ has cardinality n++, that is n+1, denoted by #(X U {x}) . That slightly better, or have i jumped th gun again?

Answer 1

The natural numbers are defined as follows:

$$0 = \varnothing \qquad \,1 = \{0\} \qquad \, 2 = \{0,1\} \qquad \, 3 = \{0,1,2\} \,\,\,\text{etc.} $$

The fact that $|X|=n$ is equivalent to the fact that there exists a bijection between $X$ and $n=\{0,1,2,\dots , n-1\}$. Call this function $f: n \rightarrow X$.

Then we can construct a function $$g: (n+1) \rightarrow (X \cup \{x\})$$ defined as follows, for all $a \in (X \cup \{x\})$:

$$g(a) = \begin{cases} f(a) & \text{if } a \in n \\ x & \text{if } a = n\end{cases}$$

This covers the entire domain because $n+1 = n \cup \{n\}$ (see successor function).

You should be able to prove that $g(a)$ is a bijection. This will finish the proof.

Answer 2

Yes, you are right. You haven't really proved anything since you used the fact that the cardinality of a disjoint union is the sum of cardinals. And this is essentially what you have to prove.

Instead, you need to verify that $\#(X\cup\{x\})=n+1$, namely find a bijection between $X\cup\{x\}$ and $\{0,\ldots,n\}$.

For this, use the assumption on $X$ to obtain a bijection between $X$ and $\{0,\ldots,n-1\}$, and extend that bijection as needed.