MHB Why can we write the set as $\{ m \in \omega: T_m=\omega \}$?

[evinda]

Hello! (Wave)

I am looking at the proof of the proposition:
$$\text{The relation } \epsilon_{\omega}=\{ \langle m,n \rangle \in \omega^2: m \in n\} \text{ is trichotomous on } \omega.$$

Proof:

We define the sets: $T_m=\{ n \in \omega: m \in n \lor m=n \lor n \in m\},m \in \omega$

It suffices to show that for each $m \in \omega, T_m=\omega.$

(because if $m,n \in \omega$ then from the above we have that $T_m=\omega$ and so $n \in \omega=T_m \rightarrow n \in m \lor n=m \lor m \in n$)

For each $n \in \omega, \varnothing \subset n$ and so

$\varnothing \in n \lor \varnothing=n$.

Therefore for each $n \in \omega, n \in T_{\varnothing}=T_0$, i.e. $T_0=\omega$

Induction hypothesis: $T_{m}=\omega$

We will show that $T_{m'}=\omega$

If we show the above then the set $\{ m \in \omega: T_m=\omega \}$ is inductive and so $\{ m \in \omega: T_m=\omega \}=\omega$

For each $n \in \omega$ we have $m \in n \lor m=n \lor n \in m$

• If $n \in m \lor m=n$, then $n \in m'$
  
• If $m \in n \rightarrow \{ m \} \subset n \wedge m \subset n \rightarrow m \cup \{ m \} \subset n \rightarrow m' \subset n$
  
  So $m' \in n \lor m'=n$
  

Therefore we have $m' \in n \lor m'=n \lor n \in m'$.

Thus $T_{m'}=\omega$.Could you explain me why we can write the set like that: $\{ m \in \omega: T_m=\omega \}$ ? (Thinking)

 

[Evgeny.Makarov]

Could you explain me why we can write the set like that: $\{ m \in \omega: T_m=\omega \}$ ?

You are implying that some set was defined in a different way, but now it is written as $\{ m \in \omega: T_m=\omega \}$. But what is that set and how was it defined originally?

In other words, if a proof says, "Consider the set $\{n\in\omega\mid P(n)\}$ for some given property $P$. You would not ask, "Why is this set written in this way?". This is because the proof author wants it like this. This question is only legitimate if this set was encountered before, it is now written in a different way and the equivalence of the new definition is not obvious.

 

[evinda]

You are implying that some set was defined in a different way, but now it is written as $\{ m \in \omega: T_m=\omega \}$. But what is that set and how was it defined originally?

In other words, if a proof says, "Consider the set \{n\in\omega\mid P(n)\}$ for some given property $P$. You would not ask, "Why is this set written in this way?". This is because the proof author wants it like this. This question is only legitimate if this set was encountered before, it is now written in a different way and the equivalence of the new definition is not obvious.

I thought that this set: $T_m=\{ n \in \omega: m \in n \lor m=n \lor n \in m\},m \in \omega$ was meant.. Am I wrong? (Thinking)

 

[Evgeny.Makarov]

I thought that this set: $T_m=\{ n \in \omega: m \in n \lor m=n \lor n \in m\},m \in \omega$ was meant.

No. The set $T_m$ depends on $m$ while the set in the bold line in post #1 does not depend on anything. These are different sets.

 

[evinda]

No. The set $T_m$ depends on $m$ while the set in the bold line in post #1 does not depend on anything. These are different sets.

A ok... (Whew) So does it suffice to show that the set $\{ m \in \omega: T_m=\omega \}$ is inductive because then it will hold

$$m \in n \lor m=n \lor n \in m, \forall m, n \in \omega$$

? (Thinking)

 

[Evgeny.Makarov]

So does it suffice to show that the set $\{ m \in \omega: T_m=\omega \}$ is inductive because then it will hold

$$m \in n \lor m=n \lor n \in m, \forall m, n \in \omega$$

?

Yes.

 

[evinda]

Do we want to show that this set: $\{ m \in \omega: T_m=\omega\}$ is inductive and not this one: $T_m=\{ n \in \omega: m \in n \lor m=n \lor n \in m\}$ because showing the latter it wouldn't hold for all $m$ ? Or am I wrong? (Thinking)

 

[Evgeny.Makarov]

Do we want to show that this set: $\{ m \in \omega: T_m=\omega\}$ is inductive and not this one: $T_m=\{ n \in \omega: m \in n \lor m=n \lor n \in m\}$ because showing the latter it wouldn't hold for all $m$ ?

What does the bold "it" in your quote refer to?

I think I answered your question in post #6. This is not counting the fact that the proof in post #1 clearly says about which set it intends to show that it is inductive.

Actually, the set $T_m$ is also inductive for every $m$ because $T_m=\omega$, but the proof does not show $T_m=\omega$ by showing that $T_m$ is inductive; it shows it directly.

 

[evinda]

What does the bold "it" in your quote refer to?

I meant the trichotomous identity...

Actually, the set $T_m$ is also inductive for every $m$ because $T_m=\omega$, but the proof does not show $T_m=\omega$ by showing that $T_m$ is inductive; it shows it directly.

So showing that $T_m$ is inductive would we also prove that the trichotomous identity is satisfied? (Thinking)

 

[Evgeny.Makarov]

What does the bold "it" in your quote refer to?

I meant the trichotomous identity...

Well, the phrase "trichotomous identity" does not appear in post #7, so it is hard to make a connection from "it" back to that phrase.

So showing that $T_m$ is inductive would we also prove that the trichotomous identity is satisfied?

I get suspicious when a student struggling with a proof asks if it can be changed in a certain way. Understanding a given proof is much easier than comping up with your own version, so usually there is not much sense in discussing such modifications.

 

[evinda]

A ok.. But if we would want to prove that $T_m$ is inductive wouldn't we do it in the same way? (Thinking)

 

[Evgeny.Makarov]

Showing that a set $\{n\in\omega\mid P(n)\}$ is inductive is the same as proving $\forall n\;P(n)$ by mathematical induction. Now, proving $\forall n\;P(n)$ by induction is more involved than constructing a direct proof. In the latter, you fix $n$ and prove $P(n)$. In the former, you also fix $n$ and prove $P(n')$, but you have the inductive hypothesis $P(n)$ at your disposal. This makes the proof go through when the direct proof may fail, but this also complicates the structure of the proof a little (you have to deal with the base case and the inductive step). On the other hand, a direct proof may be presented as an inductive proof where the inductive hypothesis is simply not be used.

The only reason to prove that $T_m$ is inductive is to show that $T_m=\omega$. But post #1 shows $T_m=\omega$ using a direct proof: it proves $n\in T_m$ for each $n$ independently and does not use the fact that $n\in T_m$ in the proof that $n'\in T_m$. But while that proof does not use induction on $n$, it employs induction on $m$ and uses the fact that $n\in T_m$ in proving $n\in T_{m'}$. If you keep induction on $m$, there is no reason to show $T_m=\omega$ by induction because it is proved directly.