Προτασιακή Λογική

MoV · #1

Εάν $\phi_1,\phi_2,...,\phi_n,...$ είναι μια άπειρη ακολουθία προτασιακών τύπων τέτοιών ώστε:

να περιέχουν προατασιακές μεταβλητές μόνο από το σύνολο $\{A_1,A_2,...,A_k\}$
για κάθε να έχουμε $\phi_n \models \phi_{n+1}$

να δείξετε ότι υπάρχει

τέτοιο ώστε για κάθε $n \geq N$ να έχουμε $\phi_{n+1} \models \phi_n$ .

#2

Κάθε συνάρτηση $v:\{A_1,\ldots,A_k\} \to \{0,1\}$ επεκτείνεται με μοναδικό τρόπο σε μια συνάρτηση $\overline{v}:\{\phi_1,\phi_2,\ldots\} \to \{0,1\}$ ώστε $\phi_i \models \phi_j$ αν και μόνο αν $\overline{v}(\phi_i) \leqslant \overline{v}(\phi_j)$ .

Επειδή όμως υπάρχει πεπερασμένος αριθμός τέτοιων συναρτήσεων (ακριβώς 2^k

) θα υπάρχει ένα απειροσύνολο $M \subseteq \mathbb{N}$ ώστε $\overline{v}(\phi_i) = \overline{v}(\phi_j)$ για κάθε $i,j \in M$ .

Έστω τώρα

το έλαχιστο στοιχείο του

και έστω $n \geqslant N$ . Παίρνω m > n

με $m \in Μ$ . Τότε $\displaystyle{\phi_{n+1} \models \phi_{n+2} \models \cdots \models \phi_m \models \phi_N \models \phi_{N+1} \models \cdots \models \phi_n}$ όπως θέλαμε να δείξουμε.

MoV · #3

Ευχαριστώ Δημήτρη για την λύση σου .
Γράφω και μία λύση που καταφεύγει στον απειροστικό λογισμό .

Έστω u_i(x_1,...,x_k)

η συνάρτηση Boole που αντιστοιχεί στον προτασιακό τύπο $\phi_i$ .
Ορίζουμε την ακολουθία $a_n:\mathbb{N} \rightarrow \mathbb{N}$ έτσι ώστε a_n=

(το πλήθος των k-άδων (x_1,...,x_k)

τέτοιες ώστε u_n(x_1,...,x_k) = T

).
Από το 2ο δεδομένο της άσκησης έχουμε ότι η a_n

είναι αύξουσα .
Ακόμα είναι άνω φραγμένη αφού $a_n \leq 2^k, \forall n \in \mathbb{N}$ .
Άρα η a_n

συγκλίνει . Έστω ότι συγκλίνει στο $b \in \mathbb{N}$ . Τότε :
$\forall \epsilon > 0 \exists N>0 : n \geq N \Rightarrow |a_n-b|< \epsilon$ .
Επιλέγοντας $\epsilon = 1$ έχουμε : $\exists N>0 : n \geq N \Rightarrow |a_n-b|< 1 \Rightarrow a_n=b$ .
Συνεπώς από το 2ο δεδομένο της άσκησης , για κάθε $n \geq N$ έχουμε $u_{n+1}=u_n \Rightarrow \phi_{n+1} \models \phi_{n}$ .

#4

MoV έγραψε:Ευχαριστώ Δημήτρη για την λύση σου .
Γράφω και μία λύση που καταφεύγει στον απειροστικό λογισμό .

Έστω η συνάρτηση Boole που αντιστοιχεί στον προτασιακό τύπο $\phi_i$ .
Ορίζουμε την ακολουθία $a_n:\mathbb{N} \rightarrow \mathbb{N}$ έτσι ώστε (το πλήθος των k-άδων τέτοιες ώστε ).
Από το 2ο δεδομένο της άσκησης έχουμε ότι η είναι αύξουσα .
Ακόμα είναι άνω φραγμένη αφού $a_n \leq 2^k, \forall n \in \mathbb{N}$ .
Άρα η συγκλίνει . Έστω ότι συγκλίνει στο $b \in \mathbb{N}$ . Τότε :
$\forall \epsilon > 0 \exists N>0 : n \geq N \Rightarrow |a_n-b|< \epsilon$ .
Επιλέγοντας $\epsilon = 1$ έχουμε : $\exists N>0 : n \geq N \Rightarrow |a_n-b|< 1 \Rightarrow a_n=b$ .
Συνεπώς από το 2ο δεδομένο της άσκησης , για κάθε $n \geq N$ έχουμε $u_{n+1}=u_n \Rightarrow \phi_{n+1} \models \phi_{n}$ .

Σωστά, και όμορφα. Μπορούμε να απλοποιήσουμε τα βήματα: Αφού φτάσουμε στο συμπέρασμα ότι η ακολουθία των φυσικών (a_n)

είναι φραγμένη, βγάζουμε αμέσως το συμπέρασμα ότι είναι τελικά σταθερή. Δεν χρειάζεται δηλαδή να πάμε μέσω σύγκλισης στο R. Και λοιπά.

