Prove: If each of m and n is a counting number, then m+n is a counting number.

A counting number is defined as a number in the minimal induction set.

The minimal induction set is the set of all counting numbers and is given by C.

Printable View

- Feb 22nd 2009, 03:03 PMnoles2188Counting numbers proof
Prove: If each of m and n is a counting number, then m+n is a counting number.

A counting number is defined as a number in the minimal induction set.

The minimal induction set is the set of all counting numbers and is given by C. - Feb 24th 2009, 03:16 AMaliceinwonderland
Below is the sketch of the proof I've tried,

Lemma 1. For a transitive set t, $\displaystyle \bigcup(t^+) = t $.

Proof.

$\displaystyle \bigcup t^+ = \bigcup (t \cup \{t\})

=\bigcup t \cup \bigcup \{t\}

=\bigcup t \cup t

=t

$

The last step is followed from $\displaystyle \bigcup t \subseteq t$ for a transitive set t.

1. Show that the minimal induction set (a.k.a "a set of natural numbers") is transitive using the above lemma.

For a set theoretic construction of natural numbers, the followings hold (since it is transitive)

$\displaystyle 0 \in 1 \in 2 \in 3 ....$

$\displaystyle 0 \subseteq 1 \subseteq 2 \subseteq 3 \subseteq...$.

2. Using a recursion theorem, show that for each $\displaystyle m \in \omega$, there exists a unique function

$\displaystyle A_m:\omega \rightarrow \omega$ (guarantees that it is a function from a set of natural numbers to a set of natural numbers) such that

$\displaystyle A_m(0) = m, A_m(n) = m + n $.

Now, combine 1 & 2 show that if each of m and n is a counting number, then m+n is a counting number. - Feb 24th 2009, 05:16 AMkalagota
you may also check this:

see this page.. in particular, look on the second post (post by jhevon) and click the hyperlink there...