Uncountable well ordered set in $Z^-$ theory.
$begingroup$
I want to build an uncountable well-ordered set within the theory $Z^textbf-$. So, I take $A=omega$ (exists by infinity axiom) and define $$W:={(X,R)inmathcal{P}(A)timesmathcal{P}(Atimes A):langle X,Rrangle text{is a well-ordered set}}$$
With this I consider the set $T:=W/cong$ (where $cong$ is isomorphism relation). Note that $W$ and $T$ are sets by power set axiom. So I define for each equivalence class $[x],[y]in T$ the order
$$
[x]leq_T[y]Leftrightarrow text{type}(x, R_x)leq text{type}(y,R_y)
$$
Here, $R_x$ means the order of $x$ that make it belongs to $[x]$.
So, $T$ is well ordered by $leq_T$ and it is uncountable.
Question: I don't pretty sure if I can build $leq_ T$ without replacement axiom. Another doubt is, Can I take the $R_x$ without AC?
set-theory axiom-of-choice
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
$endgroup$
add a comment |
$begingroup$
I want to build an uncountable well-ordered set within the theory $Z^textbf-$. So, I take $A=omega$ (exists by infinity axiom) and define $$W:={(X,R)inmathcal{P}(A)timesmathcal{P}(Atimes A):langle X,Rrangle text{is a well-ordered set}}$$
With this I consider the set $T:=W/cong$ (where $cong$ is isomorphism relation). Note that $W$ and $T$ are sets by power set axiom. So I define for each equivalence class $[x],[y]in T$ the order
$$
[x]leq_T[y]Leftrightarrow text{type}(x, R_x)leq text{type}(y,R_y)
$$
Here, $R_x$ means the order of $x$ that make it belongs to $[x]$.
So, $T$ is well ordered by $leq_T$ and it is uncountable.
Question: I don't pretty sure if I can build $leq_ T$ without replacement axiom. Another doubt is, Can I take the $R_x$ without AC?
set-theory axiom-of-choice
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
$endgroup$
1
$begingroup$
What is Z$^-$? (ZF without replacement is just "Z.") Also, "$le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here.
$endgroup$
– Noah Schweber
Dec 3 '18 at 23:06
$begingroup$
@NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity.
$endgroup$
– Gödel
Dec 4 '18 at 1:09
$begingroup$
My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $cong$ is
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:45
$begingroup$
Another name for Regularity is Foundation
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:46
add a comment |
$begingroup$
I want to build an uncountable well-ordered set within the theory $Z^textbf-$. So, I take $A=omega$ (exists by infinity axiom) and define $$W:={(X,R)inmathcal{P}(A)timesmathcal{P}(Atimes A):langle X,Rrangle text{is a well-ordered set}}$$
With this I consider the set $T:=W/cong$ (where $cong$ is isomorphism relation). Note that $W$ and $T$ are sets by power set axiom. So I define for each equivalence class $[x],[y]in T$ the order
$$
[x]leq_T[y]Leftrightarrow text{type}(x, R_x)leq text{type}(y,R_y)
$$
Here, $R_x$ means the order of $x$ that make it belongs to $[x]$.
So, $T$ is well ordered by $leq_T$ and it is uncountable.
Question: I don't pretty sure if I can build $leq_ T$ without replacement axiom. Another doubt is, Can I take the $R_x$ without AC?
set-theory axiom-of-choice
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
$endgroup$
I want to build an uncountable well-ordered set within the theory $Z^textbf-$. So, I take $A=omega$ (exists by infinity axiom) and define $$W:={(X,R)inmathcal{P}(A)timesmathcal{P}(Atimes A):langle X,Rrangle text{is a well-ordered set}}$$
With this I consider the set $T:=W/cong$ (where $cong$ is isomorphism relation). Note that $W$ and $T$ are sets by power set axiom. So I define for each equivalence class $[x],[y]in T$ the order
$$
[x]leq_T[y]Leftrightarrow text{type}(x, R_x)leq text{type}(y,R_y)
$$
Here, $R_x$ means the order of $x$ that make it belongs to $[x]$.
So, $T$ is well ordered by $leq_T$ and it is uncountable.
Question: I don't pretty sure if I can build $leq_ T$ without replacement axiom. Another doubt is, Can I take the $R_x$ without AC?
set-theory axiom-of-choice
set-theory axiom-of-choice
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
edited Dec 4 '18 at 2:42
DanielWainfleet
34.7k31648
34.7k31648
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
asked Dec 3 '18 at 22:55
GödelGödel
1,416319
1,416319
1
$begingroup$
What is Z$^-$? (ZF without replacement is just "Z.") Also, "$le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here.
$endgroup$
– Noah Schweber
Dec 3 '18 at 23:06
$begingroup$
@NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity.
$endgroup$
– Gödel
Dec 4 '18 at 1:09
$begingroup$
My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $cong$ is
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:45
$begingroup$
Another name for Regularity is Foundation
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:46
add a comment |
1
$begingroup$
What is Z$^-$? (ZF without replacement is just "Z.") Also, "$le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here.
$endgroup$
– Noah Schweber
Dec 3 '18 at 23:06
$begingroup$
@NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity.
$endgroup$
– Gödel
Dec 4 '18 at 1:09
$begingroup$
My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $cong$ is
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:45
$begingroup$
Another name for Regularity is Foundation
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:46
1
1
$begingroup$
What is Z$^-$? (ZF without replacement is just "Z.") Also, "$le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here.
$endgroup$
– Noah Schweber
Dec 3 '18 at 23:06
$begingroup$
What is Z$^-$? (ZF without replacement is just "Z.") Also, "$le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here.
$endgroup$
– Noah Schweber
Dec 3 '18 at 23:06
$begingroup$
@NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity.
$endgroup$
– Gödel
Dec 4 '18 at 1:09
$begingroup$
@NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity.
$endgroup$
– Gödel
Dec 4 '18 at 1:09
$begingroup$
My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $cong$ is
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:45
$begingroup$
My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $cong$ is
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:45
$begingroup$
Another name for Regularity is Foundation
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:46
$begingroup$
Another name for Regularity is Foundation
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:46
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hartogs' theorem is provable without Replacement. The trick is to note that the isomorphism with ordinals is really unnecessary.
Instead you want to just look at well-orders modulo order isomorphisms. In fact, one can look at ${Xsubseteqmathcal P(A)mid (X,subsetneq)text{ is well-ordered}}/cong$, or in other words, look at the set of chains of subsets of $A$ which are well-ordered by $subseteq$, modulo the order-isomorphism relation.
It is not hard to show that this set is both well-ordered, and does not embed into $A$. So if $A=omega$, the resulting order type is uncountable by definition.
Note that Replacement was never used here. We never mapped each well-order to its order type as a von Neumann ordinal. We just looked at sets of sets of chains of subsets, with a bunch of Separation.
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
1
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
3
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
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%2f3024822%2funcountable-well-ordered-set-in-z-theory%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$
Hartogs' theorem is provable without Replacement. The trick is to note that the isomorphism with ordinals is really unnecessary.
Instead you want to just look at well-orders modulo order isomorphisms. In fact, one can look at ${Xsubseteqmathcal P(A)mid (X,subsetneq)text{ is well-ordered}}/cong$, or in other words, look at the set of chains of subsets of $A$ which are well-ordered by $subseteq$, modulo the order-isomorphism relation.
It is not hard to show that this set is both well-ordered, and does not embed into $A$. So if $A=omega$, the resulting order type is uncountable by definition.
Note that Replacement was never used here. We never mapped each well-order to its order type as a von Neumann ordinal. We just looked at sets of sets of chains of subsets, with a bunch of Separation.
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
1
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
3
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
add a comment |
$begingroup$
Hartogs' theorem is provable without Replacement. The trick is to note that the isomorphism with ordinals is really unnecessary.
Instead you want to just look at well-orders modulo order isomorphisms. In fact, one can look at ${Xsubseteqmathcal P(A)mid (X,subsetneq)text{ is well-ordered}}/cong$, or in other words, look at the set of chains of subsets of $A$ which are well-ordered by $subseteq$, modulo the order-isomorphism relation.
It is not hard to show that this set is both well-ordered, and does not embed into $A$. So if $A=omega$, the resulting order type is uncountable by definition.
Note that Replacement was never used here. We never mapped each well-order to its order type as a von Neumann ordinal. We just looked at sets of sets of chains of subsets, with a bunch of Separation.
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
1
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
3
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
add a comment |
$begingroup$
Hartogs' theorem is provable without Replacement. The trick is to note that the isomorphism with ordinals is really unnecessary.
Instead you want to just look at well-orders modulo order isomorphisms. In fact, one can look at ${Xsubseteqmathcal P(A)mid (X,subsetneq)text{ is well-ordered}}/cong$, or in other words, look at the set of chains of subsets of $A$ which are well-ordered by $subseteq$, modulo the order-isomorphism relation.
It is not hard to show that this set is both well-ordered, and does not embed into $A$. So if $A=omega$, the resulting order type is uncountable by definition.
Note that Replacement was never used here. We never mapped each well-order to its order type as a von Neumann ordinal. We just looked at sets of sets of chains of subsets, with a bunch of Separation.
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
$endgroup$
Hartogs' theorem is provable without Replacement. The trick is to note that the isomorphism with ordinals is really unnecessary.
Instead you want to just look at well-orders modulo order isomorphisms. In fact, one can look at ${Xsubseteqmathcal P(A)mid (X,subsetneq)text{ is well-ordered}}/cong$, or in other words, look at the set of chains of subsets of $A$ which are well-ordered by $subseteq$, modulo the order-isomorphism relation.
It is not hard to show that this set is both well-ordered, and does not embed into $A$. So if $A=omega$, the resulting order type is uncountable by definition.
Note that Replacement was never used here. We never mapped each well-order to its order type as a von Neumann ordinal. We just looked at sets of sets of chains of subsets, with a bunch of Separation.
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
answered Dec 4 '18 at 0:32
Asaf Karagila♦Asaf Karagila
302k32429760
302k32429760
1
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
3
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
add a comment |
1
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
3
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
1
1
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It might also be worth pointing out, that replacement is not needed to construct the ordering of the equivalence classes; since we can take $E_0 le E_1$, iff, for every $ain E_0$, there is some $bin E_1$, with $asubset b$.
$endgroup$
– Not Mike
Dec 4 '18 at 2:08
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
$begingroup$
It is intuitively obvious why the set that you suggest is well-ordered under the order that @NotMike given in his comment but, in my work to prove it, I can't get nothing. Can you give me a hint?
$endgroup$
– Gödel
Dec 4 '18 at 22:49
3
3
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
$begingroup$
@Gödel: Given two well-orders, one is isomorphic to an initial segment of the other.
$endgroup$
– Asaf Karagila♦
Dec 5 '18 at 0:27
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%2f3024822%2funcountable-well-ordered-set-in-z-theory%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
1
$begingroup$
What is Z$^-$? (ZF without replacement is just "Z.") Also, "$le_T$" is the standard symbol for Turing reducibility, so it might be better to use a different symbol here.
$endgroup$
– Noah Schweber
Dec 3 '18 at 23:06
$begingroup$
@NoahSchweber $Z^-$ means, $ZF$ without replacement and regularity.
$endgroup$
– Gödel
Dec 4 '18 at 1:09
$begingroup$
My edit was for a typo in the 1st line ("whitin"). And I wanted to find out what the code for $cong$ is
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:45
$begingroup$
Another name for Regularity is Foundation
$endgroup$
– DanielWainfleet
Dec 4 '18 at 2:46