Independence (mathematical logic)

Short description: Term in mathematical logic

The parallels axiom (P) is independent of the remaining geometry axioms (R): there are models (1) that satisfy R and P, but also models (2,3) that satisfy R, but not P.

In mathematical logic, independence is the unprovability of a sentence from other sentences.

A sentence σ is 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; this is not the same meaning of "decidability" as in a decision problem.

A theory T is independent if each axiom in T is not provable from the remaining axioms in T. A theory for which there is an independent set of axioms is independently axiomatizable.

## Contents

* 1 Usage note
* 2 Independence results in set theory
* 3 Applications to physical theory
* 4 See also
* 5 Notes
* 6 References

## Usage note

Some authors say that σ is independent of T when 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

Many interesting statements in set theory are independent of Zermelo–Fraenkel set theory (ZF). The following statements in set theory are known to be independent of ZF, under the assumption that ZF is consistent:

* The axiom of choice
* The continuum hypothesis and the generalized continuum hypothesis
* The Suslin conjecture

The following statements (none of which have been proved false) cannot be proved in ZFC (the Zermelo–Fraenkel set theory plus the axiom of choice) to be independent of ZFC, under the added hypothesis that ZFC is consistent.

* The existence of strongly inaccessible cardinals
* The existence of large cardinals
* The non-existence of Kurepa trees

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+

## Applications to physical theory

Since 2000, logical independence has become understood as having crucial significance in the foundations of physics.[1][2]

## See also

* List of statements independent of ZFC
* Parallel postulate for an example in geometry

## Notes

1. ↑ Paterek, T.; Kofler, J.; Prevedel, R.; Klimek, P.; Aspelmeyer, M.; Zeilinger, A.; Brukner, Č. (2010), "Logical independence and quantum randomness", New Journal of Physics 12: 013019, doi:10.1088/1367-2630/12/1/013019, Bibcode: 2010NJPh...12a3019P
2. ↑ Székely, Gergely (2013), "The Existence of Superluminal Particles is Consistent with the Kinematics of Einstein's Special Theory of Relativity", Reports on Mathematical Physics 72 (2): 133–152, doi:10.1016/S0034-4877(13)00021-9, Bibcode: 2013RpMP...72..133S

## References

* Mendelson, Elliott (1997), An Introduction to Mathematical Logic (4th ed.), London: Chapman & Hall, ISBN 978-0-412-80830-2
* Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1, https://archive.org/details/mathematicallogi00jdon
* Stabler, Edward Russell (1948), An introduction to mathematical thought, Reading, Massachusetts: Addison-Wesley

* v
* t
* e

Mathematical logic

General|

* Formal language
* Formation rule
* Formal proof
* Formal semantics
* Well-formed formula
* Set
* Element
* Class
* Classical logic
* Axiom
* Rule of inference
* Relation
* Theorem
* Logical consequence
* Type theory
* Symbol
* Syntax
* Theory

Systems|

* Formal system
* Deductive system
* Axiomatic system
* Hilbert style systems
* Natural deduction
* Sequent calculus

Traditional logic|

* Proposition
* Inference
* Argument
* Validity
* Cogency
* Syllogism
* Square of opposition
* Venn diagram

Propositional calculus
and Boolean logic

* Boolean functions
* Propositional calculus
* Propositional formula
* Logical connectives
* Truth tables
* Many-valued logic

Predicate logic|

* First-order
* Quantifiers
* Predicate
* Second-order
* Monadic predicate calculus

Naive set theory|

* Set
* Empty set
* Element
* Enumeration
* Extensionality
* Finite set
* Infinite set
* Subset
* Power set
* Countable set
* Uncountable set
* Recursive set
* Domain
* Codomain
* Image
* Map
* Function
* Relation
* Ordered pair

Set theory|

* Foundations of mathematics
* Zermelo–Fraenkel set theory
* Axiom of choice
* General set theory
* Kripke–Platek set theory
* Von Neumann–Bernays–Gödel set theory
* Morse–Kelley set theory
* Tarski–Grothendieck set theory

Model theory|

* Model
* Interpretation
* Non-standard model
* Finite model theory
* Truth value
* Validity

Proof theory|

* Formal proof
* Deductive system
* Formal system
* Theorem
* Logical consequence
* Rule of inference
* Syntax

Computability
theory|

* Recursion
* Recursive set
* Recursively enumerable set
* Decision problem
* Church–Turing thesis
* Computable function
* Primitive recursive function

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Independence (mathematical logic). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Independence_(mathematical_logic)&oldid=334544"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template