Take the 2-minute tour ×
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.

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

Thank you again!

share|improve this question
    
As stated, this is trivial: $\varnothing\subseteq T$, and $\varnothing$ is transitive. Did you mean $T\subseteq T'$? –  Brian M. Scott Oct 26 '12 at 12:18
    
Yes! I'll fix that! –  17SI.34SA Oct 26 '12 at 12:19
add comment

2 Answers 2

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|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
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$. –  Asaf Karagila Oct 27 '12 at 19:21
1  
No problem at all. –  Asaf Karagila Oct 27 '12 at 19:51
show 2 more comments

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|improve this answer
add comment

Your Answer

 
discard

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.