Proving Uniqueness of a Set: A Logical Approach

[evinda]

Hey again! (Blush)

I want to show that the set $\{ a, b \}$ is unique.That's what I have tried:

We suppose that $\{a,b\}, \ \{a,b \}'$ are sets, so that each of them has as elements $a$ and $b$ and only these ,and $\{a,b \} \neq \{a,b \}'$.

From the axiom of extensionality, there is, without loss of generality, a $x$, such that:

$$x \in \{a,b \} \text{ and } x \notin \{a,b \}'$$

But.. how can I continue? (Thinking)

 

[Deveno]

Consider the two cases:

$x = a$
$x = b$

 

[Evgeny.Makarov]

In general, every set $A$ satisfying $\forall x\;(x\in A\leftrightarrow P(x))$ is unique. Indeed, suppose that $A$ and $A'$ satisfy this property. Then for all $x$,
\[
x\in A\leftrightarrow P(x)\leftrightarrow x\in A'
\]
so by axiom of extensionality $A=A'$.

In this case, we are given $a$ and $b$ and $P(x)$ is $x=a\lor x=b$.

 

[evinda]

In general, every set $A$ satisfying $\forall x\;(x\in A\leftrightarrow P(x))$ is unique. Indeed, suppose that $A$ and $A'$ satisfy this property. Then for all $x$,
\[
x\in A\leftrightarrow P(x)\leftrightarrow x\in A'
\]
so by axiom of extensionality $A=A'$.

In this case, we are given $a$ and $b$ and $P(x)$ is $x=a\lor x=b$.

I understand.. (Nod) So, could I justify it like that?
Or should I consider firstly that the sets are not equal and find a contradiction, formulating it like that?

Suppose that $A$ and $A'$ satisfy the property $\forall x\;(x\in A\leftrightarrow x=a \lor x=b)$.

$A \neq A'$, so from the axiom of extensionality, $\exists x$, such that:

$$x \in A \text{ and } x \notin A'$$

But, since both sets satisfy the property:

$$x\in A\leftrightarrow x=a \lor x=b \leftrightarrow x\in A' \text{ that is a contadiction.}$$

So, the set $\{a,b \}$ is unique.

 

[Evgeny.Makarov]

So, could I justify it like that?

I hope so! :)

Or should I consider firstly that the sets are not equal and find a contradiction, formulating it like that?

Suppose that $A$ and $A'$ satisfy the property $\forall x\;(x\in A\leftrightarrow x=a \lor x=b)$.

Just a bit of nitpicking: the property you wrote does not mention $A'$, only $A$. You could say, "Suppose that $A$ and $A'$ satisfy the property $P(X)$ where $P(X)$ is $\forall x\;(x\in X\leftrightarrow x=a \lor x=b)$". Or just say explicitly: Suppose that
\begin{align}
&\forall x\;(x\in A\leftrightarrow x=a \lor x=b)\\
&\forall x\;(x\in A'\leftrightarrow x=a \lor x=b).
\end{align}

$A \neq A'$, so

The status of this claim — $A \neq A'$ — is unclear. Is it given? Are you proving it? Is it an assumption towards contradiction? The correct way is to say, "Assume (towards contradiction) that $A \neq A'$".

from the axiom of extensionality, $\exists x$, such that:

$$x \in A \text{ and } x \notin A'$$

But, since both sets satisfy the property:

$$x\in A\leftrightarrow x=a \lor x=b \leftrightarrow x\in A' \text{ that is a contadiction.}$$

You could do this, but I believe reasoning by contradiction is superfluous here and can be reduced to a direct proof. In fact, every direct proof can be framed as a proof by contradiction. Suppose we want to prove $S$ using the axiom $R\to S$. A direct proof would establish $R$ and then use the axiom. But it is also possible to say: Assume that $\neg S$ is true. Then the (contraposition of the) axiom implies $\neg R$. But we can prove $R$, which makes a contradiction; therefore, $\neg S$ was false and $S$ is true. But if we could indeed prove $R$, why was it necessary to assume $\neg S$? It is more direct to use the axiom.

In the case of the proof about pairs, let $P(x)$ be $x\in A\leftrightarrow x\in A'$. The axiom of extensionality says
\[
\forall x\;P(x)\to A=A'\qquad(*)
\]
which is $R\to S$ in the previous description. You need to show $A=A'$ so you assume towards contradiction that $A\ne A'$. Then (*) implies $\neg\forall x\;P(x)$, i.e., $\exists x\;\neg P(x)$. Take an $x_0$ such that $\neg P(x_0)$. But then you use the fact that $\forall x\;P(x)$ holds and instantiate $x$ with $x_0$ to get $P(x_0)$. This creates a contradiction with $\neg P(x_0)$, so the assumption $A\ne A'$ is false. But if you are using $\forall x\;P(x)$, why not combine it with (*) for a direct proof of $A=A'$?

Anyway, your proof is correct, but it makes some unnecessary steps. I assume you model your argument after the proof in https://driven2services.com/staging/mh/index.php?threads/12334/, which also uses reasoning by contradiction. That proof can be reduced to a direct proof as well.

 

[evinda]

I hope so! :)

