8
$\begingroup$

For example, the axiom of pairing says:

Let $a$ be a set.

Let $b$ be a set.

If follows that the set $\{a,b\}$ exists.

This can be used to prove the existence of singletons, for instance, by setting $b := a$ (in the previous statement). Namely, the axiom of pairing implies the following:

Let $a$ be a set.

If follows that the set $\{a\}$ exists.


This got me thinking. What ZFC axiom implies that, for any set $a$, the set $\{a,a\}$ equals the set $\{a\}$? Equivalently, what axiom of ZFC implies that the sets of ZFC don't behave like multisets? (I suspect it's extensionality, but I couldn't argue why. So, if it is extensionality, then I'm gonna need some convincing...)

$\endgroup$
  • 1
    $\begingroup$ $a\in\{a,a\}$; if $b\ne a$ then $b\notin\{a,a\}$. $\endgroup$ – Angina Seng Jul 29 at 10:38
7
$\begingroup$

It is indeed the extensionality axiom that is at play here.

We have

$$\forall x (x \in A \iff x \in B)$$ where $A = \{a,a\}$ and $B=\{a\}$ as for both sets $A$ and $B$, $x$ belongs to one of those set if and only if $x=a$.

Therefore $A=B$ by entensionality.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A bit too terse for me. Can you add more verbiage? $\endgroup$ – étale-cohomology Jul 30 at 3:53
  • $\begingroup$ Can you point to the sentence(s) that is(are) to terse? $\endgroup$ – mathcounterexamples.net Jul 30 at 6:20
  • $\begingroup$ Everything is! You don't even define extensionality. $\endgroup$ – étale-cohomology Jul 30 at 6:22
  • $\begingroup$ But I'll try. You say "We have $\forall x ...$". Why do we have that? Where did it come from? Extensionality? Why? Why $A = \{a,a\}$ and $B = \{a\}$? Is it a hypothesis? You don't say it is. What do you mean "as for both sets $A$ and $B$"? Why "$x$ belongs to one of those sets if and only if $x = a$"? Then you say "Therefore...". Why "therefore"? Why does that follow from the previous part? I cannot see the logical flow of the proof: the hypotheses, the intermediate steps, and the conclusion, and a careful explanation of why each part follows from the previous. $\endgroup$ – étale-cohomology Jul 30 at 6:27
  • $\begingroup$ I won't define extensionality as you just have to look at Wikipedia! $\endgroup$ – mathcounterexamples.net Jul 30 at 6:37
1
$\begingroup$

The axiom of extensionality is the statement:

Axiom of extensionality.
Let $A$ be a set.
Let $B$ be a set.
IF for every set $x$ $($ $x$ is in $A$ $ $ $ $ IFF $ $ $ $ $x$ is in $B$ $)$,
THEN $A$ equals $B$.

We can use this to prove the "no repeated elements" property by setting $A := \{a,a\}$ and $B := \{a\}$ in the axiom of extensionality. So,

Theorem. The set {a,a} equals the set $\{a\}$.
Proof. Since $\{a,a\}$ and $\{a\}$ are sets, they satisfy the hypotheses of the axiom of extensionality. So, they satisfy the conclusion.
This means that the sets $\{a,a\}$ and $\{a\}$ satisfy the implication:

IF for every set $x$ $($ $x$ is in $\{a,a\}$ $ $ $ $ IFF $ $ $ $ $x$ is in $\{a\}$ $)$,
THEN $\{a,a\}$ equals $\{a\}$.

So, if we can prove the antecedent

$(*)$ for every set $x$ $($ $x$ is in $\{a,a\}$ $ $ $ $ IFF $ $ $ $ $x$ is in $\{a\}$ $)$,

then, by modus ponens, it'll follow that

$\{a,a\}$ equals $\{a\}$,

as desired.

We prove $(*)$ by verifying it for every element of $\{a,a\}$ and $\{a\}$.
The key observation is that: $a$ is in $\{a,a\}$ and $a$ is in $\{a\}$.

  1. The 1st element of $\{a,a\}$ is $a$. By the truth table of IFF, it holds that: $a$ is in $\{a,a\}$ $ $ IFF $ $ $a$ is in $\{a\}$.
  2. The 2nd element of $\{a,a\}$ is $a$. By the truth table of IFF, it holds that: $a$ is in $\{a,a\}$ $ $ IFF $ $ $a$ is in $\{a\}$.
  3. The 1st element of $\{a\}$ is $a$. By the truth table of IFF, it holds that: $a$ is in $\{a,a\}$ $ $ IFF $ $ $a$ is in $\{a\}$.
  4. There are no other elements in $\{a,a\}$ or $\{a\}$.

This proves that: for every set $x$ $($ $x$ is in $\{a,a\}$ $ $ $ $ IFF $ $ $ $ $x$ is in $\{a\}$ $)$.

This proves that: $\{a,a\}$ equals $\{a\}$.

A similar argument proves that: $\{a,a,a\}$ equals $\{a\}$, and so on.

To extend this result to every finite number of $a$'s probably requires induction, which probably requires the axiom of infinity.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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