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

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion centers on a theorem stating that if a nonempty subset \( X \) of \( \omega \) has no least element, then \( X \) must be empty, leading to the conclusion that \( Y = \omega \). The proof involves defining \( Y \) as the set of elements in \( \omega \) that do not intersect with \( X \) and showing that if \( X \cap Y = \varnothing \), it implies \( X = \varnothing \). Participants clarify the logical implications of the proof steps, particularly the necessity of proving that \( Y = \omega \) to establish \( X = \varnothing \). The conversation also touches on the importance of intuition in mathematical proofs and the relationship between different theorems. Overall, the thread emphasizes the logical structure of the proof and the need for clarity in mathematical reasoning.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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$? :confused:
 
Physics news on Phys.org
evinda said:
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$.
 
Evgeny.Makarov said:
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)
 
evinda said:
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$".
 
Evgeny.Makarov said:
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$? :confused:
 
evinda said:
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$.
 
Can we conclude from $n \notin X$ that $\{n\} \not\subset X$ ? (Thinking)
 
$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.
 
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$.
 
  • #10
Sorry, I missed that in post #7 you asked about $\{n\} \not\subset X$ and not $n \not\subset X$.

evinda said:
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.
 
  • #11
Evgeny.Makarov said:
Yes.
Nice! (Happy) And do we have to prove that $n \notin X \rightarrow \{n\} \not\subset X \rightarrow \{n\} \cap X=\varnothing$ ? (Thinking)
 
  • #12
evinda said:
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.
 
  • #13
Evgeny.Makarov said:
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)
 
  • #14
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.
 
  • #15
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)
 
Last edited:
  • #16
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)
 
  • #17
evinda said:
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.

evinda said:
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.
 
  • #18
Evgeny.Makarov said:
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)
 
  • #19
evinda said:
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$.

evinda said:
So it is exactly the same.
Yes, after reduction.
 

Similar threads

Replies
18
Views
3K
Replies
1
Views
2K
Replies
3
Views
2K
Replies
2
Views
2K
Replies
14
Views
3K
Replies
11
Views
3K
Replies
14
Views
2K
Back
Top