Set Theory - the equivalence relation on elements

[Stephen Tashi]

TL;DR Summary

Do standard versions of set theory assume that there exists an equivalence relation defined on elements of sets? Can this relation be defined without referring to the concept of set?

According to https://plato.stanford.edu/entries/zermelo-set-theory/ , Zermelo (translated) said:

Set theory is concerned with a “domain” 𝔅 of individuals, which we shall call simply “objects” and among which are the “sets”. If two symbols, a and b, denote the same object, we write a = b, otherwise a ≠ b.

I don't know if that quote is part of his formal presentation. It does raise the question of whether set theory must formally assume that there exists an equivalence relation on "elements" of set - or whether the equality or inequality of two elements is taken as a primitive notion and not formalized. (If it is formalized, how can this be done without referring to the concept of set?)

 

[yossell]

Standard versions of set theory are usually formulated in a first order logic which includes the predicates '=' and 'is a member of' as basic or primitive, along with the usual first order logical constants (and, not, every).

If pushed to go beyond the formalism, my guess would be that many would say that 'is identical to' and 'is a member of' are primitives of theory. However, there are those who think that 'identical to' can and should be defined -- for instance, by sharing all their properties.

I don't understand the link that you seem to make between identity as primitive and the assumption of an equivalence relation on the elements of the set. Can you explain?

I don't understand the statement 'whether the equality...of two elements is taken as a primitive notion and not formalised.' A notion can be primitive -- incapable of further definition -- and still part of the formalism. For instance, at least one of the quantifiers is usually taken as primitive in a formal system -- but that doesn't mean that it is omitted from the formalism. Of course, some notions can be *defined* -- is that what you meant by 'formalised' here? -- but the chain of definitions eventually terminates and the points of termination are the primitives of the theory.

