Prove Natural Numbers Subset Property

[evinda]

Hello! (Wave)

I want to prove that for any natural numbers $n,m$ it holds that:

$$n \subset m \leftrightarrow n \in m \lor n=m$$

$"\Leftarrow"$: Using the sentence:
"For any natural numbers $m,n$ it holds that $n \in m \rightarrow n \subset m$"
if $n \in m \lor n=m$, we conclude that $n \subset m$.

$"\Rightarrow"$:

$$n \subset m \rightarrow n=m \lor n \subsetneq m$$

When $n=m$, the desired property is satisfied.

When $n \subsetneq m$, then could we use the definition of subset that is the following? (Thinking)

$$n \subsetneq m \leftrightarrow \forall x(x \in n \rightarrow x \in m)$$

 

[Evgeny.Makarov]

When $n \subsetneq m$, then could we use the definition of subset that is the following?

$$n \subsetneq m \leftrightarrow \forall x(x \in n \rightarrow x \in m)$$

The left-to-right implication does not hold for arbitrary sets $m$ and $n$ but only for natural numbers (or maybe ordinals). So you need to use the definition or some properties of natural numbers and not just the definition of subset. By the way, the right-hand side of your equivalence (last line of the quote) means $n\subseteq m$ (or $n\subset m$ in your notation), so the equivalence is false.

In general, such statements should be found in some good textbook on intermediate set theory. Even if they are given as exercises, the book should provide the order in which such statements should be proved. Pretty soon such facts may become complicated, and without such context their proof may be difficult.

You could show $n\subseteq m\implies n\in m\lor n=m$ by induction on $m$. The difficult case is when $n\subseteq m\cup\{m\}$ and $n\not\subseteq m$. This means that $m\in n$. In usual notation, this means $n\le m+1$ and $m<n$, so $n=m+1$. To prove $n=m\cup\{m\}$ it is sufficient to show $\forall x\in m\;x\in n$, but this follows from $m\in n$ and transitivity of $n$.

 

[evinda]

The left-to-right implication does not hold for arbitrary sets $m$ and $n$ but only for natural numbers (or maybe ordinals). So you need to use the definition or some properties of natural numbers and not just the definition of subset. By the way, the right-hand side of your equivalence (last line of the quote) means $n\subseteq m$ (or $n\subset m$ in your notation), so the equivalence is false.

In general, such statements should be found in some good textbook on intermediate set theory. Even if they are given as exercises, the book should provide the order in which such statements should be proved. Pretty soon such facts may become complicated, and without such context their proof may be difficult.

You could show $n\subseteq m\implies n\in m\lor n=m$ by induction on $m$. The difficult case is when $n\subseteq m\cup\{m\}$ and $n\not\subseteq m$. This means that $m\in n$. In usual notation, this means $n\le m+1$ and $m<n$, so $n=m+1$. To prove $n=m\cup\{m\}$ it is sufficient to show $\forall x\in m\;x\in n$, but this follows from $m\in n$ and transitivity of $n$.

So, if we want to show $n\subseteq m\implies n\in m\lor n=m$ by induction on $m$, don't we suppose that $n \subseteq m \rightarrow n \in m \lor n=m$?
Then we want to show that $n \subseteq m' \rightarrow n \in m' \lor n=m'$ right?
Then we have that $n \subseteq m \cup \{ m \}$. But then how can it be $n\not\subseteq m$, although having supposed that $n \subseteq m$? (Worried)

 

[Evgeny.Makarov]

So, if we want to show $n\subseteq m\implies n\in m\lor n=m$ by induction on $m$, don't we suppose that $n \subseteq m \rightarrow n \in m \lor n=m$?

Yes. In fact, I would make the induction hypothesis, and the statement we are proving by induction on $m$, to be
\[
\forall n\;n\subseteq m\implies n\in m\lor n=m.
\]
This makes it possible to instantiate the hypothesis with a different $n$ than the one used in the conclusion of the induction step.

