Math 2.0

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

  1. First-order logic: formulas about elements, with quantifiers over elements only.
  2. Signature: the function, relation and constant symbols, each with its arity.
  3. Term: names built from variables and constants by function symbols, read in one way only.
  4. Atomic formula: an equation or a relation symbol applied to terms.
  5. Well-formed formula: atomic formulas closed under connectives and quantifiers.
  6. Free and bound variables: which variable occurrences a quantifier binds.
  7. Sentence: a formula without free variables.
  8. Substitution: replacing a free variable by a term without capture.
  9. First-order theory: a set of sentences over a signature.
  10. First-order logic with equality: equality as a logical symbol, and its axioms.
  11. Many-sorted logic: several domains, and the reduction to one sort.
  12. Prenex normal form: all quantifiers in front of a quantifier-free matrix.
  13. Skolem normal form: existential quantifiers replaced by new function symbols.
  14. Hilbert's epsilon calculus: a choice term for each formula, and the epsilon theorems.
  15. Definite description: "the xx such that", and Russell's analysis by quantifiers.
  16. Standard first-order languages: the signatures of orders, groups, rings, arithmetic and set theory.

Prerequisites

  1. The propositional calculus: connectives, truth tables and propositional formulas.
  2. Propositions, connectives and quantifiers: reading quantified statements in mathematics.
  3. Logic, formal systems and foundations: object language, metalanguage and formal systems.
  4. 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.

  1. Alphabet concept
  2. Arithmetical hierarchy concept
  3. Arity concept
  4. Boolean function concept
  5. Cardinal number concept
  6. Cartesian product concept
  7. Choice function concept
  8. Congruence relation concept
  9. Countable set concept
  10. Countermodel concept
  11. Definition by recursion concept
  12. Effectively decidable set concept
  13. Elementary substructure concept
  14. Equality (mathematics) concept
  15. Equivalence relation concept
  16. Field concept
  17. First-order variable concept
  18. Formal language concept
  19. Function concept
  20. Induction on well-formed formulas concept
  21. Natural numbers object
  22. Ordered field concept
  23. Peano axioms concept
  24. Power set concept
  25. Proposition concept
  26. Propositional letter concept
  27. Quotient set concept
  28. Ring concept
  29. Set concept
  30. String concept
  31. Supremum concept
  32. Tuple concept
  33. Vector space concept
  34. Signature definition member
  35. Signature concept member
  36. Logical connective definition
  37. Binary operation concept
  38. Conjunction definition
  39. Disjunction definition
  40. Material implication definition
  41. Principle of bivalence concept
  42. Predicate concept
  43. Predicate definition
  44. Associativity concept
  45. Identity element concept
  46. Biconditional definition
  47. Structure concept
  48. Term concept member
  49. Term definition member
  50. Negation concept
  51. Negation definition
  52. Inverse element concept
  53. One symbol for unary and binary minus is not a signature example member
  54. Atomic formula definition member
  55. Atomic formula concept member
  56. A function symbol with the wrong number of arguments does not give a term example member
  57. Löwenheim–Skolem theorem statement
  58. Truth table concept
  59. Material implication concept
  60. Conjunction concept
  61. Disjunction concept
  62. Group concept
  63. Tautology concept
  64. A signature with a constant for each real number example member
  65. Equations between ring terms are atomic formulas example member
  66. Biconditional concept
  67. Universal quantifier concept
  68. Groups in two signatures example member
  69. Logical equivalence concept
  70. Logical connective concept
  71. Existential quantifier concept
  72. Well-formed formula definition member
  73. Well-formed formula concept member
  74. Uniqueness quantifier concept
  75. Propositional calculus concept
  76. Propositional formula definition
  77. Propositional formula concept
  78. Quantifying a constant symbol does not give a formula example member
  79. Prenex normal form definition member
  80. A formation sequence for a formula of orders example member
  81. The parse tree of a formula of arithmetic example member
  82. Definite description concept member
  83. First-order logic concept member
  84. Free and bound variables concept member
  85. Satisfaction concept
  86. Proof of unique readability by induction on length proof member
  87. Proof of unique readability by counting brackets proof
  88. Formal system concept
  89. Prenex normal form concept member
  90. Many-sorted logic concept member
  91. A variable in the scope of a quantifier on another variable is free example member
  92. Substitution concept member
  93. The present King of France example member
  94. Sentence concept member
  95. First-order logic with equality concept member
  96. Continuity of a real function as a first-order formula example member
  97. Unique readability theorem statement
  98. Unique readability of terms and formulas statement member
  99. Second-order logic definition
  100. The predecessor as a description example member
  101. Skolem normal form definition member
  102. Skolem normal form concept member
  103. First-order theory concept member
  104. First-order theory definition member
  105. Proof of the prenex normal form theorem proof member
  106. The equality axioms for the signature of groups example member
  107. Non-strict inequality and inequations are not atomic in the language of strict orders example member
  108. Hilbert's epsilon calculus concept member
  109. Counting sentences with equality example member
  110. Truth valuation concept
  111. Atomic sentences of arithmetic example member
  112. Square roots of positive numbers as a first-order sentence example member
  113. Second-order logic concept
  114. The formation tree of a ring term example member
  115. Vector spaces as two-sorted structures example member
  116. Proof of the Skolem normal form theorem proof member
  117. Prenex normal form theorem statement member
  118. The theory of infinite sets example member
  119. A set of formulas with a free variable is not a theory example member
  120. The square root of 4 in the integers is not a definite description example member
  121. Quantifiers as epsilon terms example member
  122. An epsilon term is not a first-order term example member
  123. Adding a scalar to a vector is not a well-sorted term example member
  124. An epsilon term in the natural numbers example member
  125. Logical consequence concept
  126. First-order Peano arithmetic as a theory example member
  127. Standard first-order languages example member
  128. The least upper bound property is not first-order example member
  129. Congruence modulo 2 satisfies the equality axioms but is not equality example member
  130. A formula that begins with a quantifier need not be prenex example member
  131. Skolem normal form theorem statement member
  132. Prenex form of an implication between quantified formulas example member
  133. The prenex form of continuity example member
  134. Rule of inference concept
  135. Skolem functions for the group axioms example member
  136. Skolemizing alternating quantifiers example member
  137. A sentence and its Skolem form are not logically equivalent example member
  138. Modus ponens concept
  139. Mathematical proof concept
  140. Mathematical induction concept
  141. Inductive and recursive definitions concept
  142. Free and bound variables definition member
  143. Structural induction concept
  144. Sentence definition member
  145. A variable that is both free and bound in one formula example member
  146. The scopes of nested quantifiers example member
  147. Substitution definition member
  148. Variable capture in a substitution example member
  149. A formula with a free variable is not a sentence example member
  150. Proof that variable occurrences in atomic formulas are free proof member
  151. Without equality no sentence says that there are two elements example member
  152. The relativization of a two-sorted sentence example member
  153. The closed terms of zero and successor are the numerals example member
  154. Every element has a larger element, as a sentence example member
  155. Substitution with renaming of a bound variable example member
  156. The universal closure of an equation example member
  157. Proof of the syntactic substitution lemma by induction on terms proof member
  158. Simultaneous and successive substitution differ example member
  159. Every variable occurrence in an atomic formula is free statement member
  160. Syntactic substitution lemma statement member
About this page
TagPSRDJXRW53
URIm2://PSRDJXRW53
Kindtopic
WritingW0 stub
MSC03B10
Part ofMathematical logic
Changed17 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.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-17addthe section Remarkstamnd

What links here

Nodes in this topic