Sunday, January 27, 2013

Numbers? Natural :P

What are natural numbers? How do define them? How can they be visualized "graphically"?

1- Peano defines numbers like this:
   0 is a natural number
   ...
   For every natural number nS(n) is a natural number.
   ...
   The set of natural numbers is then defined as: N = {0, S(0), S(S(0)), …}

NOTE: S(n) is basically n+1

2- S(n) has interesting properties:    
\begin{align}
a + 0       &= a ,\\
a + S (b) &= S (a + b).
\end{align}
and
\begin{align}
a \cdot 0 &= 0, \\
a \cdot S (b) &= a + (a \cdot b).
\end{align}

3- It is possible to define natural numbers using only sets:
   s(a) = a ∪ { a }

   \begin{align}
0 &= \emptyset \\
1 &= s(0) = s(\emptyset) = \emptyset \cup \{ \emptyset \} = \{ \emptyset \} = \{ 0 \} \\
2 &= s(1) = s(\{ 0 \}) = \{ 0 \} \cup \{ \{ 0 \} \} = \{ 0 , \{ 0 \} \} = \{ 0, 1 \} \\
3 &= ... = \{ 0, 1, 2 \}
\end{align}

Visually it could be: 0 = []    "zero is a box"
and: S( [a] ) = [ a [a] ]

So: [] -> S([]) = [[]] -> S(S([])) = [ [] [[]] ] -> ...

4- Another way to visualize natural numbers is to use a string:
   Z for zero
   S for S(.), and S(Z) = SZ is one
 
So N = { Z, SZ , SSZ , SSSZ , ... }
This basically is the unary system, only that a special symbol is used ("Z" here) to mark the beginning of the string representing a number. (this offers advantages when using a Turing Machine or lambda calculus to define arithmetic operators).

5- Since each natural number can be expressed in a unique way by its prime factors (up to sorting), it is possible to define a diagram for each natural number, as they do here; these diagrams are also described here:

They are nice and prime numbers can be recognized because they are circles! But the diagrams tend to be large an less interesting for natural numbers with large factors.

6- Gödel numbering: a way to encode a list of numbers into a single (LARGE) one, so that it is always possible to re-compute back the original list of numbers.
The idea is:
   \mathrm{enc}(x_1,x_2,x_3,\dots,x_n) = 2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots p_n^{x_n}.\,
where p_n is some prime.

Example: the list (1,2,3) can be encoded as the number 21 * 32 * 5= 2*9*125 = 750
Since 2, 3 and 5 are the first 3 primes. To de-code the list, simply use the fundamental theorem of arithmetic, and find the prime factors of 750:
      750 = 21 * 3* 53
then be sure that the primes are sorted from smaller to larger, and read the exponents: (1,2,3) et voila' :)

 


No comments:

Post a Comment