Claim. Given two sets $A$ and $B$ are finite. Then $A \cup B$ is finite.

I've already read [1], [2], and [3]. But I'm not convinced it has to be as complicated as that.

Following is a list of definitions I depend on:

  1. A set is finite iff its cardinality is a natural number.
  2. A set has cardinality $n$ iff it has same cardinality than $\{i \in \mathbb{N}:1 \le i \le n\}$
  3. Two sets have equal cardinality iff there is a bijection between them

Proof. Consider the following one-to-one function $g: A \cup B \rightarrow \{i \in \mathbb{N} : 1 \le i \le n_{A \cup B}\}$

$$ g(x) = \begin{cases} f_A(x) & \text{if $x \in A$} \\ n_A + h \circ f_B(x) & \text{if $x \notin A$, } \end{cases} $$

where $n_A$ is the cardinality of $A$, $n_B$ is the cardinality of $B$, $f_A$ is the bijection between $A$ and $\{i \in \mathbb{N} : 1 \le i \le n_A \}$, and $f_B$ is the bijection between $B$ and $\{i \in \mathbb{N} : 1 \le i \le n_B \}$.

If I were able to give a bijection

$$h : B \setminus A \rightarrow \{ i \in \mathbb{N} : 1 \le i \le n_{B \setminus A} \},$$

I could consider the case closed.

But how could I possibly define such a function $h$?


The key point here, which you implicitly assume in your notation, is that $B\setminus A$ is a finite set, and therefore $n_{B\setminus A}$ is a natural number.

Of course, this requires proof, but if you already can use this fact, then the existence of a bijection is given by the fact that it is a finite set.

Now, in order to prove this fact you need to show that if $f\colon B\to\{i\in\Bbb N\mid i<n_B\}$ is a bijection, then you can find one where $B\setminus A$ are mapped to the first $n_{B\setminus A}$ numbers. This is proved by induction.

But now this ends up being "as complicated" as any other more-direct proof that the union of two finite sets is finite via induction.

The main point to take from this is that being formal is not simple, and it is important to understand that sometimes even simple arguments take a lot of writing to formalize. And that when you want to prove something complicated enough which is ultimately about natural numbers, then you cannot really avoid induction.

  • $\begingroup$ +1: The OP also seems to be assuming that $A\cup B$ is finite, so that $n_{A\cup B}$ is a natural number. $\endgroup$ – Cameron Buie Oct 20 '17 at 14:27

With the help of Asaf Karagila, I noticed that proving $B \setminus A$ to be finite (and changing $g$ accordingly) should complete the proof.

$A, B$ are finite by assumption.

Let $B_1 := B \setminus A_1,$ where $A_1$ is a set with exactly one element $a \in A$.

Given $A_1 \subseteq B$, let $f_B(a) =: i_a$, where $f_B$ is the bijection between $B$ and $\{i \in \mathbb{N} : 1 \le i \le n_B\}$.

Consider the following function $h_1 : B_1 \rightarrow \{i \in \mathbb{N} : 1 \le i \le n_B - 1\}$

$$h_1(x) = \begin{cases} f_B(x) & \text{if $x < i_a$} \\ f_B(x) - 1 & \text{if $x > i_a.$} \end{cases}$$

Hence, there is a bijection $h_1 : B_1 \rightarrow \{i \in \mathbb{N} : 1 \le i \le n_B - 1 \}$, and $B \setminus A_1$ is finite.

Let $B_k := B \setminus A_k,$ where $A_k \subset A$ and has cardinality $k$.

Assume that $B_k$ is finite and let $B_{k+1} := B_k \setminus \{a_{k+1}\}$ with $a_{k+1} \in A\; \wedge \; a_{k+1} \notin A_k$.

Given $a_{k+1} \in B_k$, let $f_B(a_{k+1}) =: i_{a_{k+1}}$.

Consider the following function $h_{k+1} : B_{k+1} \rightarrow \{ i \in \mathbb{N} : 1 \le i \le n_k - 1 \}$

$$h_{k+1}(x) = \begin{cases} h_k(x) & \text{if $x < i_{a_{k+1}}$} \\ h_k(x) - 1 & \text{if $x > i_{a_{k+1}}$.} \end{cases}$$

Since $h_k$ denotes the bijection from $B_k$ to $\{i \in \mathbb{N} : 1 \le i \le n_k\}$, $h_{k+1}$ is a bijection and $B_{k+1}$ finite.

By induction, we can conclude that $B \setminus A_k$ is finite for every $k$, in particular $k = n_A$.

Let $h$ denote the bijection from $B \setminus A$ to $\{i \in \mathbb{N} : 1 \le i \le n_{B \setminus A}\}$. Then the function $g : A \cup B \rightarrow \{i \in \mathbb{N} : 1 \le i \le n_{A \cup B}\}$

$$g(x) = \begin{cases} f_A(x) & \text{if $x \in A$} \\ n_A + h(x) & \text{if $x \notin A$} \end{cases}$$

is a bijection and $A \cup B$ is finite.


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.