Question in Proof That Every Well-Ordering is a Total-Ordering
$begingroup$
I am trying to make sense of the following:
Theorem: Let $R$ be a relation on a set $A$.
If $R$ is a well-ordered relation on $A$, then $R$ is a total-order relation on $A$.
Proof: Suppose $x,yin A.$ Let $R={x,y}not=emptyset$. By assumption, $R$ has a least element. If it is $x$, then $xleq y$. If it is $y$, then $yleq x$.
$$text{__________________________________}$$
For a relation to be total ordered, then it must be that for each $x,yin A$, $xRy$ and $yRx$. In this case we are comparing $x , y$ where one or the other is a least element. What about if neither is a least element though? Do we then simply say that $x,y$ must relate because if we consider whatever is the least element, say $z$, then both $x,y$ can relate to $z$ and therefore must relate to each other?
elementary-set-theory relations well-orders
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
$endgroup$
|
show 6 more comments
$begingroup$
I am trying to make sense of the following:
Theorem: Let $R$ be a relation on a set $A$.
If $R$ is a well-ordered relation on $A$, then $R$ is a total-order relation on $A$.
Proof: Suppose $x,yin A.$ Let $R={x,y}not=emptyset$. By assumption, $R$ has a least element. If it is $x$, then $xleq y$. If it is $y$, then $yleq x$.
$$text{__________________________________}$$
For a relation to be total ordered, then it must be that for each $x,yin A$, $xRy$ and $yRx$. In this case we are comparing $x , y$ where one or the other is a least element. What about if neither is a least element though? Do we then simply say that $x,y$ must relate because if we consider whatever is the least element, say $z$, then both $x,y$ can relate to $z$ and therefore must relate to each other?
elementary-set-theory relations well-orders
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
$endgroup$
$begingroup$
One of them must be the least element of ${x,y}$ because there are no other elements in the set, and it has a least element.
$endgroup$
– dbx
Dec 5 '18 at 15:13
$begingroup$
Where does this proof come from? In the definitions as I've learned them, well-ordered relations are defined to be both well-founded and totally ordered, and well-founded relations need not be totally ordered. See also math.stackexchange.com/questions/116642/…
$endgroup$
– J.G.
Dec 5 '18 at 15:19
$begingroup$
The definition my book uses denotes well-ordered relation as a partially-ordered relation on $A$ such that each non-empty subset of $A$ has a least element with respect to $R$.
$endgroup$
– M. Damon
Dec 5 '18 at 15:26
$begingroup$
@J.G.: Well-founded relations have a minimal element in each non-empty set; well-orders have a minimum in each non-empty set.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 15:27
$begingroup$
@AsafKaragila In other words, the minimal element of the non-empty set is only required to be unique in the latter case? Fair enough.
$endgroup$
– J.G.
Dec 5 '18 at 15:31
|
show 6 more comments
$begingroup$
I am trying to make sense of the following:
Theorem: Let $R$ be a relation on a set $A$.
If $R$ is a well-ordered relation on $A$, then $R$ is a total-order relation on $A$.
Proof: Suppose $x,yin A.$ Let $R={x,y}not=emptyset$. By assumption, $R$ has a least element. If it is $x$, then $xleq y$. If it is $y$, then $yleq x$.
$$text{__________________________________}$$
For a relation to be total ordered, then it must be that for each $x,yin A$, $xRy$ and $yRx$. In this case we are comparing $x , y$ where one or the other is a least element. What about if neither is a least element though? Do we then simply say that $x,y$ must relate because if we consider whatever is the least element, say $z$, then both $x,y$ can relate to $z$ and therefore must relate to each other?
elementary-set-theory relations well-orders
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
$endgroup$
I am trying to make sense of the following:
Theorem: Let $R$ be a relation on a set $A$.
If $R$ is a well-ordered relation on $A$, then $R$ is a total-order relation on $A$.
Proof: Suppose $x,yin A.$ Let $R={x,y}not=emptyset$. By assumption, $R$ has a least element. If it is $x$, then $xleq y$. If it is $y$, then $yleq x$.
$$text{__________________________________}$$
For a relation to be total ordered, then it must be that for each $x,yin A$, $xRy$ and $yRx$. In this case we are comparing $x , y$ where one or the other is a least element. What about if neither is a least element though? Do we then simply say that $x,y$ must relate because if we consider whatever is the least element, say $z$, then both $x,y$ can relate to $z$ and therefore must relate to each other?
elementary-set-theory relations well-orders
elementary-set-theory relations well-orders
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
asked Dec 5 '18 at 15:12
M. Damon M. Damon
235
235
$begingroup$
One of them must be the least element of ${x,y}$ because there are no other elements in the set, and it has a least element.
$endgroup$
– dbx
Dec 5 '18 at 15:13
$begingroup$
Where does this proof come from? In the definitions as I've learned them, well-ordered relations are defined to be both well-founded and totally ordered, and well-founded relations need not be totally ordered. See also math.stackexchange.com/questions/116642/…
$endgroup$
– J.G.
Dec 5 '18 at 15:19
$begingroup$
The definition my book uses denotes well-ordered relation as a partially-ordered relation on $A$ such that each non-empty subset of $A$ has a least element with respect to $R$.
$endgroup$
– M. Damon
Dec 5 '18 at 15:26
$begingroup$
@J.G.: Well-founded relations have a minimal element in each non-empty set; well-orders have a minimum in each non-empty set.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 15:27
$begingroup$
@AsafKaragila In other words, the minimal element of the non-empty set is only required to be unique in the latter case? Fair enough.
$endgroup$
– J.G.
Dec 5 '18 at 15:31
|
show 6 more comments
$begingroup$
One of them must be the least element of ${x,y}$ because there are no other elements in the set, and it has a least element.
$endgroup$
– dbx
Dec 5 '18 at 15:13
$begingroup$
Where does this proof come from? In the definitions as I've learned them, well-ordered relations are defined to be both well-founded and totally ordered, and well-founded relations need not be totally ordered. See also math.stackexchange.com/questions/116642/…
$endgroup$
– J.G.
Dec 5 '18 at 15:19
$begingroup$
The definition my book uses denotes well-ordered relation as a partially-ordered relation on $A$ such that each non-empty subset of $A$ has a least element with respect to $R$.
$endgroup$
– M. Damon
Dec 5 '18 at 15:26
$begingroup$
@J.G.: Well-founded relations have a minimal element in each non-empty set; well-orders have a minimum in each non-empty set.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 15:27
$begingroup$
@AsafKaragila In other words, the minimal element of the non-empty set is only required to be unique in the latter case? Fair enough.
$endgroup$
– J.G.
Dec 5 '18 at 15:31
$begingroup$
One of them must be the least element of ${x,y}$ because there are no other elements in the set, and it has a least element.
$endgroup$
– dbx
Dec 5 '18 at 15:13
$begingroup$
One of them must be the least element of ${x,y}$ because there are no other elements in the set, and it has a least element.
$endgroup$
– dbx
Dec 5 '18 at 15:13
$begingroup$
Where does this proof come from? In the definitions as I've learned them, well-ordered relations are defined to be both well-founded and totally ordered, and well-founded relations need not be totally ordered. See also math.stackexchange.com/questions/116642/…
$endgroup$
– J.G.
Dec 5 '18 at 15:19
$begingroup$
Where does this proof come from? In the definitions as I've learned them, well-ordered relations are defined to be both well-founded and totally ordered, and well-founded relations need not be totally ordered. See also math.stackexchange.com/questions/116642/…
$endgroup$
– J.G.
Dec 5 '18 at 15:19
$begingroup$
The definition my book uses denotes well-ordered relation as a partially-ordered relation on $A$ such that each non-empty subset of $A$ has a least element with respect to $R$.
$endgroup$
– M. Damon
Dec 5 '18 at 15:26
$begingroup$
The definition my book uses denotes well-ordered relation as a partially-ordered relation on $A$ such that each non-empty subset of $A$ has a least element with respect to $R$.
$endgroup$
– M. Damon
Dec 5 '18 at 15:26
$begingroup$
@J.G.: Well-founded relations have a minimal element in each non-empty set; well-orders have a minimum in each non-empty set.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 15:27
$begingroup$
@J.G.: Well-founded relations have a minimal element in each non-empty set; well-orders have a minimum in each non-empty set.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 15:27
$begingroup$
@AsafKaragila In other words, the minimal element of the non-empty set is only required to be unique in the latter case? Fair enough.
$endgroup$
– J.G.
Dec 5 '18 at 15:31
$begingroup$
@AsafKaragila In other words, the minimal element of the non-empty set is only required to be unique in the latter case? Fair enough.
$endgroup$
– J.G.
Dec 5 '18 at 15:31
|
show 6 more comments
1 Answer
1
active
oldest
votes
$begingroup$
How could none of them be the last element? There is no other element in ${x,y}$ besides $x$ and $y$.
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
$endgroup$
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
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%2f3027181%2fquestion-in-proof-that-every-well-ordering-is-a-total-ordering%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
How could none of them be the last element? There is no other element in ${x,y}$ besides $x$ and $y$.
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
$endgroup$
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
add a comment |
$begingroup$
How could none of them be the last element? There is no other element in ${x,y}$ besides $x$ and $y$.
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
$endgroup$
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
add a comment |
$begingroup$
How could none of them be the last element? There is no other element in ${x,y}$ besides $x$ and $y$.
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
$endgroup$
How could none of them be the last element? There is no other element in ${x,y}$ besides $x$ and $y$.
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
answered Dec 5 '18 at 15:16
José Carlos SantosJosé Carlos Santos
154k22123226
154k22123226
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
add a comment |
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
$begingroup$
+1 To expand on this answer, recall that ${x,y}$ is nonempty since $x$ and $y$ are elements (it is still possible $x$ and $y$ are equal). Because $R$ is well-ordered, there must exist a $R$-least-element in ${x,y}$.
$endgroup$
– Alberto Takase
Dec 6 '18 at 10:39
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%2f3027181%2fquestion-in-proof-that-every-well-ordering-is-a-total-ordering%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$
One of them must be the least element of ${x,y}$ because there are no other elements in the set, and it has a least element.
$endgroup$
– dbx
Dec 5 '18 at 15:13
$begingroup$
Where does this proof come from? In the definitions as I've learned them, well-ordered relations are defined to be both well-founded and totally ordered, and well-founded relations need not be totally ordered. See also math.stackexchange.com/questions/116642/…
$endgroup$
– J.G.
Dec 5 '18 at 15:19
$begingroup$
The definition my book uses denotes well-ordered relation as a partially-ordered relation on $A$ such that each non-empty subset of $A$ has a least element with respect to $R$.
$endgroup$
– M. Damon
Dec 5 '18 at 15:26
$begingroup$
@J.G.: Well-founded relations have a minimal element in each non-empty set; well-orders have a minimum in each non-empty set.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 15:27
$begingroup$
@AsafKaragila In other words, the minimal element of the non-empty set is only required to be unique in the latter case? Fair enough.
$endgroup$
– J.G.
Dec 5 '18 at 15:31