Θεωρία μοντέλων, με έμφαση στην αριθμητική

Abstract

There are a lot of proper subsystems of Peano Arithmetic. For some of these subsystems there are known theorems that provide us with information about their models. But there are quite enough subsystems, about which there are a lot of open questions. Major problems to be considered in this area are determining the position of a given subsystem in the hierarchy and finding the minimal theory for proving basic results in arithmetic. The clarification of the hierarchy of subsystems of Peano Arithmetic started in ’80. Some of the theorems that were proved are related to problems in other areas, like Computational Complexity and Number Theory. In chapters 2 and 3 of this thesis we are investigating the strength of specific subsystems. P. Clote and J. Krajicek published in 1993 a list of open problems, in which they included a lot of problems in bounded arithmetic, Proof Theory and Computational Complexity. The problems we study are from this list.The last chapter of the thesis concerns Peano Arithmetic within the framework of one non classical logic. Specifically, we study the not so old notion of a LP - model, concentrate on its properties and answer a few questions posed by G. Priest (1997, 2000). Our goal here is to better understand infinite LP-models, so that we can reach a characterization of such models. At the end of this chapter the close relation between classical and LP arithmetic is clarified.

Οι δύο κύριοι άξονες γύρω από τους οποίους κινούνται τα αποτελέσματα της διατριβής είναι οι εξής: το πρόβλημα που τέθηκε από τον J. Paris σχετικά με την ιεραρχία συγκεκριμένων υποσυστημάτων της Peano αριθμητικής και η εικασία του G. Priest, η οποία αφορά τις άπειρες δομές της λογικής του παραδόξου. Τα πρώτα κεφάλαια της διατριβής αναφέρονται σε συγκεκριμένα συστήματα της Peano αριθμητικής, καθώς και στην προσπάθεια να ενταχθούν σε μια ιεραρχία. Αρχικά ορίζονται αναλυτικά οι έννοιες της επαγωγής, της συλλογής, της αρχής του ελαχίστου για διάφορες κλάσεις τύπων της πρωτοβάθμιας λογικής και οι δύο μορφές του περιστερώνα: η ισχυρή και η ασθενής. Στη συνέχεια γίνεται μια καταγραφή των γνωστών αποτελεσμάτων καθώς και των ανοικτών προβλημάτων της περιοχής. Στα κεφάλαια 2 και 3 δίνουμε μια σειρά από θεωρήματα, που επιτρέπουν την καλύτερη κατανόηση της ιεραρχίας των ασθενών υποσυστημάτων της Peano αριθμητικής, καθώς και το ρόλο των παραμέτρων. Το τελευταίο κεφάλαιο της διατριβής είναι αφιερωμένο σε προβλήματα που τέθηκαν από τον G. Priest το 1997 και 2000 για τις ιδιότητες των πεπερασμένων και άπειρων δομών της λογικής του παραδόξου. Εμείς δίνουμε απαντήσεις σε ορισμένα από τα προβλήματα αυτά και παρουσιάζουμε μια μέθοδο κατασκευής άπειρων μοντέλων, η οποία μας επιτρέπει να πάρουμε θέση στην εικασία που διατύπωσε ο G. Priest το 2000.