146
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: not found
      • Book Chapter: not found
      Tools and Algorithms for the Construction and Analysis of Systems 

      A Practical and Complete Approach to Predicate Refinement

      other
      ,
      Springer Berlin Heidelberg

      Read this book at

      Publisher
      Buy book Bookmark
          There is no author summary for this book yet. Authors can add summaries to their books on ScienceOpen to make them more accessible to a non-specialist audience.

          Related collections

          Most cited references11

          • Record: found
          • Abstract: not found
          • Article: not found

          Simplification by Cooperating Decision Procedures

            Bookmark
            • Record: found
            • Abstract: not found
            • Book Chapter: not found

            Interpolation and SAT-Based Model Checking

              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory

              One task of metamathematics is to relate suggestive but nonelementary modeltheoretic concepts to more elementary proof-theoretic concepts, thereby opening up modeltheoretic problems to proof-theoretic methods of attack. Herbrand's Theorem (see [8] or also [9], vol. 2) or Gentzen's Extended Hauptsatz (see [5] or also [10]) was first used along these lines by Beth [1]. Using a modified version he showed that for all first-order systems a certain modeltheoretic notion of definability coincides with a certain proof theoretic notion. In the present paper the Herbrand-Gentzen Theorem will be applied to generalize Beth's results from primitive predicate symbols to arbitrary formulas and terms. This may be interpreted as showing that (apart from some relatively minor exceptions which will be made apparent below) the expressive power of each first-order system is rounded out, or the system is functionally complete , in the following sense: Any functional relationship which obtains between concepts that are expressible in the system is itself expressible and provable in the system. A second application is concerned with the hierarchy of second-order formulas. A certain relationship is shown to hold between first-order formulas and those second-order formulas which are of the form (∃T 1 )…(∃T k )A or (T 1 )…(T k )A with A being a first-order formula. Modeltheoretically this can be regarded as a relationship between the class AC and the class PC ⊿ of sets of models, investigated by Tarski in [12] and [13].
                Bookmark

                Author and book information

                Book Chapter
                2006
                : 459-473
                10.1007/11691372_33
                215a2bee-0d43-4e0c-991f-f51e476789a5

                http://www.springer.com/tdm

                History

                Comments

                Comment on this book

                Book chapters

                Similar content2,789

                Cited by39