Why is $Y=\omega$ when $X \cap Y=\varnothing$ implies $X=\varnothing$?

[evinda]

Hi! (Smile)

Theorem:
At each nonempty subset of $\omega$ there is a least element, i.e. if $X \subset \omega, X \neq \varnothing$ then there is a $n \in \omega$ such that:

$$n \in X \wedge \forall m (m<n \rightarrow m \notin x)$$

Proof:
We fix $X \subset \omega, X \neq \varnothing$.

We will use the remark:

$n$ is the least element of $X$ iff $n \in X \wedge (n \cap X=\varnothing)$​

We will show that if $X$ has no least element then $X=\varnothing$ and this will be a contradiction.We define: $Y=\{ n \in \omega: n \cap X=\varnothing\}$.

We want to show that $Y=\omega$. Then for all $n \in \omega$ we will have $n \cap X=\varnothing$, so $X=\varnothing$.

So we suppose that $X$ has no least element. Then $X \cap Y=\varnothing$ because if there was a $n \in X \cap Y$ then $n \in X \wedge n \cap X=\varnothing$. But then we would conclude that $n$ is a least element, contradiction.
Since $X \cap Y=\varnothing$ so that it holds that $X=\varnothing$ it must be: $Y=\omega$.

The last step is to show that $Y=\omega$ using induction.
Could you explain me why since $X \cap Y=\varnothing$ , so that it holds that $X=\varnothing$ it must be: $Y=\omega$?

 

[Evgeny.Makarov]

Since $X \cap Y=\varnothing$ so that it holds that $X=\varnothing$ it must be: $Y=\omega$.

I don't understand the grammar in this sentence. Since the following sentence says that it is still left to prove that $Y=\omega$, the blue sentence seems to be a comment rather than a proof step. It probably says that to show our goal, i.e., that $X=\varnothing$, it is sufficient to prove that $Y=\omega$.

 

[evinda]

I don't understand the grammar in this sentence. Since the following sentence says that it is still left to prove that $Y=\omega$, the blue sentence seems to be a comment rather than a proof step. It probably says that to show our goal, i.e., that $X=\varnothing$, it is sufficient to prove that $Y=\omega$.

I thought that it is meant that we have shown that $X \cap Y=\varnothing$ and we want to show that $X=\varnothing$ and this can only happen when $Y=\omega$. And I didn't understand why this can only happen for this value of $Y$.. (Thinking)

 

[Evgeny.Makarov]

I thought that it is meant that we have shown that $X \cap Y=\varnothing$ and we want to show that $X=\varnothing$ and this can only happen when $Y=\omega$.

Under the assumption $X\cap Y=\varnothing$, the condition $Y=\omega$ is sufficient, but not necessary for $X=\varnothing$. So it is wrong to say, "it can only happen when $Y=\omega$".

 

[evinda]

Under the assumption $X\cap Y=\varnothing$, the condition $Y=\omega$ is sufficient, but not necessary for $X=\varnothing$. So it is wrong to say, "it can only happen when $Y=\omega$".

A ok, I see... (Nod)
Then at the last step it is shown like that that $Y=\omega$:

• $0 \in Y$ because $0 \cap X=\varnothing \cap X=\varnothing$
• We assume that $n \in Y$ and we will show that $n'=n \cup \{n\} \in Y$.
  If $n \in X$ then since $n \cap X=\varnothing (n \in Y)$ we will have that $n$ is a least element of $X$, contradiction.
  So $n \notin X$ and therefore $(n \cup \{n\}) \cap X= \varnothing \rightarrow n' \cap X=\varnothing$.
  
  Thus $n' \in X$.

Since $Y$ is an inductive subset of $\omega$ we have that $Y=\omega$.
How do we conclude from $n \notin X$ that $(n \cup \{n\}) \cap X=\varnothing$?

 

[Evgeny.Makarov]

How do we conclude from $n \notin X$ that $(n \cup \{n\}) \cap X=\varnothing$?

You also need to use the fact that $n \cap X=\varnothing$ since $n \in Y$.

 

[evinda]

Can we conclude from $n \notin X$ that $\{n\} \not\subset X$ ? (Thinking)

 

[Evgeny.Makarov]

$n \cap X=\varnothing$ is a stronger claim than $n \not\subset X$.

This conclusion ($(n\cup\{n\})\cap X=\varnothing$) is trivial given the facts proved before that. Think a little about it.

 

[evinda]

Can we do it like that? (Thinking)
We know that $n \cap X=\varnothing$ and $n \notin X \rightarrow \{n\} \not\subset X \rightarrow \{n\} \cap X=\varnothing$ and therefore $(n \cup \{n\}) \cap X=\varnothing$.

 

[Evgeny.Makarov]

Sorry, I missed that in post #7 you asked about $\{n\} \not\subset X$ and not $n \not\subset X$.

We know that $n \cap X=\varnothing$ and $n \notin X \rightarrow \{n\} \not\subset X \rightarrow \{n\} \cap X=\varnothing$ and therefore $(n \cup \{n\}) \cap X=\varnothing$.

