Section 2.1: First-Order Languages

• Terms. For each $n$ -place function symbol $f$ we define an $n$ -place term-building operation $\mathcal{F}_{f}(\epsilon_{1},\ldots,\epsilon_{n})=f\epsilon_{1}\ldots\epsilon_{n}$ . We define a term to be built up from the constant symbols and variables by applying zero or more times $n$ -place term-building operations.
  • Terms form objects from constants and variables inductively, by taking functions of already constructed objects.
• Atomic formulas. An atomic formula is an expressions of the form $Pt_{1}\ldots t_{n}$ where $P$ is an $n$ -place predicate symbol (or $=$ ) and each $t_{i}$ is a term.
  • Atomic formulas are the smallest parts of formulas that are assigned truth values, they are formed as predicates of terms. They play a role similar to that of sentence symbols in sentential logic.
• Well-formed formulas. A well-formed formula (wff) is an expression that can be built up from the atomic formulas by applying zero or more times the following formula-building operations: $$\mathcal{E}_{\neg}(\gamma)=(\neg\gamma)\mbox{,}$$ $$\mathcal{E}_{\rightarrow}(\gamma,\delta)=(\gamma\rightarrow\delta)\mbox{, and}$$ $$\mathcal{Q}_{i}(\gamma)=\forall v_{i}\gamma\mbox{.}$$

• Alternatively, we define $h(\alpha)$ where $\alpha$ is atomic to be the set of all its variables, and extend it to $\overline{h}$ defined on the set of all wffs as follows: $\overline{h}(\mathcal{E}_{\neg}(\alpha))=\overline{h}(\alpha)$ , $\overline{h}(\mathcal{E}_{\rightarrow}(\alpha,\beta))=\overline{h}(\alpha)\cup\overline{h}(\beta)$ , and $\overline{h}(\mathcal{Q}_{i}(\alpha))=\overline{h}(\alpha)-\{v_{i}\}$ .
• $\alpha$ is a sentence iff $\overline{h}(\alpha)=\emptyset$ .

Conventions

• $(\alpha\vee\beta)$ abbreviates $((\neg\alpha)\rightarrow\beta)$ .
• $(\alpha\wedge\beta)$ abbreviates $(\neg(\alpha\rightarrow(\neg\beta)))$ .
• $(\alpha\leftrightarrow\beta)$ abbreviates $(\neg((\alpha\rightarrow\beta)\rightarrow(\neg(\beta\rightarrow\alpha))))$ .
• $\exists x\alpha$ abbreviates $(\neg\forall x(\neg\alpha))$ .
• $t=u$ abbreviates $=tu$ (similarly, for some other $2$ -place predicate and function symbols).
• $t\neq u$ abbreviates $(\neg=tu)$ (similarly, for some other $2$ -place predicate and function symbols).
• The outermost parentheses can be dropped.
• $\neg$ , $\forall$ and $\exists$ apply to as little as possible.
• $\wedge$ and $\vee$ apply to as little as possible subject to the previous point.
• Parentheses can be added or changed to $[$ $]$ etc. for readability.
• Right precedence: $\alpha\square\beta\square\gamma$ is understood as $(\alpha\square(\beta\square\gamma))$ .

Alphabets used

• Variables: lowercase italic letters $v_{i}$ , $u$ , $v$ , $x$ , $y$ , $z$ .
• Predicate symbols: uppercase italic letters, and specific symbols such as $\in$ , $<$ etc.
• Constant symbols: lowercase italic letters $a$ , $b$ , $c$ , $\ldots$ , and specific symbols such as $0$ etc.
• Function symbols: lowercase italic letters $f$ , $g$ , $h$ , and specific symbols such as $\mathbb{S}$ , $+$ etc.
• Terms: lowercase italic letters $t$ , $u$ .
• Formulas: lowercase Greek letters $\alpha$ , $\beta$ , $\gamma$ , $\ldots$ .
• Sentences: lowercase Greek letters $\sigma$ , $\tau$ .
• Sets of formulas: uppercase Greek letters.
• Structures (not yet introduced): uppercase German (Fraktur) letters.