Mixing
How to prove that $m < n Longleftrightarrow m + 1 < n + 1$ when defining natural numbers from scratch in ZFC?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
An important results for natural numbers and their ordering by $<$ (that is, $in$, $m < n$ means $m in n$) is that for any natural numbers $m,n$ and $k$, we have $m < n Longleftrightarrow m + 1 < n + 1$.
What preliminary results are needed? This is also a preliminary result, a lemma for the following result by induction: $forall m,n,k in mathbbN, m < n Longleftrightarrow m + k < n + k$.
Mathematical induction is assumed, of course, as is the fact that $m + 1 = mcupm$. Also, it has already been proven that $leq$ ($m leq n$ stands for $m < n$ or $m = n$) is a well-ordering on $mathbbN$. The addition is defined as follows: $forall m,n in mathbbN$,
$m + 0 = m$,
$m + (n + 1) = (m + n) + 1$.
induction set-theory natural-numbers
asked Jul 29 at 8:16
Jxt921
896616
add a comment |Â
up vote
0
down vote
favorite
An important results for natural numbers and their ordering by $<$ (that is, $in$, $m < n$ means $m in n$) is that for any natural numbers $m,n$ and $k$, we have $m < n Longleftrightarrow m + 1 < n + 1$.
What preliminary results are needed? This is also a preliminary result, a lemma for the following result by induction: $forall m,n,k in mathbbN, m < n Longleftrightarrow m + k < n + k$.
Mathematical induction is assumed, of course, as is the fact that $m + 1 = mcupm$. Also, it has already been proven that $leq$ ($m leq n$ stands for $m < n$ or $m = n$) is a well-ordering on $mathbbN$. The addition is defined as follows: $forall m,n in mathbbN$,
$m + 0 = m$,
$m + (n + 1) = (m + n) + 1$.
induction set-theory natural-numbers
asked Jul 29 at 8:16
Jxt921
896616
$m + 1 = mcupm$ is just one way to construct a set behaving like the natural numbers; the actual construction used should be of no consequence in an argument using the axioms. Once you've shown that your construction indeed fulfills the axioms, of course.
– Arthur
Jul 29 at 8:39
1
@Arthur: Depending on how you do things, you might want to argue that directly. And while it is true that the finite von Neumann ordinals is just one of many ways of doing this, it is also the standard way of constructing the natural numbers in set theory. So standard to the point that many people out side of set theory would consider it "the way of doing it" (which often has sour implications on the view people have on set theoretic foundations later in their life).
– Asaf Karagila
Jul 29 at 11:33
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
An important results for natural numbers and their ordering by $<$ (that is, $in$, $m < n$ means $m in n$) is that for any natural numbers $m,n$ and $k$, we have $m < n Longleftrightarrow m + 1 < n + 1$.
What preliminary results are needed? This is also a preliminary result, a lemma for the following result by induction: $forall m,n,k in mathbbN, m < n Longleftrightarrow m + k < n + k$.
Mathematical induction is assumed, of course, as is the fact that $m + 1 = mcupm$. Also, it has already been proven that $leq$ ($m leq n$ stands for $m < n$ or $m = n$) is a well-ordering on $mathbbN$. The addition is defined as follows: $forall m,n in mathbbN$,
$m + 0 = m$,
$m + (n + 1) = (m + n) + 1$.
induction set-theory natural-numbers
asked Jul 29 at 8:16
Jxt921
896616
An important results for natural numbers and their ordering by $<$ (that is, $in$, $m < n$ means $m in n$) is that for any natural numbers $m,n$ and $k$, we have $m < n Longleftrightarrow m + 1 < n + 1$.
What preliminary results are needed? This is also a preliminary result, a lemma for the following result by induction: $forall m,n,k in mathbbN, m < n Longleftrightarrow m + k < n + k$.
Mathematical induction is assumed, of course, as is the fact that $m + 1 = mcupm$. Also, it has already been proven that $leq$ ($m leq n$ stands for $m < n$ or $m = n$) is a well-ordering on $mathbbN$. The addition is defined as follows: $forall m,n in mathbbN$,
$m + 0 = m$,
$m + (n + 1) = (m + n) + 1$.
induction set-theory natural-numbers
asked Jul 29 at 8:16
Jxt921
896616
asked Jul 29 at 8:16
Jxt921
896616
asked Jul 29 at 8:16
Jxt921
896616
asked Jul 29 at 8:16
Jxt921
896616
896616
$m + 1 = mcupm$ is just one way to construct a set behaving like the natural numbers; the actual construction used should be of no consequence in an argument using the axioms. Once you've shown that your construction indeed fulfills the axioms, of course.
– Arthur
Jul 29 at 8:39
1
@Arthur: Depending on how you do things, you might want to argue that directly. And while it is true that the finite von Neumann ordinals is just one of many ways of doing this, it is also the standard way of constructing the natural numbers in set theory. So standard to the point that many people out side of set theory would consider it "the way of doing it" (which often has sour implications on the view people have on set theoretic foundations later in their life).
– Asaf Karagila
Jul 29 at 11:33
add a comment |Â
$m + 1 = mcupm$ is just one way to construct a set behaving like the natural numbers; the actual construction used should be of no consequence in an argument using the axioms. Once you've shown that your construction indeed fulfills the axioms, of course.
– Arthur
Jul 29 at 8:39
1
@Arthur: Depending on how you do things, you might want to argue that directly. And while it is true that the finite von Neumann ordinals is just one of many ways of doing this, it is also the standard way of constructing the natural numbers in set theory. So standard to the point that many people out side of set theory would consider it "the way of doing it" (which often has sour implications on the view people have on set theoretic foundations later in their life).
– Asaf Karagila
Jul 29 at 11:33
$m + 1 = mcupm$ is just one way to construct a set behaving like the natural numbers; the actual construction used should be of no consequence in an argument using the axioms. Once you've shown that your construction indeed fulfills the axioms, of course.
– Arthur
Jul 29 at 8:39
$m + 1 = mcupm$ is just one way to construct a set behaving like the natural numbers; the actual construction used should be of no consequence in an argument using the axioms. Once you've shown that your construction indeed fulfills the axioms, of course.
– Arthur
Jul 29 at 8:39
1
1
@Arthur: Depending on how you do things, you might want to argue that directly. And while it is true that the finite von Neumann ordinals is just one of many ways of doing this, it is also the standard way of constructing the natural numbers in set theory. So standard to the point that many people out side of set theory would consider it "the way of doing it" (which often has sour implications on the view people have on set theoretic foundations later in their life).
– Asaf Karagila
Jul 29 at 11:33
@Arthur: Depending on how you do things, you might want to argue that directly. And while it is true that the finite von Neumann ordinals is just one of many ways of doing this, it is also the standard way of constructing the natural numbers in set theory. So standard to the point that many people out side of set theory would consider it "the way of doing it" (which often has sour implications on the view people have on set theoretic foundations later in their life).
– Asaf Karagila
Jul 29 at 11:33
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
First of all, if $m+1<n+1$, then $mcupmin ncupn$, therefore either $mcupm=n$, in which case $min n$ and we are done, or $mcupmin n$, in which case $min n$ and we are done again.
Secondly, if $min n$, then either $mcupmin n$, in which case we are clearly done; or $mcupm=n$, in which case $nin ncupn$ so $mcupmin ncupn$.
What did we use? We used the fact that $n$ is transitive, so $xin yin n$ means $xin n$. It is tempting that we directly appeal to the fact that $in$ is well-founded, and therefore there are no $in$-loops, but it doesn't matter. If they were are $in$-loops in that definition it would just show that $<$ is not a linear ordering (or a partial ordering for that matter), the proof would still work.
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
First of all, if $m+1<n+1$, then $mcupmin ncupn$, therefore either $mcupm=n$, in which case $min n$ and we are done, or $mcupmin n$, in which case $min n$ and we are done again.
Secondly, if $min n$, then either $mcupmin n$, in which case we are clearly done; or $mcupm=n$, in which case $nin ncupn$ so $mcupmin ncupn$.
What did we use? We used the fact that $n$ is transitive, so $xin yin n$ means $xin n$. It is tempting that we directly appeal to the fact that $in$ is well-founded, and therefore there are no $in$-loops, but it doesn't matter. If they were are $in$-loops in that definition it would just show that $<$ is not a linear ordering (or a partial ordering for that matter), the proof would still work.
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
add a comment |Â
up vote
5
down vote
accepted
First of all, if $m+1<n+1$, then $mcupmin ncupn$, therefore either $mcupm=n$, in which case $min n$ and we are done, or $mcupmin n$, in which case $min n$ and we are done again.
Secondly, if $min n$, then either $mcupmin n$, in which case we are clearly done; or $mcupm=n$, in which case $nin ncupn$ so $mcupmin ncupn$.
What did we use? We used the fact that $n$ is transitive, so $xin yin n$ means $xin n$. It is tempting that we directly appeal to the fact that $in$ is well-founded, and therefore there are no $in$-loops, but it doesn't matter. If they were are $in$-loops in that definition it would just show that $<$ is not a linear ordering (or a partial ordering for that matter), the proof would still work.
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
First of all, if $m+1<n+1$, then $mcupmin ncupn$, therefore either $mcupm=n$, in which case $min n$ and we are done, or $mcupmin n$, in which case $min n$ and we are done again.
Secondly, if $min n$, then either $mcupmin n$, in which case we are clearly done; or $mcupm=n$, in which case $nin ncupn$ so $mcupmin ncupn$.
What did we use? We used the fact that $n$ is transitive, so $xin yin n$ means $xin n$. It is tempting that we directly appeal to the fact that $in$ is well-founded, and therefore there are no $in$-loops, but it doesn't matter. If they were are $in$-loops in that definition it would just show that $<$ is not a linear ordering (or a partial ordering for that matter), the proof would still work.
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
First of all, if $m+1<n+1$, then $mcupmin ncupn$, therefore either $mcupm=n$, in which case $min n$ and we are done, or $mcupmin n$, in which case $min n$ and we are done again.
Secondly, if $min n$, then either $mcupmin n$, in which case we are clearly done; or $mcupm=n$, in which case $nin ncupn$ so $mcupmin ncupn$.
What did we use? We used the fact that $n$ is transitive, so $xin yin n$ means $xin n$. It is tempting that we directly appeal to the fact that $in$ is well-founded, and therefore there are no $in$-loops, but it doesn't matter. If they were are $in$-loops in that definition it would just show that $<$ is not a linear ordering (or a partial ordering for that matter), the proof would still work.
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
answered Jul 29 at 8:27
Asaf Karagila
291k31402732
291k31402732
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
add a comment |Â
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Thank you, Asaf. Trying by myself, I managed to do one side of the equivalence, namely the first one in your answer. As for the second one, from what I can see, there is an additional lemma required: for any natural numbers $m$ and $n$, $n < m$ implies $n + 1 leq m$.
– Jxt921
Jul 31 at 10:47
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
Hmm. It might be needed to have that $in$ is in fact well-founded (from which you can easily derive that $n+1leq m$).
– Asaf Karagila
Jul 31 at 11:40
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
I don't think it's necessary to use the axiom of foundation. In fact, we could use the result that $leq$ is a total order on $mathbbN$: assume that $n < m$. As $mathbbN$ is totally ordered by $leq$, then we have $n + 1 leq m$ or $m < n + 1$. The latter implies that either $m = n$ or $m < n$, contradicting $n < m$ due to transitive and irreflexive nature of $<$ as a strict order with respect to total order $leq$ on $mathbbN$.
– Jxt921
Jul 31 at 17:24
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
Oh, I meant that $in$ is well-founded on the natural numbers. If you already have that this is a total order, then it's even easier.
– Asaf Karagila
Jul 31 at 17:39
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865886%2fhow-to-prove-that-m-n-longleftrightarrow-m-1-n-1-when-defining-natura%23new-answer', 'question_page');
);
Post as a guest
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
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
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
$m + 1 = mcupm$ is just one way to construct a set behaving like the natural numbers; the actual construction used should be of no consequence in an argument using the axioms. Once you've shown that your construction indeed fulfills the axioms, of course.
– Arthur
Jul 29 at 8:39
1
@Arthur: Depending on how you do things, you might want to argue that directly. And while it is true that the finite von Neumann ordinals is just one of many ways of doing this, it is also the standard way of constructing the natural numbers in set theory. So standard to the point that many people out side of set theory would consider it "the way of doing it" (which often has sour implications on the view people have on set theoretic foundations later in their life).
– Asaf Karagila
Jul 29 at 11:33