Theory of the models

The theory of the models is a theory of the mathematical truth. It primarily consists in saying that a theory is mathematically valid if one can define a universe in which it is true.

Presentation of the theory of the models

She was formulated in a complete and coherent way initially by Alfred Tarski, which called it also the Sémantique Calcul of the predicates, for two reasons.

• It gives a definition of the truth and logical consequence independent of what the demonstrations in Logique give.

• It gives an answer partial to the question of the significance of the language, because the words have direction if they make it possible to make true sentences in a possible world.

But its roots are much more remote. A first models deliberately created appears with the birth of the nonEuclidean geometries. Initially purely deductive, these geometries were accepted little by little as from the moment when one could give models of them, i.e. geometrical supports with specific interpretations to indicate the lines. Poincaré for example gives a model of the hyperbolic plan starting from a half-plane of the complex plan.

Symmetrically, if one can say, the Buée abbot and Jean-Robert Argand (plane of Argand), then Gauss and Cauchy give a geometrical model of the Complex numbers.

A model is used initially as structure to validate a logical or mathematical theory.

It will be said that a theory is noncontradictory if there exists a model in which it is true. It will be said that it is consistent (or coherent ) if it does not make it possible to prove at the same time a formula and its negation. It is not always easy or possible to show that a theory is consistent. It is sometimes easier to show than it is noncontradictory, since it is enough for that to highlight a model. The Théorème of complétude of Gödel can be regarded as the fundamental theorem of the theory of the models. It establishes an equivalence between the two concepts of non-contradiction and consistency, and makes it possible to show that a formula is true in very model if and only if it is provable in an adequate system of deduction. It closes research which go back to the theorem of Löwenheim (1915) and which takes as a starting point an approach hilbertienne of the mathematical truth. A model thus gives the certainty to work on a theory which will not lead to a contradiction.

Models of traditional propositional calculation

In propositional Calculation of the traditional Logical , it does not have there existential or universal quantifiers. The formulas consist of atomic proposals connected repeatedly by logical connectors. A model consists in defining, for each atomic propositional variable, a value of truth (true or false). One can then deduce the truth or falseness from it from any complex formula.

The complexity of a formula is measured by the maximum number encased operators. For example in $(\backslash \; lnot\; P)\; \backslash \; lor\; (Q\; \backslash \; Land\; R)$, the or $\backslash \; lor$ and the not $\backslash \; lnot$ is encased one in the other. But the not and the and $\backslash \; land$ are not it. This proposal is of complexity 2 because it has to the maximum two encased operators.

The formulas of complexity 0 are the atomic formulas. It is the selected model which defines their value of truth.

Let us suppose that the truth and the falseness of all the formulas of $n$ complexity were defined. Let us show how to define the truth and the falseness of the formulas of $n+1$ complexity. That is to say $P$ a formula of $n+1$ complexity, obtained starting from the formula or from the formulas $Q$ and $R$ of $n$ complexity or lower, by means of a logical connector. The truth or the falseness of $Q$ and $R$ is thus already defined.

a) $P\; =\; \backslash \; lnot\; Q$: If $Q$ is true then $P$ is false, by definition of the negation. If $Q$ is false then $P$ is true, for the same reason.

b) $P\; =\; (Q\; \backslash \; Land\; R)$: If $Q$ and $R$ are all two truths then $P$ also, but $P$ is false in all the other cases.

c) $P\; =\; (Q\; \backslash \; lor\; R)$: If $Q$ and $R$ are all the two forgeries then $P$ also, but $P$ is true in all the other cases.

d) $P\; =\; (Q\; \backslash \; to\; R)$: If $Q$ is true and $R$ is false then $P$ is false, but $P$ is true in all the other cases.

A true formula in very model is called a tautology . If the formula has $n$ variable propositional atomic, it is enough in fact to check the truth of the formula in the possible model $2^n$ giving the various values of truth to the $n$ atomic proposals. The number of models being finished, it results from it that the calculation of the proposals is décidable: there exists an algorithm making it possible to decide if a formula is a tautology or not.

In addition, the Théorème of complétude of the calculation of the proposals establishes equivalence between being a tautology and being provable in an adequate system of deduction.

Examples

