Free Interpretation, Quotient Interpretation and Substitution of a Letter with a Term for First Order Languages

Marco Caminati

Formalized Mathematics (2011)

  • Volume: 19, Issue: 3, page 193-203
  • ISSN: 1426-2630

Abstract

top
Fourth of a series of articles laying down the bases for classical first order model theory. This paper supplies a toolkit of constructions to work with languages and interpretations, and results relating them. The free interpretation of a language, having as a universe the set of terms of the language itself, is defined.The quotient of an interpreteation with respect to an equivalence relation is built, and shown to remain an interpretation when the relation respects it. Both the concepts of quotient and of respecting relation are defined in broadest terms, with respect to objects as general as possible.Along with the trivial symbol substitution generally defined in [11], the more complex substitution of a letter with a term is defined, basing right on the free interpretation just introduced, which is a novel approach, to the author's knowledge. A first important result shown is that the quotient operation commute in some sense with term evaluation and reassignment functors, both introduced in [13] (theorem 3, theorem 15). A second result proved is substitution lemma (theorem 10, corresponding to III.8.3 of [15]). This will be vital for proving satisfiability theorem and correctness of a certain sequent derivation rule in [14]. A third result supplied is that if two given languages coincide on the letters of a given FinSequence, their evaluation of it will also coincide. This too will be instrumental in [14] for proving correctness of another rule. Also, the Depth functor is shown to be invariant with respect to term substitution in a formula.

How to cite

top

Marco Caminati. "Free Interpretation, Quotient Interpretation and Substitution of a Letter with a Term for First Order Languages." Formalized Mathematics 19.3 (2011): 193-203. <http://eudml.org/doc/267605>.

@article{MarcoCaminati2011,
abstract = {Fourth of a series of articles laying down the bases for classical first order model theory. This paper supplies a toolkit of constructions to work with languages and interpretations, and results relating them. The free interpretation of a language, having as a universe the set of terms of the language itself, is defined.The quotient of an interpreteation with respect to an equivalence relation is built, and shown to remain an interpretation when the relation respects it. Both the concepts of quotient and of respecting relation are defined in broadest terms, with respect to objects as general as possible.Along with the trivial symbol substitution generally defined in [11], the more complex substitution of a letter with a term is defined, basing right on the free interpretation just introduced, which is a novel approach, to the author's knowledge. A first important result shown is that the quotient operation commute in some sense with term evaluation and reassignment functors, both introduced in [13] (theorem 3, theorem 15). A second result proved is substitution lemma (theorem 10, corresponding to III.8.3 of [15]). This will be vital for proving satisfiability theorem and correctness of a certain sequent derivation rule in [14]. A third result supplied is that if two given languages coincide on the letters of a given FinSequence, their evaluation of it will also coincide. This too will be instrumental in [14] for proving correctness of another rule. Also, the Depth functor is shown to be invariant with respect to term substitution in a formula.},
author = {Marco Caminati},
journal = {Formalized Mathematics},
language = {eng},
number = {3},
pages = {193-203},
title = {Free Interpretation, Quotient Interpretation and Substitution of a Letter with a Term for First Order Languages},
url = {http://eudml.org/doc/267605},
volume = {19},
year = {2011},
}

TY - JOUR
AU - Marco Caminati
TI - Free Interpretation, Quotient Interpretation and Substitution of a Letter with a Term for First Order Languages
JO - Formalized Mathematics
PY - 2011
VL - 19
IS - 3
SP - 193
EP - 203
AB - Fourth of a series of articles laying down the bases for classical first order model theory. This paper supplies a toolkit of constructions to work with languages and interpretations, and results relating them. The free interpretation of a language, having as a universe the set of terms of the language itself, is defined.The quotient of an interpreteation with respect to an equivalence relation is built, and shown to remain an interpretation when the relation respects it. Both the concepts of quotient and of respecting relation are defined in broadest terms, with respect to objects as general as possible.Along with the trivial symbol substitution generally defined in [11], the more complex substitution of a letter with a term is defined, basing right on the free interpretation just introduced, which is a novel approach, to the author's knowledge. A first important result shown is that the quotient operation commute in some sense with term evaluation and reassignment functors, both introduced in [13] (theorem 3, theorem 15). A second result proved is substitution lemma (theorem 10, corresponding to III.8.3 of [15]). This will be vital for proving satisfiability theorem and correctness of a certain sequent derivation rule in [14]. A third result supplied is that if two given languages coincide on the letters of a given FinSequence, their evaluation of it will also coincide. This too will be instrumental in [14] for proving correctness of another rule. Also, the Depth functor is shown to be invariant with respect to term substitution in a formula.
LA - eng
UR - http://eudml.org/doc/267605
ER -

References

top
  1. Grzegorz Bancerek. Cardinal numbers. Formalized Mathematics, 1(2):377-382, 1990. 
  2. Grzegorz Bancerek. The fundamental properties of natural numbers. Formalized Mathematics, 1(1):41-46, 1990. Zbl06213858
  3. Grzegorz Bancerek. The ordinal numbers. Formalized Mathematics, 1(1):91-96, 1990. 
  4. Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990. 
  5. Czesław Byliński. Finite sequences and tuples of elements of a non-empty sets. Formalized Mathematics, 1(3):529-536, 1990. 
  6. Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 
  7. Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153-164, 1990. 
  8. Czesław Byliński. The modification of a function by a function and the iteration of the composition of a function. Formalized Mathematics, 1(3):521-527, 1990. 
  9. Czesław Byliński. Partial functions. Formalized Mathematics, 1(2):357-367, 1990. 
  10. Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47-53, 1990. 
  11. Marco B. Caminati. Preliminaries to classical first order model theory. Formalized Mathematics, 19(3):155-167, 2011, doi: 10.2478/v10037-011-0025-2.[Crossref] Zbl1276.03030
  12. Marco B. Caminati. Definition of first order language with arbitrary alphabet. Syntax of terms, atomic formulas and their subterms. Formalized Mathematics, 19(3):169-178, 2011, doi: 10.2478/v10037-011-0026-1.[Crossref] Zbl1276.03031
  13. Marco B. Caminati. First order languages: Further syntax and semantics. Formalized Mathematics, 19(3):179-192, 2011, doi: 10.2478/v10037-011-0027-0.[Crossref] Zbl1276.03032
  14. Marco B. Caminati. Sequent calculus, derivability, provability. Gödel's completeness theorem. Formalized Mathematics, 19(3):205-222, 2011, doi: 10.2478/v10037-011-0029-y.[Crossref] Zbl1276.03045
  15. H. D. Ebbinghaus, J. Flum, and W. Thomas. Mathematical logic. Springer, 1994. 
  16. Rafał Kwiatek and Grzegorz Zwara. The divisibility of integers and integer relative primes. Formalized Mathematics, 1(5):829-832, 1990. 
  17. Konrad Raczkowski and Paweł Sadowski. Equivalence relations and classes of abstraction. Formalized Mathematics, 1(3):441-444, 1990. 
  18. Krzysztof Retel. Properties of first and second order cutting of binary relations. Formalized Mathematics, 13(3):361-365, 2005. 
  19. Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1(2):329-334, 1990. 
  20. Andrzej Trybulec. Domains and their Cartesian products. Formalized Mathematics, 1(1):115-122, 1990. 
  21. Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  22. Edmund Woronowicz. Many-argument relations. Formalized Mathematics, 1(4):733-737, 1990. 
  23. Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990. 
  24. Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990. 
  25. Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Formalized Mathematics, 1(1):85-89, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.