MHB How can I show that the sets are pairwise disjoint?

[evinda]

Hello! (Wave)

Could you give me a hint how I can show that the sets:

$$\{ \varnothing, \{ \varnothing \} \} , \ \ \ \{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}, \ \ \ \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \}$$

are pairwise disjoint=are not equal ?

 

[Evgeny.Makarov]

First, being disjoint is not the same as being not equal. For example, $\{1,2\}\ne\{1,3\}$, but these sets are not disjoint: both of them contain 1.

The sets you listed are not disjoint: the first and second contain $\emptyset$, and the first and third contain $\{\emptyset\}$. But they are indeed no equal because in each pair one set has some element that the other does not.

 

[evinda]

First, being disjoint is not the same as being not equal. For example, $\{1,2\}\ne\{1,3\}$, but these sets are not disjoint: both of them contain 1.

The sets you listed are not disjoint: the first and second contain $\emptyset$, and the first and third contain $\{\emptyset\}$.

I understand! (Yes)

But they are indeed no equal because in each pair one set has some element that the other does not.

1. $\displaystyle{ \{ \varnothing, \{ \varnothing \} \} }$
   
2. $\displaystyle{ \{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \} }$
   
3. $ \displaystyle{ \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \} }$

So, we have to show the following, right?

• The first set is not equal to the second set.
  $$$$
• The first set is not equal to the third set.
  $$$$
• The second set is not equal to the third set.

Could we do it like that? (Thinking)

• The first set contains $\{ \varnothing \}$, but the second set does not contain it.
  
  Otherwise, it would stand $\{ \varnothing \}= \varnothing$ or $\{ \varnothing \}=\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$.
  
  It isn't $ \{ \varnothing \}=\varnothing$, because we have $\varnothing \in \{ \varnothing \}$, but not $ \{ \varnothing \} \in \varnothing$.
  
  Also, it cannot be $\{ \varnothing \}=\{ \varnothing, \{ \varnothing , \{ \varnothing \} \} \}$, since $\{ \varnothing \} \in \{ \varnothing, \{ \varnothing , \{ \varnothing \} \} \}$, but $\{ \varnothing, \{ \varnothing , \{ \varnothing \} \} \} \notin \{ \varnothing \}$.
  
  $$$$
• The first set contains $ \varnothing $, but the third set does not contain it.
  
  Otherwise, it would stand $ \varnothing =\{ \varnothing \}$ or $\varnothing=\{ \varnothing, \{ \varnothing \} \}$.
  
  It isn't $\varnothing= \{ \varnothing \}$, because we have $\varnothing \in \{ \varnothing \}$, but not $ \{ \varnothing \} \in \varnothing$.
  
  Also, it cannot be $\varnothing= \{ \varnothing, \{ \varnothing \} \}$, since $\varnothing \in \{ \varnothing, \{ \varnothing \} \}$, but $\{ \varnothing, \{ \varnothing \} \} \notin \varnothing$.$$$$
• The second set contains $\varnothing$, but the third set does not contain it.
  Otherwise, it would stand $\varnothing= \{ \varnothing \}$ or $\varnothing=\{ \varnothing, \{ \varnothing\}\}$.
  
  It isn't $\varnothing= \{ \varnothing \}$, because we have $\varnothing \in \{ \varnothing \}$, but not $ \{ \varnothing \} \in \varnothing$.
  
  Also, it cannot be $\varnothing=\{ \varnothing, \{ \varnothing\}\}$, since $\varnothing \in \{ \varnothing, \{ \varnothing\}\}$, but $\{ \varnothing, \{ \varnothing\}\} \notin \varnothing$.
  

 

[Evgeny.Makarov]

• The first set is not equal to the second set.
  $$$$
• The first set is not equal to the third set.
  $$$$
• The second set is not equal to the third set.

Yes.

The first set contains $\{ \varnothing \}$, but the second set does not contain it.

Yes.

Otherwise, it would stand $\{ \varnothing \}= \varnothing$ or $\{ \varnothing \}=\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$.

You probably mean, "... or $\{ \varnothing \}=\{ \varnothing, \{ \varnothing \} \}$.

It isn't $ \{ \varnothing \}=\varnothing$, because we have $\varnothing \in \{ \varnothing \}$, but not $ \{ \varnothing \} \in \varnothing$.

What does checking whether $\varnothing \in \{ \varnothing \}$ and $ \{ \varnothing \} \in \varnothing$ have to do with $ \{ \varnothing \}=\varnothing$?

Also, it cannot be $\{ \varnothing \}=\{ \varnothing, \{ \varnothing , \{ \varnothing \} \} \}$, since $\{ \varnothing \} \in \{ \varnothing, \{ \varnothing , \{ \varnothing \} \} \}$, but $\{ \varnothing, \{ \varnothing , \{ \varnothing \} \} \} \notin \{ \varnothing \}$.

Same remark. $A\in B$ and $B\in A$ is not a necessary condition for $A=B$.

The first set contains $ \varnothing $, but the third set does not contain it.