Just a bit of nitpicking: the property you wrote does not mention $A'$, only $A$. You could say, "Suppose that $A$ and $A'$ satisfy the property $P(X)$ where $P(X)$ is $\forall x\;(x\in X\leftrightarrow x=a \lor x=b)$". Or just say explicitly: Suppose that
\begin{align}
&\forall x\;(x\in A\leftrightarrow x=a \lor x=b)\\
&\forall x\;(x\in A'\leftrightarrow x=a \lor x=b).
\end{align}

The status of this claim — $A \neq A'$ — is unclear. Is it given? Are you proving it? Is it an assumption towards contradiction? The correct way is to say, "Assume (towards contradiction) that $A \neq A'$".

You could do this, but I believe reasoning by contradiction is superfluous here and can be reduced to a direct proof. In fact, every direct proof can be framed as a proof by contradiction. Suppose we want to prove $S$ using the axiom $R\to S$. A direct proof would establish $R$ and then use the axiom. But it is also possible to say: Assume that $\neg S$ is true. Then the (contraposition of the) axiom implies $\neg R$. But we can prove $R$, which makes a contradiction; therefore, $\neg S$ was false and $S$ is true. But if we could indeed prove $R$, why was it necessary to assume $\neg S$? It is more direct to use the axiom.

In the case of the proof about pairs, let $P(x)$ be $x\in A\leftrightarrow x\in A'$. The axiom of extensionality says
\[
\forall x\;P(x)\to A=A'\qquad(*)
\]
which is $R\to S$ in the previous description. You need to show $A=A'$ so you assume towards contradiction that $A\ne A'$. Then (*) implies $\neg\forall x\;P(x)$, i.e., $\exists x\;\neg P(x)$. Take an $x_0$ such that $\neg P(x_0)$. But then you use the fact that $\forall x\;P(x)$ holds and instantiate $x$ with $x_0$ to get $P(x_0)$. This creates a contradiction with $\neg P(x_0)$, so the assumption $A\ne A'$ is false. But if you are using $\forall x\;P(x)$, why not combine it with (*) for a direct proof of $A=A'$?

Anyway, your proof is correct, but it makes some unnecessary steps. I assume you model your argument after the proof in https://driven2services.com/staging/mh/index.php?threads/12334/, which also uses reasoning by contradiction. That proof can be reduced to a direct proof as well.

I understand! (Nod) Thank you!We have that:

$$\forall x(x \in A \leftrightarrow x=a \vee x=b)$$
$$\forall x(x \in A' \leftrightarrow x=a \vee x=b)$$

From the above, we conclude that:

$$\forall x(x \in A \leftrightarrow x=a \vee x=b \leftrightarrow x \in A')$$

Does this imply that:
$$ \forall x(x \in A \leftrightarrow x \in A')$$

or do we have to prove it? (Thinking)

 

[Evgeny.Makarov]

From the above, we conclude that:

$$\forall x(x \in A \leftrightarrow x=a \vee x=b \leftrightarrow x \in A')$$

Does this imply that:
$$ \forall x(x \in A \leftrightarrow x \in A')$$

or do we have to prove it?

Yes, this trivially implies $ \forall x(x \in A \leftrightarrow x \in A')$.

 

[evinda]

Yes, this trivially implies $ \forall x(x \in A \leftrightarrow x \in A')$.

Great! (Smile) Thank you very much! (Clapping)