Here is a claim that sounds almost obviously false. Work inside the real numbers, using only addition, multiplication, and the full machinery of first-order logic. You cannot write a formula that picks out exactly the integers. Clever quantifiers will not help, and neither will any finite string of symbols. The integers sit right there among the reals, yet the language cannot point to them.

This is not a failure of imagination. It is a theorem, and it belongs to a family of results about definability. Definability studies which sets, relations, and properties a given logical language can express inside a given mathematical structure. It asks a deceptively simple question: given a vocabulary and a world, what can you actually say?

The answers are precise and frequently surprising. Some languages are too weak to express notions we consider elementary. Others are strong enough to talk about themselves, and that very strength forces certain concepts, truth among them, out of reach. Following the thread leads from basic definitions to the liar paradox and, remarkably, to the P versus NP problem.

We begin with the setting. A structure is a set equipped with named operations and relations. Examples include the natural numbers with addition, the real numbers with addition and multiplication, and a graph with its edge relation. First-order logic builds formulas from these names using the connectives and, or, and not, together with quantifiers that range over elements of the set.

A subset X of the structure is definable if some formula φ(x) holds of an element exactly when that element belongs to X. We may also allow parameters, which are fixed elements of the structure plugged into the formula. The definition extends naturally to relations through formulas with several free variables. In (ℕ, +), the even numbers are defined by ∃y (x = y + y). In (ℝ, +, ·), the ordering is definable: x ≤ y holds precisely when ∃z (y = x + z·z), because the nonnegative reals are exactly the squares.

Proving that something is not definable requires a different strategy, since no number of failed attempts constitutes a proof. Instead, one proves a structural theorem about all definable sets at once. Tarski showed that in the real field, every definable subset of ℝ is a finite union of points and intervals. The integers form infinitely many isolated points, so they are no such union. Therefore they are not definable. Similarly, in the complex field every definable subset of ℂ is either finite or has finite complement. Consequently, the real line itself is invisible to the language of complex arithmetic.

This is the characteristic pattern of the subject. Expressive power is measured not by what one particular formula achieves, but by a classification of everything formulas can achieve. Once that classification is in hand, impossibility follows by inspection. The hard work moves from searching for a definition to understanding the whole landscape of definitions.

Takeaway

To prove that something cannot be said, do not search for the sentence. Characterise everything that can be said, then show your target lies outside it.

Now turn to arithmetic: the natural numbers with addition and multiplication. This structure is vastly more expressive than the real field. Primality is definable, and so is every computably enumerable set. Through Gödel numbering, formulas themselves become numbers, so arithmetic can speak about its own sentences. One might therefore expect it to define the set of true ones.

Tarski's undefinability theorem says it cannot. Suppose a formula True(x) held exactly of the codes of true arithmetic sentences. The diagonal lemma, the same self-referential engine behind Gödel's incompleteness theorems, produces a sentence L equivalent to ¬True(⌜L⌝). In words, L asserts its own untruth. If L is true, then True holds of its code, so L is false. If L is false, then True fails of its code, so L is true. Both cases are contradictory. Therefore no such formula exists.

Note precisely what the argument forbids. Provability is definable in arithmetic, because checking a proof is a mechanical process. Truth is not definable. Consequently, truth and provability must differ, and incompleteness follows almost immediately. Moreover, truth is definable piecewise: for each fixed bound on quantifier complexity, some formula defines truth for sentences of that complexity. What fails is a single formula covering every level at once.

The same pattern recurs elsewhere. In set theory, truth in the universe of sets cannot be defined within that universe. The liar paradox, once a curiosity of natural language, becomes an exact theorem. A language rich enough to describe its own syntax cannot contain its own truth predicate.

Takeaway

A system that can describe itself pays for that power. The more a language can say about its own sentences, the more certain it becomes that one crucial concept lies just beyond its reach.

Restrict attention to finite structures, such as graphs, and a striking correspondence appears. Instead of asking whether a property is definable, ask how hard it is to compute. Descriptive complexity shows that these are often the same question in different clothing.

The founding result is Fagin's theorem of 1974. A property of finite structures belongs to NP exactly when it is expressible in existential second-order logic, which permits quantifying over relations before a first-order formula. Three-colourability illustrates this neatly. A graph is three-colourable if there exist sets R, G, and B covering every vertex such that no edge joins two vertices in the same set. The second-order quantifiers guess a certificate, and the first-order part verifies it. That is precisely the shape of an NP computation.

Further correspondences followed. Immerman and Vardi showed that on ordered finite structures, polynomial time coincides with first-order logic extended by a least fixed-point operator, which captures recursive definitions. Plain first-order logic, by contrast, is weak. It cannot express that a finite graph is connected, nor that its number of vertices is even. These limits are proved with Ehrenfeucht–Fraïssé games, a combinatorial technique showing that two structures satisfy the same sentences up to a given quantifier depth.

The consequence is profound. Whether P equals NP is equivalent to whether two logics have the same expressive power on ordered finite structures. A question about machines, time, and resources becomes a question about which formulas can say what. Computational cost, it turns out, can be measured in logical vocabulary.

Takeaway

Asking how hard a problem is to solve and asking what logic is needed to state it may be the same question viewed from two sides.

Definability replaces vague questions about expressiveness with exact ones. Fix a structure and a language, and the definable sets form a precise collection whose boundaries can be mapped.

Those boundaries are established by proof, not by exhaustion. The integers are absent from the real field because of a classification theorem. Truth escapes arithmetic because of a diagonal argument. Connectivity escapes first-order logic because of a game. Each result is as permanent as any theorem in mathematics.

There is a quiet satisfaction in this. Certainty about the limits of a language is still certainty. To know exactly what cannot be said is itself substantial knowledge, built brick by brick from definitions to theorems.