Prove that there exist $2^{aleph_{0}}$ well-orderings of the set of all natural numbers.
up vote
1
down vote
favorite
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
add a comment |
up vote
1
down vote
favorite
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
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 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 at 22:20
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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
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
edited Nov 20 at 4:22
asked Nov 19 at 4:40
Barycentric_Bash
31528
31528
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 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 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 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 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 at 22:20
2
2
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 at 5:34
How would a chapter and exercise number be helpful without the name of the reference?
– spaceisdarkgreen
Nov 19 at 5:34
1
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 at 22:18
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 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 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 at 22:20
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
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.
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 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 at 6:04
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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.
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 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 at 6:04
add a comment |
up vote
2
down vote
accepted
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.
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 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 at 6:04
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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.
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 at 5:32
Ross Millikan
289k23195367
289k23195367
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 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 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 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 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 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 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 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 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 at 5:34
1
Of course there are only $aleph_1$ distinct types of well-orderings on $mathbb{N}$.
– Henno Brandsma
Nov 19 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 at 22:20