Access to the full content is only available to members of institutions that have purchased access. If you belong to such an institution, please log in or find out more about how to order.


Print

Inductive definitions and proofs

DOI
10.4324/9780415249126-Y058-1
DOI: 10.4324/9780415249126-Y058-1
Version: v1,  Published online: 1998
Retrieved April 14, 2024, from https://www.rep.routledge.com/articles/thematic/inductive-definitions-and-proofs/v-1

Article Summary

An inductive definition of a predicate R characterizes the Rs as the smallest class which satisfies a basis clause of the form (β(x)→Rx), telling us that certain things satisfy R, together with one or more closure clauses of the form (Φ(x,R)→Rx), which tell us that, if certain other things satisfy R, x satisfies R as well. ’Smallest’ here means that the class of Rs is included in every other class which satisfies the basis and closure clauses.

Inductive definitions are useful because of inductive proofs. To show that every R has property P, show that the class of Rs that have P satisfies the basis and closure clauses.

The closure clauses tell us that if certain things satisfy R, x satisfies R as well. Thus satisfaction of the condition Φ(x,R) should be ensured by positive information to the effect that certain things satisfy R, and not also require negative information that certain things fail to satisfy R. In other words, the condition Φ(x,R) should be monotone, so that, if R ⊆S and Φ(x,R), then Φ(x,S); otherwise, we would have no assurance of the existence of a smallest class satisfying the basis and closure conditions.

While inductive definitions can take many forms, they have been studied most usefully in the special case in which the basis and closure clauses are formulated within the predicate calculus. Initiated by Yiannis Moschovakis, the study of such definitions has yielded an especially rich and elegant theory.

Print
Citing this article:
McGee, Vann. Inductive definitions and proofs, 1998, doi:10.4324/9780415249126-Y058-1. Routledge Encyclopedia of Philosophy, Taylor and Francis, https://www.rep.routledge.com/articles/thematic/inductive-definitions-and-proofs/v-1.
Copyright © 1998-2024 Routledge.

Related Searches

Topics

Related Articles