A first order language \( \mathcal{L} \) is an infinite collection of distinct symbols, no one of which is contained in another, separated into the following categories

• Parenthesis: \( ( , ) \)
• Connectives: \( \vee , \neg \)
• Quantifier: \( \forall \)
• Variables, one for each \( i \in \mathbb{N}_{1} \): \( v_{i} \)
• Equality symbol: =
• Constant symbols: A set of symbols
• Function symbols, for each \( n \in \mathbb{N}_{1} \): A set of \( n \)-ary function symbols
• Relation symbols, for each \( n \in \mathbb{N}_{1} \): A set of \( n \)-ary relation symbols

Since the only thing differing from language to language are its constants, variables, functions and relations then we can denote the language \( \mathcal{L} \) by \( \left ( C_{\mathcal{L}} , F_{\mathcal{L}} , R_{\mathcal{L}} \right ) \), we can denote the set of variables by \( V_{\mathcal{L}} \)

If \( \mathcal{L} \) is a language, a term of \( \mathcal{L} \) is a nonempty finite string \( t \) of symbols from \( \mathcal{L} \) such that

• \( t \) is a variable
• \( t \) is a constant
• \( t \equiv f{t}_{1} t_{2} \ldots t_{n} \) is a constant where \( f \) is an \( n \)-ary function symbol if \( \mathcal{L} \) and each \( t_{i} \) is a term of \( \mathcal{L} \)

If \( \mathcal{L} \) is a first order language, then a formula of \( \mathcal{L} \) is a non-empty finite string \( \phi \) of symbols from \( \mathcal{L} \) such that:

1. \( \phi : \equiv = t_{1} t_{2} \) where \( t_{1} , t_{2} \) are terms of \( \mathcal{L} \)
2. \( \phi : \equiv R t_{1} t_{2} \ldots t_{n} \) where \( R \) is an \( n \)-ary relation symbol of \( \mathcal{L} \) and \( t_{1} , t_{2} \) are terms of \( \mathcal{L} \)
3. \( \phi : \equiv \left ( \neg \alpha \right ) \) where \( \alpha \) is a formula of \( \mathcal{L} \)
4. \( \phi : \equiv \left ( \alpha \vee \beta \right ) \) where \( \alpha , \beta \) are formulas of \( \mathcal{L} \)
5. \( \phi : \equiv \left ( \forall v \right ) \left ( \alpha \right ) \) where \( v \) is a variable and \( \alpha \) is a formula of \( \mathcal{L} \)

The atomic formulas of \( \mathcal{ L } \) are formulas that satisfy clause 1 or 2 of their definition

We define the language \( \mathcal{L}_{N T} = \left ( \left \lbrace \mathtt{0} \right \rbrace , \left \lbrace \mathtt{S} , \mathtt{+} , \mathtt{\cdot} , \mathtt{E} \right \rbrace , \left \lbrace \mathtt{\lt} \right \rbrace \right ) \) as the language of number theory.

Fix a language \( \mathcal{L} \). An \( \mathcal{L} \)-structure \( \mathfrak{A} \) is a non-empty set \( A \), called the universe of \( \mathfrak{A} \), such that the following holds:

• For each constant symbol \( c \) of \( \mathcal{L} \), we have an element \( c^{\mathfrak{A}} \) of \( A \)
• For each \( n \)-ary function symbol \( f \) of \( \mathcal{L} \), we have a function \( f^{\mathfrak{A}}{:} A^{n} \to A \)
• For each \( n \)-ary relation symbol \( R \) of \( \mathcal{L} \), we have an \( n \)-ary relation \( R^{\mathfrak{A}} \) on \( A \)

Similar to a language we may denote it by \( \left ( A , \left \lbrace c^{\mathfrak{A}} : c \in C_{\mathcal{L}} \right \rbrace , \left \lbrace f^{\mathfrak{A}}{:} f{\in} F_{\mathcal{L}} \right \rbrace , \left \lbrace R^{\mathfrak{A}} : R \in R_{\mathcal{L}} \right \rbrace \right ) \)

Given \( \mathcal{L}_{N T} \), we define the structure \( \mathfrak{N} := \left ( \mathbb{N}_{0} , \left \lbrace 0 \right \rbrace , \left \lbrace S , + , \cdot , E \right \rbrace , \left \lbrace \lt \right \rbrace \right ) \), where the constant symbol \( \mathtt{0} \) maps to \( 0 \) (the element of \( \mathbb{N}_{0} \)), \( S \) is the successor function \( S \left ( 2 \right ) = 3 \), \( + \) is usual addition \( 3 + 3 = 6 \), \( \cdot \) multiplication \( 2 \cdot 4 = 8 \), \( E \) for exponentiation \( E \left ( 3 , 2 \right ) = 9 \)

If \( \mathfrak{A} \) is an \( \mathcal{L} \)-structure, a variable assignment function is any function of the form \( s : V_{\mathcal{L}} \to A \)

If \( s \) is a variable assigment function into \( \mathfrak{A} \) and \( x \in V_{\mathcal{L}} \) and \( a \in A \), then \( s \left [ x \mid a \right ] \) is the variable assigment function defined as follows and we say that \( s \left [ x \mid a \right ] \) is an \( x \)-modification of the assigment function \( s \)

Suppose that \( \mathfrak{A} \) is an \( L \)-structure and \( s \) is a variable assigment function into \( \mathfrak{A} \). The function \( \overline{s} \), called the term assigment function generated by \( s \), is the function with domain consisting of the set of \( \mathcal{L} \) terms and codomain \( A \) defined as follows

• if \( t \) is a variable then \( \overline{s} \left ( t \right ) = s \left ( t \right ) \)
• if \( t \) is the constant \( c \) then \( \overline{s} \left ( t \right ) = c^{\mathfrak{A}} \)
• if \( t : \equiv f{t}_{1} t_{2} \ldots t_{n} \) then \( \overline{s} \left ( t \right ) = f^{\mathfrak{A}}{\left ( \overline{s} \left ( t_{1} \right ) , \overline{s} \left ( t_{2} \right ) , \ldots , \overline{s} \left ( t_{n} \right ) \right )} \)

Given an \( \mathcal{L} \)-structure \( \mathfrak{A} \), and a term \( t \) from \( \mathcal{L} \), we say that it's interpretation in \( \mathfrak{A} \) is \( \overline{s} \left ( t \right ) \)

Suppose that \( v \) is a varaible and \( \phi \) is a formula, then \( v \) is free in \( \phi \) iff exactly one of the following holds:

1. \( \phi \) is atomic and \( v \) occurs in \( \alpha \)
2. \( \phi :\equiv \left( \neg \alpha \right) \) and \( v \) is free in \( \alpha \)
3. \( \phi : \equiv \left( \alpha \lor \beta \right) \) and \( v \) is free in at least one of \( \alpha \) or \( \beta \)
4. \( \phi : \equiv \left( \forall u \right) \left( \alpha \right) \) and \( v \) is not \( u \) and \( v \) is free in \( \alpha \)