Skolem normal form
In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers.
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers. Every first-order formula may be converted into Skolem normal form while not changing its satisfiability via a process called Skolemization (sometimes spelled Skolemnization).
The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it: it is satisfiable if and only if the original one is satisfiable. Reduction to Skolem normal form is a method for removing existential quantifiers from formal logic statements, often performed as the first step in an automated theorem prover.
How Skolemization works
Skolemization works by applying a second-order equivalence together with the definition of first-order satisfiability. The equivalence provides a way for "moving" an existential quantifier before a universal one. \forall x \exists y R(x,y) \iff \exists f \forall x R(x,f(x)) where f(x) is a function that maps x to y . Intuitively, the sentence "for every x there exists a y such that R(x,y) " is converted into the equivalent form "there exists a function f mapping every x into a y such that, for every x it holds that R(x,f(x)) ". This equivalence is useful because the definition of first-order satisfiability implicitly existentially quantifies over functions interpreting the function symbols.
In particular, a first-order formula \Phi is satisfiable if there exists a model M and an evaluation \mu of the free variables of the formula that evaluate the formula to true. The model contains the interpretation of all function symbols; therefore, Skolem functions are implicitly existentially quantified.
In the example above, \forall x R(x,f(x)) is satisfiable if and only if there exists a model M , which contains an interpretation for f , such that \forall x R(x,f(x)) is true for some evaluation of its free variables (none in this case). This may be expressed in second order as \exists f \forall x R(x,f(x)) . By the above equivalence, this is the same as the satisfiability of \forall x \exists y R(x,y) . At the meta-level, first-order satisfiability of a formula \Phi may be written with a little abuse of notation as \exists M \exists \mu ( M,\mu \models \Phi) , where M is a model, \mu is an evaluation of the free variables, and \models means that \Phi is true in M under \mu .
Since first-order models contain the interpretation of all function symbols, any Skolem function that \Phi contains is implicitly existentially quantified by \exists M . As a result, after replacing existential quantifiers over variables by existential quantifiers over functions at the front of the formula, the formula still may be treated as a first-order one by removing these existential quantifiers. This final step of treating \exists f \forall x R(x,f(x)) as \forall x R(x,f(x)) may be completed because functions are implicitly existentially quantified by \exists M in the definition of first-order satisfiability.
Correctness of Skolemization may be shown on the example formula F_1 = \forall x_1 \dots \forall x_n \exists y R(x_1,\dots,x_n,y) as follows. This formula is satisfied by a model M if and only if, for each possible value for x_1,\dots,x_n in the domain of the model, there exists a value for y in the domain of the model that makes R(x_1,\dots,x_n,y) true.
By the axiom of choice, there exists a function f such that y = f(x_1,\dots,x_n) . As a result, the formula F_2 = \forall x_1 \dots \forall x_n R(x_1,\dots,x_n,f(x_1,\dots,x_n)) is satisfiable, because it has the model obtained by adding the interpretation of f to M . This shows that F_1 is satisfiable only if F_2 is satisfiable as well. Conversely, if F_2 is satisfiable, then there exists a model M' that satisfies it; this model includes an interpretation for the function f such that, for every value of x_1,\dots,x_n , the formula R(x_1,\dots,x_n,f(x_1,\dots,x_n)) holds.
As a result, F_1 is satisfied by the same model because one may choose, for every value of x_1,\ldots,x_n , the value y=f(x_1,\dots,x_n) , where f is evaluated according to M' .
Uses of Skolemization
One of the uses of Skolemization is within automated theorem proving. For example, in the method of analytic tableaux, whenever a formula whose leading quantifier is existential occurs, the formula obtained by removing that quantifier via Skolemization may be generated.
For example, if \exists x \Phi(x,y_1,\ldots,y_n) occurs in a tableau, where x,y_1,\ldots,y_n are the free variables of \Phi(x,y_1,\ldots,y_n) , then \Phi(f(y_1,\ldots,y_n),y_1,\ldots,y_n) may be added to the same branch of the tableau. This addition does not alter the satisfiability of the tableau: every model of the old formula may be extended, by adding a suitable interpretation of f , to a model of the new formula.
This form of Skolemization is an improvement over "classical" Skolemization in that only variables that are free in the formula are placed in the Skolem term. This is an improvement because the semantics of tableaux may implicitly place the formula in the scope of some universally quantified variables that are not in the formula itself; these variables are not in the Skolem term, while they would be there according to the original definition of Skolemization.
Another improvement that may be used is applying the same Skolem function symbol for formulae that are identical up to variable renaming. Another use is in the resolution method for first-order logic, where formulas are represented as sets of clauses understood to be universally quantified. (For an example see drinker paradox.)
An important result in model theory is the Löwenheim–Skolem theorem, which can be proven via Skolemizing the theory and closing under the resulting Skolem functions.
Skolem theories
In general, if T is a theory and for each formula with free variables x_1, \dots, x_n, y there is an n-ary function symbol F that is provably a Skolem function for y , then T is called a Skolem theory. Every Skolem theory is model complete, i.e. every substructure of a model is an elementary substructure.
Given a model M of a Skolem theory T, the smallest substructure of M containing a certain set A is called the Skolem hull of A. The Skolem hull of A is an atomic prime model over A.
See also
Herbrandization, the dual of Skolemization Predicate functor logic
External links
Skolemization on PlanetMath.org Skolemization by Hector Zenil, The Wolfram Demonstrations Project.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1347481897 under CC BY-SA 4.0; modifications have been made.