Mathematical Logic Glossary

A statement accepted as true without proof, serving as a starting point for deducing other statements within a formal system.

An axiom stating that for any collection of non-empty sets, a choice function exists that selects one element from each set.

An algebraic structure defined over a set with two binary operations (AND, OR) and one unary operation (NOT) satisfying specific laws.

A measure of the number of elements in a set, extended to infinite sets by Cantor using bijections.

The hypothesis that any effectively computable function can be computed by a Turing machine.

A set of first-order sentences is satisfiable if and only if every finite subset is satisfiable.

A property of a logical system meaning every semantically valid formula is provable within the system.

The study of which problems can be solved by algorithms and the classification of unsolvable problems by degree of unsolvability.

A formula that is false under every possible interpretation or truth assignment.

Logical equivalences: NOT(A AND B) equals (NOT A) OR (NOT B), and NOT(A OR B) equals (NOT A) AND (NOT B).

A decision problem is decidable if there exists an algorithm that always terminates with a correct yes-or-no answer for every input.

A formal logical system that extends propositional logic with quantifiers and predicates, allowing statements about objects and their properties.

A system consisting of a formal language, a set of axioms, and inference rules used to derive theorems.

A technique of assigning a unique natural number to each symbol, formula, and proof in a formal system, enabling self-reference.

The undecidable problem of determining whether an arbitrary Turing machine halts on a given input.

A rule that specifies how to derive new statements from existing ones in a formal proof, such as Modus Ponens.

A mathematical structure that provides an interpretation for the symbols of a formal language and satisfies a given set of sentences.

The study of the relationship between formal languages and their interpretations (models), analyzing truth and structure.

The branch of mathematical logic that studies the structure and properties of formal proofs as mathematical objects.

The branch of logic dealing with propositions connected by logical operators, where truth values are determined by truth tables.

A logical symbol specifying the quantity of elements for which a predicate holds: universal (for all) or existential (there exists).

A formula is satisfiable if there exists at least one interpretation under which it evaluates to true.

A property of a logical system meaning every provable formula is semantically valid (true in all models).

A propositional formula that is true under every possible assignment of truth values to its variables.

An abstract mathematical model of computation consisting of a tape, head, and state transitions, formalizing the concept of an algorithm.