Absoluteness (logic)

Last updated October 04, 2024

In mathematical logic, a formula is said to be absolute to some class of structures (also called models), if it has the same truth value in each of the members of that class. One can also speak of absoluteness of a formula between two structures, if it is absolute to some class which contains both of them.^{[ clarification needed ]} Theorems about absoluteness typically establish relationships between the absoluteness of formulas and their syntactic form.

There are two weaker forms of partial absoluteness. If the truth of a formula in each substructure N of a structure M follows from its truth in M, the formula is downward absolute. If the truth of a formula in a structure N implies its truth in each structure M extending N, the formula is upward absolute.

Issues of absoluteness are particularly important in set theory and model theory, fields where multiple structures are considered simultaneously. In model theory, several basic results and definitions are motivated by absoluteness. In set theory, the issue of which properties of sets are absolute is well studied. The Shoenfield absoluteness theorem, due to Joseph Shoenfield (1961), establishes the absoluteness of a large class of formulas between a model of set theory and its constructible universe, with important methodological consequences. The absoluteness of large cardinal axioms is also studied, with positive and negative results known.

In model theory

In model theory, there are several general results and definitions related to absoluteness. A fundamental example of downward absoluteness is that universal sentences (those with only universal quantifiers) that are true in a structure are also true in every substructure of the original structure. Conversely, existential sentences are upward absolute from a structure to any structure containing it.

Two structures are defined to be elementarily equivalent if they agree about the truth value of all sentences in their shared language, that is, if all sentences in their language are absolute between the two structures. A theory is defined to be model complete if whenever M and N are models of the theory and M is a substructure of N, then M is an elementary substructure of N.

In set theory

A major part of modern set theory involves the study of different models of ZF and ZFC. It is crucial for the study of such models to know which properties of a set are absolute to different models. It is common to begin with a fixed model of set theory and only consider other transitive models containing the same ordinals as the fixed model.

Certain properties are absolute to all transitive models of set theory, including the following (see Jech (2003 sec. I.12) and Kunen (1980 sec. IV.3)).

x is the empty set.
x is an ordinal.
x is a finite ordinal.
x is a successor ordinal.
x is a limit ordinal.
x = ω.
x is finite.
x is (the graph of) a function.

Other properties are not absolute:

Failure of absoluteness for countability

Skolem's paradox is the seeming contradiction that on the one hand, the set of real numbers is uncountable (and this is provable from ZFC, or even from a small finite subsystem ZFC' of ZFC), while on the other hand there are countable transitive models of ZFC' (this is provable in ZFC), and the set of real numbers in such a model will be a countable set. The paradox can be resolved by noting that countability is not absolute to submodels of a particular model of ZFC. It is possible that a set X is countable in a model of set theory but uncountable in a submodel containing X, because the submodel may contain no bijection between X and ω, while the definition of countability is the existence of such a bijection. The Löwenheim–Skolem theorem, when applied to ZFC, shows that this situation does occur.

Shoenfield's absoluteness theorem

Shoenfield's absoluteness theorem shows that $\Pi _{2}^{1}$ and $\Sigma _{2}^{1}$ sentences in the analytical hierarchy are absolute between a model V of ZF and the constructible universe L of the model, when interpreted as statements about the natural numbers in each model. The theorem can be relativized to allow the sentence to use sets of natural numbers from V as parameters, in which case L must be replaced by the smallest submodel containing those parameters and all the ordinals. The theorem has corollaries that $\Sigma _{3}^{1}$ sentences are upward absolute (if such a sentence holds in L then it holds in V)^[1] and $\Pi _{3}^{1}$ sentences are downward absolute (if they hold in V then they hold in L). Because any two transitive models of set theory with the same ordinals have the same constructible universe, Shoenfield's theorem shows that two such models must agree about the truth of all $\Pi _{2}^{1}$ sentences.

