Mixing
Proving that every chain in a Dedekind-finite poset has an upper bound
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I'd like to be able to prove the statement in the title's subordinate clause: if $P$ is a Dedekind-finite partially ordered set and $T subset P$ is totally ordered, then $T$ has an upper bound in $P$. Here's what I've tried, essentially building up the natural numbers inside $T$ using AC using an approach based on this answer, but I'd like to know 1) how to finish up this proof if it can be made to work, 2) if there is a proof that uses a weaker choice axiom, or none at all, and 3) if there is a proof that avoids the natural numbers.
Let $(P, leq)$ be a partially ordered set and $T subset P$ a nonempty, totally ordered subset with no upper bound in $P$. Use AC to define $sigma: T to T$ by choosing some $sigma(t) > t$ for each $t in T$. Choose some $z in T$ and consider the collection of all subsets $S subset T$ satisfying $z in S$, $z leq s$ for all $s in S$, and $sigma(S) subset S$; this collection is nonempty since it contains the set $ s in T: z leq s $. Let $N$ be the intersection of all such subsets $S$. Clearly $N$ is nonempty since it contains $z$, and also $sigma(N) subset N$.
At this point, I'd like to be able to show that $N$ is well-ordered by $leq$ and that $sigma$ acts on $N$ as the successor function, i.e. $sigma(n) = minm in N: m > n $. This would imply that $sigma$ is an injection, proving that $P$ contains a Dedekind-infinite set and is therefore Dedekind-infinite, proving the desired statement by contrapositive.
However, I have no clue how to show that $N$ is well-ordered by $leq$, if in fact it is, and I'd be interested in seeing a proof that doesn't build up this much machinery. It feels there's probably a simple argument I'm not seeing.
set-theory order-theory
asked Aug 4 at 0:30
Kyle MacDonald
1066
 |Â
