The Meaning of "Higher Order"

The phrase "higher order" is used throughout logic and computer science, though not necessarily with a precise or consistent meaning in all cases.

In logic, first-order quantification refers to the kind of universal and existential (\(\forall\) and \(\exists\)) quantifiers that you see in CS 2800. These let you quantify over some domain of interest, such as the natural numbers. But for any given quantification, say \(\forall x\), the variable being quantified represents an individual element of that domain, say the natural number 42.

Second-order quantification lets you do something strictly more powerful, which is to quantify over properties of the domain. Properties are assertions about individual elements, for example, that a natural number is even, or that it is prime. In some logics we can equate properties with sets of individual, for example the set of all even naturals. So second-order quantification is often thought of as quantification over sets. You can also think of properties as being functions that take in an element and return a Boolean indicating whether the element satisfies the property; this is called the characteristic function of the property.

Third-order logic would allow quantification over properties of properties, and fourth-order over properties of properties of properties, and so forth. Higher-order logic refers to all these logics that are more powerful than first-order logic; though one interesting result in this area is that all higher-order logics can be expressed in second-order logic.

In programming languages, first-order functions similarly refer to functions that operate on individual data elements (e.g., strings, ints, records, variants, etc.). Whereas higher-order function can operate on functions, much like higher-order logics can quantify over over properties (which are like functions).

results matching ""

    No results matching ""