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
    For the sake of formal correctness, and for readability, parentheses should be used.2011-04-14
  • 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
    I was too impressed by Leibniz' and the principle's name: it's a triviality (in the context of set theory), isn't it.2011-04-14
  • 0
    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$.2014-01-26
  • 0
    @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.2014-01-27
  • 0
    @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.2014-01-27
  • 0
    @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$.2014-01-27
  • 0
    @Harveybars: You're right that my (second) comment is simply false, so let me try to repair the damage. (1) In proving a conditional, you get to assume the "if" part. (2) So, I get to assume "for all z, $x\in z$ iff $y\in z$" is true. I don't have to prove it, I get to assume it. (3) It follows from this assumption that for any particular $z$ I pick, $x\in z$ iff $y \in z$. (4) In particular, if I choose $z = \{x\}$ then $x\in z$ iff $y\in z$. (5) $x\in z$. (6) So therefore $y\in z$ as well. (7) Since $y\in z = \{x\}$, we must have $y = x$.2014-01-27
  • 0
    (continued). Could you clarify exactly which of these steps you object to?2014-01-27
  • 0
    @JasonDeVito I suppose I object to step 4, choosing a particular $z$. In a universal quantifier proof $\forall z P(z)$, you cannot constrain your choice of $z$. Example of an invalid proof using the same process you used: Conjecture: For all $p$, if $p$ is prime, then $p$ is even. Proof: proving a conditional, assume the antecedent, $p$ is a prime number. That is, for any particular $p$ I pick, let $p$ be prime. (step 4 here) In particular, I arbitrarily choose $p=2$, a prime number. Clearly $2$ is also even. Thus for any arbitrary $p$, $p$ is prime implies that $p$ is even.2014-01-27
  • 0
    @Harveybars: I guess based on our previous discussion, I should have guessed which one you'd object to ;-). But I found your counterexample iluminating: the statement I'm trying to prove is *not* of the form $\forall z (P(z)\rightarrow Q(z))$ (which your counterexample is), but rather $(\forall z P(z))\rightarrow Q$. The important distinction here is that the $\forall z$ is bound solely to the "if" part (indeed, the conclusion doesn't even have a $z$ dependence in it). So, I am not assuming I have a particular $z$ that happens to satisfy $x\in z$ iff $y\in z$,2014-01-27
  • 0
    but rather I'm assuming that $\forall z (x\in z $ iff $y\in z)$. I then proceed to show $x =y$, establishing $(\forall z(x\in z$ iff $y\in z))\rightarrow x=y$. I do not claim to establish (nor could I, because it's false), that $\forall z([x\in z$ iff $y\in z]\rightarrow x = y)$, a counterexample begin $z = \{x,y\}$ for any two distinct sets $x$ and $y$.2014-01-27
  • 0
    @JasonDeVito In FOL, is there a difference between the statement $\forall x\forall y[\forall z P(x,y,z)\implies Q(x,y)]$ and the statement $\forall x\forall y\forall z[P(x,y,z)\implies Q(x,y)]$? I wouldn't think so, since $z$ is not a variable in the predicate $Q$, but I could be wrong.2014-01-27
  • 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 think that at some point Lois Lane knew that Clark Kent and Kal El (or Superman) are the same person.2014-01-26
  • 0
    @AsafKaragila lol so I guess what you're implying is that set (or class) membership is time-based...2014-01-26
  • 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