show 1 more comment
up vote
0
down vote
favorite
I'd like to be able to prove the statement in the title's subordinate clause: if $P$ is a Dedekind-finite partially ordered set and $T subset P$ is totally ordered, then $T$ has an upper bound in $P$. Here's what I've tried, essentially building up the natural numbers inside $T$ using AC using an approach based on this answer, but I'd like to know 1) how to finish up this proof if it can be made to work, 2) if there is a proof that uses a weaker choice axiom, or none at all, and 3) if there is a proof that avoids the natural numbers.
Let $(P, leq)$ be a partially ordered set and $T subset P$ a nonempty, totally ordered subset with no upper bound in $P$. Use AC to define $sigma: T to T$ by choosing some $sigma(t) > t$ for each $t in T$. Choose some $z in T$ and consider the collection of all subsets $S subset T$ satisfying $z in S$, $z leq s$ for all $s in S$, and $sigma(S) subset S$; this collection is nonempty since it contains the set $ s in T: z leq s $. Let $N$ be the intersection of all such subsets $S$. Clearly $N$ is nonempty since it contains $z$, and also $sigma(N) subset N$.
At this point, I'd like to be able to show that $N$ is well-ordered by $leq$ and that $sigma$ acts on $N$ as the successor function, i.e. $sigma(n) = minm in N: m > n $. This would imply that $sigma$ is an injection, proving that $P$ contains a Dedekind-infinite set and is therefore Dedekind-infinite, proving the desired statement by contrapositive.
However, I have no clue how to show that $N$ is well-ordered by $leq$, if in fact it is, and I'd be interested in seeing a proof that doesn't build up this much machinery. It feels there's probably a simple argument I'm not seeing.
set-theory order-theory
asked Aug 4 at 0:30
Kyle MacDonald
1066
Isn't "every chain in a nonempty Dedekind-finite poset has an upper bound" equivalent to "every nonempty Dedekind-finite totally ordered set has a greatest element"? Is there some advantage to stating it in the more general form?
– bof
2 days ago
@bof Yes, you're quite right! I didn't realize that while I was typing it. I've actually found a solution, which is a little less heavy-handed than "take the intersection of everything in the room and hope for the best", but I'm not sure about the etiquette of answering one's own question.
– Kyle MacDonald
2 days ago
Answering your own question is perfectly fine.
– bof
2 days ago
math.meta.stackexchange.com/questions/4680/…
– bof
2 days ago
Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC?
– David Hartley
2 days ago
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'd like to be able to prove the statement in the title's subordinate clause: if $P$ is a Dedekind-finite partially ordered set and $T subset P$ is totally ordered, then $T$ has an upper bound in $P$. Here's what I've tried, essentially building up the natural numbers inside $T$ using AC using an approach based on this answer, but I'd like to know 1) how to finish up this proof if it can be made to work, 2) if there is a proof that uses a weaker choice axiom, or none at all, and 3) if there is a proof that avoids the natural numbers.
Let $(P, leq)$ be a partially ordered set and $T subset P$ a nonempty, totally ordered subset with no upper bound in $P$. Use AC to define $sigma: T to T$ by choosing some $sigma(t) > t$ for each $t in T$. Choose some $z in T$ and consider the collection of all subsets $S subset T$ satisfying $z in S$, $z leq s$ for all $s in S$, and $sigma(S) subset S$; this collection is nonempty since it contains the set $ s in T: z leq s $. Let $N$ be the intersection of all such subsets $S$. Clearly $N$ is nonempty since it contains $z$, and also $sigma(N) subset N$.
At this point, I'd like to be able to show that $N$ is well-ordered by $leq$ and that $sigma$ acts on $N$ as the successor function, i.e. $sigma(n) = minm in N: m > n $. This would imply that $sigma$ is an injection, proving that $P$ contains a Dedekind-infinite set and is therefore Dedekind-infinite, proving the desired statement by contrapositive.
However, I have no clue how to show that $N$ is well-ordered by $leq$, if in fact it is, and I'd be interested in seeing a proof that doesn't build up this much machinery. It feels there's probably a simple argument I'm not seeing.
set-theory order-theory
asked Aug 4 at 0:30
Kyle MacDonald
1066
I'd like to be able to prove the statement in the title's subordinate clause: if $P$ is a Dedekind-finite partially ordered set and $T subset P$ is totally ordered, then $T$ has an upper bound in $P$. Here's what I've tried, essentially building up the natural numbers inside $T$ using AC using an approach based on this answer, but I'd like to know 1) how to finish up this proof if it can be made to work, 2) if there is a proof that uses a weaker choice axiom, or none at all, and 3) if there is a proof that avoids the natural numbers.
Let $(P, leq)$ be a partially ordered set and $T subset P$ a nonempty, totally ordered subset with no upper bound in $P$. Use AC to define $sigma: T to T$ by choosing some $sigma(t) > t$ for each $t in T$. Choose some $z in T$ and consider the collection of all subsets $S subset T$ satisfying $z in S$, $z leq s$ for all $s in S$, and $sigma(S) subset S$; this collection is nonempty since it contains the set $ s in T: z leq s $. Let $N$ be the intersection of all such subsets $S$. Clearly $N$ is nonempty since it contains $z$, and also $sigma(N) subset N$.
At this point, I'd like to be able to show that $N$ is well-ordered by $leq$ and that $sigma$ acts on $N$ as the successor function, i.e. $sigma(n) = minm in N: m > n $. This would imply that $sigma$ is an injection, proving that $P$ contains a Dedekind-infinite set and is therefore Dedekind-infinite, proving the desired statement by contrapositive.
However, I have no clue how to show that $N$ is well-ordered by $leq$, if in fact it is, and I'd be interested in seeing a proof that doesn't build up this much machinery. It feels there's probably a simple argument I'm not seeing.
set-theory order-theory
asked Aug 4 at 0:30
Kyle MacDonald
1066
edited Aug 4 at 0:51
asked Aug 4 at 0:30
Kyle MacDonald
1066
asked Aug 4 at 0:30
Kyle MacDonald
1066
asked Aug 4 at 0:30
Kyle MacDonald
1066
1066
Isn't "every chain in a nonempty Dedekind-finite poset has an upper bound" equivalent to "every nonempty Dedekind-finite totally ordered set has a greatest element"? Is there some advantage to stating it in the more general form?
– bof
2 days ago
@bof Yes, you're quite right! I didn't realize that while I was typing it. I've actually found a solution, which is a little less heavy-handed than "take the intersection of everything in the room and hope for the best", but I'm not sure about the etiquette of answering one's own question.
– Kyle MacDonald
2 days ago
Answering your own question is perfectly fine.
– bof
2 days ago
math.meta.stackexchange.com/questions/4680/…
– bof
2 days ago
Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC?
– David Hartley
2 days ago
 |Â
