13
$\begingroup$

This question is about set equality, as it is presented in Chapter 3, Set Theory, Section 1, Fundamentals, of Terence Tao's textbook, Analysis I. However, I think it is prudent to begin earlier (technically, later) in the book, in Appendix A, the basics of mathematical logic, Section 7, Equality. On page 329, he writes,

Equality is a relation linking two objects $x$, $y$ of the same type $T$ (e.g., two integers, or two matrices, or two vectors, etc.). Given two such objects $x$ and $y$, the statement $x = y$ may or may not be true; it depends on the value of $x$ and $y$ and also on how equality is defined for the class of objects under consideration. [...]

How equality is defined depends on the class $T$ of objects under consideration, and to some extent is just a matter of definition. However, for the purposes of logic we require that equality obeys the following four axioms of equality:

  • (Reflexive axiom). Given any object $x$, we have $x = x$.
  • (Symmetry axiom). Given any two objects $x$ and $y$ of the same type, if $x = y$, then $y = x$.
  • (Transitive axiom). Given any three objects $x$, $y$, $z$ of the same type, if $x = y$ and $y = z$, then $x = z$.
  • (Substitution axiom). 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.

Based on the information in this appendix, it appears to me that Tao is developing a theory of objects, where objects may be of different types or classes (in other words, his logic is many-sorted). Returning to Chapter 3, Set Theory, he asserts that sets are a type of object, and that the $\in$ predicate can be used to form a proposition about any pair of objects, where the second object is a set: he writes, on page 34,

We first clarify one point: we consider sets themselves to be a type of object.

Axiom 3.1 (Sets are objects). If $A$ is a set, then $A$ is also an object. In particular, given two sets $A$ and $B$, it is meaningful to ask whether $A$ is also an element of $B$.

[...]

To summarize so far, among all the objects studied in mathematics, some of the objects happen to be sets; and if $x$ is an object and $A$ is a set, then either $x \in A$ is true or $x \in A$ is false.

On page 35, he presents the definition of equality for sets:

Definition 3.1.4 (Equality of sets). Two sets $A$ and $B$ are equal, $A = B$, iff every element of $A$ is an element of $B$ and vice versa. To put it another way, $A = B$ if and only if every element $x$ of $A$ belongs also to $B$, and every element $y$ of $B$ belongs also to $A$.

[...]

One can easily verify that this notion of equality is reflexive, symmetric, and transitive (Exercise 3.1.1). 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 A.7). 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$.

I feel that the statement in Definition 3.1.4 should be considered an axiom, rather than a definition, since the $=$ predicate was already axiomatized in section A.7 as part of his background logic. The exercise to "verify that this notion of equality is reflexive, symmetric, and transitive" could then be understood as a verification that the axiom for equality of sets is consistent with the axioms of equality from section A.7 (is "consistent" the correct word to use here?). Am I correct in thinking that his definition for equality of sets should actually be an axiom? More generally, how should one go about distinguishing whether a statement should be an axiom or a definition?


Added in update: I guess it comes down to whether we are using first-order logic with equality; as stated here, the first possibility is that we assume the axioms listed in the appendix for the $=$ predicate, including the substitution axioms for $\in$ with regards to sets:

  • For all sets $x$ and $y$, if $x = y$, then for all objects $z$, $z\in x$ if and only if $z\in y$.

  • For all objects $x$ and $y$, if $x = y$, then for all sets $z$, $x\in z$ if and only if $y\in z$.

Then we add in the axiom of extensionality for FOL with equality:

  • For all sets $x$ and $y$, if for all objects $z$, $z\in x$ if and only if $z\in y$, then $x = y$.

On the other hand, the second possibility, which appears to be the case in Tao's text (since he asks us to prove that equality of sets obeys the reflexive, symmetric, and transitive axioms), is that we don't axiomatize anything about the $=$ predicate until we get to this point, and then "define" it for sets with the axiom:

  • For all sets $x$ and $y$, $x = y$ if and only if, for all objects $z$, $z\in x$ if and only if $z\in y$.

The axioms of equality in the appendix then serve more as a "checklist" of what we want equality of sets to satisfy; as explained in this answer to another question about Tao's definition of equality,

