HOME

TheInfoList



OR:

In
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, a
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
of
first-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
is in Skolem normal form if it is in
prenex normal form A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propos ...
with only universal first-order quantifiers. Every first-order
formula In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
may be converted into Skolem normal form while not changing its
satisfiability In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
via a process called Skolemization (sometimes spelled Skolemnization). The resulting formula is not necessarily
equivalent Equivalence or Equivalent may refer to: Arts and entertainment *Album-equivalent unit, a measurement unit in the music industry *Equivalence class (music) *'' Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre *'' Equiva ...
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 Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
statements, often performed as the first step in an
automated theorem prover Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a ma ...
.


Examples

The simplest form of Skolemization is for existentially quantified variables that are not inside the scope of a universal quantifier. These may be replaced simply by creating new constants. For example, \exists x P(x) may be changed to P(c), where c is a new constant (does not occur anywhere else in the formula). More generally, Skolemization is performed by replacing every existentially quantified variable y with a term f(x_1,\ldots,x_n) whose function symbol f is new. The variables of this term are as follows. If the formula is in
prenex normal form A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propos ...
, then x_1,\ldots,x_n are the variables that are universally quantified and whose quantifiers precede that of y. In general, they are the variables that are quantified universally (we assume we get rid of existential quantifiers in order, so all existential quantifiers before \exists y have been removed) and such that \exists y occurs in the scope of their quantifiers. The function f introduced in this process is called a Skolem function (or Skolem constant if it is of zero
arity In logic, mathematics, and computer science, arity () is the number of arguments or operands taken by a function, operation or relation. In mathematics, arity may also be called rank, but this word can have many other meanings. In logic and ...
) and the term is called a Skolem term. As an example, the formula \forall x \exists y \forall z P(x,y,z) is not in Skolem normal form because it contains the existential quantifier \exists y. Skolemization replaces y with f(x), where f is a new function symbol, and removes the quantification over The resulting formula is \forall x \forall z P(x,f(x),z). The Skolem term f(x) contains x, but not z, because the quantifier to be removed \exists y is in the scope of \forall x, but not in that of \forall z; since this formula is in prenex normal form, this is equivalent to saying that, in the list of quantifiers, x precedes y while z does not. The formula obtained by this transformation is satisfiable if and only if the original formula is.


How Skolemization works

Skolemization works by applying a
second-order Second-order may refer to: Mathematics * Second order approximation, an approximation that includes quadratic terms * Second-order arithmetic, an axiomatization allowing quantification of sets of numbers * Second-order differential equation, a d ...
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 A model is an informative representation of an object, person, or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin , . Models can be divided in ...
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 In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
, 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 Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a majo ...
. For example, in the
method of analytic tableaux In proof theory, the semantic tableau (; plural: tableaux), also called an analytic tableau, truth tree, or simply tree, is a decision procedure for sentential logic, sentential and related logics, and a proof procedure for formulae of first-order ...
, 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 Two Mathematical object, mathematical objects and are called "equal up to an equivalence relation " * if and are related by , that is, * if holds, that is, * if the equivalence classes of and with respect to are equal. This figure of speech ...
variable renaming. Another use is in the resolution method for first-order logic, where formulas are represented as sets of
clause In language, a clause is a Constituent (linguistics), constituent or Phrase (grammar), phrase that comprises a semantic predicand (expressed or not) and a semantic Predicate (grammar), predicate. A typical clause consists of a subject (grammar), ...
s understood to be universally quantified. (For an example see
drinker paradox The drinker paradox (also known as the drinker's theorem, the drinker's principle, or the drinking principle) is a theorem of classical predicate logic that can be stated as "There is someone in the pub such that, if he or she is drinking, then e ...
.) An important result in
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
is the
Löwenheim–Skolem theorem In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. It implies that if a countable first-order ...
, which can be proven via Skolemizing the theory and closing under the resulting Skolem functions.


Skolem theories

In general, if T is a
theory A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, ...
and for each formula with
free variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a variable may be said to be either free or bound. Some older books use the terms real variable and apparent variable for f ...
s 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."Sets, Models and Proofs" (3.3) by I. Moerdijk and J. van Oosten
/ref> Every Skolem theory is
model complete In model theory, a first-order theory is called model complete if every embedding of its models is an elementary embedding. Equivalently, every first-order formula is equivalent to a universal formula. This notion was introduced by Abraham Robins ...
, i.e. every substructure of a model is an
elementary substructure In model theory, a branch of mathematical logic, two structures ''M'' and ''N'' of the same signature ''σ'' are called elementarily equivalent if they satisfy the same first-order ''σ''-sentences. If ''N'' is a substructure of ''M'', one oft ...
. 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 In mathematics, and in particular model theory, a prime model is a model that is as simple as possible. Specifically, a model P is prime if it admits an elementary embedding into any model M to which it is elementarily equivalent (that is, into a ...
over ''A''.


History

Skolem normal form is named after the late Norwegian mathematician
Thoralf Skolem Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory. Life Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skole ...
.


See also

* Herbrandization, the dual of Skolemization *
Predicate functor logic In mathematical logic, predicate functor logic (PFL) is one of several ways to express first-order logic (also known as predicate logic) by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic devices ...


Notes


References

*


External links

*
Skolemization on PlanetMath.org

Skolemization
by Hector Zenil,
The Wolfram Demonstrations Project The Wolfram Demonstrations Project is an open-source collection of interactive programmes called Demonstrations. It is hosted by Wolfram Research. At its launch, it contained 1300 demonstrations but has grown to over 10,000. The site won a Pa ...
. * Normal forms (logic) Model theory {{Normal forms in logic