1.4: B.4- Inductive Definitions

Sets, Logic, Computation · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    1.4: B.4- Inductive Definitions

    In logic we very often define kinds of objects inductively, i.e., by specifying rules for what counts as an object of the kind to be defined which explain how to get new objects of that kind from old objects of that kind. For instance, we often define special kinds of sequences of symbols, such as the terms and formulas of a language, by induction. For a simple example, consider strings of consisting of letters \(\mathrm{a}\), \(\mathrm{b}\), \(\mathrm{c}\), \(\mathrm{d}\), the symbol \(\circ\), and brackets \([\) and \(]\), such as “\([[\mathrm{c} \circ \mathrm{d}][\)”, “\([\mathrm{a}[]\circ]\)”, “\(\mathrm{a}\)” or “\([[\mathrm{a} \circ \mathrm{b}]\circ \mathrm{d}]\)”. You probably feel that there’s something “wrong” with the first two strings: the brackets don’t “balance” at all in the first, and you might feel that the “\(\circ\)” should “connect” expressions that themselves make sense. The third and fourth string look better: for every “\([\)” there’s a closing “\(]\)” (if there are any at all), and for any \(\circ\) we can find “nice” expressions on either side, surrounded by a pair of parentheses.

    We would like to precisely specify what counts as a “nice term.” First of all, every letter by itself is nice. Anything that’s not just a letter by itself should be of the form “\([t \circ s]\)” where \(s\) and \(t\) are themselves nice. Conversely, if \(t\) and \(s\) are nice, then we can form a new nice term by putting a \(\circ\) between them and surround them by a pair of brackets. We might use these operations to define the set of nice terms. This is an inductive definition.

    Definition \(\PageIndex{1}\): Nice terms

    The set of nice terms is inductively defined as follows:

    1. Any letter \(\mathrm{a}\), \(\mathrm{b}\), \(\mathrm{c}\), \(\mathrm{d}\) is a nice term.
    2. If \(s_1\) and \(s_2\) are nice terms, then so is \([s_1 \circ s_2]\).
    3. Nothing else is a nice term.

    This definition tells us that something counts as a nice term iff it can be constructed according to the two conditions (1) and (2) in some finite number of steps. In the first step, we construct all nice terms just consisting of letters by themselves, i.e., \[\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\nonumber\] In the second step, we apply (2) to the terms we’ve constructed. We’ll get \[[\mathrm{a} \circ \mathrm{a}], [\mathrm{a} \circ \mathrm{b}], [\mathrm{b} \circ \mathrm{a}], \dots, [\mathrm{d} \circ \mathrm{d}]\nonumber\] for all combinations of two letters. In the third step, we apply (2) again, to any two nice terms we’ve constructed so far. We get new nice term such as \([\mathrm{a} \circ [\mathrm{a} \circ \mathrm{a}]]\)—where \(t\) is \(\mathrm{a}\) from step 1 and \(s\) is \([\mathrm{a} \circ \mathrm{a}]\) from step 2—and \([[\mathrm{b} \circ \mathrm{c}] \circ [\mathrm{d} \circ \mathrm{b}]]\) constructed out of the two terms \([\mathrm{b} \circ \mathrm{c}]\) and \([\mathrm{d} \circ \mathrm{b}]\) from step 2. And so on. Clause (3) rules out that anything not constructed in this way sneaks into the set of nice terms.

    Note that we have not yet proved that every sequence of symbols that “feels” nice is nice according to this definition. However, it should be clear that everything we can construct does in fact “feel nice”: brackets are balanced, and \(\circ\) connects parts that are themselves nice.

    The key feature of inductive definitions is that if you want to prove something about all nice terms, the definition tells you which cases you must consider. For instance, if you are told that \(t\) is a nice term, the inductive definition tells you what \(t\) can look like: \(t\) can be a letter, or it can be \([s_1 \circ s_2]\) for some pair of nice terms \(s_1\) and \(s_2\). Because of clause (3), those are the only possibilities.

    When proving claims about all of an inductively defined set, the strong form of induction becomes particularly important. For instance, suppose we want to prove that for every nice term of length \(n\), the number of \([\) in it is \(< n/2\). This can be seen as a claim about all \(n\): for every \(n\), the number of \([\) in any nice term of length \(n\) is \(< n/2\).

    Proposition \(\PageIndex{1}\)

    For any \(n\), the number of \([\) in a nice term of length \(n\) is \(< n/2\).

    Proof. To prove this result by (strong) induction, we have to show that the following conditional claim is true:

    If for every \(l < k\), any nice term of length \(l\) has \(l/2\) \([\)’s, then any nice term of length \(k\) has \(k/2\) \([\)’s.

    To show this conditional, assume that its antecedent is true, i.e., assume that for any \(l<k\), nice terms of length \(l\) contain \(< l/2\) \([\)’s. We call this assumption the inductive hypothesis. We want to show the same is true for nice terms of length \(k\).

    So suppose \(t\) is a nice term of length \(k\). Because nice terms are inductively defined, we have two cases: (1) \(t\) is a letter by itself, or (2) \(t\) is \([s_1 \circ s_2]\) for some nice terms \(s_1\) and \(s_2\).

    1. \(t\) is a letter. Then \(k = 1\), and the number of \([\) in \(t\) is \(0\). Since \(0 < 1/2\), the claim holds.
    2. \(t\) is \([s_1 \circ s_2]\) for some nice terms \(s_1\) and \(s_2\). Let’s let \(l_1\) be the length of \(s_1\) and \(l_2\) be the length of \(s_2\). Then the length \(k\) of \(t\) is \(l_1+l_2+3\) (the lengths of \(s_1\) and \(s_2\) plus three symbols \([\), \(\circ\), \(]\)). Since \(l_1+l_2+3\) is always greater than \(l_1\), \(l_1 < k\). Similarly, \(l_2 < n\). That means that the induction hypothesis applies to the terms \(s_1\) and \(s_2\): the number \(m_1\) of \([\) in \(s_1\) is \(< l_1/2\), and the number \(m_2\) of \([\) in \(s_2\) is \(< l_2/2\).

      The number of \([\) in \(t\) is the number of \([\) in \(s_1\), plus the number of \([\) in \(s_2\), plus \(1\), i.e., it is \(m_1 + m_2 + 1\). Since \(m_1 < l_1/2\) and \(m_2 < l_2/2\) we have: \[m_1 + m_2 + 1 < \frac{l_1}{2} + \frac{l_2}{2} + 1 = \frac{l_1+l_2+2}{2} < \frac{l_1+l-2+3}{2} = k/2.\nonumber\]

    In each case, we’ve shown that the number of \([\) in \(t\) is \(< k/2\) (on the basis of the inductive hypothesis). By strong induction, the proposition follows. ◻

    Problem \(\PageIndex{1}\)

    Define the set of supernice terms by

    1. Any letter \(\mathrm{a}\), \(\mathrm{b}\), \(\mathrm{c}\), \(\mathrm{d}\) is a supernice term.
    2. If \(s\) is a supernice term, then so is \([s]\).
    3. If \(s_1\) and \(s_2\) are supernice terms, then so is \([s_1 \circ s_2]\).
    4. Nothing else is a supernice term.

    Show that the number of \([\) in a supernice term \(t\) of length \(n\) is \(\le n/2 +1\).