Let us show that $((P\; \backslash \; to\; Q)\; \backslash \; to\; P)\; \backslash \; to\; P$ (Loi of Peirce) is a tautology, by using the rule d). If $P$ is true, then $((P\; \backslash \; to\; Q)\; \backslash \; to\; P)\; \backslash \; to\; P$ being form $R\; \backslash \; to\; P$ is true. If $P$ is false, then $P\; \backslash \; to\; Q$ is true, $(P\; \backslash \; to\; Q)\; \backslash \; to\; P$ is false, and $((P\; \backslash \; to\; Q)\; \backslash \; to\; P)\; \backslash \; to\; P$ is true.

Being true in very model, $((P\; \backslash \; to\; Q)\; \backslash \; to\; P)\; \backslash \; to\; P$ is a tautology. It is thus also provable by means of systems of deduction, for example the natural Déduction.

On the other hand, $(P\; \backslash \; to\; Q)\; \backslash \; to\; P$ is not provable. Indeed, in a model where $P$ is false, $(P\; \backslash \; to\; Q)\; \backslash \; to\; P$ is also false.

Models in the calculation of the predicates

In the Calculation of the predicates first order of the traditional Logical , the predicates used apply to variables. To define a model, it is thus advisable to introduce a unit whose elements will be used as values to allot to the variables. As for propositional calculation, one starts by defining the truth or the falseness of the atomic formulas in a field given, before gradually defining the truth or the falseness of the made up formulas. One can thus define by successive stages the truth of all the complex formulas of first order logic made up starting from the fundamental symbols of a theory.

A formula is atomic when it does not contain logical operators (negation, conjunction, existentiation,…). Atomic does not want to say here that a formula contains one symbol but only which it contains only one symbol of fundamental predicate. The other names which it contains are names of object and they can be very complex. That a formula is atomic wants to say that it does not contain a subformula. It is about a logical atomicity.

The interpretation of the atomic formulas in a model

An interpretation of a first order language is defined by the following elements.

• a nonempty unit U, universe of the theory. With each name of object (constant) mentioned in the language is associated an element with U.

• has each unary predicate (in a place) fundamental mentioned in the language is associated part of U, the extension of this predicate. It is the whole of the values for which one decides that the predicate is true. With each fundamental binary predicate mentioned in the language part of the Cartesian product is associated U × U, it is the whole of all the couples for which the predicate is true. In the same way for the ternary predicates, or of higher arite.
• has each unary operator mentioned in the language is associated a function with U in U. With each binary operator mentioned in the language is associated a function with U × U in U. In the same way for the higher arite operators.

The unit U, or the interpretation of which it forms part, is a model of a theory when all the axioms of this theory are true relative with this interpretation.

The use of the word, model, is sometimes multiple. Sometimes it indicates the unit U, sometimes the whole of the true atomic formulas, sometimes interpretation. Often, when a model of a theory is said, it is supposed automatically that it is true there. But it is also said that a theory is false in a model.

The definition of the truth of the complex formulas

As soon as one has an interpretation of a theory, the truth of all the formulas which mention only the fundamental constants, predicates and operators, can be defined. One starts with the atomic formulas and one proceeds recursively to the more complex formulas.

One takes again the rules defined in the paragraph relating to the models of propositional calculation, and one defines the two additional rules, relating to the universal and existential quantifier.

e) $P\; =\; \backslash \; forall\; X\; \backslash ;\; Q$: If one of the formulas obtained in substituent an element of U to all the free occurrences of $x$ in the interpretation of $Q$ is false then $P$ is false, if not, if $Q$ does not have other free variables that $x$, $P$ is true.

f) $P\; =\; \backslash \; exists\; X\; \backslash ;\; Q$: If one of the formulas obtained in substituent an element of U to all the free occurrences of $x$ in the interpretation of $Q$ is true then $P$ is true, if not, if $Q$ does not have other free variables that $x$, $P$ is false.

e) and F) make it possible to define the truth and the falseness of all the closed formulas, i.e. without free variables.

The truth and the falseness of all the complex formulas, without free variables, of first order logic, can thus be given in a given model.

