5.5 Limitations of First Order Logic

First order logic has strong structural properties such as compactness and the Lowenheim Skolem theorems, and these properties impose intrinsic limitations on what can be expressed or uniquely characterized within the language.

Definition 5.27 (Expressibility)

A class of structures $\mathcal{K}$ is said to be first order definable if there exists a set of first order sentences $\Gamma$ such that:

\mathcal{M} \in \mathcal{K} \quad \text{if and only if} \quad \mathcal{M} \models \Gamma

Thus definability means that membership in the class can be described entirely by first order properties.

Failure to Express Finiteness

One of the most fundamental limitations is that finiteness cannot be expressed in first order logic.

Suppose, for contradiction, that there exists a set of sentences $\Gamma$ such that a structure satisfies $\Gamma$ exactly when it is finite.

For each natural number $n$ , consider the sentence:

\exists x_1 \cdots \exists x_n \; \bigwedge_{i \neq j} x_i \neq x_j

Add all such sentences to $\Gamma$ .

Every finite subset of this extended theory requires only finitely many distinct elements, and therefore it has a finite model.

By compactness, the entire theory has a model.

This model satisfies all sentences asserting the existence of arbitrarily many distinct elements, so it must be infinite, while at the same time it satisfies $\Gamma$ , so it must be finite.

This contradiction shows that finiteness is not first order definable.

Failure to Control Infinite Cardinalities

Another limitation is that first order logic cannot distinguish between different infinite sizes.

If a theory has an infinite model, then by the Lowenheim Skolem theorems it has models of every infinite cardinality.

Thus no first order theory can characterize structures of exactly one infinite size.

Definition 5.28 (Categoricity)

A theory $\Gamma$ is categorical in a cardinal $\kappa$ if all models of $\Gamma$ of cardinality $\kappa$ are isomorphic.

Categoricity expresses the idea that a theory completely determines the structure of its models at a given size.

Noncategoricity in Infinite Cardinalities

Most first order theories that have infinite models are not categorical across all infinite cardinalities.

For example, the theory of dense linear orders without endpoints is categorical in countable cardinality but has many nonisomorphic uncountable models.

This shows that first order logic cannot uniquely characterize many infinite structures.

Local Nature of First Order Logic

First order logic is local in the sense that formulas can only quantify over finitely many elements at a time.

A formula:

\forall x \exists y \; P(x,y)

speaks about each individual element and the existence of a related element, but it cannot describe global properties such as the total size of the domain or the existence of infinite configurations in a direct way.

This locality explains why compactness holds and why certain global properties cannot be expressed.

Example 5.29 (Graph Connectivity)

Consider the class of connected graphs.

Connectivity is a global property that requires that every pair of vertices is connected by a path.

Although one can write formulas asserting the existence of paths of a fixed finite length, there is no first order sentence that expresses connectivity in general, because paths of arbitrary length may be required.

Thus connectivity is not first order definable.

Example 5.30 (Well Ordering)

The property that a linear order is well ordered means that every nonempty subset has a least element.

This property cannot be expressed in first order logic, because it quantifies over all subsets, while first order logic can only quantify over elements.

Thus well ordering is not first order definable.

Compactness as a Source of Limitations

Compactness implies that if a property fails only in infinite cases, then it cannot be expressed in first order logic.

If a property were expressible and held in all finite structures, then every finite subset of the corresponding theory would be satisfiable.

By compactness, there would exist an infinite model satisfying the same property, which contradicts the assumption that the property fails in infinite structures.

This argument applies to many global properties, including finiteness and certain combinatorial conditions.

Example 5.31 (No Bound on Path Length)

Suppose one tries to express the property that a graph has no cycles.

One can write formulas forbidding cycles of length $n$ for each fixed $n$ .

Each finite subset of these formulas forbids only finitely many cycle lengths, so it is satisfiable by a graph that contains a cycle of larger length.

By compactness, the entire set of formulas has a model, and that model must contain cycles, even though all finite lengths were forbidden.

This shows that the property of being acyclic cannot be captured by finitely many first order sentences.

Beyond First Order Logic

To overcome these limitations, stronger logical systems are considered.

Second order logic allows quantification over subsets, which makes it possible to express properties such as finiteness and well ordering.

However, these stronger systems do not satisfy compactness and often lack complete proof systems, so they behave differently from first order logic.

Conceptual Summary

First order logic achieves a balance between expressive power and desirable meta logical properties such as compactness and completeness.

The limitations described above are a direct consequence of these properties.

While first order logic cannot express certain global features, it remains a powerful and flexible framework for describing and analyzing mathematical structures through their local properties.