Ηλεκτρονική Διάθεση Μαθήματος
Περιεχόμενο Μαθήματος
Το μάθημα θα καλύψει τους κλάδους της Θεωρία Μοντέλων, Θεωρίας Συνόλων, και Θεωρίας Υπολογισμού. Κάθε φορά που το μάθημα προσφέρεται θα καλύπτεται ένας από τους τρεις κλάδους και θα υπάρχει εναλλαγή Θεωρία Μοντέλων→ Θεωρία Συνόλων→ Θεωρία Υπολογισμού→ Θεωρία Μοντέλων→Θεωρία Συνόλων→ ...
Για το 2021 ο κλάδος που θα καλυφθεί είναι η Θεωρία Μοντέλων.
Παρακάτω ακολουθούν οι περιγραφές και των τριών κλάδων.
Θεωρία Μοντέλων
Το μάθημα είναι μία μεταπτυχιακού επιπέδου εισαγωγή στη Θεωρία Μοντέλων με εφαρμογές από την Άλγεβρα. Τα θέματα που θα μελετήσουμε περιλαμβάνουν:
• Ορίσιμα σύνολα
• Πλήρης θεωρίες, Αλγεβρικά Κλειστά Σώματα
• Ανοδικό και Καθοδικό Θεώρημα των Lowenheim-Skolem
• Πυκνές γραμμικές διατάξεις και μπρος-πίσω αποδείξεις
• Απαλοιφή Ποσοδεικτών
• Τύποι, Θεώρημα Παράληψης Τύπων,
• Πρωτογενή και Ατομικά Μοντέλα
• Κορεσμένα και Ομογενή Μοντέλα
• Θεώρημα Δύο Πληθικών του Vaught
• ω-ευσταθείς Θεωρίες και το Θεώρημα του Morley
Βιβλιογραφία: D. Marker, Model Theory: An Introduction
Στο μάθημα θα καλύψουμε επιλεγμένα θέματα από τα πρώτα 6 κεφάλαια
Προαπαιτούμενα: Μαθηματική Λογική, Θεωρία Συνόλων (προπτυχιακά μαθήματα)
Πιο συγκεκριμένα εξοικίωση με τις παρακάτω έννοιες:
• Τυπικές γλώσσες
• Τυπικές αποδείξεις
• L-δομές
• Θεωρήματα Ορθότητας και Πληρότητας
• Θεώρημα Συμπάγειας
• Διατακτικοί και πληθικοί αριθμοί
• Αξίωμα Επιλογής και Λήμμα του Zorn.
Θεωρία Συνόλων
Το μάθημα είναι μία εισαγωγή στη μέθοδο του forcing και τις αποδείξεις ανερξαρτησίας. Στη διάρκεια που μαθήματος θα αποδείξουμε την ανερξαρτησία της Υπόθεσης του Συνεχούς (Continuum Hypothesis) και όχι μόνο. Τα θέματα που θα μελετήσουμε περιλαμβάνουν:
• Τα αξιώματα ZFC
• Άλγεβρες του Boole
• Φίλτρα, υπερφίλτρα και γένια φίλτρα
• Μοντέλα που παίρνουν τιμές πάνω σε Άλγεβρες του Boole
• Γένιες Επεκτάσεις,
• Το Θεώρημα του Forcing και το Θεώρημα Γένιων Επεκτάσεων
• Αριθμήσιμες Αλυσίδες και διατήρηση πληθικών αριθμών
• Ανεξαρτησία της Υπόθεσης του Συνεχούς και του Αξιώματος της Επιλογής
Βιβλιογραφία: T. Jech, Set Theory
Στο μάθημα θα καλύψουμε επιλεγμένα θέματα κυρίως από τα κεφάλαια 14, 15.
Προαπαιτούμενα: Θεωρία Συνόλων, Μαθηματική Λογική (προπτυχιακά μαθήματα)
Θεωρία Υπολογισμού
Η Θεωρία Υπολογισμού είναι κλάδος των Μαθηματικών και συγκεκριμένα της Μαθηματικής Λογικής. Κεντρικό πρόβλημα είναι η Μαθηματική θεμελίωση της έννοιας του αλγορίθμου και της (μηχανικά) υπολογίσιμης συνάρτησης. Οι έννοιες του αλγορίθμου και της υπολογίσιμης συνάρτησης έχουν ενδιαφέρον και για τα ίδια τα Μαθηματικά, π.χ. το 10ο Θεώρημα του Hilber, αλλά και πάνω σε αυτές τις έννοιες θεμελιώνεται η Επιστήμη των Υπολογιστών, π.χ. το Halting problem. Οπότε το ενδιαφέρον για την Θεωρία Υπολογισμού δεν περιορίζεται στα Μαθηματικά αλλά επεκτείνεται και στη Θεωρητική Πληροφορική.
Τα θέματα που θα μελετήσουμε περιλαμβάνουν:
• Πρωτογενείς αναδρομικές συναρτήσεις και γενικές αναδρομικές συναρτήσεις.
• Αναδρομή και υπολογισμός, αναδρομικά σύνολα
• Το αίτημα των Church- Turing
• Μηχανές Turing. Turing υπολογίσιμες συναρτήσεις.
• Ημιαναδρομικές συναρτήσεις και αναδρομικά απαριθμήσιμα σύνολα
• Απαρίθμηση και κανονική μορφή Kleene
• Θεωρήματα Αναδρομής
• Αριθμητική Ιεραρχία
• Αριθμητικοποίηση και μη ορισιμότητα της αλήθειας
Βιβλιογραφία:
1. Γιάννης Μοσχοβάκης, Αναδρομή και Υπολογισιμότητα, Διαθέσιμο στη ιστοσελίδα του συγγραφέα: https://www.math.ucla.edu/~ynm/books.htm (πρόσβαση 9/2/2021)
2. Michael Sipser: Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης
3. Harry Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική
Προαπαιτούμενα: Μαθηματική Λογική (προπτυχιακό μάθημα)
Βιβλιογραφία μαθήματος (Εύδοξος)
Βιβλιογραφία Θεωρίας Μοντέλων D. Marker, Model Theory: An Introduction
Βιβλιογραφία Θεωρίας Συνόλων: T. Jech, Set Theory
Βιβλιογραφία Θεωρίας Υπολογισμού:
1. Γιάννης Μοσχοβάκης, Αναδρομή και Υπολογισιμότητα, Διαθέσιμο στη ιστοσελίδα του συγγραφέα: https://www.math.ucla.edu/~ynm/books.htm (πρόσβαση 9/2/2021)
2. Michael Sipser: Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης
3. Harry Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική