MHB Proving Uniqueness of a Set: A Logical Approach

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Set
AI Thread Summary
The discussion focuses on proving the uniqueness of the set {a, b} using the axiom of extensionality. It begins by assuming two sets, {a, b} and {a, b}', which contain the same elements but are claimed to be unequal. The participants explore how to demonstrate that this assumption leads to a contradiction, ultimately confirming that if both sets satisfy the same property regarding their elements, they must be equal. The conversation emphasizes the efficiency of direct proofs over reasoning by contradiction, concluding that the uniqueness of the set {a, b} is established through logical reasoning. The participants express satisfaction with the clarity of the proof process.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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) :confused:
 
Physics news on Phys.org
Consider the two cases:

$x = a$
$x = b$
 
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$.
 
Evgeny.Makarov said:
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.

:confused:
 
evinda said:
So, could I justify it like that?
I hope so! :)

evinda said:
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}

evinda said:
$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'$".

evinda said:
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.
 
Evgeny.Makarov said:
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)
 
evinda said:
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')$.
 
Evgeny.Makarov said:
Yes, this trivially implies $ \forall x(x \in A \leftrightarrow x \in A')$.

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

Similar threads

Replies
10
Views
3K
Replies
5
Views
2K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
3
Views
2K
Replies
11
Views
1K
Replies
11
Views
3K
Back
Top