Then we want to show that $n \subseteq m' \rightarrow n \in m' \lor n=m'$ right?

Yes.

Then we have assume that $n \subseteq m \cup \{ m \}$. But then how can it be $n\not\subseteq m$, although having supposed that $n \subseteq m$?

Where did you assume that $n \subseteq m$?

 

[evinda]

Where did you assume that $n \subseteq m$?

Oh, sorry! We don't assume it... (Tmi)So, we assume that $n \subseteq m \cup \{m\}$.
And then do we have to check the case $n \subseteq m$ and the case $n \not\subseteq m$ ? (Thinking)

 

[Evgeny.Makarov]

So, we assume that $n \subseteq m \cup \{m\}$.
And then do we have to check the case $n \subseteq m$ and the case $n \not\subseteq m$ ?

Yes.

 

[evinda]

Yes.

So we assume that $\forall n \ \ n \subset m \rightarrow n \in m \lor n=m$.
We want to show that $n \subset m' \rightarrow n \in m' \lor n=m'$.
We have that $n \subset m \cup \{m\}$.
If $n \subseteq m \rightarrow n \in m \lor n=m \rightarrow n \in m \cup \{m\} \lor n=m$.
Right? But how can we conclude that it could also be $n=m'$ ? (Thinking)
Then, if $n \not\subseteq m$ how do we conlude that $m \in n$ ?

 

[Evgeny.Makarov]

You know that this forum does not have a rule saying that every post must start with a quote, right? In fact, while quoting relevant parts of the post greatly helps understanding the discussion, indiscriminate quoting only makes it harder.

So we assume that $\forall n \ \ n \subset m \rightarrow n \in m \lor n=m$.
We want to show that $n \subset m' \rightarrow n \in m' \lor n=m'$.
We have that $n \subset m \cup \{m\}$.

"Assume" instead of "have" would be more precise.

If $n \subseteq m \rightarrow n \in m \lor n=m \rightarrow n \in m \cup \{m\} \lor n=m$.

OK, a couple of things. First, I consistently use $A\subseteq B$ for $\forall x\;x\in A\to x\in B$ and $A\subset B$ for $A\subseteq B$ and $A\ne B$ because it is analogous to $\le$ and $<$. You seemed to have consistently used $A\subset B$ for $\forall x\;x\in A\to x\in B$, but the last quote uses $\subseteq$ as well. This is a big potential confusion. Please say which notation you prefer so that we stick to it.

Second, does $n \subseteq m \rightarrow n \in m \lor n=m \rightarrow n \in m \cup \{m\} \lor n=m$ mean

(1) "$n \subseteq m$; therefore, $n \in m \lor n=m$, and this implies $n \in m \cup \{m\} \lor n=m$",

(2) "If it is true that $n \subseteq m$ implies $n \in m \lor n=m$, then $n \in m \cup \{m\} \lor n=m$", or

(3) "If $n \subseteq m$, then $n \in m \lor n=m$ implies $n \in m \cup \{m\} \lor n=m$"?

They all mean different things. If you write it with $\to$, it is supposed to mean (3). Note that (3) is a bare statement, not a proof step. It itself requires a proof. In contrast, (1) is a proof step (or two). To mean (1) please use long double arrows ([m]\implies[/m] in LaTeX):
\[
n \subseteq m \implies n \in m \lor n=m \implies n \in m \cup \{m\} \lor n=m.
\]
It is safer to use words rather than symbols $\to$ or $\implies$.

Could you rewrite your post taking these remarks into account?

 

[evinda]

You know that this forum does not have a rule saying that every post must start with a quote, right? In fact, while quoting relevant parts of the post greatly helps understanding the discussion, indiscriminate quoting only makes it harder.

I am sorry.. I will take it into consideration...

"Assume" instead of "have" would be more precise.

(Nod)

