Given a set $S$, I want to find a total antisymmetric relation $R$ on $S$:

$\forall i,j\in S$ either $iRj$ or $jRi$ or both.

In the case both, we have $i=j$, therefore any two distinct elements of $S$ have a fixed direction.

The Axiom of Choice/Well-Ordering Principle can work it out. But this is so muck weaker than AC/WO. So I am wondering if this is gonna work in ZF-system.


closed as off-topic by Namaste, Claude Leibovici, mechanodroid, Robert Z, user223391 Nov 15 '17 at 20:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Claude Leibovici, mechanodroid, Robert Z, Community
If this question can be reworded to fit the rules in the help center, please edit the question.


This would imply a statement which is probably close in strength to the full Axiom of Choice. That would be what we think of informally as the "choice of one sock from each pair in an infinite drawer": given a collection of sets $\{ A_\lambda : \lambda \in \Lambda \}$ such that $|A_\lambda| = 2$ for each $\lambda$, then by the assumption that your statement is true, find a total antisymmetric relation on $\bigcup_{\lambda \in \Lambda} A_\lambda$. Then, for each $\lambda$, we can choose the element of $A_\lambda$ which is smaller than the other in this order, and thus construct a choice function for $(A_\lambda)_{\lambda \in \Lambda}$.

Actually, a very similar argument will work in the more general case that each $A_\lambda$ is a finite set, if you strengthen the statement to assert the existence of a total order on every set (i.e. a partial order which also satisfies the given condition of being total antisymmetric).

  • $\begingroup$ The "infinite socks" principle is Form 88 in Howard and Rubin, and if I am using their database at consequences.emich.edu/conseq.htm correctly, they assert it is not provable in ZF. As such this would also imply that OP's principle is also not provable in ZF. $\endgroup$ – Nate Eldredge Nov 14 '17 at 23:12
  • $\begingroup$ @NateEldredge Oh, I was thinking of the case where $R$ was a total order (i.e. also transitive) instead of just a "total antisymmetric relation". I'll edit that side comment accordingly. $\endgroup$ – Daniel Schepler Nov 14 '17 at 23:17
  • 1
    $\begingroup$ In fact, OP's principle is equivalent to form 88, isn't it? A choice function on the set of all two-element subsets of $S$ would induce a total antisymmetric relation on $S$. $\endgroup$ – Nate Eldredge Nov 14 '17 at 23:18
  • $\begingroup$ H&R assert that form 88 does not imply AC. In fact, your "finite set" comment is form 62 (every set of finite sets has a choice function) and H&R assert that 88 does not imply 62. $\endgroup$ – Nate Eldredge Nov 14 '17 at 23:19
  • 2
    $\begingroup$ Choosing socks is quite weak. Linearly ordering every set is quite weak. No, this is not close to choice in any reasonable sense of the word "close", at least when you look at this from up close. :) $\endgroup$ – Asaf Karagila Nov 14 '17 at 23:24

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