Class Transitivity Proof

Question

Prove that a class $T$ is transitive iff $\bigcup_{t \in T},\, t \subseteq T$ iff $a \in t$ whenever $a \in b$ and $b \in T$.

I know that I need to begin by proving the first statement implies the second, the second implies the third, and the third implies the first statement.

I just don't know when to use direct proof (assume $A$ is true, then show $B$ is true) and when to use the contrapositive (Assume $B$ is false, then show $A$ is false).

Any advice would be great.

Answer 1

I'm working with the definition that a set $T$ is transitive if $\forall t\in T(t\subseteq T)$. Recall what $t\subseteq T$ is defined to mean: $\forall s\in t(s\in T)$.

The equivalence with the last statement should be clear.

Now to see the equivalence with the second, recall that $\bigcup_{t\in T}t=\{x:\exists t\in T(x\in t)\}$.

The statement $\bigcup_{t\in T}t\subseteq T$ means that if $t\in T$ and $x\in T$ then $x\in T$, which is equivalent to the last statement.

Answer 2

If I understand your question correctly, you are being asked to prove that the following are equivalent: \begin{align} & \langle \forall t : t \in T : t \subseteq T \rangle \tag{1} \\ & \langle \cup t : t \in T : t \rangle \;\subseteq\; T \tag{2} \\ & \langle \forall a,b : a \in b \land b \in T : a \in T \rangle \tag{3} \\ \end{align}

For $(1)$, expanding the definitions and simplifying gives us \begin{align} & \langle \forall t : t \in T : t \subseteq T \rangle \\ \equiv & \qquad \text{"definition $\;\subseteq\;$"} \\ & \langle \forall t : t \in T : \langle \forall a : a \in t : a \in T \rangle \\ \equiv & \qquad \text{"logic: combine quantifications"} \\ & \langle \forall t, a : t \in T \land a \in t : a \in T \rangle \\ \end{align} which (after renaming and reordening) is exactly $(3)$.

For $(2)$, we do the same: \begin{align} & \langle \cup t : t \in T : t \rangle \;\subseteq\; T \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$"} \\ & \langle \forall a : a \in \langle \cup t : t \in T : t \rangle : a \in T \rangle \\ \equiv & \qquad \text{"definition of $\;\cup\;$-quantification"} \\ & \langle \forall a : \langle \exists t : t \in T : a \in t \rangle : a \in T \rangle \\ \equiv & \qquad \text{"logic: translate $\;\exists\;$ in range to $\;\forall\;$"} \\ & \langle \forall a :: \langle \forall t : t \in T \land a \in t : a \in T \rangle \rangle \\ \end{align} and again we've reached $(3)$.

This proves that all three are equivalent.

Answer 3

As long as you are using classical logic you shouldn't worry too much whether you prove $A\to B$ or $\neg B\to\neg A$ as they are equivalent. Just try one way, and if you get stuck, try the other (of course, you might still get stuck; there are many proofs which are difficult either way). After you finish your proof you can then check if you can get a better (more elegant/informative/...) proof some other way.