2
$\begingroup$

Apologies for the simplicity of this question.

In Boolean Algebra the introduction of the function {NOR} is sufficient to create, with suitable finite combinations of this function, all possible sets of states for a set of n two state variables (so all n placed functions of two state variables can be expressed as finite combinations of NOR). There are similar combinations of two or one place boolean functions that achieve this objective e.g. it could also be any of {OR, NOT}, {$\Rightarrow$, NOT}, {AND, NOT}, {NAND}.

The question is : Is there a similar 'high level' objective behind providing both '+' and '$\times$' two place functions in arithmetic, and is there any reasoning which shows why '+' and '$\times$' are both required to meet the objective and whether there are any other function combinations that meet the objective ?

$\endgroup$
2
  • 1
    $\begingroup$ On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic. $\endgroup$
    – bsbb4
    Dec 20, 2018 at 11:27
  • $\begingroup$ Note that multiplication is basically an iterated $ +$. In general, the motivation behind the use of those operations are partly historical (they are practically useful) and partly to do with the way the logical foundations of math are built. (Peano's axioms allow us to build natural numbers recursively from 1 and 0, for instance). $\endgroup$
    – user0
    Dec 20, 2018 at 11:28

2 Answers 2

Reset to default
2
$\begingroup$

The fact that every boolean function can be expressed as some finite-length combination of $NOR$'s means that $\{NOR\}$ is an 'expressive complete' set of operators. And indeed, there are many other expressive complete sets for Boolean algebra, such as $\{\neg, \land \}$' $\{\neg, \lor\}$, and $\{\neg, \rightarrow \}$

You seem to be asking what the equivalent would be for natural numbers. That is, are there any expressively complete sets of operators to capture any function defined over the natural numbers? Are addition and multiplication always required as part of such a complete set? Or are there sets that are complete without addition or multiplication?

The answer is that there is no finite set of operators that is complete for the natural numbers. The reason is that the set of all finite-length expressions that you can create from given any finite set of operators is enumerable, but the set of all functions from natural numbers to natural numbers is not. In fact, even just the set of all 1-place functions defined over the natural numbers (which includes functions like $f(n)=n^2$) is not enumerable. Therefore, for any finite set of operators, there are functions from natural numbers to natural numbers that cannot be expressed using those operators.

Of course, this means that in particular, having just addition and multiplication would not be complete. Sure, we can express the earlier mentioned $f(n)=n^2$ in terms of multiplication: $f(n)=n*n$. But how would you capture something like a function $f(n)=2^n$? You can't use something like:

$$f(n)=\underbrace{2\cdot 2 \cdot 2 ... \cdot 2}_{n \text{ times}}$$

because that expression is a different expression for each $n$, and when we define expressive completeness, we are looking a single, fixed expression. Indeed, as such, the recursive definitions offered by some of the comments and Answers to your comment cannot be used either.

Finally, as Mauro point out in the comments, the big difference between the domains of Boolean Algebra and the natural numbers is that the domain of the first contains just two elements, whereas the latter contains infinitely many. So from that perspective, it maybe shouldn't be all that surprising that there is no finite and expressively complete set of operators for the natural numbers. It's infinity rearing its ugly head again!

$\endgroup$
-1
$\begingroup$

In Peano axiomatic, one defines

$m+0 = m$ and $m + S(n) = S(m+n)$

and

$m\cdot 0 = 0$ and $m\cdot S(n) = m\cdot n+ m$,

where $S(n)=n+1$ is the successor function. So multiplication is based on addition.

$\endgroup$

You must log in to answer this question.