Difference between revisions of "Decidability (logic)"
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
== Description == | == Description == | ||
| − | + | [[Formal system|Formal systems]] such as [[propositional calculus]] are decidable if membership in their set of logically [[Validity|valid]] formulas (or theorems) can be effectively determined. | |
A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. | A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. | ||
| − | Many important problems are undecidable, that is, it has been proven that no effective method can exist for them. | + | Many important problems are [[Undecidable problem|undecidable]], that is, it has been proven that no effective method can exist for them. |
| + | |||
| + | == Relationship with completeness == | ||
| + | |||
| + | Decidability should not be confused with completeness (see [[Complete theory]]). | ||
| + | |||
| + | For example, the theory of [[Algebraically closed field|algebraically closed fields]] is decidable but incomplete, whereas the set of all true first-order statements about nonnegative integers in the language with + and × is complete but undecidable. | ||
| + | |||
| + | Unfortunately, as a terminological ambiguity, the term "undecidable statement" is sometimes used as a synonym for [[Independence (mathematical logic)|independent statement]]. | ||
== See also == | == See also == | ||
| Line 14: | Line 22: | ||
* [[Decision problem]] | * [[Decision problem]] | ||
* [[Effective method]] | * [[Effective method]] | ||
| + | * [[Formal system]] | ||
* [[László Kalmár]] (1936) | * [[László Kalmár]] (1936) | ||
| + | * [[Propositional calculus]] | ||
* [[W.V.O. Quine]] (1953) | * [[W.V.O. Quine]] (1953) | ||
| + | * [[Undecidable problem]] | ||
* Meyer and [[Karel Lambert]] (1967) | * Meyer and [[Karel Lambert]] (1967) | ||
| + | * [[Validity]] | ||
== External links == | == External links == | ||
Latest revision as of 08:44, 13 September 2016
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas, or, more precisely, an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely).
Description
Formal systems such as propositional calculus are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined.
A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory.
Many important problems are undecidable, that is, it has been proven that no effective method can exist for them.
Relationship with completeness
Decidability should not be confused with completeness (see Complete theory).
For example, the theory of algebraically closed fields is decidable but incomplete, whereas the set of all true first-order statements about nonnegative integers in the language with + and × is complete but undecidable.
Unfortunately, as a terminological ambiguity, the term "undecidable statement" is sometimes used as a synonym for independent statement.
See also
- Alonzo Church (1956)
- Decision problem
- Effective method
- Formal system
- László Kalmár (1936)
- Propositional calculus
- W.V.O. Quine (1953)
- Undecidable problem
- Meyer and Karel Lambert (1967)
- Validity
External links
- Decidability (logic) @ Wikipedia.org
