Absoluteness (mathematical logic)


Absoluteness (mathematical logic)

In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures (also called models). Theorems about absoluteness typically show that each of a large syntactic class of formulas is absolute.

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. A theorem due to Shoenfield 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 submodel of "N", then "M" and "N" are elementarily equivalent.

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" = ω.
* "x" is (the graph of) a function.

Other properties, such as countability, are not absolute.

Failure of absoluteness for countability

Skolem's paradox is that although it is a theorem of ZF that the set of real numbers is uncountable, it is consistent that there are countable models of ZF, 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 ZF. 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 ZF, shows that this situation does occur.

Shoenfield's absoluteness theorem

Shoenfield's absoluteness theorem shows that Pi^1_2 and Sigma^1_2 sentences in the analytical hierarchy are absolute between a model "V" of ZFC 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^1_3 sentences are upward absolute (if such a sentence holds in "L" then it holds in "V") and Pi^1_3 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^1_2 sentences.

Shoenfield's theorem 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^1_2 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.

See also

* Conservative extension

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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Hegel’s logic and philosophy of mind — Willem deVries LOGIC AND MIND IN HEGEL’S PHILOSOPHY Hegel is above all a systematic philosopher. Awe inspiring in its scope, his philosophy left no subject untouched. Logic provides the central, unifying framework as well as the general… …   History of philosophy

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Axiom of choice — This article is about the mathematical concept. For the band named after it, see Axiom of Choice (band). In mathematics, the axiom of choice, or AC, is an axiom of set theory stating that for every family of nonempty sets there exists a family of …   Wikipedia

  • Skolem's paradox — is the mathematical fact that every countable axiomatisation of set theory in first order logic, if consistent, has a model that is countable, even if it is possible to prove, from those same axioms, the existence of sets that are not countable.… …   Wikipedia

  • Dialetheism — is the view that some statements can be both true and false simultaneously. More precisely, it is the belief that there can be a true statement whose negation is also true. Such statements are called true contradictions , or dialetheia.… …   Wikipedia

  • Absolute — may mean:Philosophy * Absolute (philosophy), a concept in philosophy * Moral absolutes, the belief that there are absolute standards against which moral questions can be judgedMath and science * Absolute value, in mathematics, the value of a real …   Wikipedia

  • Conservative extension — In mathematical logic, a logical theory T2 is a (proof theoretic) conservative extension of a theory T1 if the language of T2 extends the language of T1; every theorem of T1 is a theorem of T2; and any theorem of T2 which is in the language of T1 …   Wikipedia

  • Science (Philosophies of) — Philosophies of science Mach, Duhem, Bachelard Babette E.Babich THE TRADITION OF CONTINENTAL PHILOSOPHY OF SCIENCE If the philosophy of science is not typically represented as a ‘continental’ discipline it is nevertheless historically rooted in… …   History of philosophy

  • Postmodernist theory — Lyotard, Baudrillard and others Thomas Docherty INTRODUCTION Philosophy has been touched by postmodernism. Philosophy, in the modern academy, is supposed to be the discipline of disciplines: it is philosophy which will be able to gather together …   History of philosophy

  • Number — For other uses, see Numbers (disambiguation). A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.