Hilbert–Bernays paradox

Hilbert–Bernays paradox
Name	Hilbert–Bernays paradox
Field	Mathematical logic, Set theory
Discovered by	David Hilbert, Paul Bernays
Date	1934

Hilbert–Bernays paradox is a logical paradox discovered in the 1930s that reveals a contradiction in certain formulations of naive set theory and semantics. It is closely related to, but distinct from, the more famous Berry paradox and Richard's paradox, and it played a significant role in the development of modern axiomatic set theory. The paradox demonstrates the dangers of allowing unrestricted comprehension principles for defining sets and influenced subsequent work on type theory and proof theory.

Statement of the paradox

The Hilbert–Bernays paradox arises from considering the set of all natural numbers that can be uniquely characterized by a propositional function of the language of set theory containing fewer than a given number of symbols. Informally, it considers the smallest natural number not definable by a proposition with fewer than, say, one hundred symbols. The description of this number itself becomes a proposition with fewer than one hundred symbols, leading to a contradiction. This formulation highlights issues with self-reference and the definability of objects within a formal system, akin to problems explored in the Liar paradox and Grelling–Nelson paradox.

Historical context and development

The paradox was formulated by David Hilbert and his assistant Paul Bernays around 1934, during their collaboration on the monumental work Grundlagen der Mathematik. This period was a fertile time in foundations of mathematics, following the seismic impact of Gödel's incompleteness theorems and the ongoing efforts to secure a consistent foundation for all of mathematics through Hilbert's program. The discovery emerged from their investigations into the limits of formal systems and the nature of definable real numbers, work that was contemporaneous with and influenced by Alonzo Church, Kurt Gödel, and Alfred Tarski.

Mathematical details and proof

Formally, let the formal language have a finite alphabet, such as that of Zermelo–Fraenkel set theory. For a given number \(k\), consider the set \(D_k\) of natural numbers definable by a formula with fewer than \(k\) symbols. Since there are only finitely many such formulas, \(D_k\) is finite. Therefore, there exist natural numbers not in \(D_k\); let \(n\) be the least such number. The phrase "the least natural number not definable by a formula with fewer than \(k\) symbols" itself constitutes a definition. For sufficiently large \(k\), this defining phrase can be expressed in fewer than \(k\) symbols, implying \(n\) is in \(D_k\) after all, a contradiction. This reasoning hinges on the assumption that the notion of "definable in the language" is itself expressible within the language, a key point later addressed by Alfred Tarski in his work on the undefinability of truth.

Philosophical implications

The paradox challenged the logicist view that all mathematical concepts could be reduced to purely logical ones without contradiction. It underscored the critical distinction between a language and its metalanguage, a central theme in the work of Alfred Tarski and W.V. Quine. Furthermore, it contributed to philosophical debates about the nature of reference and meaning, influencing later thinkers in the analytic philosophy tradition. The paradox demonstrated that intuitive notions of definability could lead to antinomies if treated without formal care, reinforcing the need for rigorous axiomatization.

Relationship to other paradoxes

The Hilbert–Bernays paradox is a member of the family of semantic paradoxes that also includes the Berry paradox, Richard's paradox, and the Liar paradox. It shares with the Berry paradox a focus on the definability of numbers using a limited number of words or symbols. It is structurally similar to Richard's paradox, which involves definable real numbers. However, it is distinct from the purely set-theoretic Russell's paradox and the Burali-Forti paradox, which deal directly with the foundations of set theory. Its resolution is closely tied to insights gained from Gödel's incompleteness theorems.

Resolutions and impact

The primary resolution, following Alfred Tarski, is to recognize that the predicate "is definable" cannot be consistently expressed within the same object language; it belongs to a stronger metalanguage. This insight was formalized in Tarski's undefinability theorem. Consequently, modern axiomatic set theory, such as Zermelo–Fraenkel set theory, avoids the paradox by not having an unrestricted comprehension axiom and by carefully distinguishing between object language and metalanguage. The paradox's impact was significant in shaping recursion theory and the study of definable sets, influencing the work of Stephen Cole Kleene and the development of Gödel's constructible universe.

Category:Paradoxes Category:Mathematical logic Category:Set theory