Proving $leq$ is a total order on $BbbN$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Define $leqsubsetBbbN^2$ as follows: $$a<bLeftrightarrowexists:xinBbbN:a+x=b$$
and $$aleq bLeftrightarrow a=bvee a<b$$
Now, assume I've proven that $leq$ is a partial order. Now, I wish to prove that $leq$ is a total ordering on $BbbN$. Importantly, I'm working with 1-based natural numbers, that is $0notin BbbN$.
I'm working within Peano Axioms.
My go:
I first present you with a lemma I'm using during the proof:
Lemma:$forall a,binBbbN:a+bneq 1$
We want to show that $forall a,bin BbbN:aleq b vee bleq a$. The trivial case $a=b$ follows from antisymmetry, because then, we have $aleq b$ and $bleq a$. Now, assume $aneq b$. We want to show that there is some $x_1in BbbN$ such that $a+x_1=b$ or there is some $x_2in BbbN$ such that $b+x_2=a$. We show that the first case holds if and only if the seconds doesn't thus always atleast one must hold (actually exactly one).
So, to prove $Rightarrow$ Let there exist some $x_1in BbbN$ such that $a+x_1=b$, we wish to show that $forall x_2inBbbN:b+x_2neq a$. Substitute for $b$ in the second equation and add $1$ to both sides to obtain:
$$a+x_1+x_2+1=a+1$$ which shows that $x_1+x_2+1neq 1$ and that holds by the lemma.
Now in the part for $Leftarrow$ im struggling:
Assume that $forall x_2in BbbN:b+x_2neq a$, we want to show that $exists x_1in BbbN:a+x_1=b$. Now, I have no idea how to explicitly find that $x_1$ when everything i know that this $x_2$ does NOT exist at all, i definitely cannot substitute the first equation into the second, because the first doesn't hold. Help please. Is this approach even correct?
relations order-theory
asked Aug 24 at 23:44
Michal Dvořák
55112
add a comment |Â
up vote
1
down vote
favorite
Define $leqsubsetBbbN^2$ as follows: $$a<bLeftrightarrowexists:xinBbbN:a+x=b$$
and $$aleq bLeftrightarrow a=bvee a<b$$
Now, assume I've proven that $leq$ is a partial order. Now, I wish to prove that $leq$ is a total ordering on $BbbN$. Importantly, I'm working with 1-based natural numbers, that is $0notin BbbN$.
I'm working within Peano Axioms.
My go:
I first present you with a lemma I'm using during the proof:
Lemma:$forall a,binBbbN:a+bneq 1$
We want to show that $forall a,bin BbbN:aleq b vee bleq a$. The trivial case $a=b$ follows from antisymmetry, because then, we have $aleq b$ and $bleq a$. Now, assume $aneq b$. We want to show that there is some $x_1in BbbN$ such that $a+x_1=b$ or there is some $x_2in BbbN$ such that $b+x_2=a$. We show that the first case holds if and only if the seconds doesn't thus always atleast one must hold (actually exactly one).
So, to prove $Rightarrow$ Let there exist some $x_1in BbbN$ such that $a+x_1=b$, we wish to show that $forall x_2inBbbN:b+x_2neq a$. Substitute for $b$ in the second equation and add $1$ to both sides to obtain:
$$a+x_1+x_2+1=a+1$$ which shows that $x_1+x_2+1neq 1$ and that holds by the lemma.
Now in the part for $Leftarrow$ im struggling:
Assume that $forall x_2in BbbN:b+x_2neq a$, we want to show that $exists x_1in BbbN:a+x_1=b$. Now, I have no idea how to explicitly find that $x_1$ when everything i know that this $x_2$ does NOT exist at all, i definitely cannot substitute the first equation into the second, because the first doesn't hold. Help please. Is this approach even correct?
relations order-theory
asked Aug 24 at 23:44
Michal Dvořák
55112
2
Let $a$ be any natural number and prove that $displaystyle mathoplargeforall_largebin mathbb Nleft(aleq b lor bleq aright)$ by induction. I didn't check all the details, but it seems to work.
– Git Gud
Aug 25 at 0:51
So, by induction on $b$ we have that either $aleq 1 vee 1leq a$. We can show the right side holds by induction on $a$. $1leq 1$ from antisymmetry and now either $a=1$ and we are done or $exists x in BbbN:1+x=a$ add $1$ to both sides to get $1+x+1=s(a)$, take $y=s(x)$ and we have that $1+yleq s(a)$ which shows we have that $forall ainBbbN:1leq a$...Am i doing this right?
– Michal Dvořák
Aug 25 at 9:22
You probably meant "we have that $1+ycolorred= s(a)$". And yes, this is correct.
– Git Gud
Aug 25 at 11:31
Yes, thats what i meant! Got it, thanks.
– Michal Dvořák
Aug 25 at 12:51
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Define $leqsubsetBbbN^2$ as follows: $$a<bLeftrightarrowexists:xinBbbN:a+x=b$$
and $$aleq bLeftrightarrow a=bvee a<b$$
Now, assume I've proven that $leq$ is a partial order. Now, I wish to prove that $leq$ is a total ordering on $BbbN$. Importantly, I'm working with 1-based natural numbers, that is $0notin BbbN$.
I'm working within Peano Axioms.
My go:
I first present you with a lemma I'm using during the proof:
Lemma:$forall a,binBbbN:a+bneq 1$
We want to show that $forall a,bin BbbN:aleq b vee bleq a$. The trivial case $a=b$ follows from antisymmetry, because then, we have $aleq b$ and $bleq a$. Now, assume $aneq b$. We want to show that there is some $x_1in BbbN$ such that $a+x_1=b$ or there is some $x_2in BbbN$ such that $b+x_2=a$. We show that the first case holds if and only if the seconds doesn't thus always atleast one must hold (actually exactly one).
So, to prove $Rightarrow$ Let there exist some $x_1in BbbN$ such that $a+x_1=b$, we wish to show that $forall x_2inBbbN:b+x_2neq a$. Substitute for $b$ in the second equation and add $1$ to both sides to obtain:
$$a+x_1+x_2+1=a+1$$ which shows that $x_1+x_2+1neq 1$ and that holds by the lemma.
Now in the part for $Leftarrow$ im struggling:
Assume that $forall x_2in BbbN:b+x_2neq a$, we want to show that $exists x_1in BbbN:a+x_1=b$. Now, I have no idea how to explicitly find that $x_1$ when everything i know that this $x_2$ does NOT exist at all, i definitely cannot substitute the first equation into the second, because the first doesn't hold. Help please. Is this approach even correct?
relations order-theory
asked Aug 24 at 23:44
Michal Dvořák
55112
Define $leqsubsetBbbN^2$ as follows: $$a<bLeftrightarrowexists:xinBbbN:a+x=b$$
and $$aleq bLeftrightarrow a=bvee a<b$$
Now, assume I've proven that $leq$ is a partial order. Now, I wish to prove that $leq$ is a total ordering on $BbbN$. Importantly, I'm working with 1-based natural numbers, that is $0notin BbbN$.
I'm working within Peano Axioms.
My go:
I first present you with a lemma I'm using during the proof:
Lemma:$forall a,binBbbN:a+bneq 1$
We want to show that $forall a,bin BbbN:aleq b vee bleq a$. The trivial case $a=b$ follows from antisymmetry, because then, we have $aleq b$ and $bleq a$. Now, assume $aneq b$. We want to show that there is some $x_1in BbbN$ such that $a+x_1=b$ or there is some $x_2in BbbN$ such that $b+x_2=a$. We show that the first case holds if and only if the seconds doesn't thus always atleast one must hold (actually exactly one).
So, to prove $Rightarrow$ Let there exist some $x_1in BbbN$ such that $a+x_1=b$, we wish to show that $forall x_2inBbbN:b+x_2neq a$. Substitute for $b$ in the second equation and add $1$ to both sides to obtain:
$$a+x_1+x_2+1=a+1$$ which shows that $x_1+x_2+1neq 1$ and that holds by the lemma.
Now in the part for $Leftarrow$ im struggling:
Assume that $forall x_2in BbbN:b+x_2neq a$, we want to show that $exists x_1in BbbN:a+x_1=b$. Now, I have no idea how to explicitly find that $x_1$ when everything i know that this $x_2$ does NOT exist at all, i definitely cannot substitute the first equation into the second, because the first doesn't hold. Help please. Is this approach even correct?
relations order-theory
asked Aug 24 at 23:44
Michal Dvořák
55112
edited Aug 25 at 0:47
asked Aug 24 at 23:44
Michal Dvořák
55112
asked Aug 24 at 23:44
Michal Dvořák
55112
asked Aug 24 at 23:44
Michal Dvořák
55112
55112
2
Let $a$ be any natural number and prove that $displaystyle mathoplargeforall_largebin mathbb Nleft(aleq b lor bleq aright)$ by induction. I didn't check all the details, but it seems to work.
– Git Gud
Aug 25 at 0:51
So, by induction on $b$ we have that either $aleq 1 vee 1leq a$. We can show the right side holds by induction on $a$. $1leq 1$ from antisymmetry and now either $a=1$ and we are done or $exists x in BbbN:1+x=a$ add $1$ to both sides to get $1+x+1=s(a)$, take $y=s(x)$ and we have that $1+yleq s(a)$ which shows we have that $forall ainBbbN:1leq a$...Am i doing this right?
– Michal Dvořák
Aug 25 at 9:22
You probably meant "we have that $1+ycolorred= s(a)$". And yes, this is correct.
– Git Gud
Aug 25 at 11:31
Yes, thats what i meant! Got it, thanks.
– Michal Dvořák
Aug 25 at 12:51
add a comment |Â
2
Let $a$ be any natural number and prove that $displaystyle mathoplargeforall_largebin mathbb Nleft(aleq b lor bleq aright)$ by induction. I didn't check all the details, but it seems to work.
– Git Gud
Aug 25 at 0:51
So, by induction on $b$ we have that either $aleq 1 vee 1leq a$. We can show the right side holds by induction on $a$. $1leq 1$ from antisymmetry and now either $a=1$ and we are done or $exists x in BbbN:1+x=a$ add $1$ to both sides to get $1+x+1=s(a)$, take $y=s(x)$ and we have that $1+yleq s(a)$ which shows we have that $forall ainBbbN:1leq a$...Am i doing this right?
– Michal Dvořák
Aug 25 at 9:22
You probably meant "we have that $1+ycolorred= s(a)$". And yes, this is correct.
– Git Gud
Aug 25 at 11:31
Yes, thats what i meant! Got it, thanks.
– Michal Dvořák
Aug 25 at 12:51
2
2
Let $a$ be any natural number and prove that $displaystyle mathoplargeforall_largebin mathbb Nleft(aleq b lor bleq aright)$ by induction. I didn't check all the details, but it seems to work.
– Git Gud
Aug 25 at 0:51
Let $a$ be any natural number and prove that $displaystyle mathoplargeforall_largebin mathbb Nleft(aleq b lor bleq aright)$ by induction. I didn't check all the details, but it seems to work.
– Git Gud
Aug 25 at 0:51
So, by induction on $b$ we have that either $aleq 1 vee 1leq a$. We can show the right side holds by induction on $a$. $1leq 1$ from antisymmetry and now either $a=1$ and we are done or $exists x in BbbN:1+x=a$ add $1$ to both sides to get $1+x+1=s(a)$, take $y=s(x)$ and we have that $1+yleq s(a)$ which shows we have that $forall ainBbbN:1leq a$...Am i doing this right?
– Michal Dvořák
Aug 25 at 9:22
So, by induction on $b$ we have that either $aleq 1 vee 1leq a$. We can show the right side holds by induction on $a$. $1leq 1$ from antisymmetry and now either $a=1$ and we are done or $exists x in BbbN:1+x=a$ add $1$ to both sides to get $1+x+1=s(a)$, take $y=s(x)$ and we have that $1+yleq s(a)$ which shows we have that $forall ainBbbN:1leq a$...Am i doing this right?
– Michal Dvořák
Aug 25 at 9:22
You probably meant "we have that $1+ycolorred= s(a)$". And yes, this is correct.
– Git Gud
Aug 25 at 11:31
You probably meant "we have that $1+ycolorred= s(a)$". And yes, this is correct.
– Git Gud
Aug 25 at 11:31
Yes, thats what i meant! Got it, thanks.
– Michal Dvořák
Aug 25 at 12:51
Yes, thats what i meant! Got it, thanks.
– Michal Dvořák
Aug 25 at 12:51
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
By definition if $ale b$ and $ane b$ we have $a<b$. If $a<b$ by definition $b=a+x$ for some natural $x$. Assuming $ble a$ we have $b<a$ so $a=b+y$ for some natural $y$, hence $b=(b+y)+x=b+(y+x)>b$, contradiction, so no need the lemma.
And this is enough. Take $a,b$, if $ble a$ and $ale b$, assuming $ane b$, and using the exact same thing I did above you get contradiction.
If $ale b$ and $ble c$, if $b=a$ we are done, otherwise $b=a+d$ and then if $b=c$ we are done otherwise $c=b+g$ hence $c=a+d+g$ thus $a<cimplies ale c$.
Given arbitrary $b$ we have $1le b$. If $ale b$ then $a+1le blor ble a+1$ thus for arbitrary $b$ we have $ble alor ale b$ for all $a.$
answered Aug 25 at 1:04
Holo
4,3322629
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
By definition if $ale b$ and $ane b$ we have $a<b$. If $a<b$ by definition $b=a+x$ for some natural $x$. Assuming $ble a$ we have $b<a$ so $a=b+y$ for some natural $y$, hence $b=(b+y)+x=b+(y+x)>b$, contradiction, so no need the lemma.
And this is enough. Take $a,b$, if $ble a$ and $ale b$, assuming $ane b$, and using the exact same thing I did above you get contradiction.
If $ale b$ and $ble c$, if $b=a$ we are done, otherwise $b=a+d$ and then if $b=c$ we are done otherwise $c=b+g$ hence $c=a+d+g$ thus $a<cimplies ale c$.
Given arbitrary $b$ we have $1le b$. If $ale b$ then $a+1le blor ble a+1$ thus for arbitrary $b$ we have $ble alor ale b$ for all $a.$
answered Aug 25 at 1:04
Holo
4,3322629
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
add a comment |Â
up vote
1
down vote
accepted
By definition if $ale b$ and $ane b$ we have $a<b$. If $a<b$ by definition $b=a+x$ for some natural $x$. Assuming $ble a$ we have $b<a$ so $a=b+y$ for some natural $y$, hence $b=(b+y)+x=b+(y+x)>b$, contradiction, so no need the lemma.
And this is enough. Take $a,b$, if $ble a$ and $ale b$, assuming $ane b$, and using the exact same thing I did above you get contradiction.
If $ale b$ and $ble c$, if $b=a$ we are done, otherwise $b=a+d$ and then if $b=c$ we are done otherwise $c=b+g$ hence $c=a+d+g$ thus $a<cimplies ale c$.
Given arbitrary $b$ we have $1le b$. If $ale b$ then $a+1le blor ble a+1$ thus for arbitrary $b$ we have $ble alor ale b$ for all $a.$
answered Aug 25 at 1:04
Holo
4,3322629
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
By definition if $ale b$ and $ane b$ we have $a<b$. If $a<b$ by definition $b=a+x$ for some natural $x$. Assuming $ble a$ we have $b<a$ so $a=b+y$ for some natural $y$, hence $b=(b+y)+x=b+(y+x)>b$, contradiction, so no need the lemma.
And this is enough. Take $a,b$, if $ble a$ and $ale b$, assuming $ane b$, and using the exact same thing I did above you get contradiction.
If $ale b$ and $ble c$, if $b=a$ we are done, otherwise $b=a+d$ and then if $b=c$ we are done otherwise $c=b+g$ hence $c=a+d+g$ thus $a<cimplies ale c$.
Given arbitrary $b$ we have $1le b$. If $ale b$ then $a+1le blor ble a+1$ thus for arbitrary $b$ we have $ble alor ale b$ for all $a.$
answered Aug 25 at 1:04
Holo
4,3322629
By definition if $ale b$ and $ane b$ we have $a<b$. If $a<b$ by definition $b=a+x$ for some natural $x$. Assuming $ble a$ we have $b<a$ so $a=b+y$ for some natural $y$, hence $b=(b+y)+x=b+(y+x)>b$, contradiction, so no need the lemma.
And this is enough. Take $a,b$, if $ble a$ and $ale b$, assuming $ane b$, and using the exact same thing I did above you get contradiction.
If $ale b$ and $ble c$, if $b=a$ we are done, otherwise $b=a+d$ and then if $b=c$ we are done otherwise $c=b+g$ hence $c=a+d+g$ thus $a<cimplies ale c$.
Given arbitrary $b$ we have $1le b$. If $ale b$ then $a+1le blor ble a+1$ thus for arbitrary $b$ we have $ble alor ale b$ for all $a.$
answered Aug 25 at 1:04
Holo
4,3322629
answered Aug 25 at 1:04
Holo
4,3322629
answered Aug 25 at 1:04
Holo
4,3322629
answered Aug 25 at 1:04
Holo
4,3322629
4,3322629
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
add a comment |Â
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
In the first paragraph, you proved antisymmetry, right? In the third line i used $b=b+y+xRightarrow b+1=b+y+x+1Rightarrow x+y+1=1$ which is impossible.
– Michal Dvořák
Aug 25 at 9:14
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
@MichalDvořák yes, exactly
– Holo
Aug 25 at 12:07
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%2f2893671%2fproving-leq-is-a-total-order-on-bbbn%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
2
Let $a$ be any natural number and prove that $displaystyle mathoplargeforall_largebin mathbb Nleft(aleq b lor bleq aright)$ by induction. I didn't check all the details, but it seems to work.
– Git Gud
Aug 25 at 0:51
So, by induction on $b$ we have that either $aleq 1 vee 1leq a$. We can show the right side holds by induction on $a$. $1leq 1$ from antisymmetry and now either $a=1$ and we are done or $exists x in BbbN:1+x=a$ add $1$ to both sides to get $1+x+1=s(a)$, take $y=s(x)$ and we have that $1+yleq s(a)$ which shows we have that $forall ainBbbN:1leq a$...Am i doing this right?
– Michal Dvořák
Aug 25 at 9:22
You probably meant "we have that $1+ycolorred= s(a)$". And yes, this is correct.
– Git Gud
Aug 25 at 11:31
Yes, thats what i meant! Got it, thanks.
– Michal Dvořák
Aug 25 at 12:51