Concept

Second-order logic

Logic whose quantifiers may range over sets and relations of objects, not only over the objects themselves. Its existential part describes exactly the problems whose solutions can be checked quickly, and on infinite structures it can pin down the whole numbers up to isomorphism.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Where a word of m letters stops being distinguishable from one of m + 1. A row for each quantifier depth and a cell for each length, shaded where Duplicator survives the game between words of that length and one longer.

A language that can name a set

Allow a sentence to quantify over sets of positions as well as positions, and on words the answer changes completely: the sets buy exactly the languages a finite automaton recognises. Whether the number of letters is even is the smallest example of what the sets are for.

logic · Ehrenfeucht–Fraïssé games

Three-colourability as a sentence: there exist three sets such that …. Petersen graph coloured with three colours; witness sets R = {0,2,6}, G = {1,3,5,9}, B = {4,7,8}; all 25 first-order checks pass.

There is a relation such that

A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.

logic · Quantifiers

Named alongside it

The objects these essays reach for when they reach for this one.

Ehrenfeucht fraisse game Exhaustive search Finite automaton Graph colouring Monoid NP-hard Quantifier Quantifier depth Regular language

All concepts