show 1 more comment
Isn't "every chain in a nonempty Dedekind-finite poset has an upper bound" equivalent to "every nonempty Dedekind-finite totally ordered set has a greatest element"? Is there some advantage to stating it in the more general form?
– bof
2 days ago
@bof Yes, you're quite right! I didn't realize that while I was typing it. I've actually found a solution, which is a little less heavy-handed than "take the intersection of everything in the room and hope for the best", but I'm not sure about the etiquette of answering one's own question.
– Kyle MacDonald
2 days ago
Answering your own question is perfectly fine.
– bof
2 days ago
math.meta.stackexchange.com/questions/4680/…
– bof
2 days ago
Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC?
– David Hartley
2 days ago
Isn't "every chain in a nonempty Dedekind-finite poset has an upper bound" equivalent to "every nonempty Dedekind-finite totally ordered set has a greatest element"? Is there some advantage to stating it in the more general form?
– bof
2 days ago
Isn't "every chain in a nonempty Dedekind-finite poset has an upper bound" equivalent to "every nonempty Dedekind-finite totally ordered set has a greatest element"? Is there some advantage to stating it in the more general form?
– bof
2 days ago
@bof Yes, you're quite right! I didn't realize that while I was typing it. I've actually found a solution, which is a little less heavy-handed than "take the intersection of everything in the room and hope for the best", but I'm not sure about the etiquette of answering one's own question.
– Kyle MacDonald
2 days ago
@bof Yes, you're quite right! I didn't realize that while I was typing it. I've actually found a solution, which is a little less heavy-handed than "take the intersection of everything in the room and hope for the best", but I'm not sure about the etiquette of answering one's own question.
– Kyle MacDonald
2 days ago
Answering your own question is perfectly fine.
– bof
2 days ago
Answering your own question is perfectly fine.
– bof
2 days ago
math.meta.stackexchange.com/questions/4680/…
– bof
2 days ago
math.meta.stackexchange.com/questions/4680/…
– bof
2 days ago
Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC?
– David Hartley
2 days ago
Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC?
– David Hartley
2 days ago
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
1
down vote
As bof observed, your claim is equivalent to, every non-empty totally-ordered Dedekind-finite set has a maximum. But that implies every non-empty subset of such a set also has a maximum and, by reversing the order, a minimum. I.e. every such set is well-ordered and so finite. There are apparently models of ZF with infinite, Dedekind-finite sets of reals and so your claim cannot be proved without some extra assumption.
answered 2 days ago
David Hartley
550138
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
As bof observed, your claim is equivalent to, every non-empty totally-ordered Dedekind-finite set has a maximum. But that implies every non-empty subset of such a set also has a maximum and, by reversing the order, a minimum. I.e. every such set is well-ordered and so finite. There are apparently models of ZF with infinite, Dedekind-finite sets of reals and so your claim cannot be proved without some extra assumption.
answered 2 days ago
David Hartley
550138
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
add a comment |Â
up vote
1
down vote
As bof observed, your claim is equivalent to, every non-empty totally-ordered Dedekind-finite set has a maximum. But that implies every non-empty subset of such a set also has a maximum and, by reversing the order, a minimum. I.e. every such set is well-ordered and so finite. There are apparently models of ZF with infinite, Dedekind-finite sets of reals and so your claim cannot be proved without some extra assumption.
answered 2 days ago
David Hartley
550138
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
As bof observed, your claim is equivalent to, every non-empty totally-ordered Dedekind-finite set has a maximum. But that implies every non-empty subset of such a set also has a maximum and, by reversing the order, a minimum. I.e. every such set is well-ordered and so finite. There are apparently models of ZF with infinite, Dedekind-finite sets of reals and so your claim cannot be proved without some extra assumption.
answered 2 days ago
David Hartley
550138
As bof observed, your claim is equivalent to, every non-empty totally-ordered Dedekind-finite set has a maximum. But that implies every non-empty subset of such a set also has a maximum and, by reversing the order, a minimum. I.e. every such set is well-ordered and so finite. There are apparently models of ZF with infinite, Dedekind-finite sets of reals and so your claim cannot be proved without some extra assumption.
answered 2 days ago
David Hartley
550138
answered 2 days ago
David Hartley
550138
answered 2 days ago
David Hartley
550138
answered 2 days ago
David Hartley
550138
550138
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
add a comment |Â
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
Thanks for pointing that out -- I've got a proof that uses Zorn quite liberally, and will post it for completeness, but it's good to know that something more than ZF really is necessary.
– Kyle MacDonald
2 days ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2871604%2fproving-that-every-chain-in-a-dedekind-finite-poset-has-an-upper-bound%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Isn't "every chain in a nonempty Dedekind-finite poset has an upper bound" equivalent to "every nonempty Dedekind-finite totally ordered set has a greatest element"? Is there some advantage to stating it in the more general form?
– bof
2 days ago
@bof Yes, you're quite right! I didn't realize that while I was typing it. I've actually found a solution, which is a little less heavy-handed than "take the intersection of everything in the room and hope for the best", but I'm not sure about the etiquette of answering one's own question.
– Kyle MacDonald
2 days ago
Answering your own question is perfectly fine.
– bof
2 days ago
math.meta.stackexchange.com/questions/4680/…
– bof
2 days ago
Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC?
– David Hartley
2 days ago