Well ordering and maximal chains in power set
$begingroup$
Let $M$ be a set and "$le$" a well-ordering of $M$. For $x in M$ define:
$$ M_{le x} := { y in M vert y le x } $$
The map
$$ f : M to mathcal{P}(M) , x mapsto M_{le x}$$
is injective and has the following property:
$$ x le y Leftrightarrow f(x) subseteq f(y)$$
Furthermore the set ${ emptyset } cup f(M) cup {M}$ is a maximal chain in $mathcal{P}(M)$ (ordered by "$subseteq$").
My question is: Does every maximal chain in $mathcal{P}(M)$ derive this way? Is there a bijection between the well-orderings of $M$ and the maximal chains in its power set? I was not yet able to proof that.
I would be super glad if this was even provable without the axiom of choice.
This would give a short proof of the well-ordering theorem by Hausdorffs maximal principle. Also, if $(M,le)$ is a partial ordered set and $K$ is a maximal chain in $mathcal{P}(M)$, I think that $f^{-1}(({emptyset} cup f(M) cup {M} ) cap K)$ (where $f$ is now defined via the partial ordering "$le$") is a maximal chain in $M$. So this would give a short proof of the maximal principle via well-ordering theorem. What do you think? I hope there is no obvious mistake...
Edit: Well, there was an obvious mistake and as you pointed out, maximal chains in $mathcal{P}(M)$ really dont need to relate to well-orderings of $M$. My original goal was to characterize the statement "$M$ is well-ordable" to a statement like "the maximal principle applies to $M$", whatever this should mean. I know the proof about maximal elements/chains in the set of partial well-orderings (well-orderings on subsets of $M$) being equivalent to well-orderings of $M$ but this doesnt seem useful to construct a maximal chain in $M$ if $M$ is partial ordered.
order-theory well-orders
asked Dec 22 '18 at 2:13
LucinaLucina
655
$endgroup$
|
show 2 more comments
$begingroup$
Let $M$ be a set and "$le$" a well-ordering of $M$. For $x in M$ define:
$$ M_{le x} := { y in M vert y le x } $$
The map
$$ f : M to mathcal{P}(M) , x mapsto M_{le x}$$
is injective and has the following property:
$$ x le y Leftrightarrow f(x) subseteq f(y)$$
Furthermore the set ${ emptyset } cup f(M) cup {M}$ is a maximal chain in $mathcal{P}(M)$ (ordered by "$subseteq$").
My question is: Does every maximal chain in $mathcal{P}(M)$ derive this way? Is there a bijection between the well-orderings of $M$ and the maximal chains in its power set? I was not yet able to proof that.
I would be super glad if this was even provable without the axiom of choice.
This would give a short proof of the well-ordering theorem by Hausdorffs maximal principle. Also, if $(M,le)$ is a partial ordered set and $K$ is a maximal chain in $mathcal{P}(M)$, I think that $f^{-1}(({emptyset} cup f(M) cup {M} ) cap K)$ (where $f$ is now defined via the partial ordering "$le$") is a maximal chain in $M$. So this would give a short proof of the maximal principle via well-ordering theorem. What do you think? I hope there is no obvious mistake...
Edit: Well, there was an obvious mistake and as you pointed out, maximal chains in $mathcal{P}(M)$ really dont need to relate to well-orderings of $M$. My original goal was to characterize the statement "$M$ is well-ordable" to a statement like "the maximal principle applies to $M$", whatever this should mean. I know the proof about maximal elements/chains in the set of partial well-orderings (well-orderings on subsets of $M$) being equivalent to well-orderings of $M$ but this doesnt seem useful to construct a maximal chain in $M$ if $M$ is partial ordered.
order-theory well-orders
asked Dec 22 '18 at 2:13
LucinaLucina
655
$endgroup$
$begingroup$
As for your claim at the end, why would $f^{-1}(f(M)cap K)$ be maximal? You can find counterexamples to that even when $M$ has just two elements (try it!).
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:26
$begingroup$
Sorry, I wanted to write "$f^{-1}(({ emptyset} cup f(M) cup {M}) cap K)$". It will be corrected in the post.
$endgroup$
– Lucina
Dec 22 '18 at 2:33
$begingroup$
If $M$ is a countably infinite set, then the chains of the sort you describe are countable chains, but there are also uncountable chains in $mathcal P(M)$. For instance, the set of lower Dedekind cuts is an uncountable chain in the power set of the rational numbers.
$endgroup$
– bof
Dec 22 '18 at 2:41
$begingroup$
@Lucina: That doesn't help. The point is that maximality of $K$ in no way guarantees that $f(M)cap K$ is large, since most elements of $f(M)$ could be incomparable to elements of $K$. If you don't see this, I recommend actually thinking through what could happen if $M$ has two elements.
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:45
1
$begingroup$
Are you possibly confusing "well-ordering" with "total ordering?" Because your construction can be done with any total order on $M,$ and any maximal chain on $P(M)$ is a total order on $M.$
$endgroup$
– Thomas Andrews
Dec 22 '18 at 3:14
|
show 2 more comments
$begingroup$
Let $M$ be a set and "$le$" a well-ordering of $M$. For $x in M$ define:
$$ M_{le x} := { y in M vert y le x } $$
The map
$$ f : M to mathcal{P}(M) , x mapsto M_{le x}$$
is injective and has the following property:
$$ x le y Leftrightarrow f(x) subseteq f(y)$$
Furthermore the set ${ emptyset } cup f(M) cup {M}$ is a maximal chain in $mathcal{P}(M)$ (ordered by "$subseteq$").
My question is: Does every maximal chain in $mathcal{P}(M)$ derive this way? Is there a bijection between the well-orderings of $M$ and the maximal chains in its power set? I was not yet able to proof that.
I would be super glad if this was even provable without the axiom of choice.
This would give a short proof of the well-ordering theorem by Hausdorffs maximal principle. Also, if $(M,le)$ is a partial ordered set and $K$ is a maximal chain in $mathcal{P}(M)$, I think that $f^{-1}(({emptyset} cup f(M) cup {M} ) cap K)$ (where $f$ is now defined via the partial ordering "$le$") is a maximal chain in $M$. So this would give a short proof of the maximal principle via well-ordering theorem. What do you think? I hope there is no obvious mistake...
Edit: Well, there was an obvious mistake and as you pointed out, maximal chains in $mathcal{P}(M)$ really dont need to relate to well-orderings of $M$. My original goal was to characterize the statement "$M$ is well-ordable" to a statement like "the maximal principle applies to $M$", whatever this should mean. I know the proof about maximal elements/chains in the set of partial well-orderings (well-orderings on subsets of $M$) being equivalent to well-orderings of $M$ but this doesnt seem useful to construct a maximal chain in $M$ if $M$ is partial ordered.
order-theory well-orders
asked Dec 22 '18 at 2:13
LucinaLucina
655
$endgroup$
Let $M$ be a set and "$le$" a well-ordering of $M$. For $x in M$ define:
$$ M_{le x} := { y in M vert y le x } $$
The map
$$ f : M to mathcal{P}(M) , x mapsto M_{le x}$$
is injective and has the following property:
$$ x le y Leftrightarrow f(x) subseteq f(y)$$
Furthermore the set ${ emptyset } cup f(M) cup {M}$ is a maximal chain in $mathcal{P}(M)$ (ordered by "$subseteq$").
My question is: Does every maximal chain in $mathcal{P}(M)$ derive this way? Is there a bijection between the well-orderings of $M$ and the maximal chains in its power set? I was not yet able to proof that.
I would be super glad if this was even provable without the axiom of choice.
This would give a short proof of the well-ordering theorem by Hausdorffs maximal principle. Also, if $(M,le)$ is a partial ordered set and $K$ is a maximal chain in $mathcal{P}(M)$, I think that $f^{-1}(({emptyset} cup f(M) cup {M} ) cap K)$ (where $f$ is now defined via the partial ordering "$le$") is a maximal chain in $M$. So this would give a short proof of the maximal principle via well-ordering theorem. What do you think? I hope there is no obvious mistake...
Edit: Well, there was an obvious mistake and as you pointed out, maximal chains in $mathcal{P}(M)$ really dont need to relate to well-orderings of $M$. My original goal was to characterize the statement "$M$ is well-ordable" to a statement like "the maximal principle applies to $M$", whatever this should mean. I know the proof about maximal elements/chains in the set of partial well-orderings (well-orderings on subsets of $M$) being equivalent to well-orderings of $M$ but this doesnt seem useful to construct a maximal chain in $M$ if $M$ is partial ordered.
order-theory well-orders
order-theory well-orders
asked Dec 22 '18 at 2:13
LucinaLucina
655
asked Dec 22 '18 at 2:13
LucinaLucina
655
edited Dec 23 '18 at 8:17
Lucina
asked Dec 22 '18 at 2:13
LucinaLucina
655
asked Dec 22 '18 at 2:13
LucinaLucina
655
asked Dec 22 '18 at 2:13
LucinaLucina
655
655
$begingroup$
As for your claim at the end, why would $f^{-1}(f(M)cap K)$ be maximal? You can find counterexamples to that even when $M$ has just two elements (try it!).
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:26
$begingroup$
Sorry, I wanted to write "$f^{-1}(({ emptyset} cup f(M) cup {M}) cap K)$". It will be corrected in the post.
$endgroup$
– Lucina
Dec 22 '18 at 2:33
$begingroup$
If $M$ is a countably infinite set, then the chains of the sort you describe are countable chains, but there are also uncountable chains in $mathcal P(M)$. For instance, the set of lower Dedekind cuts is an uncountable chain in the power set of the rational numbers.
$endgroup$
– bof
Dec 22 '18 at 2:41
$begingroup$
@Lucina: That doesn't help. The point is that maximality of $K$ in no way guarantees that $f(M)cap K$ is large, since most elements of $f(M)$ could be incomparable to elements of $K$. If you don't see this, I recommend actually thinking through what could happen if $M$ has two elements.
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:45
1
$begingroup$
Are you possibly confusing "well-ordering" with "total ordering?" Because your construction can be done with any total order on $M,$ and any maximal chain on $P(M)$ is a total order on $M.$
$endgroup$
– Thomas Andrews
Dec 22 '18 at 3:14
|
show 2 more comments
$begingroup$
As for your claim at the end, why would $f^{-1}(f(M)cap K)$ be maximal? You can find counterexamples to that even when $M$ has just two elements (try it!).
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:26
$begingroup$
Sorry, I wanted to write "$f^{-1}(({ emptyset} cup f(M) cup {M}) cap K)$". It will be corrected in the post.
$endgroup$
– Lucina
Dec 22 '18 at 2:33
$begingroup$
If $M$ is a countably infinite set, then the chains of the sort you describe are countable chains, but there are also uncountable chains in $mathcal P(M)$. For instance, the set of lower Dedekind cuts is an uncountable chain in the power set of the rational numbers.
$endgroup$
– bof
Dec 22 '18 at 2:41
$begingroup$
@Lucina: That doesn't help. The point is that maximality of $K$ in no way guarantees that $f(M)cap K$ is large, since most elements of $f(M)$ could be incomparable to elements of $K$. If you don't see this, I recommend actually thinking through what could happen if $M$ has two elements.
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:45
1
$begingroup$
Are you possibly confusing "well-ordering" with "total ordering?" Because your construction can be done with any total order on $M,$ and any maximal chain on $P(M)$ is a total order on $M.$
$endgroup$
– Thomas Andrews
Dec 22 '18 at 3:14
$begingroup$
As for your claim at the end, why would $f^{-1}(f(M)cap K)$ be maximal? You can find counterexamples to that even when $M$ has just two elements (try it!).
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:26
$begingroup$
As for your claim at the end, why would $f^{-1}(f(M)cap K)$ be maximal? You can find counterexamples to that even when $M$ has just two elements (try it!).
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:26
$begingroup$
Sorry, I wanted to write "$f^{-1}(({ emptyset} cup f(M) cup {M}) cap K)$". It will be corrected in the post.
$endgroup$
– Lucina
Dec 22 '18 at 2:33
$begingroup$
Sorry, I wanted to write "$f^{-1}(({ emptyset} cup f(M) cup {M}) cap K)$". It will be corrected in the post.
$endgroup$
– Lucina
Dec 22 '18 at 2:33
$begingroup$
If $M$ is a countably infinite set, then the chains of the sort you describe are countable chains, but there are also uncountable chains in $mathcal P(M)$. For instance, the set of lower Dedekind cuts is an uncountable chain in the power set of the rational numbers.
$endgroup$
– bof
Dec 22 '18 at 2:41
$begingroup$
If $M$ is a countably infinite set, then the chains of the sort you describe are countable chains, but there are also uncountable chains in $mathcal P(M)$. For instance, the set of lower Dedekind cuts is an uncountable chain in the power set of the rational numbers.
$endgroup$
– bof
Dec 22 '18 at 2:41
$begingroup$
@Lucina: That doesn't help. The point is that maximality of $K$ in no way guarantees that $f(M)cap K$ is large, since most elements of $f(M)$ could be incomparable to elements of $K$. If you don't see this, I recommend actually thinking through what could happen if $M$ has two elements.
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:45
$begingroup$
@Lucina: That doesn't help. The point is that maximality of $K$ in no way guarantees that $f(M)cap K$ is large, since most elements of $f(M)$ could be incomparable to elements of $K$. If you don't see this, I recommend actually thinking through what could happen if $M$ has two elements.
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:45
1
1
$begingroup$
Are you possibly confusing "well-ordering" with "total ordering?" Because your construction can be done with any total order on $M,$ and any maximal chain on $P(M)$ is a total order on $M.$
$endgroup$
– Thomas Andrews
Dec 22 '18 at 3:14
$begingroup$
Are you possibly confusing "well-ordering" with "total ordering?" Because your construction can be done with any total order on $M,$ and any maximal chain on $P(M)$ is a total order on $M.$
$endgroup$
– Thomas Andrews
Dec 22 '18 at 3:14
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
No. Indeed, let $Asubsetmathcal{P}(M)$ be any chain that is not well-ordered (such a chain exists as long as $M$ is infinite; for instance you can just take an infinite descending sequence where you remove one element at a time). By Zorn's lemma, $A$ is contained in some maximal chain $B$ of $mathcal{P}(M)$, which is not well-ordered since it contains $A$. Since all the chains you describe are well-ordered, this $B$ cannot be of that form.
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
$endgroup$
add a comment |
$begingroup$
Your construction works for any total order on $M,$ not just well-orderings.
And given a maximal chain in $P(M),$ you get a total order on $M.$ These are in 1-1 correspondence.
Start of Proof: Let $C$ be a maximal chain in $P(M).$ Then $emptyset, Min C,$ because the chain wouldn't be maximal if they weren't.
If $x,yin M$ we say $xleq_C y$ if and only if $forall Sin C$, if $yin Simplies xin S.$
To prove:
(1) This is a partial order. Reflexivity and transitivity are easy. The only hard part is proving if $xleq y$ and $yleq x,$ you'd have $x=y.$ This is due to the maximality of $C.$
(2) This is a total order.
The ultimate reason for this is that any maximal chain in $P(M)$ is closed under arbitrary unions and intersections. So the union $U_x$ of the elements of $C$ which do not contain $x$ and the intersection $V_x$ of all elements of $C$ which do contain $x$ are both in $C$, and there are no elements of $C$ strictly between $U_x$ and $V_x.$
For (1), this means that if $xleq y$ and $yleq x$ then $yin U_x$ and $ynotin V_x.$ But this means that $U_xcup{y}$ is strictly between $U_x$ and $V_x.$
For (2), this means that for $x.yin M,$ either $U_xsubseteq U_y$ or $U_ysubseteq U_x$, since $U_x,U_yin C$ and $C$ is a chain. But $U_xsubseteq U_y$ means $xleq y$ so either $xleq_C y$ or $yleq_C x.$
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
$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%2f3049065%2fwell-ordering-and-maximal-chains-in-power-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No. Indeed, let $Asubsetmathcal{P}(M)$ be any chain that is not well-ordered (such a chain exists as long as $M$ is infinite; for instance you can just take an infinite descending sequence where you remove one element at a time). By Zorn's lemma, $A$ is contained in some maximal chain $B$ of $mathcal{P}(M)$, which is not well-ordered since it contains $A$. Since all the chains you describe are well-ordered, this $B$ cannot be of that form.
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
$endgroup$
add a comment |
$begingroup$
No. Indeed, let $Asubsetmathcal{P}(M)$ be any chain that is not well-ordered (such a chain exists as long as $M$ is infinite; for instance you can just take an infinite descending sequence where you remove one element at a time). By Zorn's lemma, $A$ is contained in some maximal chain $B$ of $mathcal{P}(M)$, which is not well-ordered since it contains $A$. Since all the chains you describe are well-ordered, this $B$ cannot be of that form.
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
$endgroup$
add a comment |
$begingroup$
No. Indeed, let $Asubsetmathcal{P}(M)$ be any chain that is not well-ordered (such a chain exists as long as $M$ is infinite; for instance you can just take an infinite descending sequence where you remove one element at a time). By Zorn's lemma, $A$ is contained in some maximal chain $B$ of $mathcal{P}(M)$, which is not well-ordered since it contains $A$. Since all the chains you describe are well-ordered, this $B$ cannot be of that form.
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
$endgroup$
No. Indeed, let $Asubsetmathcal{P}(M)$ be any chain that is not well-ordered (such a chain exists as long as $M$ is infinite; for instance you can just take an infinite descending sequence where you remove one element at a time). By Zorn's lemma, $A$ is contained in some maximal chain $B$ of $mathcal{P}(M)$, which is not well-ordered since it contains $A$. Since all the chains you describe are well-ordered, this $B$ cannot be of that form.
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
answered Dec 22 '18 at 2:21
Eric WofseyEric Wofsey
188k14216345
188k14216345
add a comment |
add a comment |
$begingroup$
Your construction works for any total order on $M,$ not just well-orderings.
And given a maximal chain in $P(M),$ you get a total order on $M.$ These are in 1-1 correspondence.
Start of Proof: Let $C$ be a maximal chain in $P(M).$ Then $emptyset, Min C,$ because the chain wouldn't be maximal if they weren't.
If $x,yin M$ we say $xleq_C y$ if and only if $forall Sin C$, if $yin Simplies xin S.$
To prove:
(1) This is a partial order. Reflexivity and transitivity are easy. The only hard part is proving if $xleq y$ and $yleq x,$ you'd have $x=y.$ This is due to the maximality of $C.$
(2) This is a total order.
The ultimate reason for this is that any maximal chain in $P(M)$ is closed under arbitrary unions and intersections. So the union $U_x$ of the elements of $C$ which do not contain $x$ and the intersection $V_x$ of all elements of $C$ which do contain $x$ are both in $C$, and there are no elements of $C$ strictly between $U_x$ and $V_x.$
For (1), this means that if $xleq y$ and $yleq x$ then $yin U_x$ and $ynotin V_x.$ But this means that $U_xcup{y}$ is strictly between $U_x$ and $V_x.$
For (2), this means that for $x.yin M,$ either $U_xsubseteq U_y$ or $U_ysubseteq U_x$, since $U_x,U_yin C$ and $C$ is a chain. But $U_xsubseteq U_y$ means $xleq y$ so either $xleq_C y$ or $yleq_C x.$
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
$endgroup$
add a comment |
$begingroup$
Your construction works for any total order on $M,$ not just well-orderings.
And given a maximal chain in $P(M),$ you get a total order on $M.$ These are in 1-1 correspondence.
Start of Proof: Let $C$ be a maximal chain in $P(M).$ Then $emptyset, Min C,$ because the chain wouldn't be maximal if they weren't.
If $x,yin M$ we say $xleq_C y$ if and only if $forall Sin C$, if $yin Simplies xin S.$
To prove:
(1) This is a partial order. Reflexivity and transitivity are easy. The only hard part is proving if $xleq y$ and $yleq x,$ you'd have $x=y.$ This is due to the maximality of $C.$
(2) This is a total order.
The ultimate reason for this is that any maximal chain in $P(M)$ is closed under arbitrary unions and intersections. So the union $U_x$ of the elements of $C$ which do not contain $x$ and the intersection $V_x$ of all elements of $C$ which do contain $x$ are both in $C$, and there are no elements of $C$ strictly between $U_x$ and $V_x.$
For (1), this means that if $xleq y$ and $yleq x$ then $yin U_x$ and $ynotin V_x.$ But this means that $U_xcup{y}$ is strictly between $U_x$ and $V_x.$
For (2), this means that for $x.yin M,$ either $U_xsubseteq U_y$ or $U_ysubseteq U_x$, since $U_x,U_yin C$ and $C$ is a chain. But $U_xsubseteq U_y$ means $xleq y$ so either $xleq_C y$ or $yleq_C x.$
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
$endgroup$
add a comment |
$begingroup$
Your construction works for any total order on $M,$ not just well-orderings.
And given a maximal chain in $P(M),$ you get a total order on $M.$ These are in 1-1 correspondence.
Start of Proof: Let $C$ be a maximal chain in $P(M).$ Then $emptyset, Min C,$ because the chain wouldn't be maximal if they weren't.
If $x,yin M$ we say $xleq_C y$ if and only if $forall Sin C$, if $yin Simplies xin S.$
To prove:
(1) This is a partial order. Reflexivity and transitivity are easy. The only hard part is proving if $xleq y$ and $yleq x,$ you'd have $x=y.$ This is due to the maximality of $C.$
(2) This is a total order.
The ultimate reason for this is that any maximal chain in $P(M)$ is closed under arbitrary unions and intersections. So the union $U_x$ of the elements of $C$ which do not contain $x$ and the intersection $V_x$ of all elements of $C$ which do contain $x$ are both in $C$, and there are no elements of $C$ strictly between $U_x$ and $V_x.$
For (1), this means that if $xleq y$ and $yleq x$ then $yin U_x$ and $ynotin V_x.$ But this means that $U_xcup{y}$ is strictly between $U_x$ and $V_x.$
For (2), this means that for $x.yin M,$ either $U_xsubseteq U_y$ or $U_ysubseteq U_x$, since $U_x,U_yin C$ and $C$ is a chain. But $U_xsubseteq U_y$ means $xleq y$ so either $xleq_C y$ or $yleq_C x.$
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
$endgroup$
Your construction works for any total order on $M,$ not just well-orderings.
And given a maximal chain in $P(M),$ you get a total order on $M.$ These are in 1-1 correspondence.
Start of Proof: Let $C$ be a maximal chain in $P(M).$ Then $emptyset, Min C,$ because the chain wouldn't be maximal if they weren't.
If $x,yin M$ we say $xleq_C y$ if and only if $forall Sin C$, if $yin Simplies xin S.$
To prove:
(1) This is a partial order. Reflexivity and transitivity are easy. The only hard part is proving if $xleq y$ and $yleq x,$ you'd have $x=y.$ This is due to the maximality of $C.$
(2) This is a total order.
The ultimate reason for this is that any maximal chain in $P(M)$ is closed under arbitrary unions and intersections. So the union $U_x$ of the elements of $C$ which do not contain $x$ and the intersection $V_x$ of all elements of $C$ which do contain $x$ are both in $C$, and there are no elements of $C$ strictly between $U_x$ and $V_x.$
For (1), this means that if $xleq y$ and $yleq x$ then $yin U_x$ and $ynotin V_x.$ But this means that $U_xcup{y}$ is strictly between $U_x$ and $V_x.$
For (2), this means that for $x.yin M,$ either $U_xsubseteq U_y$ or $U_ysubseteq U_x$, since $U_x,U_yin C$ and $C$ is a chain. But $U_xsubseteq U_y$ means $xleq y$ so either $xleq_C y$ or $yleq_C x.$
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
edited Dec 22 '18 at 19:13
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
answered Dec 22 '18 at 3:36
Thomas AndrewsThomas Andrews
130k12146298
130k12146298
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%2f3049065%2fwell-ordering-and-maximal-chains-in-power-set%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$
As for your claim at the end, why would $f^{-1}(f(M)cap K)$ be maximal? You can find counterexamples to that even when $M$ has just two elements (try it!).
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:26
$begingroup$
Sorry, I wanted to write "$f^{-1}(({ emptyset} cup f(M) cup {M}) cap K)$". It will be corrected in the post.
$endgroup$
– Lucina
Dec 22 '18 at 2:33
$begingroup$
If $M$ is a countably infinite set, then the chains of the sort you describe are countable chains, but there are also uncountable chains in $mathcal P(M)$. For instance, the set of lower Dedekind cuts is an uncountable chain in the power set of the rational numbers.
$endgroup$
– bof
Dec 22 '18 at 2:41
$begingroup$
@Lucina: That doesn't help. The point is that maximality of $K$ in no way guarantees that $f(M)cap K$ is large, since most elements of $f(M)$ could be incomparable to elements of $K$. If you don't see this, I recommend actually thinking through what could happen if $M$ has two elements.
$endgroup$
– Eric Wofsey
Dec 22 '18 at 2:45
1
$begingroup$
Are you possibly confusing "well-ordering" with "total ordering?" Because your construction can be done with any total order on $M,$ and any maximal chain on $P(M)$ is a total order on $M.$
$endgroup$
– Thomas Andrews
Dec 22 '18 at 3:14