# Identity of indiscernibles

It follows from the axioms of identity alone that $x = y \Rightarrow \big((\forall z) x \in z \equiv y \in z\big)$ and $x = y \Rightarrow \big((\forall z) z \in x \equiv z \in y\big)$.

One of the most important axioms of presumably every set theory is the axiom of extensionality: $\big((\forall z) z \in x \equiv z \in y\big) \Rightarrow x = y$.

But what about its reverse: $\big((\forall z) x \in z \equiv y \in z\big) \Rightarrow x = y$? Does this statement have a name among mathematical logicians and/or set theorists, maybe Identity of indiscernibles? In which set theories can it be proved? And in which set theories (or models) does it not hold?

-
For the sake of formal correctness, and for readability, parentheses should be used. –  André Nicolas Apr 14 '11 at 17:14
@user6312: done –  Hans Stricker Apr 14 '11 at 17:22

We can prove it in any set theory with the axiom of extensionality and the axiom of pairing.

Assume $(\forall z) x\in z$ iff $y\in z$.

Given $x$, form the set $\{x,x\} = \{x\}$ by the pairing axiom. Now, set $z = \{x\}$.

We see that $x\in \{x\}$ so we must have $y\in \{x\}$ so that $y= x$.

-
I was too impressed by Leibniz' and the principle's name: it's a triviality (in the context of set theory), isn't it. –  Hans Stricker Apr 14 '11 at 17:29
This proof doesn't really work "for all $z$", which is in the antecedent. You have successfully shown that $\exists z(x\in z \iff y\in z) \implies y=x$ but you did not show that the statement is true for every set $z$. –  chharvey Jan 26 '14 at 6:21
@Harveybars: I don't think you understand what I'm supposed to show. The "for all" is part of the "if", so I'm allowed to assume the hypothesis for every $z$. There is no "for all" in the conclusion of the theorem. –  Jason DeVito Jan 27 '14 at 1:56
@Harveybars: Here's another way of looking at it. It's a theorem of first order logic that for any first order formula with one free variable, $\forall z P(z)\rightarrow \exists z P(z)$ when the domain of discourse is nonempty. So, if you believe I've shown $\exists z(x\in z...$, this can easily be turned into a proof of what you want. –  Jason DeVito Jan 27 '14 at 2:05
@JasonDeVito, yes, you are right, in FOL if $\forall z P(z)$ is true then certainly $\exists z P(z)$ is also true. But this implication is unidirectional. What you just said is that a proof of $\exists z P(z)$ "can easily be turned into a proof of" $\forall z P(z)$. This is simply incorrect. You have proven that for all $x$ and $y$, there exists a set $z$ such that if $x\in z \iff y\in z$ then $x=y$. You have only shown this holds for one particular set $z$, namely $\{x\}$. While your proof is sound, it cannot be used to prove that the fact holds for every set $z$. –  chharvey Jan 27 '14 at 3:59

The statement is trivially true in any reasonable set theory. Given any $x$, let $z$ be the set whose only element is $x$. Then for any $y$, $y\in z$ iff $y=x$.

-

In set theory and logic this rule is called the Identity of Indiscernibles (if two sets "have the same properties"—that is, they are contained within the same sets—then they are equal).

But in real life there are complications, such as those mentioned in the Wikipedia page you referenced...

Consider the collection: $$A=\{x \mid \text{ Lois Lane believes }x\text{ can fly}\}$$ Clearly, $\text{Superman}\in A$ but $\text{Clark Kent}\not\in A$. Thus by the Identity of Indiscernibles, $\text{Superman}\not=\text{Clark Kent}$, which we know to be false. The contradiction arises under the assumption that $A$ is a set. It may just be a proper class. And I don't believe proper classes follow the same rules as sets.

Anyway, under First-Order Logic with equality, the Axiom of Extensionality states that equal sets contain the same exact elements: $$(x=y) \iff \forall a(a\in x \iff a\in y)$$ However, in FOL without equality, rather than taking this fact as an axiom, we can make it a definition. Under this definition of equality, we would make the Axiom of Extensionality state that equal sets, "equal" as defined above, have the same containers: $$(x=y) \iff \forall b(x\in b \iff y\in b)$$ This expands to: $$\forall a(a\in x \iff a\in y) \iff \forall b(x\in b \iff y\in b)$$

The bi-directionality of the statement proves the Identity of Indiscernibles.

-
I think that at some point Lois Lane knew that Clark Kent and Kal El (or Superman) are the same person. –  Asaf Karagila Jan 26 '14 at 14:02
@AsafKaragila lol so I guess what you're implying is that set (or class) membership is time-based... –  chharvey Jan 26 '14 at 16:35
I'm claiming that real life "examples" are trickier than one tries to make them. Also, yes. The real world is temporal, and you just bumped a question from three years ago. –  Asaf Karagila Jan 26 '14 at 21:13