Yes.

 

[evinda]

Yes.

Nice! (Happy) And do we have to prove that $n \notin X \rightarrow \{n\} \not\subset X \rightarrow \{n\} \cap X=\varnothing$ ? (Thinking)

 

[Evgeny.Makarov]

And do we have to prove that $n \notin X \rightarrow \{n\} \not\subset X \rightarrow \{n\} \cap X=\varnothing$ ?

I don't see how $\{n\} \not\subset X$ helps, though technically it does imply $\{n\} \cap X=\varnothing$. The answer to whether you should prove it is the same as whether you should prove the fact $(n\cup\{n\})\cap X=(n\cap X)\cup (\{n\}\cap X)$, which you used. In general, you should be able to prove everything you use.

 

[evinda]

I don't see how $\{n\} \not\subset X$ helps, though technically it does imply $\{n\} \cap X=\varnothing$. The answer to whether you should prove it is the same as whether you should prove the fact $(n\cup\{n\})\cap X=(n\cap X)\cup (\{n\}\cap X)$, which you used. In general, you should be able to prove everything you use.

Could we prove the implication $n \notin X \rightarrow \{n\} \cap X=\varnothing$ like that? (Thinking)

We suppose that $n \notin X$. Let $m \in \{n\} \cap X \rightarrow m \in \{n\} \wedge m \in X \rightarrow m=n \wedge m \in X \rightarrow n \in X$, contradiction since $n \notin X$.
Therefore, there is no $m \in \omega$ such that $m \in \{n\} \cap X$, i.e. $\{n\} \cap X=\varnothing$.In order to prove that $(n \cup \{ n \}) \cap X=(n \cap X) \cup (\{n\} \cap X)$ I tried the following:$$m \in (n \cup \{ n \}) \cap X \leftrightarrow m \in (n \cup \{ n \}) \wedge m \in X \leftrightarrow (m \in n \lor m \in \{n\}) \wedge m \in X \\ \leftrightarrow (m \in n \wedge m \in X) \lor (m \in \{n\} \wedge m \in X) \leftrightarrow m \in ( n \cap X) \cup (\{n\} \cap X)$$Is it right? (Thinking)

 

[Evgeny.Makarov]

Technicall, you are right. However, recall my remark about mental images of mathematical concepts from another thread about a month ago. Mathematics is not string manipulation. On the one hand, the ability to prove a statement formally, going to axioms if necessary, is commendable, but if you don't have a picture and intuition of the concepts you are working with, you won't be able to devise nontrivial proofs. If it is not obvious to you why $n\notin X$ implies $\{n\}\cap X=\varnothing$ without writing several lines of symbols, you are doing something wrong.

 

[evinda]

We could consider $X$ as the set of dog owners.
If we assume that John doesn't have a dog then John $\notin X$.
So $\{ \text{ John} \} \cap \text{set of dog owners}=\varnothing$, right? (Thinking)

 

[evinda]

Then, according to my lecture notes, the following theorem is an other version of the theorem we saw:

Theorem:

Let $\phi$ type. We assume that $(\exists n \in \omega) \phi(n)$.
Then $\exists m(\phi(m) \wedge \forall k(k<n \rightarrow \lnot \phi(k))$

And the proof is the following:

We define the set $X=\{ n \in \omega: \phi(n)\}$.
From the assumption that there is a $n \in \omega$ such that $\phi(n)$ we have that $X \neq \varnothing$.

So from the previous theorem there is the element $m=\text{min}X$ and we can easily verify that $m$ satifies the relation
$$\forall k(k<m \rightarrow \lnot \phi(k))$$

In order to verify the last implication could we use again the previous theorem? (Thinking)

 

[Evgeny.Makarov]

We could consider $X$ as the set of dog owners.
If we assume that John doesn't have a dog then John $\notin X$.
So $\{ \text{ John} \} \cap \text{set of dog owners}=\varnothing$, right?

Yes, that's a good way to think about it.

In order to verify the last implication could we use again the previous theorem?

Why don't you try?

Note that the notation $\min X$ has not been used in this thread before.

 

[evinda]

Why don't you try?

The previous theorem was this:

At each nonempty subset of $\omega$ there is a least element, i.e. if $X \subset \omega, X \neq \varnothing$ then there is a $n \in \omega$ such that:

$$n \in X \wedge \forall m (m<n \rightarrow m \notin X)$$

At this theorem with $\phi(n)$ we mean the identity $n \in X$, right?
So it is exactly the same. But can we just use the previous theorem?
I didn't think so because it should be an other version of the previous theorem.. (Thinking)

 

[Evgeny.Makarov]

At this theorem with $\phi(n)$ we mean the identity $n \in X$, right?

$n \in X$ is not an identity, but yes, roughly speaking. More precisely, if you are reducing the new theorem to the old one, you have a type $\phi$, but you don't yet have a set $X$. You define $X=\{n\in\omega\mid\phi(x)\}$ and apply the old theorem to that $X$. Then indeed $\phi(n)$ is equivalent to $n\in X$.

So it is exactly the same.

Yes, after reduction.