Decidability (logic)

Definition

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems are decidable if membership in their set of logically valid formulas can be effectively determined. Zeroth-order logic is decidable, whereas first-order and higher-order logic are not. A theory 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 for determining membership can exist for them.

Related concepts

Abelian group Abstract logic Academic Press Ackermann set theory Aleph number Alfred Tarski Algebraic logic Algebraically closed field Alphabet (formal languages)Anatoly Maltsev Andrzej Mostowski Argument Arity Atomic formula Atomic model (mathematical logic)Atomic sentence Automata theory Automated theorem proving Axiom Axiom of choice Axiom schema Axiomatic system Axiomatization of Boolean algebras Banach–Tarski paradox Bijection Binary operation Bjorn Poonen Boolean algebra Boolean algebras canonically defined Boolean function Boris Trakhtenbrot Cantor's diagonal argument Cantor's paradox Cantor's theorem Cardinality Cartesian product Categorical theory Category (mathematics)Category of sets Category theory Characteristic (algebra)Church's thesis Church encoding Church–Turing thesis Class (set theory)Classical logic Codomain Compactness theorem Complement (set theory)Complete theory Completeness (logic)Computability in Europe Computability theory Computable function Computable set Computably enumerable Computably enumerable set Concrete category Conservative extension Consistency Constructible universe Construction of the real numbers Constructive set theory Continuum hypothesis Countable set Decidability of First-order Theory of Real Numbers Decidable set Decidable sublanguages of set theory Decision problem Deductive closure Deductive system Deductively closed Diagram (mathematical logic)Doklady Akademii Nauk SSSR Domain of a function Effective method Ehrenfeucht Element (mathematics)Elementary diagram Elementary equivalence Elementary function arithmetic Empty set Entscheidungsproblem Enumeration Equiconsistency Equivalence relation Euclid's Elements Euclidean geometry Existential quantification Expression (mathematics)Extension by definitions Extension by new constant and function names Extensionality Field (mathematics)Finitary relation Finite-valued logic Finite group Finite model theory Finite set First-order logic Fixed-point logic Forcing (mathematics)Formal grammar Formal language Formal proof Formal semantics (logic)Formal system Formation rule Foundations of geometry Foundations of mathematics Free logic Free variables and bound variables Function (mathematics)Functional predicate Fuzzy set Games General set theory Grothendieck universe Ground expression Ground formula Group (mathematics)Gödel's completeness theorem Gödel's incompleteness theorems Gödel numbering H. J. Keisler Halting problem Hereditary set Higher-order logic Hilbert's axioms Hilbert system History of logic History of mathematical logic Hyperbolic geometry Image (mathematics)Imperfect information Inaccessible cardinal Independence (mathematical logic)Inference Infinite-valued logic Infinite chess Infinite set Information theory Inhabited set Injective function Interpretability Interpretation (logic)Interpretation (model theory)Interpretation function Intersection (set theory)Isomorphism J. Symb. Log.Joel David Hamkins Jon Barwise Julia Robinson Kolmogorov complexity Kripke's theory of truth Kripke–Platek set theory Lambda calculus Large cardinal Lemma (mathematics)Leopold Löwenheim Lindström's theorem Linear logic List of Hilbert systems List of axioms List of first-order theories List of formal systems List of mathematical theories List of set identities and relations List of statements independent of ZFC Logic Logical biconditional Logical conjunction Logical connective Logical consequence Logical constant Logical disjunction Logical equality Logical equivalence Logical system Logical truth Logical validity Logicism Löwenheim–Skolem theorem Many-one reduction Many-valued logic Map (mathematics)Martin Davis (mathematician)Material conditional Mathematical logic Mathematical object Metalanguage Metalogic Metamathematics Metatheorem Minimal axioms for Boolean algebra Model complete theory Model completeness Model theory Mojżesz Presburger Monadic predicate calculus Monadic second-order logic Morse–Kelley set theory NP (complexity)Naive set theory Natural deduction Natural number Negation New Foundations Non-Euclidean geometry Non-logical symbol Non-standard model Non-standard model of arithmetic Open formula Operation (mathematics)Ordinal analysis Ordinal number P (complexity)P versus NP problem Paraconsistent logic Paradoxes of set theory Partition of a set Peano arithmetic Peano axioms Philosophy of mathematics Power set Predicate (logic)Predicate (mathematical logic)Predicate logic Predicate variable Presburger arithmetic Prime model Primitive recursive arithmetic Primitive recursive function Principia Mathematica Proof of impossibility Proof theory Proposition Propositional calculus Propositional formula Propositional logic Propositional variable Quantifier (logic)Quantifier elimination Quantifier rank Raphael Robinson Rational number Real closed field Recursion Recursive set Relation (mathematics)Reverse mathematics Ring (mathematics)Robinson arithmetic Rule of inference Russell's paradox S2S (mathematics)Satisfiability Saturated model Schröder–Bernstein theorem Second-order arithmetic Second-order logic Self-verifying theories Semantic theory of truth Semantics of logic Semigroup Sentence (mathematical logic)Sequent Sequent calculus Set (mathematics)Set theory Signature (logic)Singleton (mathematics)Skolem arithmetic Soundness Spectrum of a sentence Spectrum of a theory Springer-Verlag Square of opposition Strength (mathematical logic)String (formal languages)Structure (mathematical logic)Substitution (logic)Substructure (mathematics)Supertask Surjective function Syllogism Symbol (formal)Syntax (logic)T-schema Tarski's axiomatization of the reals Tarski's axioms Tarski's exponential function problem Tarski's theory of truth Tarski's undefinability theorem Tarski–Grothendieck set theory Tarski–Seidenberg theorem Tautology (logic)Term (logic)Term logic Ternary logic Theorem Theories of truth Theory (mathematical logic)Three-valued logic Timeline of mathematical logic Transfer principle Transitive set Tree (graph theory)True arithmetic Truth predicate Truth table Truth value Turing machine Type (model theory)Type theory Type–token distinction Ultrafilter (set theory)Ultraproduct Uncountable set Undecidable problem Uninterpreted function Union (set theory)Uniqueness quantification Universal quantification Universal set Universe (mathematics)Urelement Use–mention distinction Validity (logic)Variable (mathematics)Venn diagram Von Neumann universe Von Neumann–Bernays–Gödel set theory Wanda Szmielew Well-formed formula Yuri Gurevich Zermelo–Fraenkel set theory Zeroth-order logic Łoś–Vaught test

143 concepts already in your glossary