Prove that there exist $2^{aleph_{0}}$ well-orderings of the set of all natural numbers.
From Chapter 6 Hrbacek and Jech (Ordinal Numbers) Problem 1.3. I don't understand how to begin. Below is the only solution I could find online, but even then I still don't understand how they arrived with those figures.
elementary-set-theory
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
add a comment |
From Chapter 6 Hrbacek and Jech (Ordinal Numbers) Problem 1.3. I don't understand how to begin. Below is the only solution I could find online, but even then I still don't understand how they arrived with those figures.
elementary-set-theory
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 '18 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 '18 at 22:18
Any bijection of $mathbb{N}$ can be declared an order isomorphism with another well-order (of type $omega$), e.g.
– Henno Brandsma
Nov 19 '18 at 22:20
add a comment |
From Chapter 6 Hrbacek and Jech (Ordinal Numbers) Problem 1.3. I don't understand how to begin. Below is the only solution I could find online, but even then I still don't understand how they arrived with those figures.
elementary-set-theory
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
From Chapter 6 Hrbacek and Jech (Ordinal Numbers) Problem 1.3. I don't understand how to begin. Below is the only solution I could find online, but even then I still don't understand how they arrived with those figures.
elementary-set-theory
elementary-set-theory
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
edited Nov 20 '18 at 4:22
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
asked Nov 19 '18 at 4:40
Barycentric_Bash
40139
40139
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 '18 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 '18 at 22:18
Any bijection of $mathbb{N}$ can be declared an order isomorphism with another well-order (of type $omega$), e.g.
– Henno Brandsma
Nov 19 '18 at 22:20
add a comment |
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 '18 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 '18 at 22:18
Any bijection of $mathbb{N}$ can be declared an order isomorphism with another well-order (of type $omega$), e.g.
– Henno Brandsma
Nov 19 '18 at 22:20
2
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 '18 at 5:34
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 '18 at 5:34
1
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 '18 at 22:18
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 '18 at 22:18
Any bijection of $mathbb{N}$ can be declared an order isomorphism with another well-order (of type $omega$), e.g.
– Henno Brandsma
Nov 19 '18 at 22:20
Any bijection of $mathbb{N}$ can be declared an order isomorphism with another well-order (of type $omega$), e.g.
– Henno Brandsma
Nov 19 '18 at 22:20
add a comment |
1 Answer
1
active
oldest
votes
Given the usual order on $Bbb N$, you can show there are at least $2^{aleph_0}$ because you can break $Bbb N$ into $aleph_0$ pairs $(2n, 2n+1)$. You can then invert each pair or not, which is $aleph_0$ binary choices. There are at most $aleph_0^{aleph_0}$ because there are $aleph_0$ choices for the first element of the well order, and again for the next, and so on. If you know $2^{aleph_0}=aleph_0^{aleph_0}=mathfrak c$ you are done.
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
2
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
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%2f3004529%2fprove-that-there-exist-2-aleph-0-well-orderings-of-the-set-of-all-natural%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
Given the usual order on $Bbb N$, you can show there are at least $2^{aleph_0}$ because you can break $Bbb N$ into $aleph_0$ pairs $(2n, 2n+1)$. You can then invert each pair or not, which is $aleph_0$ binary choices. There are at most $aleph_0^{aleph_0}$ because there are $aleph_0$ choices for the first element of the well order, and again for the next, and so on. If you know $2^{aleph_0}=aleph_0^{aleph_0}=mathfrak c$ you are done.
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
2
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
add a comment |
Given the usual order on $Bbb N$, you can show there are at least $2^{aleph_0}$ because you can break $Bbb N$ into $aleph_0$ pairs $(2n, 2n+1)$. You can then invert each pair or not, which is $aleph_0$ binary choices. There are at most $aleph_0^{aleph_0}$ because there are $aleph_0$ choices for the first element of the well order, and again for the next, and so on. If you know $2^{aleph_0}=aleph_0^{aleph_0}=mathfrak c$ you are done.
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
2
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
add a comment |
Given the usual order on $Bbb N$, you can show there are at least $2^{aleph_0}$ because you can break $Bbb N$ into $aleph_0$ pairs $(2n, 2n+1)$. You can then invert each pair or not, which is $aleph_0$ binary choices. There are at most $aleph_0^{aleph_0}$ because there are $aleph_0$ choices for the first element of the well order, and again for the next, and so on. If you know $2^{aleph_0}=aleph_0^{aleph_0}=mathfrak c$ you are done.
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
Given the usual order on $Bbb N$, you can show there are at least $2^{aleph_0}$ because you can break $Bbb N$ into $aleph_0$ pairs $(2n, 2n+1)$. You can then invert each pair or not, which is $aleph_0$ binary choices. There are at most $aleph_0^{aleph_0}$ because there are $aleph_0$ choices for the first element of the well order, and again for the next, and so on. If you know $2^{aleph_0}=aleph_0^{aleph_0}=mathfrak c$ you are done.
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
answered Nov 19 '18 at 5:32
Ross Millikan
292k23196371
292k23196371
2
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
add a comment |
2
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
2
2
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
I think your upper bound argument is kind of vague (and might give the misleading impression that the order type is necessarily $omega$). A more simple way is just that the well orders are all subsets of $mathbb Ntimes mathbb N.$
– spaceisdarkgreen
Nov 19 '18 at 5:46
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
@spaceisdarkgreen: good point. When I first read it I thought it claimed the well order was a set of pairs $(a,b)$ where $ain Bbb N$ and $bin Bbb N$ was the position of $a$ in the list, which again claims that the order type is $omega$, but the well order can just be all the pairs $(a,b)$ where $a$ comes before $b$.
– Ross Millikan
Nov 19 '18 at 6:04
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3004529%2fprove-that-there-exist-2-aleph-0-well-orderings-of-the-set-of-all-natural%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
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 '18 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 '18 at 22:18
Any bijection of $mathbb{N}$ can be declared an order isomorphism with another well-order (of type $omega$), e.g.
– Henno Brandsma
Nov 19 '18 at 22:20