4
$\begingroup$

What would happen if we would use pre-order (there is no weak-antisymmetry, only reflexivity and transitivity) in Kuratowski-Zorn Lemma instead of partial order?

Suppose that we have set P which is preordered and has the property that every chain (i.e. totally ordered subset) has an upper bound in P. Then the set P contains at least one maximal element.

Is this statement true in ZFC? If not, what can we postulate to make it true? I think it can be false, or at least we need to postulate something more (or not?), but I am just missing something and don't see it.

P.S.

I wanted to put tags with combination of words like: Kuratowski Zorn Lemma Pre-order Proset, but it seems that none of them exist and I need to have 300+ reputation to create new ones, thus I only typed (set-theory) :( If someone with bigger reputation could make this topics' tags more precise, I would be grateful :)

$\endgroup$
1
  • 1
    $\begingroup$ As a comment about tagging issues, there has been some discussion on the meta site regarding Zorn's Lemma tag. $\endgroup$
    – Asaf Karagila ♦
    Commented Dec 29, 2013 at 13:10

1 Answer 1

Reset to default
4
$\begingroup$

In $\sf ZFC$ you can do the following trick.

Let $(P,\leq)$ be a preordered set. Define $x\sim y\iff x\leq y\land y\leq x$, clearly an equivalence relation. Now using the axiom of choice choose a representative from each equivalence class. This defines $P'\subseteq P$ which is a partially ordered set.

If $(P,\leq)$ satisfied the Zorn lemma assumptions, so must $(P',\leq)$. Therefore $P'$ has a maximal element, so $P$ has one as well. Where maximal in a preordered set means that there is no strictly larger element.

(As Hagen von Eitzen points out, one can looks at the partial order defined naturally on $P/\sim$, and see that it satisfies Zorn's lemma assumptions, therefore it has a maximal element, which has an equivalence class of maximal elements in $P'$.

We do not resort to using the axiom of choice directly, since we are not choosing from the representatives of each class, but since Zorn's lemma is equivalent to the axiom of choice to begin with, this does not exempt us from using the axiom of choice in its full generality anyway.)

$\endgroup$
6
  • 1
    $\begingroup$ Not that it matters when Zorn is given anyway, but maybe there is "less choice" involved if one considers the partial order on the set of equivalence classes instead of on a set of representatives. $\endgroup$
    – Hagen von Eitzen
    Commented Dec 29, 2013 at 13:19
  • $\begingroup$ True, true. Although it's not quite less choice, but rather less-obvious. $\endgroup$
    – Asaf Karagila ♦
    Commented Dec 29, 2013 at 13:25
  • 1
    $\begingroup$ @bof: If $C$ is a chain of equivalence classes, $\bigcup C$ is a chain in the preorder. Therefore has an upper bound. Its equivalence class is an upper bound of $C$ by definition. $\endgroup$
    – Asaf Karagila ♦
    Commented Dec 29, 2013 at 13:47
  • 4
    $\begingroup$ Or, in the old greedy slogan of choiceless proofs: $$\sf\text{If you can't choose one, take everything!}$$ $\endgroup$
    – Asaf Karagila ♦
    Commented Dec 29, 2013 at 13:49
  • $\begingroup$ @bof: The question was not whether or not the two are equivalent in $\sf ZF$, but rather whether or not they are equivalent in $\sf ZFC$. Hagen didn't claim that there was less choice per se, either. $\endgroup$
    – Asaf Karagila ♦
    Commented Dec 29, 2013 at 13:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .