This question comes from the first chapter of Robert Stoll's book, and it asks:

For each positive integer $n$, give an example of a set $A_n$ of $n$ elements such that for each pair of elements of $A_n$, one member is an element of the other.

I was able to solve for the case where, for a pair $a,b \in A$ we have $a \in b$ without necessarily having $b \in a$.

It is only when I tried to make both membership relations be true that I ran into some doubts. In particular, my solution was to define the $n$ elements in this way:

$$ S_0 = \{S_1, S_2, ..., S_n\} $$ $$ S_1 = \{S_0, S_2, ..., S_n\} $$ $$ S_2 = \{S_0, S_1, S_3, ..., S_n\} $$

and so on, and then define

$$ A_n = \{m_1, m_2, ..., m_n\}. $$

But I am uncertain on whether or not this is allowed, mostly because I am unfamiliar with rigorous, axiomatic set theories, but also because I know that, when we're dealing with infinities such as defined above, we often get counter intuitive results which are hard to see at first glance. In order to check, I tried to disprove this by deriving either a contradiction or an absurdity from this definition, but couldn't.

So my question is: is this allowed? If not, could you explain why not? Would this lead to either a contradiction or an absurdity?


Your particular proposal is indeed disallowed by standard set theory: since every two elements of your $A_n$ contain each other both ways, $A_n$ would violate the Axiom of Regularity.

This follows necessarily from your interpretation of the task as wanting inclusion both ways, but I'm very sure that it is only meant to require that for every $a,b\in A_n$ it holds that there is one of $a$ and $b$ that is an element of the other -- in other words, either $a\in b$ or $b\in a$ must hold.

This naturally leads to a solution based on successively defining $$ A_n = \{A_0, A_1, \ldots, A_{n-1}\}$$ which happens to produce the most popular representation of the natural numbers themselves within pure set theory: the (finite) Von Neumann ordinals.

  • $\begingroup$ This was indeed my solution for the "or" interpretation. I was confused by the wording of the question, specially because I'm not a native English speaker, which led me to try the second solution. Thank you very much! $\endgroup$ – Danks C. Mar 30 '18 at 0:18

This is not allowed, in fact. If we had $a\in b\in a,$ the set $c=\{a,b\}$ would violate the axiom of regularity. The axiom of regularity says that any set has an element disjoint from itself, but $b\in a \cap c$ and $a\in b\cap c$ contradiction.

  • $\begingroup$ Thank you, I appreciate your answer! The reason I chose @Henning Makholm's answer is because it expands a little further. $\endgroup$ – Danks C. Mar 30 '18 at 0:19

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.