Ο τελεστής ελαχιστοποίησης δεύτερης τάξης είναι μέγιστος

Είναι κοινώς γνωστό στους κόλπους της ανώτερης υπολογισιμότητας, και συγκεκριμένα στη θεωρία πεδίων, οτι ο τελεστής ελαχιστοποίησης (δεύτερης τάξης), στα αγγλικά «minimization operator», είναι παράδειγμα συναρτησιακού που ενώ είναι μέγιστο δέν είναι ολικό, ωστόσο δύσκολα να βρεί κανείς απόδειξη γι' αυτό το πράγμα. Γιά να δούμε εδώ μια απόδειξη, που πατάει πάνω στα χνάρια του παραδείγματος 8.3.2 του [Stoltenberg-Hansen & al 1994].

«Αποτελεσματικότητα και ολικότητα»

Στο πολύ ωραίο (και αρκετά λάιτ) αρθράκι [Berger 1999], πρόδρομο του --πάνω-κάτω ίδιου-- [Berger 2002], ο Ούλριχ Μπέργκερ γράφει μιά πολύ συνοπτική, αλλα αρκετά ζουμερή ρετροσπεκτίβα της ανώτερης υπολογισιμότητας μέσω πεδίων Σκότ, και συγκεκριμένα όσον αφορά τα δύο κομβικά θέματα της αποτελεσματικότητας (effectivity/effectiveness) και της ολικότητας (totality).

Aτομικότητα κατα Μπουκιαρέλι ϗ σία

Η έννοια της ατομικότητας της πληροφορίας είν' απ' τα πράγματα που μ' έχουν στοιχειώσει στο παρελθόν, κι' ακόμα με στοιχειώνουν. Λές οτι ένα σύνολο \(U\) απο ατομικές πληροφορίες είναι το ίδιο ατομικό, στην περίπτωση που για κάθε ατομική πληροφορία \(b\), όταν \(U \vdash b\), τότε υπάρχει μία \(a \in U\) με \(\{a\} \vdash b\): οποιαδήποτε ατομική πληροφορία ενέχεται στην \(U\), θα ενέχεται και σε κάποιο ατομικό της κομμάτι.

Αυτό ενγένει είναι χοντρή απαίτηση, καθώς η ατομικότητα κατα κάποιο τρόπο πάει κόντρα σε μία εγγενή στο χώρο έννοια ανεξαρτησίας. Σκέψου το \(U\) ως (περατό) σύνολο διανυσμάτων σε κάποιον διανυσματικό χώρο και το \(b\) ως διάνυσμα, και ερμήνευσε τον ισχυρισμό «το \(U\) ενέχει την πληροφορία \(b\)» ώς «το διάνυσμα \(b\) γράφεται ως γραμμικός συνδυασμός κάποιων διανυσμάτων του \(U\)». Να πείς οτι το \(U\) είναι ατομικό, είναι να πείς οτι κάθε φορά που ένα διάνυσμα \(b\) γράφεται ως γραμμικός συνδυασμός διανυσμάτων \(\{a_1, \ldots, a_m\} \subseteq U\), στην πραγματικότητα μπορεί να γραφτεί ως γραμμικός συνδυασμός, δηλαδή πολλαπλάσιο, ενός μόνο διανύσματος \(a \in U\). Αυτό ισχύει πιχί στην πραγματική ευθεία, οπου μάλιστα για κάθε μή μηδενικό διάνυσμα \(a \in U\) (με \(U\) μή κενο) έχουμε \(b = \kappa a\), για \(\kappa = b/a\), αλλα δέν ισχύει σε ανώτερες διαστάσεις: στο επίπεδο πιχί έχουμε \(\{(1, 0), (0,1)\} \vdash (1,1)\), αλλα κανένα απο τα διανύσματα αριστερά δέν αρκεί για να παράξει απο μόνο του το διάνυσμα στα δεξιά.