The following is written in the first chapter of Shoenfeld's text on mathematical logic.

"...suppose that a collection C is defined by a generalized inductive definition. Then in order to prove that every object in C has property P, it suffices to prove that the objects having property P satisfy the laws of the definition. Such a proof is called a proof by induction on objects in C".

Am I wrong to think that this is mistaken? Wouldn't this be merely showing that objects with property P belong to C, rather than showing that objects in C have property P?

  • $\begingroup$ You are mistaken. The $C$ is defined by the induction, meaning that every element in $C$ can be specified by an induction. $\endgroup$ – David G. Stork Nov 2 '20 at 21:09

The phrase "laws of the definition" is a bit slippery. What it means is that:

  • $C$ is defined as the smallest set of objects with some closure properties (including containment of some "basic objects" analogous to the base case of an induction proof).

  • If we then show that the set of things having property $P$ satisfies the same closure properties (including the containment of the same "basic objects"), then we have $C\subseteq P$.

For a very silly example, the set $C$ of even natural numbers is the smallest set of natural numbers containing $0$ and closed under the operation $x\mapsto 2+x$. Let $P$ be the property "Is a multiple of $2$ or is $>17$ (or both)." Then we have $P(0)$, and $P(x)\rightarrow P(2+x)$ for all $x$; so $C\subseteq P$.

  • $\begingroup$ Your $C$ would rather be $\{0\}$ $\endgroup$ – Hagen von Eitzen Nov 2 '20 at 21:11
  • $\begingroup$ @HagenvonEitzen Derp, fixed! $\endgroup$ – Noah Schweber Nov 2 '20 at 21:12

Your Answer

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