1
$\begingroup$

I am trying to self-learn set theory from Analysis 1 by Terence Tao. I am facing a problem understanding how he shows the relation $\in$ for sets follows the axiom of substitution.

He begins by informally defining sets and the $\in$ relation. He then states the axiom: all sets are objects. Instead of stating the axiom of extension, he defines what it means for two sets to be equal.

(Definition 3.1.4.) Two sets $A$ and $B$ are equal iff every element of $A$ is an element of $B$ and vice versa.

He then leaves proving the fact that equality of sets is reflexive, symmetric and transitive to the reader. This is what he says next:

Observe that if $x \in A$ and $A=B$, then $x \in B$, by Definition 3.1.4. Thus the “is an element of” relation $\in$ obeys the axiom of substitution (see Section A7). Because of this, any new operation we define on sets will also obey the axiom of substitution, as long as we can define that operation purely in terms of the relation $\in$.

What I don't understand is how does $x \in A$ and $A=B$, then $x \in B$ show that the relation $\in$ obeys the axiom of substitution? To me it seems like the argument implies that the relation of equality obeys the axiom of substitution instead. What am I missing here?

$\endgroup$
4
$\begingroup$

See page 330 :

(Substitution axiom [for equality]). Given any two objects $x$ and $y$ of the same type, if $x = y$, then $f(x) = f(y)$ for all functions or operations $f$.

Similarly, for any property $P(x)$ depending on $x$, if $x = y$, then $P(x)$ and $P(y)$ are equivalent statements.

We have to consider the part regarding "properties" and consider as $P(x)$ the formula $z \in x$.

The susbtitution axiom manages the interrelations of the equality predicate with the other functions and predicates of the language.

In set theory we hav only one "basic" predicate : $\in$.

Thus, the substituion axiom "applied" to set theory will be :

if $A=B$, then $z \in A$ is equivalent to $z \in B$,

and this is exactly what Definition 3.1.4. asserts.

Thus, Tao's conclusion is : provided the equality axioms, that define the basic property of what we intuitively count as the equality relation, the specific set theoretic definition of $=$ is a "good" definition, because it satisfies the axioms.


We can see how the "machinery" works for

any new operation we define on sets,

like e.g. $A \cup B$.

The union is defined such that $(z \in A \cup B) \leftrightarrow (z \in A \lor z \in B)$.

The corresponding substitution instance will be :

if $x=y$, then $z \in x \cup B \text { iff } z \in y \cup B$.

We have : $(z \in x \cup B) \text { iff } (z \in x) \lor (z \in B)$, by definition.

And : $(z \in x) \lor (z \in B) \text { iff } (z \in y) \lor (z \in B)$, by the substitution instance of $=$ in set theory and propositional logic.

Finally, the last holds iff $(z \in y \cup B)$.

Thus, we have :

$(z \in x \cup B) \text { iff } (z \in y \cup B)$

and this, by Def.3.1.4. is exactly : $x \cup B = y \cup B$.

Conclusion :

if $x=y$, then $x \cup B = y \cup B$.


Having said that, the above "machinery" is a little bit boring: thus is the reason why usually axiomatized set theory is treated assuming as "underlying logic" first order logic with equality.

See e.g. The axioms of [$\mathsf { ZFC}$ ] set theory :

$\mathsf { ZFC}$ is an axiom system formulated in first-order logic with equality and with only one binary relation symbol $\in$ for membership.

$\endgroup$
5
  • $\begingroup$ Thank you for answering. As I mentioned in my question to me it seems that Tao's argument implied that the notion equality of sets follows the axiom substitution. I am confused regarding the statement that " Thus the “is an element of” relation obeys the axiom of substitution (see Section A7). Because of this, any new operation we define on sets will also obey the axiom of substitution, as long as we can define that operation purely in terms of the relation $\in$". $\endgroup$
    – HDatta
    Apr 23 '18 at 13:46
  • $\begingroup$ @HDatta - having verified that $=$ defined with $\in$ only is a "good" def, the verification that $=$ is "good" also for every set-theoretic operation is a straightforward induction proof. $\endgroup$ Apr 23 '18 at 13:49
  • $\begingroup$ I still am not convinced that proving $=$ is "good" for any set theoretic operation proves that $\in$ is also good. $\endgroup$
    – HDatta
    Apr 23 '18 at 13:57
  • $\begingroup$ @HDatta - is the other way: we have proved that the set theoretic def of $=$ in terms of $\in$ is "good". Then, trivially, this allows us to prove that the def of $=$ works correctly for every new operations defines set.theoretically. $\endgroup$ Apr 23 '18 at 14:06
  • $\begingroup$ I see the flaw in my understanding of the axiom of substitution. The newly added example helped a lot as well. Anyways thank you. $\endgroup$
    – HDatta
    Apr 23 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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