Αντιπαραδείγματα

Εισαγωγή στα Αντιπαραδείγματα

Ένα αντιπαράδειγμα είναι ένα συγκεκριμένο παράδειγμα που δείχνει ότι μια καθολική πρόταση είναι ψευδής. Είναι ένα από τα πιο ισχυρά εργαλεία για να διαψεύσουμε (αποδείξουμε ότι είναι λάθος) μια μαθηματική πρόταση.

Λογική Βάση

Μια πρόταση της μορφής "Για κάθε $x$, ισχύει $P(x)$" (συμβολικά: $\forall x: P(x)$) είναι ψευδής αν υπάρχει έστω και ένα $x$ για το οποίο η $P(x)$ δεν ισχύει.

Συμβολικά:

$$\neg(\forall x: P(x)) \Leftrightarrow \exists x: \neg P(x)$$

Δηλαδή, για να διαψεύσουμε μια καθολική πρόταση, αρκεί να βρούμε ένα μόνο αντιπαράδειγμα.

Η Δύναμη του Αντιπαραδείγματος

• Ένα αντιπαράδειγμα αρκεί για να διαψεύσει μια καθολική πρόταση
• Χίλια παραδείγματα δεν αρκούν για να αποδείξουν μια καθολική πρόταση

Για παράδειγμα, αν θέλουμε να διαψεύσουμε ότι "όλοι οι πρώτοι αριθμοί είναι περιττοί", αρκεί να δείξουμε ότι ο 2 είναι πρώτος και άρτιος.

Στρατηγικές Εύρεσης Αντιπαραδειγμάτων

1. Δοκιμάστε Ακραίες Τιμές

• $n = 0$ ή $n = 1$
• Πολύ μεγάλους ή πολύ μικρούς αριθμούς
• Αρνητικούς αριθμούς αν επιτρέπονται

2. Δοκιμάστε Ειδικές Περιπτώσεις

• Άρτιους vs περιττούς
• Πρώτους vs σύνθετους
• Ρητούς vs άρρητους
• Θετικούς vs αρνητικούς

3. Σκεφτείτε τις Οριακές Περιπτώσεις

• Τι γίνεται όταν κάτι είναι ακριβώς ίσο;
• Τι γίνεται στα άκρα ενός διαστήματος;

4. Χρησιμοποιήστε Γνωστά Αντιπαραδείγματα

• Ο αριθμός 2 (ο μόνος άρτιος πρώτος)
• Το 0 (ούτε θετικό ούτε αρνητικό)
• Η συνάρτηση $|x|$ (συνεχής αλλά όχι παραγωγίσιμη στο 0)

Αντιπαραδείγματα vs Αποδείξεις

Συνηθισμένες Ψευδείς Προτάσεις

Ορισμένες προτάσεις φαίνονται αληθείς αλλά είναι ψευδείς:

• "Αν $a^2 = b^2$ τότε $a = b$" (Αντιπαράδειγμα: $a = 1, b = -1$)
• "Η συνάρτηση $f(n) = n^2 - n + 41$ δίνει πάντα πρώτους" (Αποτυγχάνει για $n = 41$)
• "Αν $f$ και $g$ δεν είναι συνεχείς, τότε το $f + g$ δεν είναι συνεχές"

Προσοχή στις Υποθέσεις

Όταν ψάχνουμε αντιπαράδειγμα, πρέπει να βεβαιωθούμε ότι το παράδειγμά μας ικανοποιεί όλες τις υποθέσεις της πρότασης που θέλουμε να διαψεύσουμε.