Yes.

The second set contains $\varnothing$, but the third set does not contain it.

Yes, but your explanation is again incorrect.

 

[evinda]

You probably mean, "... or $\{ \varnothing \}=\{ \varnothing, \{ \varnothing \} \}$.

Yes, that's what I meant.. (Nod)

What does checking whether $\varnothing \in \{ \varnothing \}$ and $ \{ \varnothing \} \in \varnothing$ have to do with $ \{ \varnothing \}=\varnothing$?

Same remark. $A\in B$ and $B\in A$ is not a necessary condition for $A=B$.Yes, but your explanation is again incorrect.

A ok.. How could I show otherwise that the sets are not equal? (Thinking)

 

[Evgeny.Makarov]

Why don't you answer the question in post #4?

 

[evinda]

Why don't you answer the question in post #4?

I thought that we could show like that, that the two sets are not equal.
Do we have to show maybe that one one of the following relations is not satisfied:

$$\varnothing \subseteq \{ \varnothing \} \\ \{ \varnothing \} \subseteq \varnothing$$

in order to show that $ \{ \varnothing \} \neq \varnothing$ ? (Thinking)

 

[Evgeny.Makarov]

Do we have to show maybe that one one of the following relations is not satisfied:

$$\varnothing \subseteq \{ \varnothing \} \\ \{ \varnothing \} \subseteq \varnothing$$

in order to show that $ \{ \varnothing \} \neq \varnothing$ ?

Yes, that's correct. If $A,B$ are two sets, then we have the following.
\begin{align}
(A\subseteq B)\land (B\subseteq A)&\iff\forall x\;(x\in A\to x\in B)\land \forall x\;(x\in B\to x\in A)\\
&\phantom{\iff}\text{by definition of }\subseteq\\
&\iff\forall x\;(x\in A\leftrightarrow x\in B)\\
&\phantom{\iff}\text{by logical reasoning}\\
&\iff A=B\\
&\phantom{\iff}\text{by axiom of extensionality}
\end{align}
Here "logical reasoning" means ordinary logic that does not rely on any axioms or definitions of set theory.

 

[evinda]

Yes, that's correct. If $A,B$ are two sets, then we have the following.
\begin{align}
(A\subseteq B)\land (B\subseteq A)&\iff\forall x\;(x\in A\to x\in B)\land \forall x\;(x\in B\to x\in A)\\
&\phantom{\iff}\text{by definition of }\subseteq\\
&\iff\forall x\;(x\in A\leftrightarrow x\in B)\\
&\phantom{\iff}\text{by logical reasoning}\\
&\iff A=B\\
&\phantom{\iff}\text{by axiom of extensionality}
\end{align}
Here "logical reasoning" means ordinary logic that does not rely on any axioms or definitions of set theory.

I understand! (Nod)So, in order to show, for example, that the first set ($\{ \varnothing, \{ \varnothing \} \}$) is not equal to the second one ( $ \{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \} $), could we do it like that? (Thinking)The first set contains $\{ \varnothing \}$, but the second set does not contain it.Otherwise, it would stand $\{ \varnothing \}= \varnothing$ or $\{ \varnothing \}=\{ \varnothing, \{ \varnothing \} \}$.

It isn't $\{ \varnothing \}= \varnothing$, since $ \varnothing \subseteq \{ \varnothing \}$, but $ \{ \varnothing \} \nsubseteq \varnothing$.

Also, it cannot be $\{ \varnothing \}= \{ \varnothing, \{ \varnothing \} \}$, because $\{ \varnothing \} \subseteq \{ \varnothing, \{ \varnothing \} \}$, but $\{ \varnothing, \{ \varnothing \} \} \nsubseteq \{ \varnothing \}$.

Do we have to prove that $\text{ one set } \subseteq \text{ an other one }$ or $\text{one set } \nsubseteq \text{ an other one }$ or is it obvious? (Thinking)

 

[Evgeny.Makarov]

Note that you reduced the problem of proving that $\{ \varnothing, \{ \varnothing \} \}\ne\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$ to showing that $\{ \varnothing \}\ne\varnothing$ and $\{ \varnothing \}\ne\{ \varnothing, \{ \varnothing \}\}$. These are problems of the same type (proving inequalities of sets), so they should be shown in the same way. You started by exhibiting an element $\{ \varnothing \}$ of the first set that you claimed is not an element of the second one. To prove this, it is sufficient to show that $\{\varnothing\}$ is not equal to any of the two elements of the second set. But now $\{ \varnothing \}\ne\varnothing$ can be shown in the same way: $ \varnothing\in\{\varnothing \}$, but $ \varnothing\notin\varnothing$ by definition of $\varnothing$. Similarly, for the second inequality $\{ \varnothing \}\ne\{ \varnothing, \{ \varnothing \}\}$, we have $\{ \varnothing \}\in\{ \varnothing, \{ \varnothing \}\}$, but $\{\varnothing\}\notin\{\varnothing\}$. End of proof.

