1
$\begingroup$

In Naive Set Theory by Halmos, there is an assertion given as follows:

Another example is the assertion that if $E$ and $F$ are finite sets, then $E \bigcup F$ is finite, and, moreover, if $E$ and $F$ are disjoint, then $\#(E \bigcup F) = \#(E) + \#(F).$ The crucial step in the proof is the fact that if $m$ and $n$ are natural numbers, then the complement of $m$ in the sum $m+n$ is equivalent to $n$; the proof of this auxiliary fact is achieved by induction on $n$.

In the preceding paragraph, he gives a definition of the number of elements in a finite set as:

The number of elements in a finite set E is, by definition, the unique natural number equivalent to E; we shall denote it by #(E). It is clear that if the correspondence between E and #(E) is restricted to the finite subsets of some set X, the result is a function from a subset of the power set $\mathcal{P}(x)$ to $\omega$. This function is pleasantly related to the familiar set-theoretic relations and operations. Thus, for example, if $E$ and $F$ are finite sets such that $E \subset F$, then $\#(E) \leq \#(F)$. (The reason is that since $E \cong \#(E)$ and $F \cong \#(F)$, it follows that $\#(E)$ is equivalent to a subset of $\#(F)$.)

I'm trying to prove the assertion.

I have proven the auxiliary step via mathematical induction on $n$ as follows.

To prove: if $m, n \in \omega$, then $(m + n) - n \sim n$

  1. (induction base) $n = 0$

\begin{align} & \quad (m + 0) - m & \\ &= m - m & \text{(by definition of addition)} \\ &= \emptyset & \\ &= n \sim n \end{align}

  1. (induction hypothesis) $(m + n) - m \sim n$

(induction conclusion) $(m + n^+) - m \sim n^+$

\begin{align} & \quad (m + n^+) - m & \\ &= (m + n)^+ - m & \text{(by definition of addition)} \\ &= (m + n) \cup \{m + n\} - m & \text{(by induction hypothesis)}\\ &= [(m + n) - m] \cup \{m + n\} \end{align}

By induction hypothesis, there exists a bijection $f$ from $(m + n) - m$ to $n$. We can construct a bijection $g$ from $[(m + n) - m] \cup \{m + n\}$ to $n^+$ as follows:

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

and thus, $(m + n^+) - m \sim n^+$.

Now, to prove the assertion I suppose that it's crucial to prove the second sentence about the disjoint sets, from which it would be obvious that the union of two finite sets is finite.

I don't understand however how to start with that proof. Maybe I should consider a resulting set $(E \cup F)$ and construct some bijection from it to some other set (possibly a natural number), or use the auxiliary fact to somehow connect relationship between the "arbitrary" sets in a problem $E, F$ and the equivalent natural numbers?

$\endgroup$

1 Answer 1

2
$\begingroup$

I think I figured it out inspired to consider a set $[(m+n)\setminus m] \bigcup m$ from the proof

That proof also "uses arithmetic" (in particular, subtraction), talking in terms of the question posed here. On that link there are many proofs of that question but I couldn't find one perfectly corresponding to the setting of Sec. 13 of Halmos' book.

In the Halmos' book there was no notion of subtraction to that moment, so it seems that he wanted us to find some other way.

So, my proof goes like this:

Theorem Suppose $E, F$ are finite, disjoint sets. Then $\#(E) + \#(F) = \#(E \cup F)$

  1. If $E = \emptyset$ or $F = \emptyset$, then the proof is trivial. From now on, we consider a case of nonempty $E$ and $F$.

  2. $E, F$ are not empty, then there exist $m, n \in \omega$ such that:

$$E \sim m$$ $$F \sim n$$

so there exist bijections (by definition of equivalence)

$$ g_1: E \rightarrow m $$ $$ g_2: F \rightarrow n $$

  1. There also exist bijections

$$ \phi: (m + n) \setminus m \rightarrow n $$ and its inversion $$ \psi: n \rightarrow (m + n) \setminus m $$

The reason for their existence is the auxiliary fact.

  1. Let's construct a function:

$$ h: E \cup F \rightarrow ((m + n) \setminus m) \cup (m) \text{, as}$$

$$ h(x) = g_1(x) \in m, \text{if } x \in E $$ $$ h(x) = \psi(g_2(x)) \in (m + n) \setminus m, \text{if } x \in F $$

it's easy to show that $h(x)$ is also a bijection.

  1. Thus,

$$ E \cup F \sim ((m + n) \setminus m) \cup (m) $$ based on the existence of a bijection $h(x)$ between those two sets.

The set in the right hand side is $m + n$, so:

$$ E \cup F \sim (m + n) \text{, thus} $$ $$ \#(E \cup F) = m + n \text{, q.e.d.}$$

$\endgroup$

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.