# Possible typo in Shoenfeld's Mathematical Logic?

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?

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

## 1 Answer

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

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