(Notice that identity is one of those predicates that cannot easily be treated as a set-theoretic relation -- i.e. a set of ordered pairs. For there is no set containing all the ordered pairs of the form <x x> -- I mention this in case you think set-theory should somehow set-theoretically define all its predicates: it can't do that.)

There is the suggestion that identity can be defined in set-theoretic terms. As two sets are identical if they have the same members, some suggest using the axiom of extensionality as a set-theoretic definition of identity:
s1 = s2 iff, for every x (x is in s1 iff x is in s2).

Of course, that definition still uses 'is a member of' and so, in some loose sense, employs the concept of a set. But we would expect the set-theoretician to be using sets in his definitions, wouldn't we? After all, one of the interesting things about set theory is that so much mathematics can be done using just the set-theoretic axioms and primitives.

 

[Stephen Tashi]

Standard versions of set theory are usually formulated in a first order logic which includes the predicates '=' and 'is a member of' as basic or primitive, along with the usual first order logical constants (and, not, every).

Is the transitive property of "=" an assumption in that formalism?

I don't understand the link that you seem to make between identity as primitive and the assumption of an equivalence relation on the elements of the set. Can you explain?

I'm not linking the concepts. I'm thinking of identity-as-primitive being distinct from defining identity as an equivalence relation.

For there is no set containing all the ordered pairs of the form <x x> -- I mention this in case you think set-theory should somehow set-theoretically define all its predicates: it can't do that.)

Is that because the existence of the set of all $(x,x)$ would employ a Universal set, a "set of all elements"?

There is the suggestion that identity can be defined in set-theoretic terms. As two sets are identical if they have the same members, some suggest using the axiom of extensionality as a set-theoretic definition of identity:
s1 = s2 iff, for every x (x is in s1 iff x is in s2).

That's how I think of the definition of "=" for sets, but the quoted remarks by Zermelo seem to use an common language notion of identical to define "=" for sets.For a set $A$, suppose we are given:
$\exists x, x \in A$ and $\exists y, y \notin A$.
How hard is it to prove the obvious $x \ne y$?

 

[yossell]

As with any primitive logical symbol, there will be rules of logic which tell you how the symbol behaves. In the textbook 'An Introduction to Mathematical Logic', Mendelson takes as axioms the reflexivity of identity, and the substitution principle (if x = y, then, (if P(x) the P(y)). Reflexivity and transitivity follow. Substitutivity also allows us to prove what you want to be proved in the last three lines very quickly.

However, I'm afraid I'm not sure what you're getting at -- why you think there might even be a question of whether obvious principles involving identity would be provable in systems of logic in which '=' is a primitive of the system. Whether transitivity is taken as an axiom or follows from other principles (as it does in the system above), it's clear that these should be theorems of a system which contains '=' --- just as 'Fa' should follow from 'everything is F'. Again, I want to say that, just because a predicate isn't definable in a system doesn't imply that the system contains no rules governing the logical behaviour of that predicate.

In Kunen's book on set-theory, the axiom of extensionality appears as an axiom rather than a definition of identity. For most working set-theoreticians, I doubt it makes much of a difference whether extensionality is treated as a posit about sets or a definition of the symbol '='. That kind of question only seems to become relevant when looking at certain conceptual or philosophical questions.

As for Zermelo, it doesn't seem unnatural or wrong to think that identity is a perfectly reasonable primitive concept to use in our logical theories, in no worse standing than the quantifiers and the truth functional connectives. Certainly, if you thought the concept of a set was less basic than the concept of identity, then you might take the axiom of extensionality as helping to clarify the concept of a set.

Incidentally, note that, in set-theories that include urelements (non-sets) (as (I have heard) were originally considered by Zermelo and others at that time (Barwise, Admissible sets and structures, p.9)), then there are distinct things which share the same members (namely -- they both have no members). This may be why he felt he couldn't use extensionality as a definition.

 

[Stephen Tashi]

However, I'm afraid I'm not sure what you're getting at -- why you think there might even be a question of whether obvious principles involving identity would be provable in systems of logic in which '=' is a primitive of the system.

I might not understand the technical definition of "primitive", if it has one!

My question is motivated by doubt that an equivalence relation could be formally defined for "elements" in set theory. The only reason my question occurs is that people are very clever and sometimes accomplish things that seem impossible to me.

I understand that, at its foundations, mathematics must be discussed in a "metalanguage" where there is no attempt to formally define the concepts of the metalanguage. I don't know whether "primitive" refers to a concept only used in the metalanguage or whether a primitive is at some a level above that.

 

[yossell]

My question is motivated by doubt that an equivalence relation could be formally defined for "elements" in set theory.

<mentor edit>
Yes, equivalence relations can be defined in set theory.

An equivalence relation is just a relation that is symmetric, reflexive and transitive. The predicate 'x has the same cardinality as y' (call it xRy) is definable in set-theory in purely set-theoretic terms. The axioms of set-theory allow us to prove that , for every x, xRx; For every x and y, xRy -> yRx; for every x, y and z, xRy & yRz -> xRz. Thus R really does indeed stand for an equivalence relation.

Set theory also allows us to define the predicate 'x is a subset of y and y is a subset of x.' Again, the transitivity, reflexivity and symmetry of this predicate follow from the axioms of set theory. There are many other equivalence relations that can be defined in set-theory.

My guess is that these observations will not satisfy your underlying doubt , but I'm not sure what you're underlying doubt really is.[/Quote]

 

[SSequence]

I haven't read the question and answers in detail, but here is the impression that I get from reading the posts (sorry if the actual question is something else): "is the equality symbol (for sets) 'necessary' for language of set theory?"

I tend to struggle with technical aspects of logic, but as far as I know, I think the answer is no? The way I understand, a lot of the elementary (and advanced) notions (subset,union,intersection etc.) are also the same. In semi-informal writing they serve as a very convenient short-hand, but they aren't "really" necessary in the sense that language of set theory doesn't need them.

Isn't the same true for equality symbol or there are some further important subtleties to it?

 

[yossell]

Subset, Union, intersection, complement are usually defined notions in set theory. A U B is defined as the set which contains precisely the objects which are members of A or (inclusive or!) members of B. 'is a member of' is usually a primitive of the theory.

One way or another, a reasonable set theory must contain notions for intersection, union, subset, etc -- in that sense, these notions are necessary for set theory. But intersection, union and subset can all be *defined* so -- in another sense, they are not necessary for set theory.

Similarly, a reasonable logic will contain 'and, 'or' 'if...then' and 'not' -- but different presentations might include just 'and' and 'not' as undefined, and define the other truth functions in terms of them. Would that mean that 'if...then' is necessary or not necessary?

Any reasonable set-theory will include identity. But one can wonder whether identity should be defined, or is a primitive of the theory.

For my part, I see no problem with leaving it as a primitive -- any more than taking 'for all' as a primitive of the theory. But it is an interesting conceptual question whether, say, extensionality should be treated as a definition of '='. There are interesting questions about whether and how to define identity in general. However, since the axioms of set theory are the same whether this is treated as a definition of identity or as a statement about sets, I can't see the question making any difference to the practice of set-theory.

 

[Stephen Tashi]

Yes, equivalence relations can be defined in set theory.

You are distinguishing between the concept of "identity" and the concept of an equivalence relation. In my OP, I wasn't making such a distinction.

With that vocabulary, I think that we agree that once we have the concept "identity" (specifically for things that are "elements") we can define a concept of equivalence for sets with respect to some set of elements smaller than "all elements". I think we also agree that the concept of "identity" cannot be defined as a set consisting of all pairs $(x,x)$. Such a definition would have the same logical problems as defining a "universal set" that consists of all elements.

If we have a concept of "identity", it is a technical question whether we need to define a different "=" for sets. You wrote:

There is the suggestion that identity can be defined in set-theoretic terms. As two sets are identical if they have the same members, some suggest using the axiom of extensionality as a set-theoretic definition of identity:
s1 = s2 iff, for every x (x is in s1 iff x is in s2).

and

Any reasonable set-theory will include identity. But one can wonder whether identity should be defined, or is a primitive of the theory.

For my part, I see no problem with leaving it as a primitive -- any more than taking 'for all' as a primitive of the theory. But it is an interesting conceptual question whether, say, extensionality should be treated as a definition of '='. There are interesting questions about whether and how to define identity in general. However, since the axioms of set theory are the same whether this is treated as a definition of identity or as a statement about sets, I can't see the question making any difference to the practice of set-theory.

So, I take it that different experts on set theory can have different opinions on this matter.

As with any primitive logical symbol, there will be rules of logic which tell you how the symbol behaves. In the textbook 'An Introduction to Mathematical Logic', Mendelson takes as axioms the reflexivity of identity, and the substitution principle (if x = y, then, (if P(x) the P(y)). Reflexivity and transitivity follow. Substitutivity also allows us to prove what you want to be proved in the last three lines very quickly.

In the fourth edition, p. 95 there is:

(A6) $(\forall x) x = x$ (reflexivity of equality)
(A7) $x = y \implies ( \mathscr{B}(x,x) \implies \mathscr{B}(x,y) )$ (substitutivity of equality)

Is this to be interpreted as metalanguage? For example, does "$\forall x$" refer to all elements of some set? It's interesting that (A7) doesn't bother to associate quantifiers with the symbols $x$,$y$, and $\mathscr{B}$.

As to the concept of "identity", can it be precisely defined in simpler metalanguage?

I don't know whether the study of formal languages is regarded as a proper subfield of Logic. Perhaps those who study formal languages think that the only rigorous way to study Logic is to implement it as a formal language! If I take the view of a formal language, the metalanguage describing it must assume some basic cognitive capabilities on the part of those who read it. For example, they must be able to distingush strings of symbols such as "$x$", "$x + x$", "$x + y$". This involves distinguishing individual symbols, an ordering of the symbols, and which symbols are "the same". The occurrence of two $x$'s in the string "$x + x$" involves distinguishing two things that are different with respect to their position, but the same with respect to which symbol they are.

However, when I think of the concept of "identity", I think of the concept that two different representations of "the same thing" are, in some contexts, completely interchangeable. This concept of "identity" would add semantics to the cognition of $x+x$ as being two occurrences of the same symbol. It would assume the symbol "represents" something.

 

[SSequence]

Perhaps this maybe useful:
Generally speaking, a lot of the symbols $\subseteq$, $\subset$, $\cup$, $\cap$, $\omega$ etc. aren't necessary and aren't formally part of the language. They can be thought of as abbreviations.

One analogy that I think might be useful is thinking of them as a subroutine, just like one would call a function in a prog. language instead of writing the same piece of text (with minor alteration) over and over. This eases things [though I still have a somewhat difficult time wrapping my head around even with the analogy]

Regarding equality, this may be relevant?:
https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory#1._Axiom_of_extensionality

 

[yossell]

You are distinguishing between the concept of "identity" and the concept of an equivalence relation. In my OP, I wasn't making such a distinction.

They are different concepts -- there are equivalence relations that aren't identity -- and you need to tell me which one you want to talk about. I'm now simply unsure whether you want to talk about identity or whether you want to talk about equivalence relations. I believe: (a) it's trivial that set theory can define equivalence relations; (b) it's more contentious whether identity can be defined in set-theoretic terms. But (b) turns into an (interesting) philosophical discussion rather than a mathematical one.

So, I take it that different experts on set theory can have different opinions on this matter.

I don't know. I don't know whether they even have opinions on this kind of thing. You would have to poll the experts on set theory. My point is that, as far as I know, set theory can be done either either by treating extensionality as a definition or as a posit about sets. From the point of view of the theory, proving things, etc, it doesn't much matter. Set theorists can safely avoid the issue.

Yes, A6 and A7 are what I had in mind, though I think I've only got the 3rd edition. Poor me.

It is interesting that he includes quantifiers in the first but not in the second. I'm not sure why. The quantified sentence will follow in his system by the rule of Universal generalisation so I don't think anything turns on it.

For example, does "$\forall x$" refer to all elements of some set?

No -- "$\forall x (x = x)$" is a theorem of set-theory even though there is no universal set. However, the quantifiers of set theory are normally taken to be restricted to the sets -- just don't say there's a set of all sets .

As for (A7) -- it's a little tricky to explain -- the $\mathscr{B}$ is NOT a symbol of set-theory. In this sense, $\mathscr{B}$ can be thought of as a symbol in the metalanguage. (A7) is really a schema - a way of presenting in one line infinitely many axioms. Any sentence of the object language which has the form (A7) -- $\mathscr{B}$ replaced by any arbitrary predicate (complex predicates included) -- is an axiom.

As to the concept of "identity", can it be precisely defined in simpler metalanguage?

Attempts to define identity usually involve notions more complex than found in first order logic. We might want to say a and b are identical iff they share all their properties -- but 'properties' is not a mathematical notion. Alternatively, we might just say that identity just is a relation that satisfies A6 and A7 -- treat A6 and A7 as implicitly defining the notion. One can construct models where A6 and A7 are satisfied but = is not interpreted as identity -- I would say that's a refutation of this view, but not everyone agrees.

 

[Stephen Tashi]

They are different concepts -- there are equivalence relations that aren't identity -- and you need to tell me which one you want to talk about.

I'd be interested talking about either concept, with reference to how it is (or isn't) implemented on the "elements" in set theory.

If "identity" has a technical description, I don't know what it says.

Discussing the equivalence of two things makes sense since two things can be "identical" to each other in some respects but not in others. However, two things can't be "identical" in all respects. If they were, they would only be one thing, not two things.

Symbolic expressions like "x = y" or "x = x", incorporate different things separated by the "=" sign. In one case "x" and "y" are distinct as symbols. In the other case the two "x"'s are in different locations. The semantic interpretation of "x = y" might be that "x" and "y" represent the "same" thing. So I can understand "identity" as referring to the use of "=" with that semantic interpretation. However, that interpretation must remain in the metalanguage because to say that "=" has this interpretation "for all x and y" introduces the need to define a domain for x and y. The domain can't be the universal set if a set theory does not allow a universal set.

If we are thinking about formal languages consisting of finite strings of symbols then we can define the domain of x and y to be the set of possible strings. If we have a notion of substitution, we can define "x=y" to mean that x may be substituted for y in any string to produce a new string that has all the defined properties of the original string ( such as the string being a WFF or being derivable from some other WFF etc.). I don't think this approach to "identity" involves the semantic intepretation that x and y represent the "same" thing.

Yes, A6 and A7 are what I had in mind, though I think I've only got the 3rd edition. Poor me.

Look online!

 

[Stephen Tashi]

Perhaps this maybe useful:
Generally speaking, a lot of the symbols $\subseteq$, $\subset$, $\cup$, $\cap$, $\omega$ etc. aren't necessary and aren't formally part of the language. They can be thought of as abbreviations.

I agree that such symbols are use by people in writing about mathematics with less formality than writing in a formal language.

One analogy that I think might be useful is thinking of them as a subroutine, just like one would call a function in a prog. language instead of writing the same piece of text (with minor alteration) over and over. This eases things [though I still have a somewhat difficult time wrapping my head around even with the analogy]

In that context ( a computer program) , we'd be writing in a formal language, so there would be formal syntax that governed the use of the symbols. There might or might not be formal semantics (e.g. virtual machine) that described what expressions in the language do. I find it difficult to think of $A \subset B$ as a call to a subroutine that does something acoording to given semantic interpretation. However, I can see that a program parsing the string "$A \subset B$" might call a subroutine to handle the symbol "$\subset$".

 

[SSequence]

However, I can see that a program parsing the string "$A \subset B$" might call a subroutine to handle the symbol "$\subset$".

Yeah that's what I had in my mind pretty much. Short-hand for writing longer expressions, which could be parsed mechanically (e.g. by a computer) in principle if needed.

 

[sysprog]

This is a link to a good page with some good links: https://plato.stanford.edu/entries/logic-firstorder-emergence/