One consequence of Shoenfield's theorem relates to the axiom of choice. Gödel proved that the constructible universe L always satisfies ZFC, including the axiom of choice, even when V is only assumed to satisfy ZF. Shoenfield's theorem shows that if there is a model of ZF in which a given $\Sigma _{3}^{1}$ statement φ is false, then φ is also false in the constructible universe of that model. In contrapositive, this means that if ZFC proves a $\Sigma _{3}^{1}$ sentence then that sentence is also provable in ZF. The same argument can be applied to any other principle that always holds in the constructible universe, such as the combinatorial principle ◊. Even if these principles are independent of ZF, each of their $\Sigma _{3}^{1}$ consequences is already provable in ZF. In particular, this includes any of their consequences that can be expressed in the (first-order) language of Peano arithmetic.

Shoenfield's theorem also shows that there are limits to the independence results that can be obtained by forcing. In particular, any sentence of Peano arithmetic is absolute to transitive models of set theory with the same ordinals. Thus it is not possible to use forcing to change the truth value of arithmetical sentences, as forcing does not change the ordinals of the model to which it is applied. Many famous open problems, such as the Riemann hypothesis and the P = NP problem, can be expressed as $\Pi _{2}^{1}$ sentences (or sentences of lower complexity), and thus cannot be proven independent of ZFC by forcing.

Large cardinals

There are certain large cardinals that cannot exist in the constructible universe (L) of any model of set theory. Nevertheless, the constructible universe contains all the ordinal numbers that the original model of set theory contains. This "paradox" can be resolved by noting that the defining properties of some large cardinals are not absolute to submodels.

One example of such a nonabsolute large cardinal axiom is for measurable cardinals; for an ordinal to be a measurable cardinal there must exist another set (the measure) satisfying certain properties. It can be shown that no such measure is constructible.

Related Research Articles

In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family $of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.$

In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. Intuitively, forcing can be thought of as a technique to expand the set theoretical universe $to a larger universe by introducing a new "generic" object .$

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal $κ$ is strongly inaccessible if it satisfies the following three conditions: it is uncountable, it is not a sum of fewer than $κ$ cardinals smaller than $κ$ , and $implies .$

In set theory, a branch of mathematics, a Q-indescribable cardinal is a certain kind of large cardinal number that is hard to axiomatize in some language Q. There are many different types of indescribable cardinals corresponding to different choices of languages Q. They were introduced by Hanf & Scott (1961).

In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.

In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem.

In mathematics, in set theory, the constructible universe, denoted by $, is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this paper, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result.$

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by V, is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after John von Neumann, although it was first published by Ernst Zermelo in 1930.

The axiom of constructibility is a possible axiom for set theory in mathematics that asserts that every set is constructible. The axiom is usually written as V = L. The axiom, first investigated by Kurt Gödel, is inconsistent with the proposition that zero sharp exists and stronger large cardinal axioms. Generalizations of this axiom are explored in inner model theory.

In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences.

In set theory, a branch of mathematical logic, an inner model for a theory T is a substructure of a model M of a set theory that is both a model for T and contains all the ordinals of M.

In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a supertheory which is not conservative, and can prove more theorems than the original.

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take values in some fixed complete Boolean algebra.

In set theory, a branch of mathematics, a reflection principle says that it is possible to find sets that, with respect to any given property, resemble the class of all sets. There are several different forms of the reflection principle depending on exactly what is meant by "resemble". Weak forms of the reflection principle are theorems of ZF set theory due to Montague (1961), while stronger forms can be new and very powerful axioms for set theory.

In set theory, inner model theory is the study of certain models of ZFC or some fragment or strengthening thereof. Ordinarily these models are transitive subsets or subclasses of the von Neumann universe V, or sometimes of a generic extension of V. Inner model theory studies the relationships of these models to determinacy, large cardinals, and descriptive set theory. Despite the name, it is considered more a branch of set theory than of model theory.

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations. However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not ; various more-concrete ways of defining ordinals that definitely have notations are available.

In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically called just the language of set theory. This is analogous to the arithmetical hierarchy, which provides a similar classification for sentences of the language of arithmetic.

This is a glossary of terms and definitions related to the topic of set theory.

References

Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
Kunen, Kenneth, 1980. Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.
Shoenfield, Joseph, 1961. "The problem of predicativity", Essays on the foundations of mathematics, Y. Bar-Hillel et al., eds., pp. 132–142.

Inline citations

↑ P. Odifreddi, Classical Recursion Theory (1989), p.430

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] P. Odifreddi, Classical Recursion Theory (1989), p.430

[1]