Second-order logic can say things first-order logic cannot, such as describing ancestors

Second-order logic can say things first-order logic cannot, such as describing ancestors
Image: Intellect (generated)

In short: Ordinary logic can talk about individual things but not about properties or collections of them. Second-order logic extends the reach by allowing quantification over relations and sets. That single change lets it express ideas like ancestry, reachability and the exact identity of mathematical structures, which first-order logic simply cannot capture.

In logic, first-order logic lets us quantify over individuals, so we can say that something exists with a given property. However, we cannot quantify over the properties themselves. Second-order logic adds variables that range over sets of individuals and over relations among them. This means a sentence can assert that some collection of things exists, without naming it in advance. For example, it can state that a set containing exactly the cubes and tetrahedrons exists, and then make claims about that set, such as that it contains no dodecahedrons.

A particularly useful capability is expressing reachability. If one person is a parent of another, first-order logic cannot state that someone is an ancestor of another. Second-order logic handles this by saying that every set of people which contains the later person and is closed under the parent relation must also contain the earlier person. The same expressive power lets it state the induction axiom of Peano arithmetic as one sentence, where first-order logic needs an infinite family of axioms.

The field distinguishes several variants. Weak second-order logic allows quantification only over finite sets. Monadic second-order logic restricts quantification to unary relations, meaning sets, and it is central to Courcelle's theorem in graph theory. Full second-order logic is stronger still. Monadic logic over the complete infinite binary tree is decidable, but full second-order logic over any infinite set can interpret true second-order arithmetic and is therefore undecidable.

Second-order logic also has two commonly used semantics, standard and Henkin. The difference lies only in how the ranges of second-order quantifiers are interpreted, while first-order quantifiers and connectives work the same in both. The existence of these choices is one reason the subject remains an active area of study, as its strength and its limits are closely tied to exactly which semantics is adopted.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-second-order-logic.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…