Formalized attempt of proof that well ordered-ness ( of subsets of $\mathbb{Z}$ that are bounded below) implies induction seems to have issue?

Question

I want to prove that well-orderedness on the integers implies induction. The proof is the classical "assume a contradiction" and see what happens.

So begin with an intended contradiction:

\begin{align*} &\quad A\subset\mathbb{Z} \;\wedge\; 0\in A \;\wedge\; (n\in A \implies (n+1)\in A) \;\;\implies\;\; \neg \mathbb{N}\subset A \\ &\quad\text{...unpacking definition of $\neg\mathbb{N}\subset A$...} \\ &= A\subset\mathbb{Z} \;\wedge\; 0\in A \;\wedge\; (n\in A \implies (n+1)\in A) \;\;\implies\;\; \exists n\in \mathbb{N} \;s.t. \neg n\in A \\ &\quad\text{...definition of bunches...} \\ &= A\subset\mathbb{Z} \;\wedge\; 0\in A \;\wedge\; (n\in A \implies (n+1)\in A) \;\;\implies\;\; \exists B\subset \mathbb{N} \;s.t. |B| > 0 \;\wedge\; &&B\cap A = \emptyset \end{align*}

Working within the context of what has been proven so far, we let $c$ be the minimal element of the non-empty set $B$:

\begin{align*} &\quad (c = \min B) \\ &\quad\text{...$0\in A \wedge B\cap A = \emptyset$...}\\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; c > 0 \\ &\quad\text{...algebra...}\\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; c - 1 > -1 \\ &\quad\text{...properties of $>$ and $\geq$...}\\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; c - 1 \geq 0 \\ &\quad\text{...definition of $\geq$...} \\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; (c - 1 = 0 \vee c > 0) \\ &\quad \text{...$0\in A$...} \\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; [(c - 1 = 0 \implies c - 1\in A) \vee c > 0] \\ &\quad\text{...$n-1\in A \implies n\in A$...} \\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; [(c - 1 = 0 \implies c - 1\in A \implies c\in A) \vee c > 0] \\ &\quad\text{...transitivity of $\implies$...}\\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \;\wedge\; [(c - 1 = 0 \implies c\in A) \vee c > 0]\\ &\quad\text{...distributivity of $\wedge$ over $\vee$...}\\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \wedge (c - 1 = 0 \implies c\in A) \vee \neg (c\in A) \wedge c > 0 \\ &\quad\text{...contrapositive law...}\\ &= c = \min B \;\;\implies\;\; \neg (c\in A) \wedge (\neg(c\in A) \implies \neg(c - 1 = 0)) \vee \neg (c\in A) \wedge c > 0 \\ &\quad\text{...law of discharge...} \\ &= c = \min B \;\;\implies\;\; \neg(c\in A) \wedge \neg(c - 1 = 0) \vee \neg (c\in A) \wedge c > 0 \\ &\quad\text{...De Morgan's Law...} \\ &= c = \min B \;\;\implies\;\; \neg(c \in A \vee c - 1 = 0) \;\vee\; \neg (c \in A) \wedge c > 0 \\ &\quad\text{...De Morgan's Law...} \\ &= c = \min B \;\;\implies\;\; \neg(c \in A \vee c - 1 = 0) \;\vee\; \neg ((c \in A) \vee c \leq 0) \\ &\quad\text{...De Morgan's Law...} \\ &= c = \min B \;\;\implies\;\; \neg[(c \in A \vee c - 1 = 0) \wedge (c \in A \vee c \leq 0)] \\ &\quad\text{...factoring out $c:A$...} \\ &= c = \min B \;\;\implies\;\; \neg[c \in A \vee (c - 1 = 0 \wedge c \leq 0)] \\ &\quad\text{...algebra...} \\ &= c = \min B \;\;\implies\;\; \neg[c \in A \vee (c = 1 \wedge c \leq 0)] \\ &\quad\text{...integer properties...} \\ &= c = \min B \;\;\implies\;\; \neg[c \in A \vee \bot] \\ &\quad\text{...definition of $\vee$...} \\ &= c = \min B \;\;\implies\;\; \neg(c \in A) \end{align*}

I am supposed to get a simpler contradiction, which is that $c = \min B \wedge c \in A$. Formally, I do not get this. What is my error?

Answer 1

It seems that you're trying to prove that $$\forall A,\Bigl[(A\subseteq\Bbb Z)\wedge(0\in A)\wedge\bigl((n\in A)\longrightarrow (n+1\in A)\bigr)\Bigr]\longrightarrow \Bbb N\subseteq A.$$

Sadly, if this is indeed what you're trying to show, you got off to a bad start.

Recall that for statements $p,q,$ we have that $p\longrightarrow q$ is equivalent to $q\vee\neg p.$ On the one hand, then, $p\longrightarrow\neg q$ is equivalent to $\neg q\vee\neg p,$ or $\neg(p\wedge q).$ On the other hand, $\neg(p\longrightarrow q)$ is equivalent to $\neg(q\vee\neg p),$ or $p\wedge\neg q.$ But $p\wedge\neg q$ is a strictly stronger statement than $\neg(p\wedge q)$--that is, $p\wedge\neg q$ implies $\neg(p\wedge q),$ but the converse implication doesn't hold--so you've erred in your negation in the first step. Instead, you should start with the assumption $$\exists A:\Bigl[(A\subseteq\Bbb Z)\wedge(0\in A)\wedge\bigl((n\in A)\longrightarrow (n+1\in A)\bigr)\Bigr]\wedge\neg(\Bbb N\subseteq A).$$

Can you take it from there?

Answer 2

Your style of proof is close to unreadable, making so much of trivial logical equivalences that the underlying idea, if any, is very difficult go get sight of. There's too many trees to see your forest.

That being said, the usual way to argue that well-orderedness of $\mathbb N$ (not $\mathbb Z$!) implies induction would be something like:

1. Assume (as you do) that $A\subseteq \mathbb N$ satisfies $0\in A$ and $\forall n\in\mathbb N.n\in A\to n+1\in A$. Further assume (for a contradiction) that $A\ne \mathbb N$.

2. $B=\mathbb N\setminus A$ must be nonempty because otherwise $A=\mathbb N$.

3. Because of well-ordering, $B$ contains a minimal element $c$.

4. Since we're assuming $0\in A$, we must have $c\ne 0$. But then $c=d+1$ for some $d\in \mathbb N$.

5. Because $d<c$ and $c$ was minimal in $B$, $d\notin B$. But then $d\in A$.

6. By the induction-step assumption this implies that $c=d+1\in A$.

7. But if $c\in A$ then $c\notin B$, which contradicts how we picked $c$.