1
$\begingroup$

How to show that for every set, $T$ there is a transitive set, $T'$ such that $T\subseteq T'$?

Thank you again!

2 Answers 2

2

First note that $T'=\varnothing$ is transitive and it is a subset of every other set.

The more likely situation is that you are asked to find a transitive $T'$ such that $T\subseteq T'$. Let $T_0=T$ and $T_{n+1}=\{x\mid\exists y\in T_n: x\in y\}$. Now take $T'=\bigcup_{n=0}^\infty T_n$, and show it is transitive.

This $T'$ is called the transitive closure of $T$. Generally speaking if $(X,R)$ is an ordered set we can talk about the transitive closure of $R$, and in the context of sets we simply take the transitive closure of $(T,\in)$.

  • 0
    Asaf, could you show me how you are proving T', as union of T_n is transitive? My attempt: let $x\in T'$, hence exist natural $m$, such that $x\in T_m$, for such $x$ exist $y$, that in $T_{m-1}$. Now what?2012-10-27
  • 0
    Suppose that $x\in T'$ and $y\in x$. Let us see that $y\in T'$. As you say, $x\in T_n$ for some $n$, then by the definition of $T_{n+1}$ we have that $y\in T_{n+1}$ because there is some $x\in T_n$ such that $y\in x$. Therefore $y\in T'$ as wanted.2012-10-27
  • 0
    Why y∈T_{n+1} and not y∈T_n? Wait! :)2012-10-27
  • 0
    But the definition says, exist $y\in T_n$2012-10-27
  • 1
    Yes, but you want to show that if $y\in T'$ then $y\subseteq T'$. Namely, $x\in y$ implies $x\in T'$ as well. Being an element of a set from $T_n$ means to have a rank of $n+1$.2012-10-27
  • 0
    Asaf, thank you very much!2012-10-27
  • 1
    No problem at all.2012-10-27
1

The smallest such set $T'$ is the transitive closure of $T$, which is constructed recursively. Let $T_0=T$, and for $n\in\omega$ let $T_{n+1}=\bigcup T_n$. Then let $T'=\bigcup_{n\in\omega}T_n$; clearly $T\subseteq T'$, and it’s not hard to show that $T'$ is transitive: you’ve thrown in everything that’s needed to make it so.