[...] in set theory, these "axioms" are not the definition of equality. Rather, equality is defined via the formula above: two sets are equal when they consist of identical elements. But when we define equality in this way, there is a natural question: why we are naming this as "equality" at all? This is why we prove "axioms of equality", which we are already used to, to show that the naming "equality" is adequate. And when we prove them, they become theorems of set theory and properties of equality rather than axioms. [...]

Note. While there isn't at this point any assumption about the $=$ relation for objects of other types, he does appear to rely on it existing for his statement of the axiom of pairing on page 36:

[...] if $a$ and $b$ are objects, then there exists a set $\{a, b\}$ whose only elements are $a$ and $b$; i.e., for every object $y$, we have $y \in \{a, b\}$ if and only if $y = a$ or $y = b$ [...]

Also, while he never explicitly states it, I think he probably assumes the axiom of extensionality for FOL without equality:

  • For all objects $x$ and $y$, if $x = y$, then for all sets $z$, $x\in z$ if and only if $y\in z$.
$\endgroup$
  • $\begingroup$ Possibly related, I did not read them: math.stackexchange.com/questions/2124670/… math.stackexchange.com/questions/1948674/equality-definition $\endgroup$ – Carsten S Apr 2 '17 at 23:49
  • 1
    $\begingroup$ As per discussion on your previous post, it seems that Tao assuems three primitive objects: natural numbers, sets and functions. Apaprently, he relies on FOL without equality, and thus he gives defintions of equality for primitive objects... except numbers. $\endgroup$ – Mauro ALLEGRANZA Apr 3 '17 at 6:31
  • $\begingroup$ @MauroALLEGRANZA Good point about natural numbers--my guess is that for the equality predicate for natural numbers, he simply assumes without stating them the axioms of reflexivity, symmetry, and transitivity, as well as the substitution axiom for the successor function $S$: if $a$ and $b$ are natural numbers and $a=b$, then $S(a) = S(b)$. $\endgroup$ – justin Apr 3 '17 at 17:10
  • $\begingroup$ I agree with you... But if the axioms for equality are not part of the "underlying logic", we have to prove also e.g. $a=b \to a+n = b+n$ and so on. $\endgroup$ – Mauro ALLEGRANZA Apr 3 '17 at 17:14
  • $\begingroup$ @MauroALLEGRANZA That's true; in his development of addition, the substitution axioms for addition follow if we assume the substitution axioms for the successor function, because he defines addition in terms of the successor function. $\endgroup$ – justin Apr 3 '17 at 17:37
11
$\begingroup$

A good observation, but note that the $=$ predicate was not axiomatized previously. In fact, Tao explicitly says: "how equality is defined depends on the class $T$ of objects under consideration". The axioms listed in that section describe the behavior of all $=$ predicates, but certainly do not define any of them! It's analogous to the axiom "all positive divisors of $p$ are either $1$ or $p$"; this correctly describes all primes, but does not define a particular prime.

$\endgroup$
  • 1
    $\begingroup$ But surely OP is right in that if "=" is one of the relations in the theory you cannot subsequently define that relation, you must have instead axioms asserting equivalence of formulae containing "=" and formulae involving the objects you require to be equal. $\endgroup$ – Martin Rattigan Apr 2 '17 at 23:40
  • $\begingroup$ @MartinRattigan Generally, formal "theories" do not admit definitions at all; they operate in a fixed language. Certainly in a formal theory we would need axioms for this, but only because all definitions would require axioms. Given that we're apparently allowing definitions, we're working in the metatheory, which permits notational conventions like using the same predicate for several different, non-overlapping meanings (as we have here). $\endgroup$ – Reese Apr 2 '17 at 23:55
  • 1
    $\begingroup$ Interesting. I understand that definitions are part of the metatheory, but I've always assumed that they are "mere typographical conveniences" (to quote PM), introducing new symbols into the metalanguage that translate directly to a strings in the formal theory. I'm not sure how defining old symbols that are already part of the formal theory would work. Would it be possible to give a reference to something that explains this please? $\endgroup$ – Martin Rattigan Apr 3 '17 at 2:26
  • 1
    $\begingroup$ @MartinRattigan I'm not sure I'm articulating myself clearly. "$=$" isn't an "old" symbol, because the earlier axioms didn't really introduce it; they provided a definition of what an $=$ relation can be. The $=$ between sets is an instance of a relation of that sort, in the same way that $47$ is an instance of a prime; we can easily define the notion of being prime before we define the numeral $47$. The fact that the symbol used for set equality is the same as the symbol used previously is just a notational convenience, permitted by the flexibility of the metalanguage. $\endgroup$ – Reese Apr 3 '17 at 2:37
  • $\begingroup$ An axiom wouldn't introduce a symbol, but the axioms in the appendix do use $=$, which in a formal system would mean that it is either a predicate letter of the formal system or has previously been defined as a metasymbol (e.g. Def $t=s$ for $A_1^2(t,s)$ or something similar.) At least that is my understanding and that is also what I meant by an "old" symbol. Given the fact that the first section appears in an appendix Tao may be simply describing a theory with equality rather than intending the statements labelled axioms to be part of the main development - notice they are unlabelled. $\endgroup$ – Martin Rattigan Apr 3 '17 at 3:49
