# Are proofs by “maximality” equivalent to proofs by induction?

I apologize for the lack of proper terminology; I have zero experience in this field.

What I mean by "proof by maximality": One way to show that a set $$A$$ has a certain property $$p$$ is to assume there is a largest proper subset $$X \subsetneq A$$ which verifies $$p$$ and then show that there is another subset of $$A$$ larger than $$X$$, $$Y\supsetneq X$$, which also verifies $$p$$, a contradiction. Then one concludes that $$A$$ verifies $$p$$.

Now, these kinds of proofs seem strikingly similar to proofs by induction, where one assumes that a proposition holds for $$n$$ (i.e. $$n$$ is the largest number that verifies it) and then proves that it must hold for $$n+1$$ as well and therefore, by the principle of induction, it is true for all the elements of $$\mathbb{N}.$$ The "base case" is similar as well, since in proofs by "maximality" one first has to show that there exists a subset verifying the property $$p$$.

I was wondering if there is a link between these two proof techniques and, if at all, how one can be turned into the other. I am having trouble trying to formalize this. Where can I learn more about it?

• Yes; see e.g.Enderton, Mathematical Logic, Ch.1.4 Induction and Recursion. – Mauro ALLEGRANZA Mar 20 at 16:38
• See Structural induction : "a proof method used in mathematical logic that is a generalization of mathematical induction used to prove that some proposition $P(x)$ holds for all elements of some sort of recursively defined structure, such as formulas, lists, or trees." – Mauro ALLEGRANZA Mar 20 at 16:44
• Thanks @MauroALLEGRANZA, very helpful. Will look into those. – The Footprint Mar 20 at 16:46
• The principle you describe is invalid unless $A$ is finite. The structural induction principles referred to by Mauro assume some restriction on the subsets $X \subseteq A$. E.g., your principle is valid for all finite subsets of the natural numbers but not valid for all subsets of the natural numbers. Being finite is a property that satisfies the conditions of your principle - there is no maximal finite set of natural numbers. But not every set of natural numbers is finite. – Rob Arthan Mar 20 at 20:41

Let $${\Bbb N}_0$$ be the set of natural numbers. Let $$N$$ be a subset of $${\Bbb N}_0$$ such that $$0\in N$$ and with each $$n\in N$$ we have $$n+1\in N$$. Then $$N = {\Bbb N}_0$$.