3
$\begingroup$

In set theory, we come across the definition of an ordinal as a well-ordered transitive set. And then we show that $\omega$ and all its elements are ordinals.

My question whether there are finite transitive sets which are not ordinals. Also, whether we know all the finite transitive sets.

$\endgroup$
  • 1
    $\begingroup$ An answer mentions the hereditarily finite sets. It may perhaps be useful to add that these are precisely the elements of $V_\omega=\bigcup_{n\in\mathbb N}V_n$ where $V_0=\emptyset$ and $V_{n+1}=\mathcal P(V_n)$ for all $n$. $\endgroup$ – Andrés E. Caicedo Oct 11 '15 at 12:27
  • 1
    $\begingroup$ There has been some recent attention given to (combinatorial and graph theoretic properties of) these sets. Note, for instance, that $V_\omega=\bigcup_n A_n$, where $A_0=\{\emptyset\}$, and $A_{n+1}=\{\emptyset\}\cup\{x\cup\{y\}\mid x,y\in A_n\}$. If you let $a_n=|A_n|$, the sequence $a_0,a_1,a_2,\dots$ is $1,2,4,12,112,11680,\dots$ You can find some work on it and related references in Enumeration of the adjunctive hierarchy of hereditarily finite sets, by Audrito, Tomescu, and Wagner, J Logic Computation (2015) 25 (3): 943-963. $\endgroup$ – Andrés E. Caicedo Oct 11 '15 at 12:40
4
$\begingroup$

Yes, there are finite transitive sets which are not ordinals. For example, take $X = \{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}\}$.

You can check quickly that $X$ is transitive, but it is not an ordinal, since it is not linearly ordered under $\in$. We have $\emptyset\not\in \{\{\emptyset\}\}$ and $\{\{\emptyset\}\}\not\in\emptyset$. Of course, the only ordinal of size $3$ is $3 = \{0,1,2\} = \{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}$.

As for your second question, every set has a transitive closure, and the transitive closure of $X$ is finite if and only if $X$ is hereditarily finite. So the finite transitive sets are exactly the transitive closures of hereditarily finite sets. I don't think you're going to find a more concrete characterization than that, unfortunately.

$\endgroup$
  • $\begingroup$ However, come to think of it, other characterizations might be very interesting. It seems combinatorists haven't paid them much attention but perhaps they should. $\endgroup$ – BrianO Oct 11 '15 at 6:08
  • 1
    $\begingroup$ @BrianO See OEIS sequence A001192. $\endgroup$ – bof Oct 11 '15 at 6:21
  • $\begingroup$ @bof - Thanks, I was ignorant. $\endgroup$ – BrianO Oct 11 '15 at 6:25
  • 1
    $\begingroup$ Anent the last sentence of the question, "whether we know all the finite transitive sets." Yes, in the sense that they are in one-to-one correspondence with the finite extensional acyclic digraphs, i.e., the finite acyclic digraphs with the property that distinct vertices have distinct out-neighborhoods. $\endgroup$ – bof Oct 11 '15 at 6:45

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.