5
$\begingroup$

Some axioms are 'definitional axioms' ... they are axioms and definitions at the same time. So, when the book defines set equality, we could capture that using a definitional axiom, such as: for any sets $x$ and $y$:

$$x = y \leftrightarrow \forall z (z \in x \leftrightarrow z \in y)$$

The fact that $\leftrightarrow$ was used is often indicative of such definitional axioms.

Also: the fact that $=$ was already used as a logical symbol, having the properties of reflexivity, symmetry, transitivity, and indiscernability (what the book calls the Substitution axiom) does not mean that set equality had to obey this: we could have chosen a different symbol specific for 'set equality', and we could have defined it in such a way that in fact it did not have all these properties, had we wanted to. Notice, for example, how we don't use the $=$ symbol for 'cardinality-equality' or 'equinumerosity'. So, to avoid confusion, maybe we should have used a special symbol for 'set-equality' as well.

Indeed, to say that sets are equal when they have the same elements is to have an 'extensional' view on sets, which is different from an 'intensional' view, where sets can have the same elements but still not be the same set. For example, suppose that all and only people whose favorite color is green are people whose middle name start with a 'J'. Then on the extensional view, the set of 'all people whose favorite color is green' equals the set of 'all people whose middle name starts with a 'J'. But on the intensional view, the two sets just happen to have the same members, but are still considered different sets. So we could have defined sets that way, and in that case, the 'has-the-same-members-as' predicate would definitely have needed a symbol other than $=$.

$\endgroup$
4
$\begingroup$

While Tao overloads the equality symbol here to ambiguously mean either the logical equality or set equality (at the sort of sets), he does not equate them. To do that would indeed require an axiom. Instead what he states is if we carefully articulate everything in terms of the membership relation then it would be admissible to add an axiom identifying logical equality at sets with the definition he provided. To put it another way, if he was taking the conflation as an axiom the qualification in the sentence "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$." would have been unnecessary. Instead, if the statement was an axiom it would be inconsistent to have an operation that didn't obey the axiom of substitution. Tao's use of the same symbol for logical equality (at sets) and set equality is only justifiable though, if he does guarantee every definition satisfies all the expressible instances of the axiom of substitution with respect to set equality. This is a metalogical exercise.

While I'm pretty sure it's not important for Tao's purposes, there are differences between axiomatically asserting that these equalities coincide and not asserting that even in the case where the axiom is admissible. I was originally going to just talk about this as an aside, but with your update to the question it's more directly relevant. Tao is working in a first-order logic with equality (at least for the purpose of talking about the "axioms of equality"). Just because our logic has equality doesn't mean we can't take the second option in the link you provided and define an equivalence relation that represents set equality, though you definitely should use a different symbol in that case. This is what Tao is doing. By an abuse of notation, he's using the same symbol. This is justified by having the first option in that link — identifying the logical equality and the defined set theoretic equality — be admissible.

So what's the difference? With a logical notion of equality, the semantics of equality is equality of the interpretations. The Substitution Axiom is not a theorem you can prove (or even state) in first-order logic about any relation. In this sense, logical equality is on par with other logical connectives as talking about an operation on interpretations. For a defined notion of "equality", you are simply introducing a new relation symbol and proving some properties about it. For the Substitution Axiom you must metalogically prove that it holds for all predicates/operations that you can write down.

