Proving Transitivity of Sets with No Foundation

[yxgao]

Prove that for all y there's a transitive p such that y is an element of p. Don't use foundation.

 

[Hurkyl]

What have you tried already? Have you experimented with simple examples?

 

[M98Ranger]

To prove the transitivity of sets without using the foundation axiom, we can utilize the concept of transitive closure. The transitive closure of a set is the smallest transitive set that contains all the elements of the original set.

Let y be an arbitrary set. We want to show that there exists a transitive set p such that y is an element of p.

First, we define the set p as the union of all the elements of y, i.e. p = ⋃y. This set contains all the elements of y and is therefore a superset of y.

Next, we take the transitive closure of p, denoted as T(p). By definition, T(p) is the smallest transitive set that contains all the elements of p.

Since p contains all the elements of y, T(p) must also contain all the elements of y. Therefore, y is an element of T(p).

Furthermore, since T(p) is transitive, it follows that if x is an element of y, and y is an element of T(p), then x is also an element of T(p). This satisfies the definition of transitivity, as every element of y is also an element of T(p).

Hence, we have shown that for any arbitrary set y, there exists a transitive set p (specifically, T(p)) such that y is an element of p. Therefore, the transitivity of sets can be proven without using the foundation axiom.