information:classification, quality:corruption
First-order logic

A first-order formula is built out of atomic formulas such as R (f (x, y), z) {\displaystyle R(f(x,y),z)} or y = x + 1 {\displaystyle y=x+1} by means of the Boolean connectives ¬, ∧, ∨, → {\displaystyle \neg,\land,\lor,\rightarrow } and prefixing of quantifiers ∀ v {\displaystyle \forall v} or ∃ v {\displaystyle \exists v}. A sentence is a formula in which each occurrence of a variable is in the scope of a corresponding quantifier. Examples for formulas are φ {\displaystyle \varphi } (or φ (x) {\displaystyle \varphi (x)} to indicate x {\displaystyle x} is the unbound variable in φ {\displaystyle \varphi }) and ψ {\displaystyle \psi } (or ψ (x) {\displaystyle \psi (x)}), defined as follows:

(Note that the equality symbol has a double meaning here.) It is intuitively clear how to translate such formulas into mathematical meaning. In the σ -structure N {\displaystyle {\mathcal {N}}} of the natural numbers, for example, an element n {\displaystyle n} satisfies the formula φ {\displaystyle \varphi } if and only if n {\displaystyle n} is a prime number. The formula ψ {\displaystyle \psi } similarly defines irreducibility. Tarski gave a rigorous definition, sometimes called "Tarski's definition of truth", for the satisfaction relation ⊨ {\displaystyle \models }, so that one easily proves:

A set T {\displaystyle T} of sentences is called a (first-order) theory, which takes the sentences in the set as its axioms. A theory is satisfiable if it has a model M ⊨ T {\displaystyle {\mathcal {M}}\models T}, i.e. a structure (of the appropriate signature) which satisfies all the sentences in the set T {\displaystyle T}. A complete theory is a theory that contains every sentence or its negation.The complete theory of all sentences satisfied by a structure is also called the theory of that structure.

It's a consequence of Gödel's completeness theorem (not to be confused with his incompleteness theorems) that a theory has a model if and only if it is consistent, i.e. no contradiction is proved by the theory.Therefore, model theorists often use "consistent" as a synonym for "satisfiable".