Prove the Principle of Complete Induction

107 Views Asked by At

The question is stated as:

Prove the Principle of Complete Induction $$(\forall B)([B \subseteq P \land (\forall x)((\forall y)(y<x \Rightarrow y \in B)\Rightarrow x \in B)] \Rightarrow P=B)$$ (Hint: Assume $P \neq B$. Then, $P-B \neq \emptyset$. Apply the Least Number Principle. Notice that, when $x=1$, $(\forall y)(y<x \Rightarrow y \in B)$ is trivially true, since $y<1$ is always false.)

The set $P$ here is a set from a Peano System $(P,S,1)$.

Here is my atempt:

Let $B$ be a some subset of $P$ where $(\forall x)((\forall y)(y<x \Rightarrow y \in B)\Rightarrow x \in B)$ holds true, the if $x=1$ we get $(\forall y)(y<1 \Rightarrow y \in B)$ which is trivially true, then $1 \in B$.

Now assume $x \in B$ thus, $(\forall y)(y < x \Rightarrow y \in B)$. If we take $S(x)$ we have that $(\forall y)(y < x < S(x))$, but as we have $x \in B$ by assumption we have also $(\forall y)(y < S(x) \Rightarrow y \in B)$ which implies $S(x) \in B$, and therefore $x \in B \Rightarrow S(x) \in B$, then by mathematical induction $P=B$.

Edit 1: Trying to use the author hint

Let $B$ be a subset of $P$ where, $(\forall x)((\forall y)(y<x \Rightarrow y \in B)\Rightarrow x \in B)$ holds true.

Assume $B \neq P$ and let $A=P-B$, so $A \neq \emptyset$, as $A \subseteq P \land A \neq \emptyset$ then $A$ have a least element that is $(\exists z)(z \in A \land (\forall u )(u \in A \Rightarrow z \leq u))$

We have as a Theorem in Peano System that $(\forall x)(x=1 \lor (\exists p)(x=S(p)))$

Thus taking $z$ as the least element of $A$ we have that $z=1 \lor (\exists p)(z = S(p))$, if we suppose $z=1$, then $1 \in A$, so $1 \notin B$, thus $(\exists y)(y<1 \land y \notin B)$ which is clearly false, thuse we have that $z \neq 1$.

But if $z=S(p)$ for some $p$ in $P$, we have that $S(p) \in A$ then $S(p) \notin B$ and from this $(\exists y)(y<S(p) \land y \notin B)$, but if $y \notin B$ we have that $y \in A$. But if $(y<S(p) \land y \in A)$ then $S(p)$ cant be the least element of $A$ which is a contradiction.

Edit 1 end

I think I have missed the point in this exercise, because I cant manage to use the Least Number Principle at all and that was the hint from the author, my proof is valid? and how can I use ths Least Number Principle in this case?

1

There are 1 best solutions below

4
On BEST ANSWER

Here is the argument that the OP is looking for (we've eliminated the quantifiers and formal presentation to focus on the main proof 'flow').

The set $B$ satisfies the (complete/strong) induction hypotheses.

Assume $B \subsetneq P$ and let

$\tag 1 m = \text{min}(P \setminus B)$

Then

$\tag 2 x \lt m \Rightarrow x \in B$

is true (otherwise $m$ wouldn't be the minimum number).

By the inductive hypyotheis $m\in B$, but that (also) contradicts $\text{(1)}$.

So assuming $B \subsetneq P$ leads to a contradiction, and so $B = P$.