OK, a couple of things. First, I consistently use $A\subseteq B$ for $\forall x\;x\in A\to x\in B$ and $A\subset B$ for $A\subseteq B$ and $A\ne B$ because it is analogous to $\le$ and $<$. You seemed to have consistently used $A\subset B$ for $\forall x\;x\in A\to x\in B$, but the last quote uses $\subseteq$ as well. This is a big potential confusion. Please say which notation you prefer so that we stick to it.

I prefer this definition: $A \subset B \leftrightarrow \forall x(x \in A \rightarrow x \in B)$.
I just used $\subseteq$ as you did in post #2.

Could you rewrite your post taking these remarks into account?

We assume that $\forall n \ \ n \subset m \rightarrow n \in m \lor n=m$.
We want to show that $n \subset m' \rightarrow n \in m' \lor n=m'$.

So, we assume that $n \subset m'=m \cup \{m\}$.
If $n \subset m$ then $n \in m \lor n=m \implies n \in m \cup \{m\} \lor n=m$.
But how can we conclude that it could also be $n=m'$ ? (Thinking)

If $n \not\subset m$ how do we conclude that $m \in n$ ?

 

[Evgeny.Makarov]

I prefer this definition: $A \subset B \leftrightarrow \forall x(x \in A \rightarrow x \in B)$.

OK, let's stick with that.

If $n \subset m$ then $n \in m \lor n=m \implies n \in m \cup \{m\} \lor n=m$.
But how can we conclude that it could also be $n=m'$ ?

$n=m'$ is impossible under these assumptions, but $n \in m \lor n=m$ trivially implies $n \in m\cup\{m\} \lor n=m\cup\{m\}$.

If $n \not\subset m$ how do we conclude that $m \in n$ ?

Sorry, not going to answer this.

 

[evinda]

$n=m'$ is impossible under these assumptions, but $n \in m \lor n=m$ trivially implies $n \in m\cup\{m\} \lor n=m\cup\{m\}$.

Do we conclude $n=m\cup\{m\}$ from a relation or do we just claim that it could be like that? (Thinking)

Sorry, not going to answer this.

It is like that, right?

$n \subset m \cup \{m \}$

But we have assumed that $n \not\subset m$. Therefore it must hold $n \cap \{m\} \neq \varnothing \Rightarrow m \in n$.

 

[Evgeny.Makarov]

Do we conclude $n=m\cup\{m\}$ from a relation or do we just claim that it could be like that?

I don't know what relation you have in mind and what you mean by "be like that". I said that $n=m'$ is impossible if $n \in m \lor n=m$.

It is like that, right?

$n \subset m \cup \{m \}$

But we have assumed that $n \not\subset m$. Therefore it must hold $n \cap \{m\} \neq \varnothing \Rightarrow m \in n$.

Yes.

 

[evinda]

I don't know what relation you have in mind and what you mean by "be like that". I said that $n=m'$ is impossible if $n \in m \lor n=m$.

I am sorry.. I didn't notice that... (Tmi)

How can we use the fact that $m \in n$ in order to conclude that $n \in m' \lor n=m'$ ? (Thinking)

 

[Evgeny.Makarov]

How can we use the fact that $m \in n$ in order to conclude that $n \in m' \lor n=m'$ ?

See post #2.

 

[evinda]

You could show $n\subseteq m\implies n\in m\lor n=m$ by induction on $m$. The difficult case is when $n\subseteq m\cup\{m\}$ and $n\not\subseteq m$. This means that $m\in n$. In usual notation, this means $n\le m+1$ and $m<n$, so $n=m+1$. To prove $n=m\cup\{m\}$ it is sufficient to show $\forall x\in m\;x\in n$, but this follows from $m\in n$ and transitivity of $n$.

Could you exlain me further why in order to show that $n=m\cup\{m\}$ we have to show that $\forall x\in m\;x\in n$? (Thinking)

 

[Evgeny.Makarov]

Because you assumed that $n\subset m\cup\{m\}$ as the first thing in the induction step and, for the converse inclusion, you also concluded that $m\in n$.

 

[evinda]

