Independence (mathematical logic)
- Independence (mathematical logic)
In mathematical logic, a sentence σ is called "independent" of a given first-order theory "T" if "T" neither proves nor refutes σ; that is, it is impossible to prove σ from "T", and it is also impossible to prove from "T" that σ is false.
Sometimes, σ is said (synonymously) to be "undecidable" from "T"; however, this usage risks confusion with the distinct notion of the undecidability of a decision problem.
Many interesting statements in set theory are independent of Zermelo-Fraenkel set theory (ZF). It is possible for the statement "σ is independent from T" to be itself independent from T. This reflects the fact that statements about proofs of mathematical statements when represented in mathematics become themselves mathematical statements.
Usage note
Some authors say that σ is independent of "T" if "T" simply cannot prove σ, and do not necessarily assert by this that "T" cannot refute σ. These authors will sometimes say "σ is independent of and consistent with "T" to indicate that "T" can neither prove nor refute σ.
Independence results in set theory
The following statements in set theory are known to be independent of ZF, granting that ZF is consistent (see also the list of statements undecidable in ZFC):
*The axiom of choice
*The continuum hypothesis and the generalised continuum hypothesis
*The Souslin conjecture
*The existence of a Kurepa tree
The following statements (none of which have been proved false) cannot be proved in ZFC to be independent of ZFC, even if the added hypothesis is granted that ZFC is consistent. However, they cannot be proved in ZFC (granting that ZFC is consistent), and few working set theorists expect to find a refutation of them in ZFC.
*The existence of strongly inaccessible cardinals
*The existence of large cardinals
The following statements are inconsistent with the axiom of choice, and therefore with ZFC. However they are probably independent of ZF, in a corresponding sense to the above: They cannot be proved in ZF, and few working set theorists expect to find a refutation in ZF. However ZF cannot prove that they are independent of ZF, even with the added hypothesis that ZF is consistent.
*The Axiom of determinacy
*The axiom of real determinacy
*AD+
Wikimedia Foundation.
2010.
Look at other dictionaries:
Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… … Wikipedia
Structure (mathematical logic) — In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it. Universal algebra studies structures that generalize the algebraic structures such as… … Wikipedia
Theory (mathematical logic) — This article is about theories in a formal language, as studied in mathematical logic. For other uses, see Theory (disambiguation). In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. Usually… … Wikipedia
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… … Wikipedia
List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic … Wikipedia
Independence (disambiguation) — Independence is the self government of a nation, country, or state by its residents and population.Independence may also mean:;In mathematics: *Independence (mathematical logic), Logical independence *Linear independence *Statistical independence … Wikipedia
logic, history of — Introduction the history of the discipline from its origins among the ancient Greeks to the present time. Origins of logic in the West Precursors of ancient logic There was a medieval tradition according to which the Greek philosopher … Universalium
Logic — For other uses, see Logic (disambiguation). Philosophy … Wikipedia
Mathematical proof — In mathematics, a proof is a convincing demonstration (within the accepted standards of the field) that some mathematical statement is necessarily true.[1][2] Proofs are obtained from deductive reasoning, rather than from inductive or empirical… … Wikipedia
Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… … Wikipedia
