Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Thank you again!

share|cite|improve this question
up vote 1 down vote accepted

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)$.

share|cite|improve this answer
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? – 17SI.34SA Oct 27 '12 at 18:50
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. – Asaf Karagila Oct 27 '12 at 18:59
Why y∈T_{n+1} and not y∈T_n? Wait! :) – 17SI.34SA Oct 27 '12 at 19:11
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$. – Asaf Karagila Oct 27 '12 at 19:21
No problem at all. – Asaf Karagila Oct 27 '12 at 19:51

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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