MHB Minimal successor set - difficult

  • Thread starter Thread starter Andrei1
  • Start date Start date
  • Tags Tags
    Set
AI Thread Summary
The discussion focuses on proving that for all x, y in ω, either x is a subset of y or y is a subset of x. The initial assumption is that the conclusion is false, leading to the existence of elements a in x and b in y such that a is not in b and b is not in a. There is contemplation on whether to prove that the complement of x or y in ω forms a smaller successor set. The plan includes proving various equivalences related to subset relationships using induction and properties of successor sets. The goal is to establish the relationship between subsets and their successors to ultimately prove the original statement.
Andrei1
Messages
36
Reaction score
0
Prove that for all $$x,y\in\omega,\ \ x\subset y\vee y\subset x.$$

If I assume that the conclusion is false then I can prove that for some $$a\in x,\ b\in y$$ we have $$a\notin b$$ and $$b\notin a.$$

Also I am thinking that if assume the contrary then $$\omega$$ minus $$\{x\}$$ or minus $$\{y\}$$ or both is a smaller successor set. Should I try to prove this?

I get stuck in trying to prove for sets from $$\omega$$ the equivalence: $$a\subseteq b\wedge a\not=b\Leftrightarrow\exists c(a\cup c^+=b)$$.
 
Physics news on Phys.org
Here's the plan.
(1) Prove $$a\subset b^+\Rightarrow b\notin a$$ by induction on $$a.$$ Use also $$x=y\Rightarrow x^+=y^+.$$
(2) Prove $$a\subseteq b\Leftrightarrow a\subset b^+$$. In proving ($$\Leftarrow$$) side use (1). In proving ($$\Rightarrow$$) side use $$x\subset x^+$$, which follows from $$x\notin x.$$
(3) Prove $$b\subset a\Leftrightarrow b^+\subseteq a$$. In proving ($$\Rightarrow$$) side use induction on $$a.$$ Use also $$x=y\Rightarrow x^+=y^+$$ and $$x\subseteq x^+.$$ In ($$\Leftarrow$$) side you need $$x\notin x.$$
(4) Prove $$a\subset b\vee a=b\vee b\subset a$$ by using (2) and (3). Use induction.
 

Similar threads

Back
Top