A true formula in very model is called logical law or theorem. As for propositional calculation, the Théorème of complétude of Gödel states equivalence between logical law and provable formula in an adequate system of deduction. This result is remarkable, taking into account the fact that, contrary to the calculation of the proposals, the number of models which can be considered is in general infinite. Moreover, contrary to the calculation of the proposals, the calculation of the predicates is not décidable.

Examples

The formula $\backslash \; exist\; X\; \backslash ;\; \backslash \; forall\; there\; \backslash ;\; (R\; (X)\; \backslash \; to\; R\; (there))$ is a logical law. Indeed, let us consider a nonempty model U. There are then two possibilities.

• Or one allots the true value to R ( there ) when is seen there allotted an unspecified value in U , and in this case, one allots to X an unspecified value in U. the implication $R\; (X)\; \backslash \; to\; R\; (there)$ is then true for all there in U, therefore $\backslash \; forall\; there\; \backslash ;\; (R\; (X)\; \backslash \; to\; R\; (there))$ is also true in U, and X also indicating an element of U, $\backslash \; exist\; X\; \backslash ;\; \backslash \; forall\; there\; \backslash ;\; (R\; (X)\; \backslash \; to\; R\; (there))$ is true in U.
• Or one allots the value forgery to R ( there ) for at least a in U. then Indicate there by X this element. Then for all there of U, $R\; (X)\; \backslash \; to\; R\; (there)$ is true, therefore $\backslash \; forall\; there\; \backslash ;\; (R\; (X)\; \backslash \; to\; R\; (there))$ is true in U, and thus $\backslash \; exist\; X\; \backslash ;\; \backslash \; forall\; there\; \backslash ;\; (R\; (X)\; \backslash \; to\; R\; (there))$ is also true.

In both cases, the formula is true. U being unspecified, the formula is true in very model, and can also be proven by means of a system of deduction.

On the other hand, the formula $\backslash \; exists\; X\; (P\; \backslash \; to\; Q\; (X))\; \backslash \; to\; (P\; \backslash \; to\; \backslash \; forall\; X\; Q\; (X))$ is not provable. It is enough to take as model a unit U with two elements has and B , to pose P and Q ( has ) true, and Q ( B ) false. $P\; \backslash \; to\; \backslash \; forall\; X\; Q\; (X)$ is false in U, whereas $\backslash \; exists\; X\; (P\; \backslash \; to\; Q\; (X))$ is true (with X = has ). It results from it that $\backslash \; exists\; X\; (P\; \backslash \; to\; Q\; (X))\backslash \; to\; (P\; \backslash \; to\; \backslash \; forall\; X\; Q\; (X))$ is false in U. the formula being falsifiable is not a theorem.

Models of logic intuitionalist

The models presented up to now are models of the traditional Logique. But there exist other logics, for example the Logique intuitionalist which is a logic which builds the demonstrations starting from the premises. There exists for this logic a theory of the models, the model of Kripke with a theorem of complétude: a formula is demonstrable in logic intuitionalist if and only if it is true in very model of Kripke.

These models make it possible for example to answer the following questions. That is to say $F$ a closed formula:

• Or $F$ is not a theorem of logic intutionnist. To show it, it is enough to exhiber a model of Kripke which invalidates the formula.
• Or $F$ is a theorem of traditional logic. To show it, it is enough to give of it a demonstration in a system of deduction of traditional logic. There are then two under-cases:

Or $F$ is also a theorem of logic intuitionalist. To show it, it is enough to give of it a demonstration in a system of intuitionalist deduction (or to show that $F$ is true in all the models of Kripke).

Or $F$ is not demonstrable in logic intuitionalist. To show it, it is enough to give a model of Kripke invalidating the formula.

Thus one can show that:

$(\backslash \; lnot\; \backslash \; forall\; X\; \backslash ;\; F\; (X))\; \backslash \; to\; (\backslash \; exists\; X\; \backslash ;\; \backslash \; lnot\; F\; (X))$ is a theorem of traditional logic, but not of logic intuitionalist.

$(\backslash \; lnot\; \backslash \; exists\; X\; \backslash ;\; F\; (X))\; \backslash \; to\; (\backslash \; forall\; X\; \backslash ;\; \backslash \; lnot\; F\; (X))$ is a theorem of logic intuitionalist (and also of traditional logic).

