Is there a characterization of which posets arise as the transitive closure of a set?

108 Views Asked by At

I'm self-studying Kunen's "new" Set Theory and I just got to the transitive closure of a set. This is (somewhat abusively) defined as the sets below $x$ in the transitive closure of $\in$. The example given (shown below) is a lattice, and this got me wondering if $\text{trcl}(\{x\})$ is always a lattice with top element $x$ and bottom element $\emptyset$.

I have convinced myself that this probably isn't the case1, but it did get me wondering if there is a characterization of which posets can arise as $\text{trcl}(x)$. I suspect that is too complicated a question, so I would be happy for partial results. I suspect there are lots of posets and lattices which we know can be embedded into $\text{trcl}(x)$ for some $x$, for instance.


Here is the lattice

\text{trcl}({(1,2)})

  1. Say $x \cap y = \emptyset$, and $z \neq \{x,y\}$. Then if $\{x,y\}$ and $\{x,y,z\}$ are both in the transitive closure of some set, $x$ and $y$ might not have a well defined join

Thanks in advance ^_^

2

There are 2 best solutions below

1
On BEST ANSWER

Belatedly expanding on my comment above:

We can show by a variation of the proof of Mostowski's collapse lemma the following:

If $P$ is a well-founded partial order then there is some set $X$ such that the membership relation restricted to elements of $X$ is isomorphic to $P$.

In particular, this means that every well-founded partial order embeds into $trcl(\{x\})$ for some $x$.

Suppose $P$ is well-founded. Mostowski would have us consider the map $\rho$ defined recursively by $\rho(p)=\{\rho(q): q<_Pp\}$. This recursive definition makes sense because $P$ is well-founded. However, it doesn't behave well in this context since $P$ may not be extensional: $\rho$ will not in general be injective.

Instead we have to fold in some additional "labelling." Fix some bijection $b:P\rightarrow A$. We define the map $\rho^b$ recursively by $$\rho^b(p)=\{\rho^b(q): q<_Pp\}\cup\{b(p)\}.$$ The map $\rho^b$ is clearly injective, and we have $$p<_Pq\leftrightarrow \rho^b(p)\in \rho^b(q).$$ So we just need to check that we don't have any unwanted elementhood-nesses. Of course we might if we pick the labelling function $b$ poorly. So we have to go back and be more careful about our $b$: we want a set $A$ which is "totally unrelated" to $P$ so that no annoyances will crop up. One choice which will work is to take an $A$ whose elements are each cardinals greater than $\vert P\vert$; the point then is that the elements of $A$ are so big that we can't "accidentally" build one of them via the recursive construction of $\rho^b$.

2
On

Here's a partial answer: To see an example where $\text{trcl}(\{x\})$ is not a lattice, consider

enter image description here

Then $2$ and $\{1\}$ have no meet, because their upper bounds do not have a least element.