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?

  • 1
    $\begingroup$ Yes; see e.g.Enderton, Mathematical Logic, Ch.1.4 Induction and Recursion. $\endgroup$ – Mauro ALLEGRANZA Mar 20 at 16:38
  • 1
    $\begingroup$ 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." $\endgroup$ – Mauro ALLEGRANZA Mar 20 at 16:44
  • $\begingroup$ Thanks @MauroALLEGRANZA, very helpful. Will look into those. $\endgroup$ – The Footprint Mar 20 at 16:46
  • 2
    $\begingroup$ 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. $\endgroup$ – Rob Arthan Mar 20 at 20:41

Well, not familiar with your argument. But the induction axiom goes in the direction of maximality.

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$.

  • $\begingroup$ I don't see how a proof by maximality can be turned into one by induction, though. $\endgroup$ – The Footprint Mar 20 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.