1 \chapter{Inductively Defined Sets} \label{chap:inductive}
2 \index{inductive definitions|(}
4 This chapter is dedicated to the most important definition principle after
5 recursive functions and datatypes: inductively defined sets.
7 We start with a simple example: the set of even numbers. A slightly more
8 complicated example, the reflexive transitive closure, is the subject of
9 {\S}\ref{sec:rtc}. In particular, some standard induction heuristics are
10 discussed. Advanced forms of inductive definitions are discussed in
11 {\S}\ref{sec:adv-ind-def}. To demonstrate the versatility of inductive
12 definitions, the chapter closes with a case study from the realm of
13 context-free grammars. The first two sections are required reading for anybody
14 interested in mathematical modelling.
17 Predicates can also be defined inductively.
18 See {\S}\ref{sec:ind-predicates}.
21 \input{Inductive/document/Even}
22 \input{Inductive/document/Mutual}
23 \input{Inductive/document/Star}
25 \section{Advanced Inductive Definitions}
26 \label{sec:adv-ind-def}
27 \input{Inductive/document/Advanced}
29 \input{Inductive/document/AB}
31 \index{inductive definitions|)}