However, this just says you can't write down anything that distinguishes objects related by this equivalence relation; there could still be things that can distinguish those objects. Semantically, this means the interpretation of this defined "equality" is an equivalence relation that is respected by all the defined predicates and operations, but there could be other functions in the interpretation that don't respect that equivalence relation. For example, I could interpret "sets" as pairs of sets and membership as membership in only the first component of the pair. The condition for the substitution would then, at the semantic level, look like the following for predicates (which get interpreted as subsets): $(x,y)\in P\Leftrightarrow \forall z.(x,z)\in P$. The identifying of logical equality with the defined "equality" would be admissible for the definition of set "equality" Tao provided if there was an interpretation that made the above condition true (and a similar one for operations). Whether such an interpretation exists depends on the predicates, operations, and axioms we assert. Of course, there exist subsets that don't satisfy the above, so if we did assert the axiom identifying the two forms of equality, the above would no longer be a valid interpretation.

Ultimately, in a fixed theory where axiomatically asserting a given equivalence relation coincides with logical equality is admissible we can't tell the difference between whether that equivalence relation is logical equality or not at the level of logic/syntax. I assume Tao isn't concerned with interpretations of the theory he's building up, and he's saying that he'll maintain this admissibility property as he extends the theory. To the extent that you want an explicit formula for equality, the work is the same either way. Either you have the axiom and you must check that the logic is (relatively) consistent, or you have to check admissibility of the axiom which is checking that it would be consistent to add the axiom. The only difference between him working in FOL with or without equality is in the latter case he is obligated to provide an explicit definition of "equality" (if he uses it). Explicitly defining a notion of equality and showing that it is admissible to have it be the (logical) notion of equality for a sort as Tao does is a good bit of logical hygiene which I recommend.

$\endgroup$
  • $\begingroup$ The second part of the substitution axiom shown quantifies over the property P. Can this still be a first order logic? $\endgroup$ – Martin Rattigan Apr 3 '17 at 4:13
  • $\begingroup$ @MartinRattigan As formulated in the excerpt of Tao, it is not a formula in first-order logic which is why it's not provable. You can't prove it if you can't even say it. This is why we know that Tao is either working in a higher-order logic or taking the general equality as a logical notion. In the latter case the Substitution Axiom is part of the definition of what an interpretation is, i.e. an interpretation takes logical equality to a (set-theoretic) equivalence relation satisfying the Substitution Axiom which is now a FOL formula in ZF, say, about subsets and set functions. $\endgroup$ – Derek Elkins Apr 3 '17 at 4:24
  • $\begingroup$ @DerekElkins I was initially asking this as a separate question, but I'll ask it here as a comment: what does it mean--or at least, in this case, what do you mean--when you say that addition of an axiom is "admissible" or "consistent"? The link you included to the Wikipedia page on admissibility discusses it in the context of rules, not axioms. As far as I understand, what Tao proves is that his axiom for equality of sets implies the existing axioms of equality for the sort of sets--is that correct? $\endgroup$ – justin Apr 15 '17 at 15:36
  • $\begingroup$ @justin An axiom is a special case of a rule in general, in particular, an axiom is a rule with no premises. However, you can often internalize the entailment relation with implication so rules can often be presented as axioms. Indeed, in a Hilbert-style presentation the only "rule" is modus ponens and what are rules in, say, natural deduction, become axioms. Unless I'm making a technical distinction, I don't really differentiate between rules and axioms. In this case, the "axiom" can be presented as $\forall x,y.x\sim y \Leftrightarrow x=y$ (call this A) or as a rule ... $\endgroup$ – Derek Elkins Apr 15 '17 at 19:46
  • $\begingroup$ ... $\cfrac{\Gamma,x,y\vdash x\sim y}{\Gamma,x,y\vdash x=y}$. At the most basic level, I just mean the notion of relative consistency. Admissibility certainly implies relative consistency. Call Tao's system T, then T+A is consistent if T is. Checking the "Substitution Axiom" in all expressible instances is the main part of a syntactic proof of this. Semantically, it's clear that Tao intends T to be compatible with a set theory like ZFC and that a model of ZFC would "trivially" give rise ... $\endgroup$ – Derek Elkins Apr 15 '17 at 19:46

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.