Section 2.1: Problem 1 Solution »

# Section 2.1: First-Order Languages

We are given the following infinite set of symbols:
 logical symbols sentential connective symbols $\neg$ (negation symbol) $\rightarrow$ (conditional symbol) punctuation symbols $($ (left parenthesis) $)$ (right parenthesis) variables $v_{n}$ (for each $n\in\mathbb{N}$ ) equality symbol $=$ (optional) parameters quantifier symbols $\forall$ (universal quantifier symbol) predicate symbols For each $n>0$ , some set of symbols, called $n$ -place predicate symbols. constant symbols Some set of symbols (a.k.a. $0$ -place function symbols). function symbols For each $n>0$ , some set of symbols, called $n$ -place function symbols.
The first-order languages differ in (a) the presence of the equality symbol (which is a logical symbol rather than a parameter), and (b) parameters.
An expression is a finite sequence of symbols. There are special types of expressions:
• 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 -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:
A variable $x$ is said to occur free in a wff $\alpha$ ($x$ is a free variable of $\alpha$ ) iff one of the following holds: (a) $\alpha$ is atomic and $x$ occurs in $\alpha$ , (b) $\alpha=(\neg\beta)$ and $x$ occurs free in $\beta$ , (c) $\alpha=(\beta\rightarrow\gamma)$ and $x$ occurs free in $\beta$ and/or $\gamma$ , and (d) $\alpha=\forall v_{i}\beta$ and $x\neq v_{i}$ occurs free in $\beta$ .
• 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.