0
$\begingroup$

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) = \min\{m \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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bof Aug 4 '18 at 5:27
  • $\begingroup$ @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. $\endgroup$ – K. MacDonald Aug 4 '18 at 16:57
  • $\begingroup$ Answering your own question is perfectly fine. $\endgroup$ – bof Aug 4 '18 at 18:15
  • $\begingroup$ math.meta.stackexchange.com/questions/4680/… $\endgroup$ – bof Aug 4 '18 at 18:20
  • $\begingroup$ Even many quite weak forms of Choice imply that Dedekind-finite = finite, so is there any point in attempting a proof that uses AC? $\endgroup$ – David Hartley Aug 4 '18 at 19:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – K. MacDonald Aug 5 '18 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.