Είναι κοινώς γνωστό στους κόλπους της ανώτερης υπολογισιμότητας, και συγκεκριμένα στη θεωρία πεδίων, οτι ο τελεστής ελαχιστοποίησης (δεύτερης τάξης), στα αγγλικά «minimization operator», είναι παράδειγμα συναρτησιακού που ενώ είναι μέγιστο δέν είναι ολικό, ωστόσο δύσκολα να βρεί κανείς απόδειξη γι' αυτό το πράγμα. Γιά να δούμε εδώ μια απόδειξη, που πατάει πάνω στα χνάρια του παραδείγματος 8.3.2 του [Stoltenberg-Hansen & al 1994].
Ο τελεστής ελαχιστοποίησης δέχεται ως όρισμα μία αριθμητική συνάρτηση πρώτης τάξης και επιστρέφει ως τιμή τον πρώτο φυσικό στον οποίο η συνάρτηση δίνει μή μηδενικό αποτέλεσμα. Συγκεκριμένα, ορίζουμε το συναρτησιακό \(M : (\mathbb{N} \to \mathbb{N}) \to \mathbb{N}\) ώς εξής:\[ M(f) := \mu_n (f(n) > 0 \land \forall_{m<n} f(m) = 0) .\]Εδώ γράφω \(\mathbb{N}\) για τους ισόπεδους φυσικούς αριθμούς, οι οποίοι περιλαμβάνουνε λοιπόν και το ελάχιστο \(\bot\). Για παράδειγμα, για κάθε σταθερή συνάρτηση εκτός της μηδενικής, δηλαδή για κάθε \(n>0\), έχουμε \(M(\lambda_x n) = 0\) και για την ταυτοτική συνάρτηση έχουμε \(M(\lambda_x x) = 1\). Αντίθετα, στην περίπτωση που για κάποιο \(n = 0, 1, 2, \ldots\) ισχύει \(f(n) = \bot\) με \(f(m) = 0\) για κάθε \(m<n\), τότε \(M(f) = \bot\), και, ακόμη χειρότερα, το ίδιο παίρνουμε και για τη σταθερή μηδενική συνάρτηση \(\mathsf{zr} : \mathbb{N} \to \mathbb{N}\) με \(\mathsf{zr} = \lambda_x 0\)· ήδη βλέπουμε δηλαδή οτι πρόκειται για μή ολικό συναρτησιακό, καθώς βέβαια η \(\mathsf{zr}\) είναι ολική.
Καταρχήν να βεβαιωθούμε οτι ο τελεστής ελαχιστοποίησης είναι συνεχές συναρτησιακό, δηλαδή μονότονο και με περατό φορέα. Για τη μονοτονία θεωρούμε δύο συναρτήσεις \(f, f' : \mathbb{N} \to \mathbb{N}\) με \(f \sqsubseteq f'\) και δείχνουμε οτι \(M(f) \sqsubseteq M(f')\)· άν είναι \(M(f) = \bot\) τότε τελειώσαμε, αλλ' αν έχουμε \(M(f) = n\) για κάποιο \(n \neq \bot\), τότε θά 'χαμε \(f(0) = \cdots = f(n-1) = 0\) και \(f(n) > 0\), και καθώς \(f \sqsubseteq f'\), το ίδιο θα πρέπει να ισχύει και για την \(f'\), δηλαδή \(f'(0) = \cdots = f'(n-1) = 0\) και \(f'(n) > 0\); συνεπάγεται οτι \(M(f') = n\). Για τον περατό φορέα θεωρούμε μία \( f : \mathbb{N} \to \mathbb{N}\) και έναν ισόπεδο φυσικό \(n : \mathbb{N}\) τέτοια ώστε \(M(f) = n\), και ψάχνουμε μία συμπαγή συνάρτηση \(f_0 \sqsubseteq f\) για την οποία ήδη \(M(f_0) = n\)· στην περίπτωση που \(n = \bot\), αρκεί να θέσουμε \(f_0 := \emptyset\); στην περίπτωση που \(n \neq \bot\) (είναι δηλαδή ολικός φυσικός αριθμός), απ' τον ορισμό της \(M\) έχουμε \(f(0) = \cdots = f(n-1) = 0\) και \(f(n) > 0\), άρα μπορούμ' απλά να θέσουμε \(f_0 := \{0 \mapsto 0, 1 \mapsto 0, \ldots, n-1 \mapsto 0, n \mapsto f(n)\}\).
Για να δείξουμε τώρα οτι πρόκειται για μέγιστο συναρτησιακό, θεωρούμε κάποιο \(F : (\mathbb{N} \to \mathbb{N}) \to \mathbb{N}\) με \(M \sqsubseteq F\). Άν η διάταξη ήταν γνήσια, δηλαδή \(M \sqsubset F\), τότε θα μπορούσαμε να βρούμε όρισμα \(f : \mathbb{N} \to \mathbb{N}\) για το οποίο \(\bot = M(f) \sqsubseteq F(f) \neq \bot\). Μάλιστα, λόγω περατού φορέα, δέ χάνουμε σε γενικότητα να υποθέσουμε οτι αυτό το \(f\) θα ήταν συμπαγές.
Αυτό το \(f\) θα μπορούσε να παίρνει σταθερή ολική τιμή ή όχι. Άν ναί, τότε, όπως είδαμε πρίν, η τιμή αυτή θα μπορούσε να είναι μόνο το μηδέν, δηλαδή θά 'πρεπε \(f \sqsubseteq \mathsf{zr}\). Τότε θα μπορούσαμε να σκαρφιστούμε επεκτάσεις \(f_1, f_2 \sqsupseteq f\), για τις οποίες θα 'χαμε\[\bot \neq M(f_1) \neq M(f_2) \neq \bot .\]Για παράδειγμα, αν είχαμε \(f = \{0 \mapsto 0, 1 \mapsto 0\}\), τότε θα μπορούσαμε να διαλέγαμε \(f_1 = f \cup \{2 \mapsto 1\}\) και \(f_2 = f \cup \{2 \mapsto 0, 3 \mapsto 1\}\). Για τέτοιες επεκτάσεις όμως θά 'πρεπε να ισχύει\[ M(f_1) = F(f_1) = F(f) = F(f_2) = M(f_2) ,\]αφού έχουμε υποθέσει οτι \(M \sqsubseteq F\), \(F(f) \neq \bot\), \(f \sqsubseteq f_1, f_2\) και οτι βέβαια η \(F\) είναι μονότονη· άτοπο. Άρα η \(f\) δέν μπορεί να παίρνει σταθερή ολική τιμή.
Θα περιμέναμε τότε οτι η \(f\) διαφέρει απο τη \(\mathsf{zr}\) σε κάποια ορίσματα. Ας ήταν \(n\) ο πρώτος-πρώτος (ολικός) αριθμός για τον οποίο \(f(n) > 0\). Εφόσον \(M(f) = \bot\), θα έπρεπε να υπάρχει ένας ελάχιστος φυσικός \(m < n\) με \(f(m) = \bot\), γιατι αλλιώς θά 'χαμε \(M(f) = n\). Πάλι θα μπορούσαμε να σκαρφιστούμε επεκτάσεις \(f_3, f_4 \sqsupseteq f\), με \(\bot \neq f_3(m) > 0\) για τη μιά και \(\forall_{k < n} f_4(k) = 0\) για την άλλη, οπότε θα παίρναμε\[m = M(f_3) = F(f_3) = F(f) = F(f_4) = M(f_4) = n ,\]όπως πρίν· άτοπο. Άρα η \(f\) δέν επιτρέπεται ούτε να διαφέρει απ' τη σταθερή μηδενική σε κάποια ορίσματα.
Άτοπο λοιπόν, απ' το οποίο συμπεραίνουμε οτι ο τελεστής \(M\) δέ μπορεί παρα να είναι μέγιστος. Τέλος.
Ο τελεστής ελαχιστοποίησης δέχεται ως όρισμα μία αριθμητική συνάρτηση πρώτης τάξης και επιστρέφει ως τιμή τον πρώτο φυσικό στον οποίο η συνάρτηση δίνει μή μηδενικό αποτέλεσμα. Συγκεκριμένα, ορίζουμε το συναρτησιακό \(M : (\mathbb{N} \to \mathbb{N}) \to \mathbb{N}\) ώς εξής:\[ M(f) := \mu_n (f(n) > 0 \land \forall_{m<n} f(m) = 0) .\]Εδώ γράφω \(\mathbb{N}\) για τους ισόπεδους φυσικούς αριθμούς, οι οποίοι περιλαμβάνουνε λοιπόν και το ελάχιστο \(\bot\). Για παράδειγμα, για κάθε σταθερή συνάρτηση εκτός της μηδενικής, δηλαδή για κάθε \(n>0\), έχουμε \(M(\lambda_x n) = 0\) και για την ταυτοτική συνάρτηση έχουμε \(M(\lambda_x x) = 1\). Αντίθετα, στην περίπτωση που για κάποιο \(n = 0, 1, 2, \ldots\) ισχύει \(f(n) = \bot\) με \(f(m) = 0\) για κάθε \(m<n\), τότε \(M(f) = \bot\), και, ακόμη χειρότερα, το ίδιο παίρνουμε και για τη σταθερή μηδενική συνάρτηση \(\mathsf{zr} : \mathbb{N} \to \mathbb{N}\) με \(\mathsf{zr} = \lambda_x 0\)· ήδη βλέπουμε δηλαδή οτι πρόκειται για μή ολικό συναρτησιακό, καθώς βέβαια η \(\mathsf{zr}\) είναι ολική.
Καταρχήν να βεβαιωθούμε οτι ο τελεστής ελαχιστοποίησης είναι συνεχές συναρτησιακό, δηλαδή μονότονο και με περατό φορέα. Για τη μονοτονία θεωρούμε δύο συναρτήσεις \(f, f' : \mathbb{N} \to \mathbb{N}\) με \(f \sqsubseteq f'\) και δείχνουμε οτι \(M(f) \sqsubseteq M(f')\)· άν είναι \(M(f) = \bot\) τότε τελειώσαμε, αλλ' αν έχουμε \(M(f) = n\) για κάποιο \(n \neq \bot\), τότε θά 'χαμε \(f(0) = \cdots = f(n-1) = 0\) και \(f(n) > 0\), και καθώς \(f \sqsubseteq f'\), το ίδιο θα πρέπει να ισχύει και για την \(f'\), δηλαδή \(f'(0) = \cdots = f'(n-1) = 0\) και \(f'(n) > 0\); συνεπάγεται οτι \(M(f') = n\). Για τον περατό φορέα θεωρούμε μία \( f : \mathbb{N} \to \mathbb{N}\) και έναν ισόπεδο φυσικό \(n : \mathbb{N}\) τέτοια ώστε \(M(f) = n\), και ψάχνουμε μία συμπαγή συνάρτηση \(f_0 \sqsubseteq f\) για την οποία ήδη \(M(f_0) = n\)· στην περίπτωση που \(n = \bot\), αρκεί να θέσουμε \(f_0 := \emptyset\); στην περίπτωση που \(n \neq \bot\) (είναι δηλαδή ολικός φυσικός αριθμός), απ' τον ορισμό της \(M\) έχουμε \(f(0) = \cdots = f(n-1) = 0\) και \(f(n) > 0\), άρα μπορούμ' απλά να θέσουμε \(f_0 := \{0 \mapsto 0, 1 \mapsto 0, \ldots, n-1 \mapsto 0, n \mapsto f(n)\}\).
Για να δείξουμε τώρα οτι πρόκειται για μέγιστο συναρτησιακό, θεωρούμε κάποιο \(F : (\mathbb{N} \to \mathbb{N}) \to \mathbb{N}\) με \(M \sqsubseteq F\). Άν η διάταξη ήταν γνήσια, δηλαδή \(M \sqsubset F\), τότε θα μπορούσαμε να βρούμε όρισμα \(f : \mathbb{N} \to \mathbb{N}\) για το οποίο \(\bot = M(f) \sqsubseteq F(f) \neq \bot\). Μάλιστα, λόγω περατού φορέα, δέ χάνουμε σε γενικότητα να υποθέσουμε οτι αυτό το \(f\) θα ήταν συμπαγές.
Αυτό το \(f\) θα μπορούσε να παίρνει σταθερή ολική τιμή ή όχι. Άν ναί, τότε, όπως είδαμε πρίν, η τιμή αυτή θα μπορούσε να είναι μόνο το μηδέν, δηλαδή θά 'πρεπε \(f \sqsubseteq \mathsf{zr}\). Τότε θα μπορούσαμε να σκαρφιστούμε επεκτάσεις \(f_1, f_2 \sqsupseteq f\), για τις οποίες θα 'χαμε\[\bot \neq M(f_1) \neq M(f_2) \neq \bot .\]Για παράδειγμα, αν είχαμε \(f = \{0 \mapsto 0, 1 \mapsto 0\}\), τότε θα μπορούσαμε να διαλέγαμε \(f_1 = f \cup \{2 \mapsto 1\}\) και \(f_2 = f \cup \{2 \mapsto 0, 3 \mapsto 1\}\). Για τέτοιες επεκτάσεις όμως θά 'πρεπε να ισχύει\[ M(f_1) = F(f_1) = F(f) = F(f_2) = M(f_2) ,\]αφού έχουμε υποθέσει οτι \(M \sqsubseteq F\), \(F(f) \neq \bot\), \(f \sqsubseteq f_1, f_2\) και οτι βέβαια η \(F\) είναι μονότονη· άτοπο. Άρα η \(f\) δέν μπορεί να παίρνει σταθερή ολική τιμή.
Θα περιμέναμε τότε οτι η \(f\) διαφέρει απο τη \(\mathsf{zr}\) σε κάποια ορίσματα. Ας ήταν \(n\) ο πρώτος-πρώτος (ολικός) αριθμός για τον οποίο \(f(n) > 0\). Εφόσον \(M(f) = \bot\), θα έπρεπε να υπάρχει ένας ελάχιστος φυσικός \(m < n\) με \(f(m) = \bot\), γιατι αλλιώς θά 'χαμε \(M(f) = n\). Πάλι θα μπορούσαμε να σκαρφιστούμε επεκτάσεις \(f_3, f_4 \sqsupseteq f\), με \(\bot \neq f_3(m) > 0\) για τη μιά και \(\forall_{k < n} f_4(k) = 0\) για την άλλη, οπότε θα παίρναμε\[m = M(f_3) = F(f_3) = F(f) = F(f_4) = M(f_4) = n ,\]όπως πρίν· άτοπο. Άρα η \(f\) δέν επιτρέπεται ούτε να διαφέρει απ' τη σταθερή μηδενική σε κάποια ορίσματα.
Άτοπο λοιπόν, απ' το οποίο συμπεραίνουμε οτι ο τελεστής \(M\) δέ μπορεί παρα να είναι μέγιστος. Τέλος.
