45
$\begingroup$

I'm a programmer, and I've been thinking about this for some time. I have a saying:

There are only three specific numbers: 0, 1, and ∞. ∞ is just a special case of 1.

Our base function really just converts a unary value into a string (example: "101") that we can parse in a given base.

Tonight, I've been putting some thought towards this, and I realize - I believe that the entire set of natural numbers can be represented by a recursive function that only works on a unit value, as follows (I apologize in advance for the terrible notation, this is not my forte):

// Please ignore the fact that this is invalid code for various, various reasons
N (the set of natural numbers) = add(1) where add(x) = return x + add(x);

Following this, I believe that the set of integers can be found as a union of the natural number function and a similar function using subtract instead of add (resulting in the full set of negative numbers).

Going further, I applied more thought - perhaps the set of real numbers can be applied through division functions for the set of all integers divided by the set of all integers (which we've already established via the functions above).

I suppose my question is this - as strange as it may seem, is there only one unit value? (Or, possibly, a very small subset of seed numbers - perhaps 0 and 1 (and maybe -1 for the complex plane?)) Is our number system just a system of transforms on top of one unit value?

If this is a really stupid question, I apologize. It's just that the more I think about this, the more I really wonder about it. There's a good chance that I'm missing something or that this has already been derived, but I'd love to know. I'm sure this community knows much more than I do about this. I hope that this interests all of you as much as it does me.

$\endgroup$
  • 9
    $\begingroup$ If you introduce a division over integer numbers, you only get rational numbers, not every real number. The construction of $\mathbb{R}$ is quite a delicate thing, usually performed through Dedekind cuts or completion of a metric space. $\endgroup$ – Jack D'Aurizio Oct 3 '16 at 1:39
  • 2
    $\begingroup$ but they are different "kinds" of infinity. Please see en.wikipedia.org/wiki/Cantor%27s_diagonal_argument $\endgroup$ – Jack D'Aurizio Oct 3 '16 at 1:58
  • 6
    $\begingroup$ You first comment on natural numbers is an early musing of what leads to something called the Peano Postulates $\endgroup$ – Phillip Hamilton Oct 3 '16 at 2:13
  • 3
    $\begingroup$ @PhillipHamilton Can't edit your post, but in case anyone else stumbles upon my question - the Peano Axioms: en.wikipedia.org/wiki/Peano_axioms $\endgroup$ – lunchmeat317 Oct 3 '16 at 2:29
  • 3
    $\begingroup$ You use the adjective "unary" a lot, but frankly, I cannot decide with which meaning of that term. It can mean "with one argument" for an operation, as in "successor is an unary operation, whereas addition and multiplication are binary operations", or it can mean what is loosely called "base 1" representations of natural numbers, as in "the binary representation of $6$ is $110$, while its unary representation is $||||||$". While the latter certainly relates to your question, you are applying unary to numbers themselves, and this does not make sense. Constants can be seen as nullary operations. $\endgroup$ – Marc van Leeuwen Oct 3 '16 at 4:48
69
$\begingroup$

the entire set of natural numbers can be represented by a recursive function that only works on a single unary value

Bravo -- this is exactly the key insight that is exploited in most standard formalizations of the natural numbers (the most famous of which is called Peano arithmetic, if you are curious about the details). The recursive function you refer to, which you denoted add(1), is usually called the successor function and written $S$. It's a function from the natural numbers to the natural numbers, which takes a natural number $n$ and returns $n+1$.

To define the natural numbers $\mathbb{N}$, we say that $0$ is a natural number, and for any natural number $n$, $Sn$ is a natural number. This gives us all natural numbers: $0$, $1 = S0$, $2 = SS0$, $3 = SSS0$, and so on. We also may want to say that $Sn$ is a new natural number, one that has not been defined before (so for example, $4 = SSSS0$ is not equal to $2 = SS0$).

Some logics are strong enough that this definition alone is enough to define and prove what we want about the natural numbers! You seem to be interested in formalizing it as a program. In the proof assistant Coq, we may define the natural numbers as:

Inductive naturals : Type :=
  | O : naturals
  | S : naturals -> naturals.

This is similar to your code snippet, but unlike yours (which was invalid code) this is perfectly valid code defining the naturals. Yes, it really is that simple -- nothing else is needed. Even more surprising, we can go from here to define addition, multiplication, exponentiation, prime numbers, and whatever else we like, and prove things about these that we want to be true. (Most of the definitions will be recursive, and the proofs will be by induction.) Once we have the successor function $S$, everything else follows.

Following this, I believe that the set of integers can be found as a union of the natural number function and a similar function using subtract instead of add (resulting in the full set of negative numbers).

Yes, this basic idea will work to define the integers $\mathbb{Z}$ from $\mathbb{N}$. The integers could be defined by $0$, the successor function $S$, and a predecessor function $P$ which takes $n$ to $n-1$. Unlike with the natural numbers, we do have to define a special equality (equivalence relation) on the integers, so that $PSn$ and $SPn$ are both equivalent to $n$.

An alternate definition (perhaps more common) is that an integer is an ordered pair $(a,b)$, where $a$ and $b$ are natural numbers, and this represents informally the integer $a-b$. We then have to define what it means for two integers to be equal (an equivalence relation), and we say that $(a,b) = (c,d)$ if $a + d = b + c$.

Once again, either definition may be easily formalized in a programming language like Coq.

Going further, I applied more thought - perhaps the set of real numbers can be applied through division functions for the set of all integers divided by the set of all integers (which we've already established via the functions above).

Introducing division in this way (fractions) will get you from $\mathbb{Z}$ to the rational numbers $\mathbb{Q}$. But it won't get you the real numbers $\mathbb{R}$, yet, which is a MUCH bigger set than $\mathbb{Q}$. There are a lot of real numbers -- so many that computationally speaking, we can't really write down most of them. As a theoretical tool, however, it's useful to define this giant set, which we do usually using "Dedekind cuts" or "Cauchy sequences". There are several other less-known ways as well. You can read about it here.

I suppose my question is this - as strange as it may seem, is there only one unary value? (Or, possibly, a very small subset of seed numbers - perhaps 0 and 1 (and maybe -1 for the complex plane?)) Is our number system just a system of transforms on top of one unary value?

Yes, the idea is that we can start with $0$ as the only base value, and use the successor function $S$, together with a way of constructing ordered pairs (for subtraction and division) to generate all the numbers we need. More generically, we start with one or several base values (seed numbers) and one or several recursive constructors (transforms) to build up all possible numbers.

We can develop the complex numbers $\mathbb{C}$ from $\mathbb{R}$ using ordered pairs again where $(a,b)$ is $a + bi$.

However, we do have to be careful to understand the limits of our construction. For example, for lots of computations involving natural numbers to be efficient, it is actually essential that they be represented as binary strings and not unary strings of $S$s. So if we care about efficiency, then not all representations are created equal.

$\endgroup$
  • 4
    $\begingroup$ +1 Very thorough response! The topic of efficient number representations is so vast. Here's an older SE question about it that just scratches the surface: math.stackexchange.com/questions/446664/… $\endgroup$ – Yacoub Kureh Oct 3 '16 at 5:10
  • 1
    $\begingroup$ Related to your great explanation: en.wikipedia.org/wiki/Typographical_Number_Theory $\endgroup$ – iadvd Oct 3 '16 at 7:53
  • 1
    $\begingroup$ When giving a similar speal, I like illustrating how to implement $S$ in the naive set-based counting of $S(x) := x \cup\{ x \}$, with $0 = \{\}$. But maybe not wise, as it could confuse things. $\endgroup$ – Yakk Oct 3 '16 at 14:02
  • 3
    $\begingroup$ The Computer Science version of this (since @lunchmeat317 says that's his background) is called Church numerals. If you understand the basics of JavaScript, I recommend the blog entry Nothing but Functions - Numbers and Math. It's tied tightly to the foundations of Functional Programming. $\endgroup$ – Joel Harmon Oct 3 '16 at 22:23
  • 3
    $\begingroup$ @lunchmeat317 if you prefer discussions of complexity - using any base other than unary changes Ω(n) into Ω(log n), regardless of physical details. $\endgroup$ – OrangeDog Oct 4 '16 at 15:40
17
$\begingroup$

You may be interested in reading about groups, rings, and fields. Wikipedia is a good place to start.

We say that 1 generates all integers under addition and inversion, that is, every positive integer is just a sum of ones, and and every negative integer is just its negation.

If we introduce division, then we get all rational numbers. If we further allow roots of polynomials we get algebraic numbers which include some complex numbers. However, we cannot get all real numbers using algebraic techniques like this--such numbers are called transcendental numbers, e.g. $\pi$ and $e$.

This is a really interesting part of math and not a stupid question at all!

$\endgroup$
  • 3
    $\begingroup$ +1. The phrases "inductive definition" and (less importantly) "term model" are also relevant, especially given the CS background. $\endgroup$ – Noah Schweber Oct 3 '16 at 1:25
  • 4
    $\begingroup$ This is AWESOME! :-D Maybe I just like being validated but I'll definitely check this out! I'm no mathematician by any means of the term, but the more I think about this the more interesting I find it. I know that transcendental numbers can't be defined by a single function - they must be defined by a sequence of functions that, for lack of a better term, recurse upon each other, but I was wondering if that's not included within the infinity of real numbers. (From set theory, I know it isn't - I learned this in class - but in terms of infinities I'm not sure how it can't be possible.) $\endgroup$ – lunchmeat317 Oct 3 '16 at 1:27
  • $\begingroup$ @lunchmeat317 This really depends on what sorts of functions you are willing to consider. Both π and e can be simply expressed in terms of convergent power series, and there is even a computable function which calculates the nth hexadecimal digit of π directly without needing to calculate any of the others. $\endgroup$ – Robin Saunders Oct 5 '16 at 14:34
2
$\begingroup$

You might want to check out Church numerals, where each natural number $n$ is defined as the function $f \mapsto f^n$; so

  • $0 = f \mapsto id$
  • $1 = f \mapsto f$
  • $2 = f \mapsto f \circ f$
  • $3 = f \mapsto f \circ f \circ f$

etc. It's easy to define a successor function, addition, multiplication, etc. using this style (omitting un-necessary parentheses in function applications by convention):

$$Sn = f \mapsto f \circ nf$$

$$n + m = mS\;n$$

$$n * m = m (k\mapsto n+k)\;0$$

$$n^m = m(k \mapsto n * k)\; 1$$

etc.

While this is mostly used today in a programming / programming languages context, I believe it was originally intended in a foundations of math context (so in math, the natural numbers would be taken to 'mean' the above functions). Of course, programming and programming languages as we know them today grew directly out of the work in foundations of mathematics during the 1920s and 1930s.

$\endgroup$

protected by user223391 Oct 28 '16 at 16:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.