Example:Inductive definition of the set of expressions

Mathematical expressions of various kinds are often defined inductively. For example, one might define a set of arithmetic expressions by the rules

Here, we are treating "+", "*", and "-" as uninterpreted symbols. For example, [math](3 + (4*5)) + (-2) [/math] is an expression, formed from the substructures [math](3+(4*5)) [/math] and [math](-2) [/math] using the "+" rule. Most programming languages have a similar inductive definition, allowing us to formally model programs.