# Counting numbers proof

• Feb 22nd 2009, 04:03 PM
noles2188
Counting 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, 04:16 AM
aliceinwonderland
Quote:

Originally Posted by noles2188
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.

Below is the sketch of the proof I've tried,

Lemma 1. For a transitive set t, $\bigcup(t^+) = t$.
Proof.
$\bigcup t^+ = \bigcup (t \cup \{t\})
=\bigcup t \cup \bigcup \{t\}
=\bigcup t \cup t
=t
$

The last step is followed from $\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)

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

2. Using a recursion theorem, show that for each $m \in \omega$, there exists a unique function
$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

$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, 06:16 AM
kalagota
you may also check this:

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