Can we find a well ordering on an infinite set with no largest element?
$begingroup$
According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.
My question is:
For a given infinite set, can we find a well ordering on it such that there is no largest element?
elementary-set-theory well-orders
$endgroup$
|
show 2 more comments
$begingroup$
According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.
My question is:
For a given infinite set, can we find a well ordering on it such that there is no largest element?
elementary-set-theory well-orders
$endgroup$
2
$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54
2
$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55
$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02
$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16
$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02
|
show 2 more comments
$begingroup$
According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.
My question is:
For a given infinite set, can we find a well ordering on it such that there is no largest element?
elementary-set-theory well-orders
$endgroup$
According to the well ordering theorem "Any set can be well ordered". Whenever we have a well ordering on a set, it is not difficult to construct a new well ordering with a largest element.
My question is:
For a given infinite set, can we find a well ordering on it such that there is no largest element?
elementary-set-theory well-orders
elementary-set-theory well-orders
edited Jul 2 '17 at 22:52
RQM
1213
1213
asked Jul 2 '17 at 18:53
BumblebeeBumblebee
9,74912551
9,74912551
2
$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54
2
$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55
$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02
$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16
$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02
|
show 2 more comments
2
$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54
2
$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55
$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02
$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16
$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02
2
2
$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54
$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54
2
2
$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55
$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55
$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02
$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02
$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16
$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16
$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02
$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.
Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.
It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.
If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff
$a, bin I_X$ and $a<b$ in the original sense of $X$; or
$a, bin F_X$ and $a<b$ in the original sense of $X$; or
$ain F_X, bin I_X$.
$endgroup$
add a comment |
$begingroup$
If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.
$endgroup$
2
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
1
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
add a comment |
$begingroup$
In the usual development of ZFC, a cardinal is defined to the the
least ordinal with a given cardinality. Infinite cardinals are "limit
ordinals" --- as ordered sets they have no largest element.
$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%2f2344254%2fcan-we-find-a-well-ordering-on-an-infinite-set-with-no-largest-element%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.
Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.
It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.
If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff
$a, bin I_X$ and $a<b$ in the original sense of $X$; or
$a, bin F_X$ and $a<b$ in the original sense of $X$; or
$ain F_X, bin I_X$.
$endgroup$
add a comment |
$begingroup$
Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.
Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.
It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.
If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff
$a, bin I_X$ and $a<b$ in the original sense of $X$; or
$a, bin F_X$ and $a<b$ in the original sense of $X$; or
$ain F_X, bin I_X$.
$endgroup$
add a comment |
$begingroup$
Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.
Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.
It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.
If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff
$a, bin I_X$ and $a<b$ in the original sense of $X$; or
$a, bin F_X$ and $a<b$ in the original sense of $X$; or
$ain F_X, bin I_X$.
$endgroup$
Yes. In fact, there is a canonical way to transform a well-ordering into a well-ordering of the same set with no greatest element.
Suppose I have an infinite well-order $X$. Let $F_X$ be the set of elements of $X$ with finitely many things bigger than them - for instance, the greatest element of $X$ (if such an element exists) is in $F_X$, while (if $X$ is infinite) the least element of $X$ (which always exists, since $X$ is a well-ordering) is not in $F_X$.
It's not hard to show that $F_X$ is finite, since otherwise we could build an infinite descending chain in $X$ (exercise). Now let $I_X=Xsetminus F_X$; this is a well-ordered set with no greatest element.
If $X$ is infinite, $I_X$ and $X$ have the same cardinality. If you want an explicit isomorphism, we can "move $F_X$ to the back" - define a new ordering $prec$ on $X$, given by $aprec b$ iff
$a, bin I_X$ and $a<b$ in the original sense of $X$; or
$a, bin F_X$ and $a<b$ in the original sense of $X$; or
$ain F_X, bin I_X$.
edited Jul 2 '17 at 21:47
answered Jul 2 '17 at 20:05
Noah SchweberNoah Schweber
128k10152294
128k10152294
add a comment |
add a comment |
$begingroup$
If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.
$endgroup$
2
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
1
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
add a comment |
$begingroup$
If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.
$endgroup$
2
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
1
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
add a comment |
$begingroup$
If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.
$endgroup$
If $A$ is infinite then $A$ can be put in bijection with $A cup mathbb{N}$. Now from the well ordering of $A$ you can ge a well ordering of $A cup mathbb{N}$ without a largest element ( in the obvious way ) and then back, a new well-ordering of $A$ without a largest element.
answered Jul 2 '17 at 19:58
Orest BucicovschiOrest Bucicovschi
28.6k31748
28.6k31748
2
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
1
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
add a comment |
2
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
1
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
2
2
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
$begingroup$
As an interesting aside, note that for the first sentence, we either need a weak form of the axiom of choice or the assumption (which is present here) that $A$ is well-orderable: it is consistent with ZF that there is an infinite set $A$ which is not in bijection with $Acupmathbb{N}$ (namely, any infinite Dedekind-finite set).
$endgroup$
– Noah Schweber
Jul 2 '17 at 21:48
1
1
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
$begingroup$
@Noah Schweber: Very interesting.! To do away with the bijection, I guess we could just move $mathbb{N}$ from the beginning to the end, similarly to the move in your solution.
$endgroup$
– Orest Bucicovschi
Jul 2 '17 at 23:44
add a comment |
$begingroup$
In the usual development of ZFC, a cardinal is defined to the the
least ordinal with a given cardinality. Infinite cardinals are "limit
ordinals" --- as ordered sets they have no largest element.
$endgroup$
add a comment |
$begingroup$
In the usual development of ZFC, a cardinal is defined to the the
least ordinal with a given cardinality. Infinite cardinals are "limit
ordinals" --- as ordered sets they have no largest element.
$endgroup$
add a comment |
$begingroup$
In the usual development of ZFC, a cardinal is defined to the the
least ordinal with a given cardinality. Infinite cardinals are "limit
ordinals" --- as ordered sets they have no largest element.
$endgroup$
In the usual development of ZFC, a cardinal is defined to the the
least ordinal with a given cardinality. Infinite cardinals are "limit
ordinals" --- as ordered sets they have no largest element.
answered Jul 2 '17 at 18:56
Lord Shark the UnknownLord Shark the Unknown
108k1162135
108k1162135
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%2f2344254%2fcan-we-find-a-well-ordering-on-an-infinite-set-with-no-largest-element%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
2
$begingroup$
Set of natural numbers.
$endgroup$
– Wuestenfux
Jul 2 '17 at 18:54
2
$begingroup$
Induce the well-order by a bijection with a cardinal number.
$endgroup$
– Daniel Fischer
Jul 2 '17 at 18:55
$begingroup$
Use Choice + transfinite induction to define it one at a time?
$endgroup$
– Chappers
Jul 2 '17 at 19:02
$begingroup$
math.stackexchange.com/questions/6501/…
$endgroup$
– Count Iblis
Jul 2 '17 at 19:16
$begingroup$
@CountIblis That question is not related to this one at all.
$endgroup$
– Noah Schweber
Jul 2 '17 at 20:02