I am saying that your proof using $\subseteq$ is correct, but it is strange that you used it to disprove $\{ \varnothing \}= \varnothing$ but not the original $\{ \varnothing, \{ \varnothing \} \}=\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$. Note that invoking $\subseteq$ still amounts to exhibiting an element of one set that is not an element of the other.

Do we have to prove that one set $\subseteq$ an other one or one set $\nsubseteq$ an other one or is it obvious?

First, to disprove equality you only have to show $\nsubseteq$. Second, whether it is obvious depends on you and the requirements of the course. I think it is a good idea just once to go all the way to $\varnothing$

You could also start using $\subseteq$ from the start, though this is basically the same proof. Maybe once in life it is OK to go through a very detailed proof, whose outline is shown in the following picture.

View attachment 3314

It has three layers where one needs to prove inequality, and all of them are proven in the same way: by showing some element of one set that does not belong to the other.

After you've done this once or twice, the original statement is indeed obvious because the first set cannot be matched with the second one by changing the order of elements.

 

[evinda]

Note that you reduced the problem of proving that $\{ \varnothing, \{ \varnothing \} \}\ne\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$ to showing that $\{ \varnothing \}\ne\varnothing$ and $\{ \varnothing \}\ne\{ \varnothing, \{ \varnothing \}\}$. These are problems of the same type (proving inequalities of sets), so they should be shown in the same way. You started by exhibiting an element $\{ \varnothing \}$ of the first set that you claimed is not an element of the second one. To prove this, it is sufficient to show that $\{\varnothing\}$ is not equal to any of the two elements of the second set. But now $\{ \varnothing \}\ne\varnothing$ can be shown in the same way: $ \varnothing\in\{\varnothing \}$, but $ \varnothing\notin\varnothing$ by definition of $\varnothing$. Similarly, for the second inequality $\{ \varnothing \}\ne\{ \varnothing, \{ \varnothing \}\}$, we have $\{ \varnothing \}\in\{ \varnothing, \{ \varnothing \}\}$, but $\{\varnothing\}\notin\{\varnothing\}$. End of proof.

I am saying that your proof using $\subseteq$ is correct, but it is strange that you used it to disprove $\{ \varnothing \}= \varnothing$ but not the original $\{ \varnothing, \{ \varnothing \} \}=\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$. Note that invoking $\subseteq$ still amounts to exhibiting an element of one set that is not an element of the other.

First, to disprove equality you only have to show $\nsubseteq$. Second, whether it is obvious depends on you and the requirements of the course. I think it is a good idea just once to go all the way to $\varnothing$

You could also start using $\subseteq$ from the start, though this is basically the same proof. Maybe once in life it is OK to go through a very detailed proof, whose outline is shown in the following picture.

View attachment 3314

It has three layers where one needs to prove inequality, and all of them are proven in the same way: by showing some element of one set that does not belong to the other.

After you've done this once or twice, the original statement is indeed obvious because the first set cannot be matched with the second one by changing the order of elements.

So, in order to show that the first set is not equal to the second one ($\{ \varnothing, \{ \varnothing \} \} \neq \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \}$) could we do it like that? (Thinking)We have that $ \varnothing \in \{ \varnothing, \{ \varnothing \} \}$, but $\varnothing \notin \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \}$.
Actually:
$\varnothing \neq \{ \varnothing \}$, since $\varnothing \in \{ \varnothing \}$, but $\varnothing \notin \varnothing$.

$\varnothing \neq \{ \varnothing, \{ \varnothing \} \}$, since $\varnothing \in \{ \varnothing, \{ \varnothing \} \}$, but $\varnothing \notin \varnothing$.
Also, can we prove in this way that $\{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \} \neq \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \}$ :

We have that $\varnothing \in \{ \varnothing, \{ \varnothing, \{ \varnothing \} \} \}$, but $\varnothing \notin \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \} $.

Actually:

$\varnothing \neq \{ \varnothing \}$, since $\varnothing \in \{ \varnothing \}$, but $\varnothing \notin \varnothing$

$\varnothing \neq \{ \varnothing, \{ \varnothing \} \}$, since $\{ \varnothing \} \in \{ \varnothing, \{ \varnothing \} \}$, but $\{ \varnothing \} \notin \varnothing$

Or am I wrong? (Thinking)

 

[Evgeny.Makarov]

I think this is fine, though extremely detailed. I've never seen anybody proving $\varnothing \notin \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \}$ since it is obvious; however, if you go down to the axiom level, this is indeed how it is done.

I would replace "Actually" by "The latter fact holds because" and remove commas before "since".

 

[evinda]

I think this is fine, though extremely detailed.

So, would it be also right, if we would only say the two sets are not equal, because we have that $ \varnothing \in \{ \varnothing, \{ \varnothing \} \}$, but $\varnothing \notin \{ \{ \varnothing \}, \{ \varnothing, \{ \varnothing \} \} \}$ ?

I would replace "Actually" by "The latter fact holds because" and remove commas before "since".

A ok! (Nod)