I haven't understood it yet why we have to show that $\forall x \in m \ \ x \in n$.(Worried)

 

[Evgeny.Makarov]

You could try proving $n=m\cup\{m\}$ in a different way.

 

[evinda]

You could try proving $n=m\cup\{m\}$ in a different way.

How else could we prove it? (Thinking)

 

[Evgeny.Makarov]

I personally have not come up with another way. Your other latest questions are very easy to answer and you should try to collect all that that has been said in this thread and think harder.

 

[evinda]

I personally have not come up with another way. Your other latest questions are very easy to answer and you should try to collect all that that has been said in this thread and think harder.

Could we say that $n \le m+1 \iff n \le m \lor n = m+1$ ?
If so how could we show formally that $n \le m$ is impossible given $m < n$? (Thinking)

 

[Evgeny.Makarov]

Could we say that $n \le m+1 \iff n \le m \lor n = m+1$ ?

If you mean using standard concept of $\le$ on natural numbers, then of course. If you mean the definition of $\le$ using $\subset$ or $\in$, then this is correct as well, but if you plan to use this fact in your proof, you need to prove it as well.

 

[evinda]

If you mean using standard concept of $\le$ on natural numbers, then of course. If you mean the definition of $\le$ using $\subset$ or $\in$, then this is correct as well, but if you plan to use this fact in your proof, you need to prove it as well.

So you mean that we have to prove that $n \in m \Rightarrow n<m $ and $n \subset m \Rightarrow n \leq m$ ? (Thinking)

 

[Evgeny.Makarov]

So you mean that we have to prove that $n \in m \Rightarrow n<m $ and $n \subset m \Rightarrow n \leq m$ ?

I don't know why you brought up $<$ and $\le$. The original problem does not have them.

 

[evinda]

Could you maybe explain me further why we have to show that $\forall x \in m \ \ x \in n$ ? (Thinking)

 

[Evgeny.Makarov]

That's how you show that two sets are equal: by showing that each is a subset of the other.

 

[evinda]

We know that $n \subset m \cup \{m\}$ and we want to prove that $n=m'$.
So doesn't it suffice to show that $m \cup \{m\} \subset n$ ?
If so we have $m \cup \{m\} \subset n \leftrightarrow m \subset n \wedge \{m\} \subset n$.

We know that $\{m\} \subset n$ because of the fact that $m \in n$, right?

But we cannot conclude something for $m \in n$ from our induction hypothesis, right?

 

[Evgeny.Makarov]

We know that $n \subset m \cup \{m\}$ and we want to prove that $n=m'$.
So doesn't it suffice to show that $m \cup \{m\} \subset n$ ?
If so we have $m \cup \{m\} \subset n \leftrightarrow m \subset n \wedge \{m\} \subset n$.

We know that $\{m\} \subset n$ because of the fact that $m \in n$, right?

Yes.

But we cannot conclude something for $m \in n$ from our induction hypothesis, right?

I am not sure what you mean. Please see post #11.

 

[evinda]

I haven't understood from which relation we can conclude that $m \subset n$.
We have shown that $m \in n$ but we cannot dedude from that that $m \subset n$ because that's what we want to prove.
Or am I wrong?

 

[Evgeny.Makarov]

I haven't understood from which relation we can conclude that $m \subset n$.

A note about terminology. You can conclude some fact only from another fact. Some synonyms of the word fact are proposition, statement, claim. Some statements can serve as assumptions, or premises. In contrast, a relation is a subset of a Cartesian product, or, equivalently, a function (usually taking two arguments) to the set $\{T,F\}$. A relation is not a proposition, so it cannot imply anything. If you are using the word relation in a different sense, it may create confusion.

We have shown that $m \in n$ but we cannot dedude from that that $m \subset n$ because that's what we want to prove.

To prove $n=m\cup\{m\}$ it is sufficient to show $\forall x\in m\;x\in n$, but this follows from $m\in n$ and transitivity of $n$.

 

[evinda]

I got it.. Thank you very much! (Happy)