Reason why addition and multiplication are both required - unlike boolean algebra where NOR is enough?
$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 ?
abstract-algebra elementary-number-theory elementary-set-theory logic boolean-algebra
edited Dec 21 '18 at 21:25
user376343
3,7883828
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
$endgroup$
add a comment |
$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 ?
abstract-algebra elementary-number-theory elementary-set-theory logic boolean-algebra
edited Dec 21 '18 at 21:25
user376343
3,7883828
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
$endgroup$
1
$begingroup$
On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic.
$endgroup$
– Lukas Kofler
Dec 20 '18 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$
– Devashish Kaushik
Dec 20 '18 at 11:28
add a comment |
$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 ?
abstract-algebra elementary-number-theory elementary-set-theory logic boolean-algebra
edited Dec 21 '18 at 21:25
user376343
3,7883828
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
$endgroup$
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 ?
abstract-algebra elementary-number-theory elementary-set-theory logic boolean-algebra
abstract-algebra elementary-number-theory elementary-set-theory logic boolean-algebra
edited Dec 21 '18 at 21:25
user376343
3,7883828
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
edited Dec 21 '18 at 21:25
user376343
3,7883828
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
edited Dec 21 '18 at 21:25
user376343
3,7883828
edited Dec 21 '18 at 21:25
user376343
3,7883828
edited Dec 21 '18 at 21:25
user376343
3,7883828
3,7883828
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
asked Dec 20 '18 at 11:19
Little CheeseLittle Cheese
937
937
1
$begingroup$
On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic.
$endgroup$
– Lukas Kofler
Dec 20 '18 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$
– Devashish Kaushik
Dec 20 '18 at 11:28
add a comment |
1
$begingroup$
On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic.
$endgroup$
– Lukas Kofler
Dec 20 '18 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$
– Devashish Kaushik
Dec 20 '18 at 11:28
1
1
$begingroup$
On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic.
$endgroup$
– Lukas Kofler
Dec 20 '18 at 11:27
$begingroup$
On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic.
$endgroup$
– Lukas Kofler
Dec 20 '18 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$
– Devashish Kaushik
Dec 20 '18 at 11:28
$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$
– Devashish Kaushik
Dec 20 '18 at 11:28
add a comment |
2 Answers
2
active
oldest
votes
$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{2cdot 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!
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
$endgroup$
add a comment |
$begingroup$
In Peano axiomatic, one defines
$m+0 = m$ and $m + S(n) = S(m+n)$
and
$mcdot 0 = 0$ and $mcdot S(n) = mcdot n+ m$,
where $S(n)=n+1$ is the successor function. So multiplication is based on addition.
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047436%2freason-why-addition-and-multiplication-are-both-required-unlike-boolean-algebr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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{2cdot 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!
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
$endgroup$
add a comment |
$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{2cdot 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!
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
$endgroup$
add a comment |
$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{2cdot 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!
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
$endgroup$
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{2cdot 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!
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
edited Dec 20 '18 at 18:04
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
answered Dec 20 '18 at 13:13
Bram28Bram28
62.7k44793
62.7k44793
add a comment |
add a comment |
$begingroup$
In Peano axiomatic, one defines
$m+0 = m$ and $m + S(n) = S(m+n)$
and
$mcdot 0 = 0$ and $mcdot S(n) = mcdot n+ m$,
where $S(n)=n+1$ is the successor function. So multiplication is based on addition.
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
$endgroup$
add a comment |
$begingroup$
In Peano axiomatic, one defines
$m+0 = m$ and $m + S(n) = S(m+n)$
and
$mcdot 0 = 0$ and $mcdot S(n) = mcdot n+ m$,
where $S(n)=n+1$ is the successor function. So multiplication is based on addition.
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
$endgroup$
add a comment |
$begingroup$
In Peano axiomatic, one defines
$m+0 = m$ and $m + S(n) = S(m+n)$
and
$mcdot 0 = 0$ and $mcdot S(n) = mcdot n+ m$,
where $S(n)=n+1$ is the successor function. So multiplication is based on addition.
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
$endgroup$
In Peano axiomatic, one defines
$m+0 = m$ and $m + S(n) = S(m+n)$
and
$mcdot 0 = 0$ and $mcdot S(n) = mcdot n+ m$,
where $S(n)=n+1$ is the successor function. So multiplication is based on addition.
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
answered Dec 20 '18 at 11:33
WuestenfuxWuestenfux
4,7001413
4,7001413
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047436%2freason-why-addition-and-multiplication-are-both-required-unlike-boolean-algebr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
On the naturals, you only need the successor function $S(n)=n+1$ to define all of arithmetic.
$endgroup$
– Lukas Kofler
Dec 20 '18 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$
– Devashish Kaushik
Dec 20 '18 at 11:28