3
$\begingroup$

On page $132$ of Fraenkel's Abstract Set Theory ($1961$), Fraenkel writes, concerning the question whether every set can be well-ordered, that

... one can prove without the axiom of choice that, to a given set $S$ and a certain way of reduction, there exists the set $M$ whose members are all possible orders M of $S$ in the way adopted. Yet this result , far-reaching as it is, does not answer the above question whether every set can be ordered, for without the axiom of choice it cannot be proved that $M≠\emptyset$, i.e. that there exists an order $M$.

Can anyone please reference me to a source which proves that for any set $S$ there exists the set $M$ whose members are all possible orders of $S$, or provide the proof?

$\endgroup$
4
  • 1
    $\begingroup$ You do know that set theory has changed a lot since the days of Fraenkel, right? Why are you reading this book? $\endgroup$
    – Asaf Karagila ♦
    Dec 29, 2017 at 6:19
  • $\begingroup$ @AsafKaragila, foundational set-theorists like Fraenkel and Cantor had this totally beautiful, intuitive way of explicating concepts. I consider it a privilege to read set theory in the context of such important and intuitive thinkers as they. $\endgroup$
    – hydrangea
    Dec 29, 2017 at 22:29
  • $\begingroup$ I have just seen your comment and so thought I would ask you. Regarding Fraenkel's book, do you think it wouldn't be good idea to recommend it to a beginner of Set Theory? $\endgroup$
    – user170039
    Nov 9, 2018 at 3:10
  • $\begingroup$ Do we have an example that a set does not have an order? $\endgroup$
    – dodo
    2 days ago

1 Answer 1

Reset to default
8
$\begingroup$

A binary relation $R$ on a set $S$ is nothing more than the set $\{(a,b) \in S^2 \mid aRb\}$. In particular, it is an element of $\mathcal P(S^2)$, i.e. a subset of $S^2$.

Now, $\mathcal P(S^2)$ is a set if $S$ is a set. Then, you need the axiom of subset to come up with the relations that satisfy the ordering properties.

In particular, you want the elements $A$ of $\mathcal P(S^2)$ that satisfies:

$$\forall x,y,z \in S :(x,x) \in A \land [(x,y) \in A \land (y,x) \in A \to x=y] \land \\ [(x,y) \in A \land (y,z) \in A \to (x,z) \in A] \\ [(x,y) \in A \lor (y,x) \in A]$$

Then you will have obtained all the possible orderings on $S$.

$\endgroup$
7
  • $\begingroup$ Oh my god, my reading comprehension is the worst. Quite sorry. $\endgroup$
    – Noah Schweber
    Dec 29, 2017 at 3:24
  • 2
    $\begingroup$ To the OP: let me emphasize an important point in this answer. Generally, while choice often needs to be used to prove that a set with certain properties exists, usually ZF alone (in particular, the axiom scheme variously called separation/specification/subset) is enough to show that the set of all such things exists (it just might be empty). In particular, ZF proves "For every set $X$ of nonempty sets, the set of choice functions on $X$ exists" (although of course it doesn't prove that there is an element of this set). $\endgroup$
    – Noah Schweber
    Dec 29, 2017 at 3:26
  • $\begingroup$ @NoahSchweber OP asked for a proof that the set of all the possible linear orderings of S exists without the axiom of choice. I did exactly that. I don't see the need for more clarification. $\endgroup$
    – Kenny Lau
    Dec 29, 2017 at 3:27
  • $\begingroup$ @KennyLau Thank you for the quick answer and thank you for listing the ordering properties needed! $\endgroup$
    – hydrangea
    Dec 29, 2017 at 3:29
  • 1
    $\begingroup$ Kenny, note that I deleted my initial comment (I misread "subset" as "choice," no idea how I pulled that off). This answer is great and doesn't need to be rewritten at all. My remaining comment above isn't directed at you, but rather to the OP: I think the general theme here is worth stating explicitly and more broadly. $\endgroup$
    – Noah Schweber
    Dec 29, 2017 at 3:30

You must log in to answer this question.

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