Θυμήθηκα τώρα τα φοιτητικά μου χρόνια που με έναν τότε συμφοιτητή μου και καθηγητή σήμερα στο Μαθηματικό Αθηνών, τον Αριστείδη Κατάβολο, κάναμε επίτηδες και χάρην αστείου "τα εύκολα δύσκολα". Παίρναμε δηλαδή σχετικά εύκολα προβλήματα και τα λύναμε με επιτηδευμένο τρόπο, χρησιμοποιώντας βαρύ πυροβολικό.

Παράδειγμα: Αν $f: \mathbb R \rightarrow \mathbb R$ είναι συνεχής και ικανοποεί
f(x+y)=f(x)+f(y)

, τότε υπάρχει

με

.

Απόδειξη: Το $\mathbb R$ εφοδιασμένο με το εσωτερικό γινόμενο <x,y>=xy

είναι χώρος Hilbert. H παραπάνω

ικανοποιεί στις συνθήκες του θεωρήματος αναπαραστάσεως Riesz στο πυκνό υποσύνολο $\mathbb Q$ του $\mathbb R$ . Άρα υπάρχει

με

. Από αυτό έπεται το ζητούμενο.

Για το ίδιο πρόβλημα είχαμε και μία απόδειξη με το "Pontriagin duality theorem", αλλά την ξέχασα...

Φιλικά,

Μιχάλης

#5

Mihalis_Lambrou έγραψε: Για το ίδιο πρόβλημα είχαμε και μία απόδειξη με το "Pontriagin duality theorem", αλλά την ξέχασα...

Για να δούμε. Το $\mathbb{R}$ είναι τοπικά συμπαγής αβελιανή ομάδα άρα $\mathbb{R} \cong \mathbb{R}^{\ast \ast}$ με τον κανονικό ισομορφισμό $x \mapsto \tilde{x}$ όπου $\tilde{x}(\rho) = \rho(x)$ για κάθε συνεχή $\rho: \mathbb{R} \to \mathbb{T}$ .

Έστω τώρα $G = \{x \in \mathbb{R} : f(x) = f(1)x\}$ . Τότε το

περιέχει το $\mathbb{Q}$ και άρα είναι πυκνό στο $\mathbb{R}$ . Έχουμε $G^{\ast} = \{\rho: \mathbb{R} \to \mathbb{T} | \rho(x) = 0 \; \forall \; x \in G\} = \{0\}$ αφού το

είναι πυκνό. Επομένως $G^{\ast \ast} = \{\tilde{x} \in \mathbb{R}^{\ast \ast}: \tilde{x}(\rho) = 0 \; \forall \; \rho \in G^{\ast}\} = \mathbb{R}^{\ast \ast}$ . Αλλά (με τον κανονικό ισομορφισμό) η $G^{\ast \ast}$ είναι ο μικρότερος κλειστός υποχώρος που περιέχει τον

. Προφανώς όμως ο

είναι κλειστός και άρα $G = \mathbb{R}$ όπως θέλαμε να δείξουμε.

MoV · #6

Mihalis_Lambrou έγραψε: Σωστά, και όμορφα. Μπορούμε να απλοποιήσουμε τα βήματα: Αφού φτάσουμε στο συμπέρασμα ότι η ακολουθία των φυσικών είναι φραγμένη, βγάζουμε αμέσως το συμπέρασμα ότι είναι τελικά σταθερή. Δεν χρειάζεται δηλαδή να πάμε μέσω σύγκλισης στο R. Και λοιπά.

Χαχα όντως .
Εγώ βλέποντας ότι η άσκηση ζητούσε να δείξουμε ότι υπάρχει N , λέω που το 'χω δει που το 'χω δει , στον ορισμό του ορίου . Ε και σε συνδιασμό με το μονότονη και φραγμένη πήγα χωρίς δεύτερη σκέψη στο όριο.

#7

Demetres έγραψε:
Mihalis_Lambrou έγραψε: Για το ίδιο πρόβλημα είχαμε και μία απόδειξη με το "Pontriagin duality theorem", αλλά την ξέχασα...
Για να δούμε. <...>

Ναι, σωστά.

Με παραλλαγή της απόδειξης που δίνεις μπορείς να κάνεις και άλλη μία που χρησιμοποιεί το γεγονός ότι το $\mathbb R$ ως χώρος Banach είναι αυτοπαθής (reflexive) οπότε εμφυτεύεται ισομετρικά στον δεύτερο δυικό του μέσω της $x \rightarrow \hat x$ , όπου $\hat {x}(x^*) = x^*(x)$ . Τρεχαγύρευε.

Φιλικά,

Μιχάλης

Προτασιακή Λογική

Προτασιακή Λογική

Re: Προτασιακή Λογική

Re: Προτασιακή Λογική

Re: Προτασιακή Λογική

Re: Προτασιακή Λογική

Re: Προτασιακή Λογική

Re: Προτασιακή Λογική

Μέλη σε σύνδεση