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?

  • 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 '17 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 '17 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 '18 at 3:10

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$.

| cite | improve this answer | |
  • $\begingroup$ Oh my god, my reading comprehension is the worst. Quite sorry. $\endgroup$ – Noah Schweber Dec 29 '17 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 '17 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 '17 at 3:27
  • $\begingroup$ @KennyLau Thank you for the quick answer and thank you for listing the ordering properties needed! $\endgroup$ – hydrangea Dec 29 '17 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 '17 at 3:30

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.