Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 3 down vote accepted

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$.

share|improve this answer
    
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 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 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 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 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$.

share|improve this answer

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.

share|improve this answer
    
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 at 14:02
    
@AsafKaragila lol so I guess what you're implying is that set (or class) membership is time-based... –  chharvey Jan 26 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 at 21:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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