How to define addition (of natural number) in ZF
$begingroup$
The picture is from Enderton's "elements of set theory"(1977) page79.
My question is: How to construct the set "+" by using the axioms in ZF set theory? In the picture above, those one-place functions "Am" are constructed first, but I even have trouble constructing those one-place functions. I have no trouble constructing A1 or A2 or whatever because each of them can be obtained by the recursion theorem on ω(the set of natural numbers, which is defined to be the intersection of all inductive sets),but how can I define all of them? I have $aleph_0$ such functions to define but it is impossible for me to apply the recursion theorem $aleph_0$ times.
Or perhaps I can define "+" like this. I have seen this from other sources:
For any natural number m,n:
m+0=m
m+S(n)=S(m+n), S is the successor function on ω.
This definition seems to be able to skip those one-place functions and deal with the binary function directly, but meanwhile another problem arises. This definition would require another form of the recursion theorem as its justification. Such recursion theorem is nowhere to be found and I don't know how to state it and prove it.
elementary-set-theory arithmetic
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
asked Feb 20 '15 at 10:03
user5938user5938
705
$endgroup$
|
show 1 more comment
$begingroup$
The picture is from Enderton's "elements of set theory"(1977) page79.
My question is: How to construct the set "+" by using the axioms in ZF set theory? In the picture above, those one-place functions "Am" are constructed first, but I even have trouble constructing those one-place functions. I have no trouble constructing A1 or A2 or whatever because each of them can be obtained by the recursion theorem on ω(the set of natural numbers, which is defined to be the intersection of all inductive sets),but how can I define all of them? I have $aleph_0$ such functions to define but it is impossible for me to apply the recursion theorem $aleph_0$ times.
Or perhaps I can define "+" like this. I have seen this from other sources:
For any natural number m,n:
m+0=m
m+S(n)=S(m+n), S is the successor function on ω.
This definition seems to be able to skip those one-place functions and deal with the binary function directly, but meanwhile another problem arises. This definition would require another form of the recursion theorem as its justification. Such recursion theorem is nowhere to be found and I don't know how to state it and prove it.
elementary-set-theory arithmetic
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
asked Feb 20 '15 at 10:03
user5938user5938
705
$endgroup$
$begingroup$
I can't understand what you want. Do you want to avoid the recursion theorem?
$endgroup$
– Git Gud
Feb 20 '15 at 10:15
$begingroup$
You have to read the comment at the bottom of the page [H.Enderton, Elements of set Theory (1977), page 79] : the definition via Recursion Th "serve to characterize the binary operation $+$ in a recursive fashion", i.e. for any $n,m$ : $m+0=m$ and $m+n^+=(m+n)^+$. We can say that, in order to "compute" $3+2$ we need the "set" $A_2$ and "apply it" to $3$ : $A_2(3)=A_2(2)^+=A_2(1)^{++}=A_2(0)^{+++}=2^{+++}$.
$endgroup$
– Mauro ALLEGRANZA
Feb 20 '15 at 10:24
$begingroup$
I feel that this question has been asked several times before.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:30
$begingroup$
Also, when you quote something, it's usually a great idea to give an accurate citation.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:32
$begingroup$
@GitGud I think my question is clear:How to construct the set "+" by using the axioms in ZF set theory?
$endgroup$
– user5938
Feb 20 '15 at 12:15
|
show 1 more comment
$begingroup$
The picture is from Enderton's "elements of set theory"(1977) page79.
My question is: How to construct the set "+" by using the axioms in ZF set theory? In the picture above, those one-place functions "Am" are constructed first, but I even have trouble constructing those one-place functions. I have no trouble constructing A1 or A2 or whatever because each of them can be obtained by the recursion theorem on ω(the set of natural numbers, which is defined to be the intersection of all inductive sets),but how can I define all of them? I have $aleph_0$ such functions to define but it is impossible for me to apply the recursion theorem $aleph_0$ times.
Or perhaps I can define "+" like this. I have seen this from other sources:
For any natural number m,n:
m+0=m
m+S(n)=S(m+n), S is the successor function on ω.
This definition seems to be able to skip those one-place functions and deal with the binary function directly, but meanwhile another problem arises. This definition would require another form of the recursion theorem as its justification. Such recursion theorem is nowhere to be found and I don't know how to state it and prove it.
elementary-set-theory arithmetic
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
asked Feb 20 '15 at 10:03
user5938user5938
705
$endgroup$
The picture is from Enderton's "elements of set theory"(1977) page79.
My question is: How to construct the set "+" by using the axioms in ZF set theory? In the picture above, those one-place functions "Am" are constructed first, but I even have trouble constructing those one-place functions. I have no trouble constructing A1 or A2 or whatever because each of them can be obtained by the recursion theorem on ω(the set of natural numbers, which is defined to be the intersection of all inductive sets),but how can I define all of them? I have $aleph_0$ such functions to define but it is impossible for me to apply the recursion theorem $aleph_0$ times.
Or perhaps I can define "+" like this. I have seen this from other sources:
For any natural number m,n:
m+0=m
m+S(n)=S(m+n), S is the successor function on ω.
This definition seems to be able to skip those one-place functions and deal with the binary function directly, but meanwhile another problem arises. This definition would require another form of the recursion theorem as its justification. Such recursion theorem is nowhere to be found and I don't know how to state it and prove it.
elementary-set-theory arithmetic
elementary-set-theory arithmetic
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
asked Feb 20 '15 at 10:03
user5938user5938
705
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
asked Feb 20 '15 at 10:03
user5938user5938
705
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
edited Feb 20 '15 at 15:31
Andrés E. Caicedo
65.5k8158249
65.5k8158249
asked Feb 20 '15 at 10:03
user5938user5938
705
asked Feb 20 '15 at 10:03
user5938user5938
705
asked Feb 20 '15 at 10:03
user5938user5938
705
705
$begingroup$
I can't understand what you want. Do you want to avoid the recursion theorem?
$endgroup$
– Git Gud
Feb 20 '15 at 10:15
$begingroup$
You have to read the comment at the bottom of the page [H.Enderton, Elements of set Theory (1977), page 79] : the definition via Recursion Th "serve to characterize the binary operation $+$ in a recursive fashion", i.e. for any $n,m$ : $m+0=m$ and $m+n^+=(m+n)^+$. We can say that, in order to "compute" $3+2$ we need the "set" $A_2$ and "apply it" to $3$ : $A_2(3)=A_2(2)^+=A_2(1)^{++}=A_2(0)^{+++}=2^{+++}$.
$endgroup$
– Mauro ALLEGRANZA
Feb 20 '15 at 10:24
$begingroup$
I feel that this question has been asked several times before.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:30
$begingroup$
Also, when you quote something, it's usually a great idea to give an accurate citation.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:32
$begingroup$
@GitGud I think my question is clear:How to construct the set "+" by using the axioms in ZF set theory?
$endgroup$
– user5938
Feb 20 '15 at 12:15
|
show 1 more comment
$begingroup$
I can't understand what you want. Do you want to avoid the recursion theorem?
$endgroup$
– Git Gud
Feb 20 '15 at 10:15
$begingroup$
You have to read the comment at the bottom of the page [H.Enderton, Elements of set Theory (1977), page 79] : the definition via Recursion Th "serve to characterize the binary operation $+$ in a recursive fashion", i.e. for any $n,m$ : $m+0=m$ and $m+n^+=(m+n)^+$. We can say that, in order to "compute" $3+2$ we need the "set" $A_2$ and "apply it" to $3$ : $A_2(3)=A_2(2)^+=A_2(1)^{++}=A_2(0)^{+++}=2^{+++}$.
$endgroup$
– Mauro ALLEGRANZA
Feb 20 '15 at 10:24
$begingroup$
I feel that this question has been asked several times before.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:30
$begingroup$
Also, when you quote something, it's usually a great idea to give an accurate citation.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:32
$begingroup$
@GitGud I think my question is clear:How to construct the set "+" by using the axioms in ZF set theory?
$endgroup$
– user5938
Feb 20 '15 at 12:15
$begingroup$
I can't understand what you want. Do you want to avoid the recursion theorem?
$endgroup$
– Git Gud
Feb 20 '15 at 10:15
$begingroup$
I can't understand what you want. Do you want to avoid the recursion theorem?
$endgroup$
– Git Gud
Feb 20 '15 at 10:15
$begingroup$
You have to read the comment at the bottom of the page [H.Enderton, Elements of set Theory (1977), page 79] : the definition via Recursion Th "serve to characterize the binary operation $+$ in a recursive fashion", i.e. for any $n,m$ : $m+0=m$ and $m+n^+=(m+n)^+$. We can say that, in order to "compute" $3+2$ we need the "set" $A_2$ and "apply it" to $3$ : $A_2(3)=A_2(2)^+=A_2(1)^{++}=A_2(0)^{+++}=2^{+++}$.
$endgroup$
– Mauro ALLEGRANZA
Feb 20 '15 at 10:24
$begingroup$
You have to read the comment at the bottom of the page [H.Enderton, Elements of set Theory (1977), page 79] : the definition via Recursion Th "serve to characterize the binary operation $+$ in a recursive fashion", i.e. for any $n,m$ : $m+0=m$ and $m+n^+=(m+n)^+$. We can say that, in order to "compute" $3+2$ we need the "set" $A_2$ and "apply it" to $3$ : $A_2(3)=A_2(2)^+=A_2(1)^{++}=A_2(0)^{+++}=2^{+++}$.
$endgroup$
– Mauro ALLEGRANZA
Feb 20 '15 at 10:24
$begingroup$
I feel that this question has been asked several times before.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:30
$begingroup$
I feel that this question has been asked several times before.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:30
$begingroup$
Also, when you quote something, it's usually a great idea to give an accurate citation.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:32
$begingroup$
Also, when you quote something, it's usually a great idea to give an accurate citation.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:32
$begingroup$
@GitGud I think my question is clear:How to construct the set "+" by using the axioms in ZF set theory?
$endgroup$
– user5938
Feb 20 '15 at 12:15
$begingroup$
@GitGud I think my question is clear:How to construct the set "+" by using the axioms in ZF set theory?
$endgroup$
– user5938
Feb 20 '15 at 12:15
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
You don't apply the recursion theorem infinitely many times. You apply it once.
First you prove that given an arbitrary $m$, the function $A_m$ is uniquely determined. Using generalization, we actually proved that for each $m$ there exists a unique function $A_m$ which has the properties that we want. Now, it is claimed that we can just define $m+n=A_m(n)$.
Of course for this we need to know that the map $mmapsto A_m$ is also a set, but this holds because the formula used to define $A_m$ is the same formula used to define $A_{m'}$, namely $m$ is just a parameter. To see this, however, you have to delve into the proof of the recursion theorem.
It is, essentially, the same as defining it directly as $m+0=m; m+s(n)=s(m+n)$ and appealing to the recursion theorem. Since here it is clear why the function $mmapsto A_m$ is a set as well.
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
$endgroup$
add a comment |
$begingroup$
It can be shown that there is exactly one function $f$ from $mathbb{N}^2$ to $mathbb{N}$ such that
- $forall x in mathbb{N} f(x, 0) = x$
- $forall x in mathbb{N}forall y in mathbb{N} f(x, S(y)) = S(f(x, y))$
Now we can define that $forall x in mathbb{N}forall y in mathbb{N}$, $x + y$ means $f(x, y)$.
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
$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%2f1157372%2fhow-to-define-addition-of-natural-number-in-zf%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$
You don't apply the recursion theorem infinitely many times. You apply it once.
First you prove that given an arbitrary $m$, the function $A_m$ is uniquely determined. Using generalization, we actually proved that for each $m$ there exists a unique function $A_m$ which has the properties that we want. Now, it is claimed that we can just define $m+n=A_m(n)$.
Of course for this we need to know that the map $mmapsto A_m$ is also a set, but this holds because the formula used to define $A_m$ is the same formula used to define $A_{m'}$, namely $m$ is just a parameter. To see this, however, you have to delve into the proof of the recursion theorem.
It is, essentially, the same as defining it directly as $m+0=m; m+s(n)=s(m+n)$ and appealing to the recursion theorem. Since here it is clear why the function $mmapsto A_m$ is a set as well.
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
$endgroup$
add a comment |
$begingroup$
You don't apply the recursion theorem infinitely many times. You apply it once.
First you prove that given an arbitrary $m$, the function $A_m$ is uniquely determined. Using generalization, we actually proved that for each $m$ there exists a unique function $A_m$ which has the properties that we want. Now, it is claimed that we can just define $m+n=A_m(n)$.
Of course for this we need to know that the map $mmapsto A_m$ is also a set, but this holds because the formula used to define $A_m$ is the same formula used to define $A_{m'}$, namely $m$ is just a parameter. To see this, however, you have to delve into the proof of the recursion theorem.
It is, essentially, the same as defining it directly as $m+0=m; m+s(n)=s(m+n)$ and appealing to the recursion theorem. Since here it is clear why the function $mmapsto A_m$ is a set as well.
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
$endgroup$
add a comment |
$begingroup$
You don't apply the recursion theorem infinitely many times. You apply it once.
First you prove that given an arbitrary $m$, the function $A_m$ is uniquely determined. Using generalization, we actually proved that for each $m$ there exists a unique function $A_m$ which has the properties that we want. Now, it is claimed that we can just define $m+n=A_m(n)$.
Of course for this we need to know that the map $mmapsto A_m$ is also a set, but this holds because the formula used to define $A_m$ is the same formula used to define $A_{m'}$, namely $m$ is just a parameter. To see this, however, you have to delve into the proof of the recursion theorem.
It is, essentially, the same as defining it directly as $m+0=m; m+s(n)=s(m+n)$ and appealing to the recursion theorem. Since here it is clear why the function $mmapsto A_m$ is a set as well.
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
$endgroup$
You don't apply the recursion theorem infinitely many times. You apply it once.
First you prove that given an arbitrary $m$, the function $A_m$ is uniquely determined. Using generalization, we actually proved that for each $m$ there exists a unique function $A_m$ which has the properties that we want. Now, it is claimed that we can just define $m+n=A_m(n)$.
Of course for this we need to know that the map $mmapsto A_m$ is also a set, but this holds because the formula used to define $A_m$ is the same formula used to define $A_{m'}$, namely $m$ is just a parameter. To see this, however, you have to delve into the proof of the recursion theorem.
It is, essentially, the same as defining it directly as $m+0=m; m+s(n)=s(m+n)$ and appealing to the recursion theorem. Since here it is clear why the function $mmapsto A_m$ is a set as well.
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
answered Feb 20 '15 at 12:39
Asaf Karagila♦Asaf Karagila
305k33435765
305k33435765
add a comment |
add a comment |
$begingroup$
It can be shown that there is exactly one function $f$ from $mathbb{N}^2$ to $mathbb{N}$ such that
- $forall x in mathbb{N} f(x, 0) = x$
- $forall x in mathbb{N}forall y in mathbb{N} f(x, S(y)) = S(f(x, y))$
Now we can define that $forall x in mathbb{N}forall y in mathbb{N}$, $x + y$ means $f(x, y)$.
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
$endgroup$
add a comment |
$begingroup$
It can be shown that there is exactly one function $f$ from $mathbb{N}^2$ to $mathbb{N}$ such that
- $forall x in mathbb{N} f(x, 0) = x$
- $forall x in mathbb{N}forall y in mathbb{N} f(x, S(y)) = S(f(x, y))$
Now we can define that $forall x in mathbb{N}forall y in mathbb{N}$, $x + y$ means $f(x, y)$.
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
$endgroup$
add a comment |
$begingroup$
It can be shown that there is exactly one function $f$ from $mathbb{N}^2$ to $mathbb{N}$ such that
- $forall x in mathbb{N} f(x, 0) = x$
- $forall x in mathbb{N}forall y in mathbb{N} f(x, S(y)) = S(f(x, y))$
Now we can define that $forall x in mathbb{N}forall y in mathbb{N}$, $x + y$ means $f(x, y)$.
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
$endgroup$
It can be shown that there is exactly one function $f$ from $mathbb{N}^2$ to $mathbb{N}$ such that
- $forall x in mathbb{N} f(x, 0) = x$
- $forall x in mathbb{N}forall y in mathbb{N} f(x, S(y)) = S(f(x, y))$
Now we can define that $forall x in mathbb{N}forall y in mathbb{N}$, $x + y$ means $f(x, y)$.
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
answered Dec 18 '18 at 1:03
TimothyTimothy
315214
315214
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%2f1157372%2fhow-to-define-addition-of-natural-number-in-zf%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
$begingroup$
I can't understand what you want. Do you want to avoid the recursion theorem?
$endgroup$
– Git Gud
Feb 20 '15 at 10:15
$begingroup$
You have to read the comment at the bottom of the page [H.Enderton, Elements of set Theory (1977), page 79] : the definition via Recursion Th "serve to characterize the binary operation $+$ in a recursive fashion", i.e. for any $n,m$ : $m+0=m$ and $m+n^+=(m+n)^+$. We can say that, in order to "compute" $3+2$ we need the "set" $A_2$ and "apply it" to $3$ : $A_2(3)=A_2(2)^+=A_2(1)^{++}=A_2(0)^{+++}=2^{+++}$.
$endgroup$
– Mauro ALLEGRANZA
Feb 20 '15 at 10:24
$begingroup$
I feel that this question has been asked several times before.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:30
$begingroup$
Also, when you quote something, it's usually a great idea to give an accurate citation.
$endgroup$
– Asaf Karagila♦
Feb 20 '15 at 10:32
$begingroup$
@GitGud I think my question is clear:How to construct the set "+" by using the axioms in ZF set theory?
$endgroup$
– user5938
Feb 20 '15 at 12:15