2
$\begingroup$

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?

  • 0
    @user6312: done2011-04-14

3 Answers 3

3

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

  • 0
    @Harvey: In FOL, those two statements are different. Someone asked a question on precisely the equivalence that started this http://math.stackexchange.com/questions/211691/factoring-out-universal-quantifier-in-combination-with-an-implication. In fact, in there it is shown that $(\forall x P(x))\rightarrow Q$ is logically equivalent to $\exists x(P(x)\rightarrow Q)$.2014-01-27
2

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

0

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.

  • 0
    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.2014-01-26