The models of Kripke are also used to give models for the modal logical .

Examples of application of the models

We already gave applications of the models:

• to satisfy or on the contrary to falsify a formula (for example to distinguish true formula in traditional logic but distorts in logic intuitionalist: the formula is true in very traditional model, but there exists a model in logic intuitionalist which falsifies it).
• to prove that a theory or a system of axioms is not contradictory by exhibant a model satisfying all the axioms.

With regard to the systems of axioms, the models also intervene to show the independence of the axioms between them, or to establish the consistency of an axiomatic system while being based on the consistency of another system. Let us give some examples.

In geometry, Ve postulate of Euclide is independent of the other axioms of the geometry. Indeed, on the one hand, the plan of the Euclidean Géométrie is a model in which this postulate is true. In addition, the Demi-plan of Poincaré is a model of the hyperbolic Géométrie in which this postulate is false. In this model, the universe (the hyperbolic plan) is consisted of the points of the higher open Euclidean half-plane $\backslash \; \{(X,\; there)\; \backslash ;\; |\backslash ;\; y>0\; \backslash \}$. The lines of the hyperbolic plan are the whole of equation $x\; =\; a$ or $(x-a)\; ^2\; +\; y^2\; =\; R^2$.

In this universe, if one gives oneself a line and a point external on this line, there exists an infinity of right-hand sides passing by the point and not secants with the first right-hand side.

In this example, one sees that one can define the objects of a new model (right-hand sides of the hyperbolic plan) while making use of other objects of another model (half-lines and half-circles of the Euclidean half-plane). If one supposes the consistency of the Euclidean model, then one established the consistency of the hyperbolic model.

This use of model to show the relative consistency of another model is very frequent. Let us consider for example the axiomatic Théorie of the units, noted ZF. In addition let us consider ZF to which one adds the Axiome of the choice, noted ZFC. One can show that if ZF is consistent, then ZFC too. One is indeed able to define a function F defined on the ordinal which with very ordinal $\backslash \; alpha$ associates a unit $F\_\; \{\backslash \; alpha\}$, and $L\; classifies\; it\; =\; \backslash \; \{F\_\; \{\backslash \; alpha\}\; \backslash ;\; |\backslash ;\; \backslash \; alpha\; \backslash ;\; \backslash \; mathrm\; \{ordinal\}\; \backslash \}$ so that:

• $L$ checks all the axioms of ZF
• the units $F\_\; \{\backslash \; alpha\}$ pertaining to $L$ are constructible in the direction where $F\_\; \{\backslash \; alpha\}$ is defined starting from the $F\_\; \{\backslash \; beta\}$, for , by transfinite Récurrence.
• For all $x$ of $L$, one defines the order of $x$ as being smallest ordinal $\backslash \; alpha$ such as $x\; =\; F\_\; \{\backslash \; alpha\}$.
• all $x$ of $L$, one can associate $y$ to him element of $x$ of a minimal nature, defining a function $f$ $L$ in $L$ by posing $y\; =\; F\; (X)$.

One then defined in $L$ a function $f$ checking $\backslash \; forall\; X,\; F\; (X)\; \backslash \; in\; x$. In other words, $f$ is a function of choice in $L$, and $L$ checks ZF as well as the axiom of the choice. $L$ is thus a model of ZFC.

Always in the set theory, if one poses $R\_0\; =\; \backslash \; varnothing$ and for entire $n$, $R\_\; \{n+1\}\; =\; \backslash \; mathfrak\; P\; (R\_n)$ (together of the parts of $R\_n$), then the meeting of the $R\_n$ for all $n$ whole defines a model which checks all the axioms of ZF except the Axiome of infinite the. This proves that this last axiom cannot be proven starting from the other axioms.

See also

• Calculation of the predicates
• Calculation of the proposals
• natural Deduction
• traditional Skolémisation
• Logical
• Logical minimal intuitionalist
• Logical
• Semantic Model
• of Kripke

Random links:

Saint-Romain-in-Gier | Madhukar | Quintus Fabius Vibulanus (consul in -467) | Boogy (album of Jackson 5) | Fusion (rock'n'roll) | Banlieue_noire_de_Spring_Hill,_comté_de_Fayette,_Pennsylvanie

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org