Areas Mathematical logic Topic
First-order languages and syntax
Summary
This topic is a part of mathematical logic. It covers the syntax of first-order logic: signatures, terms, formulas, free and bound variables, substitution and the standard normal forms.
Remarks
Reading order
- First-order logic: formulas about elements, with quantifiers over elements only.
- Signature: the function, relation and constant symbols, each with its arity.
- Term: names built from variables and constants by function symbols, read in one way only.
- Atomic formula: an equation or a relation symbol applied to terms.
- Well-formed formula: atomic formulas closed under connectives and quantifiers.
- Free and bound variables: which variable occurrences a quantifier binds.
- Sentence: a formula without free variables.
- Substitution: replacing a free variable by a term without capture.
- First-order theory: a set of sentences over a signature.
- First-order logic with equality: equality as a logical symbol, and its axioms.
- Many-sorted logic: several domains, and the reduction to one sort.
- Prenex normal form: all quantifiers in front of a quantifier-free matrix.
- Skolem normal form: existential quantifiers replaced by new function symbols.
- Hilbert's epsilon calculus: a choice term for each formula, and the epsilon theorems.
- Definite description: "the such that", and Russell's analysis by quantifiers.
- Standard first-order languages: the signatures of orders, groups, rings, arithmetic and set theory.
Prerequisites
- The propositional calculus: connectives, truth tables and propositional formulas.
- Propositions, connectives and quantifiers: reading quantified statements in mathematics.
- Logic, formal systems and foundations: object language, metalanguage and formal systems.
- Structural induction, used in most proofs about terms and formulas.
Everything in this topic
The members of this topic and each page that they need, 160 pages in all.
- Alphabet concept
- Arithmetical hierarchy concept
- Arity concept
- Boolean function concept
- Cardinal number concept
- Cartesian product concept
- Choice function concept
- Congruence relation concept
- Countable set concept
- Countermodel concept
- Definition by recursion concept
- Effectively decidable set concept
- Elementary substructure concept
- Equality (mathematics) concept
- Equivalence relation concept
- Field concept
- First-order variable concept
- Formal language concept
- Function concept
- Induction on well-formed formulas concept
- Natural numbers object
- Ordered field concept
- Peano axioms concept
- Power set concept
- Proposition concept
- Propositional letter concept
- Quotient set concept
- Ring concept
- Set concept
- String concept
- Supremum concept
- Tuple concept
- Vector space concept
- Signature definition member
- Signature concept member
- Logical connective definition
- Binary operation concept
- Conjunction definition
- Disjunction definition
- Material implication definition
- Principle of bivalence concept
- Predicate concept
- Predicate definition
- Associativity concept
- Identity element concept
- Biconditional definition
- Structure concept
- Term concept member
- Term definition member
- Negation concept
- Negation definition
- Inverse element concept
- One symbol for unary and binary minus is not a signature example member
- Atomic formula definition member
- Atomic formula concept member
- A function symbol with the wrong number of arguments does not give a term example member
- Löwenheim–Skolem theorem statement
- Truth table concept
- Material implication concept
- Conjunction concept
- Disjunction concept
- Group concept
- Tautology concept
- A signature with a constant for each real number example member
- Equations between ring terms are atomic formulas example member
- Biconditional concept
- Universal quantifier concept
- Groups in two signatures example member
- Logical equivalence concept
- Logical connective concept
- Existential quantifier concept
- Well-formed formula definition member
- Well-formed formula concept member
- Uniqueness quantifier concept
- Propositional calculus concept
- Propositional formula definition
- Propositional formula concept
- Quantifying a constant symbol does not give a formula example member
- Prenex normal form definition member
- A formation sequence for a formula of orders example member
- The parse tree of a formula of arithmetic example member
- Definite description concept member
- First-order logic concept member
- Free and bound variables concept member
- Satisfaction concept
- Proof of unique readability by induction on length proof member
- Proof of unique readability by counting brackets proof
- Formal system concept
- Prenex normal form concept member
- Many-sorted logic concept member
- A variable in the scope of a quantifier on another variable is free example member
- Substitution concept member
- The present King of France example member
- Sentence concept member
- First-order logic with equality concept member
- Continuity of a real function as a first-order formula example member
- Unique readability theorem statement
- Unique readability of terms and formulas statement member
- Second-order logic definition
- The predecessor as a description example member
- Skolem normal form definition member
- Skolem normal form concept member
- First-order theory concept member
- First-order theory definition member
- Proof of the prenex normal form theorem proof member
- The equality axioms for the signature of groups example member
- Non-strict inequality and inequations are not atomic in the language of strict orders example member
- Hilbert's epsilon calculus concept member
- Counting sentences with equality example member
- Truth valuation concept
- Atomic sentences of arithmetic example member
- Square roots of positive numbers as a first-order sentence example member
- Second-order logic concept
- The formation tree of a ring term example member
- Vector spaces as two-sorted structures example member
- Proof of the Skolem normal form theorem proof member
- Prenex normal form theorem statement member
- The theory of infinite sets example member
- A set of formulas with a free variable is not a theory example member
- The square root of 4 in the integers is not a definite description example member
- Quantifiers as epsilon terms example member
- An epsilon term is not a first-order term example member
- Adding a scalar to a vector is not a well-sorted term example member
- An epsilon term in the natural numbers example member
- Logical consequence concept
- First-order Peano arithmetic as a theory example member
- Standard first-order languages example member
- The least upper bound property is not first-order example member
- Congruence modulo 2 satisfies the equality axioms but is not equality example member
- A formula that begins with a quantifier need not be prenex example member
- Skolem normal form theorem statement member
- Prenex form of an implication between quantified formulas example member
- The prenex form of continuity example member
- Rule of inference concept
- Skolem functions for the group axioms example member
- Skolemizing alternating quantifiers example member
- A sentence and its Skolem form are not logically equivalent example member
- Modus ponens concept
- Mathematical proof concept
- Mathematical induction concept
- Inductive and recursive definitions concept
- Free and bound variables definition member
- Structural induction concept
- Sentence definition member
- A variable that is both free and bound in one formula example member
- The scopes of nested quantifiers example member
- Substitution definition member
- Variable capture in a substitution example member
- A formula with a free variable is not a sentence example member
- Proof that variable occurrences in atomic formulas are free proof member
- Without equality no sentence says that there are two elements example member
- The relativization of a two-sorted sentence example member
- The closed terms of zero and successor are the numerals example member
- Every element has a larger element, as a sentence example member
- Substitution with renaming of a bound variable example member
- The universal closure of an equation example member
- Proof of the syntactic substitution lemma by induction on terms proof member
- Simultaneous and successive substitution differ example member
- Every variable occurrence in an atomic formula is free statement member
- Syntactic substitution lemma statement member
About this page
| Tag | PSRDJXRW53 |
|---|---|
| URI | m2://PSRDJXRW53 |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03B10 |
| Part of | Mathematical logic |
| Changed | 17 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a same_as or a source (0 of 1)
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
History
Each change to this page, from its provenance log. A change by an agent names its run.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-17 | add | the section Remarks | tamnd |
What links here
Nodes in this topic
- First-order logic
- Prenex normal form
- Well-formed formula
- The least upper bound property is not first-order
- Unique readability of terms and formulas
- An epsilon term in the natural numbers
- Quantifying a constant symbol does not give a formula
- Proof of the Skolem normal form theorem
- Term
- The equality axioms for the signature of groups
- Many-sorted logic
- Without equality no sentence says that there are two elements
- First-order theory
- Free and bound variables
- A variable in the scope of a quantifier on another variable is free
- A sentence and its Skolem form are not logically equivalent
- Atomic formula
- Term
- The prenex form of continuity
- The formation tree of a ring term
- Every element has a larger element, as a sentence
- Groups in two signatures
- Standard first-order languages
- Congruence modulo 2 satisfies the equality axioms but is not equality
- Prenex normal form
- A set of formulas with a free variable is not a theory
- Every variable occurrence in an atomic formula is free
- Sentence
- Non-strict inequality and inequations are not atomic in the language of strict orders
- Adding a scalar to a vector is not a well-sorted term
- Skolem normal form
- Proof of the syntactic substitution lemma by induction on terms
- A variable that is both free and bound in one formula
- Syntactic substitution lemma
- First-order theory
- Skolem normal form
- Proof of the prenex normal form theorem
- Counting sentences with equality
- The relativization of a two-sorted sentence
- Well-formed formula
- A function symbol with the wrong number of arguments does not give a term
- The present King of France
- The theory of infinite sets
- Atomic sentences of arithmetic
- The predecessor as a description
- The scopes of nested quantifiers
- Atomic formula
- Prenex normal form theorem
- First-order Peano arithmetic as a theory
- Proof that variable occurrences in atomic formulas are free
- Substitution
- The square root of 4 in the integers is not a definite description
- Proof of unique readability by induction on length
- Definite description
- Skolemizing alternating quantifiers
- Signature
- First-order logic with equality
- Skolem normal form theorem
- Sentence
- An epsilon term is not a first-order term
- Square roots of positive numbers as a first-order sentence
- A formula with a free variable is not a sentence
- The parse tree of a formula of arithmetic
- Quantifiers as epsilon terms
- A formation sequence for a formula of orders
- Hilbert's epsilon calculus
- The closed terms of zero and successor are the numerals
- Simultaneous and successive substitution differ
- Signature
- Skolem functions for the group axioms
- Variable capture in a substitution
- Equations between ring terms are atomic formulas
- Substitution
- Substitution with renaming of a bound variable
- A formula that begins with a quantifier need not be prenex
- Free and bound variables
- Continuity of a real function as a first-order formula
- One symbol for unary and binary minus is not a signature
- The universal closure of an equation
- A signature with a constant for each real number
- Vector spaces as two-sorted structures
- Prenex form of an implication between quantified formulas