Απόδειξη με Άτοπο

Μεσαίο

Εισαγωγή στην Απόδειξη με Άτοπο

Η απόδειξη με άτοπο (ή εις άτοπο απαγωγή) είναι μία από τις πιο ισχυρές μεθόδους μαθηματικής απόδειξης. Αντί να αποδείξουμε απευθείας μια πρόταση, υποθέτουμε ότι είναι ψευδής και δείχνουμε ότι αυτό οδηγεί σε αντίφαση.

Λογική Βάση

Η μέθοδος βασίζεται στον νόμο του αποκλειομένου τρίτου: κάθε πρόταση είναι είτε αληθής είτε ψευδής, δεν υπάρχει τρίτη δυνατότητα.

Αν η υπόθεση ότι η πρόταση $P$ είναι ψευδής οδηγεί σε αντίφαση, τότε η $P$ πρέπει να είναι αληθής.

Συμβολικά: $(\neg P \Rightarrow \bot) \Rightarrow P$

όπου $\bot$ συμβολίζει την αντίφαση (κάτι αδύνατο).

Δομή της Απόδειξης με Άτοπο

Υπόθεση της άρνησης: Υποθέτουμε ότι η πρόταση που θέλουμε να αποδείξουμε είναι ψευδής
Λογική επεξεργασία: Χρησιμοποιούμε την υπόθεση μαζί με γνωστά αποτελέσματα
Εύρεση αντίφασης: Καταλήγουμε σε κάτι που είναι προφανώς ψευδές ή αντιφάσκει με κάποια υπόθεση
Συμπέρασμα: Άρα η αρχική υπόθεσή μας ήταν λανθασμένη, δηλαδή η πρόταση είναι αληθής

Πότε Χρησιμοποιούμε την Απόδειξη με Άτοπο

Η μέθοδος είναι ιδιαίτερα χρήσιμη όταν:

Θέλουμε να αποδείξουμε ότι κάτι δεν υπάρχει ή είναι αδύνατο
Η πρόταση περιέχει άρνηση ή ποσοδείκτη καθολικότητας
Η άμεση απόδειξη είναι δύσκολη ή αδύνατη
Θέλουμε να αποδείξουμε ότι ένα σύνολο είναι άπειρο

Τυπικές Αντιφάσεις

Συνήθεις μορφές αντίφασης που αναζητούμε:

$x = y$ και $x \neq y$
$n > 0$ και $n \leq 0$
Ένας αριθμός είναι ταυτόχρονα άρτιος και περιττός
Ένα σύνολο είναι ταυτόχρονα κενό και μη κενό
$0 = 1$ ή γενικότερα δύο διαφορετικοί αριθμοί να είναι ίσοι

Η Ιστορική Απόδειξη του Αρρήτου

Μία από τις πιο διάσημες αποδείξεις με άτοπο είναι η απόδειξη ότι η $\sqrt{2}$ είναι άρρητος αριθμός, που αποδόθηκε στους Πυθαγόρειους.

Συμβουλές

Διατυπώστε καθαρά την άρνηση: Τι σημαίνει η πρόταση να είναι ψευδής;
Αναζητήστε αντίφαση συστηματικά: Ακολουθήστε τις λογικές συνέπειες της υπόθεσης
Μην ξεχνάτε όλες τις υποθέσεις: Η αντίφαση μπορεί να προκύψει με οποιαδήποτε από τις υποθέσεις σας

Βασικοί Τύποι

(\neg P \Rightarrow \bot) \Rightarrow P

\sqrt{2} \notin \mathbb{Q}

\text{Άπειροι πρώτοι: } p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1

Παραδείγματα

Παράδειγμα 1

Παράδειγμα 1: Να αποδειχθεί ότι η $\sqrt{2}$ είναι άρρητος αριθμός.

Απόδειξη:

Υποθέτουμε το αντίθετο, ότι η $\sqrt{2}$ είναι ρητός.

Τότε υπάρχουν ακέραιοι $p, q$ με $q \neq 0$ και $\gcd(p, q) = 1$ (ανάγωγο κλάσμα) τέτοιοι ώστε:

$\sqrt{2} = \frac{p}{q}$

Υψώνοντας στο τετράγωνο: $2 = \frac{p^2}{q^2}$ , άρα $p^2 = 2q^2$ .

Άρα το $p^2$ είναι άρτιο, που σημαίνει ότι το $p$ είναι άρτιο (αφού το τετράγωνο περιττού είναι περιττό).

Έστω $p = 2k$ για κάποιον ακέραιο $k$ . Τότε:

$(2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2$

Άρα το $q^2$ είναι άρτιο, που σημαίνει ότι το $q$ είναι άρτιο.

Αντίφαση: Τα $p$ και $q$ είναι και τα δύο άρτια, άρα $\gcd(p, q) \geq 2$ , που αντιφάσκει με την υπόθεση ότι το κλάσμα είναι ανάγωγο.

Άρα η $\sqrt{2}$ είναι άρρητος.

$\blacksquare$

Παράδειγμα 2

Παράδειγμα 2: Να αποδειχθεί ότι δεν υπάρχει μεγαλύτερος πρώτος αριθμός (οι πρώτοι είναι άπειροι).

Απόδειξη (Ευκλείδης):

Υποθέτουμε το αντίθετο, ότι υπάρχουν πεπερασμένοι πρώτοι αριθμοί.

Έστω $p_1, p_2, \ldots, p_n$ όλοι οι πρώτοι αριθμοί.

Θεωρούμε τον αριθμό:

$N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$

Ο $N$ είναι μεγαλύτερος από 1, άρα έχει τουλάχιστον έναν πρώτο διαιρέτη $p$ .

Ο $p$ πρέπει να είναι κάποιος από τους $p_1, p_2, \ldots, p_n$ (αφού αυτοί είναι όλοι οι πρώτοι).

Όμως $N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$ αφήνει υπόλοιπο 1 όταν διαιρεθεί με οποιονδήποτε $p_i$ .

Αντίφαση: Ο $p$ διαιρεί το $N$ αλλά δεν μπορεί να είναι κανένας από τους $p_i$ .

Άρα οι πρώτοι αριθμοί είναι άπειροι.

$\blacksquare$

Παράδειγμα 3

Παράδειγμα 3: Να αποδειχθεί ότι αν $a^2$ είναι άρτιος, τότε ο $a$ είναι άρτιος.

Απόδειξη:

Υποθέτουμε το αντίθετο: το $a^2$ είναι άρτιος αλλά ο $a$ είναι περιττός.

Αφού ο $a$ είναι περιττός, υπάρχει ακέραιος $k$ τέτοιος ώστε $a = 2k + 1$ .

Τότε:

$a^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Άρα το $a^2$ είναι περιττός.

Αντίφαση: Υποθέσαμε ότι το $a^2$ είναι άρτιος, αλλά δείξαμε ότι είναι περιττός.

Άρα αν το $a^2$ είναι άρτιος, τότε ο $a$ είναι άρτιος.

$\blacksquare$

Σχετικά Θέματα

direct-proof contrapositive mathematical-induction prime-numbers

Απόδειξη με Άτοπο

Μεσαίο

Εισαγωγή στην Απόδειξη με Άτοπο

Λογική Βάση

Αν η υπόθεση ότι η πρόταση $P$ είναι ψευδής οδηγεί σε αντίφαση, τότε η $P$ πρέπει να είναι αληθής.

Συμβολικά: $(\neg P \Rightarrow \bot) \Rightarrow P$

όπου $\bot$ συμβολίζει την αντίφαση (κάτι αδύνατο).

Δομή της Απόδειξης με Άτοπο

Υπόθεση της άρνησης: Υποθέτουμε ότι η πρόταση που θέλουμε να αποδείξουμε είναι ψευδής
Λογική επεξεργασία: Χρησιμοποιούμε την υπόθεση μαζί με γνωστά αποτελέσματα
Εύρεση αντίφασης: Καταλήγουμε σε κάτι που είναι προφανώς ψευδές ή αντιφάσκει με κάποια υπόθεση
Συμπέρασμα: Άρα η αρχική υπόθεσή μας ήταν λανθασμένη, δηλαδή η πρόταση είναι αληθής

Πότε Χρησιμοποιούμε την Απόδειξη με Άτοπο

Η μέθοδος είναι ιδιαίτερα χρήσιμη όταν:

Θέλουμε να αποδείξουμε ότι κάτι δεν υπάρχει ή είναι αδύνατο
Η πρόταση περιέχει άρνηση ή ποσοδείκτη καθολικότητας
Η άμεση απόδειξη είναι δύσκολη ή αδύνατη
Θέλουμε να αποδείξουμε ότι ένα σύνολο είναι άπειρο

Τυπικές Αντιφάσεις

Συνήθεις μορφές αντίφασης που αναζητούμε:

$x = y$ και $x \neq y$
$n > 0$ και $n \leq 0$
Ένας αριθμός είναι ταυτόχρονα άρτιος και περιττός
Ένα σύνολο είναι ταυτόχρονα κενό και μη κενό
$0 = 1$ ή γενικότερα δύο διαφορετικοί αριθμοί να είναι ίσοι

Η Ιστορική Απόδειξη του Αρρήτου

Συμβουλές

Διατυπώστε καθαρά την άρνηση: Τι σημαίνει η πρόταση να είναι ψευδής;
Αναζητήστε αντίφαση συστηματικά: Ακολουθήστε τις λογικές συνέπειες της υπόθεσης
Μην ξεχνάτε όλες τις υποθέσεις: Η αντίφαση μπορεί να προκύψει με οποιαδήποτε από τις υποθέσεις σας

Βασικοί Τύποι

(\neg P \Rightarrow \bot) \Rightarrow P

\sqrt{2} \notin \mathbb{Q}

\text{Άπειροι πρώτοι: } p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1

Παραδείγματα

Παράδειγμα 1

Παράδειγμα 1: Να αποδειχθεί ότι η $\sqrt{2}$ είναι άρρητος αριθμός.

Απόδειξη:

Υποθέτουμε το αντίθετο, ότι η $\sqrt{2}$ είναι ρητός.

Τότε υπάρχουν ακέραιοι $p, q$ με $q \neq 0$ και $\gcd(p, q) = 1$ (ανάγωγο κλάσμα) τέτοιοι ώστε:

$\sqrt{2} = \frac{p}{q}$

Υψώνοντας στο τετράγωνο: $2 = \frac{p^2}{q^2}$ , άρα $p^2 = 2q^2$ .

Άρα το $p^2$ είναι άρτιο, που σημαίνει ότι το $p$ είναι άρτιο (αφού το τετράγωνο περιττού είναι περιττό).

Έστω $p = 2k$ για κάποιον ακέραιο $k$ . Τότε:

$(2k)^2 = 2q^2 \Rightarrow 4k^2 = 2q^2 \Rightarrow q^2 = 2k^2$

Άρα το $q^2$ είναι άρτιο, που σημαίνει ότι το $q$ είναι άρτιο.

Άρα η $\sqrt{2}$ είναι άρρητος.

$\blacksquare$

Παράδειγμα 2

Παράδειγμα 2: Να αποδειχθεί ότι δεν υπάρχει μεγαλύτερος πρώτος αριθμός (οι πρώτοι είναι άπειροι).

Απόδειξη (Ευκλείδης):

Υποθέτουμε το αντίθετο, ότι υπάρχουν πεπερασμένοι πρώτοι αριθμοί.

Έστω $p_1, p_2, \ldots, p_n$ όλοι οι πρώτοι αριθμοί.

Θεωρούμε τον αριθμό:

$N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$

Ο $N$ είναι μεγαλύτερος από 1, άρα έχει τουλάχιστον έναν πρώτο διαιρέτη $p$ .

Ο $p$ πρέπει να είναι κάποιος από τους $p_1, p_2, \ldots, p_n$ (αφού αυτοί είναι όλοι οι πρώτοι).

Όμως $N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$ αφήνει υπόλοιπο 1 όταν διαιρεθεί με οποιονδήποτε $p_i$ .

Αντίφαση: Ο $p$ διαιρεί το $N$ αλλά δεν μπορεί να είναι κανένας από τους $p_i$ .

Άρα οι πρώτοι αριθμοί είναι άπειροι.

$\blacksquare$

Παράδειγμα 3

Παράδειγμα 3: Να αποδειχθεί ότι αν $a^2$ είναι άρτιος, τότε ο $a$ είναι άρτιος.

Απόδειξη:

Υποθέτουμε το αντίθετο: το $a^2$ είναι άρτιος αλλά ο $a$ είναι περιττός.

Αφού ο $a$ είναι περιττός, υπάρχει ακέραιος $k$ τέτοιος ώστε $a = 2k + 1$ .

Τότε:

$a^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Άρα το $a^2$ είναι περιττός.

Αντίφαση: Υποθέσαμε ότι το $a^2$ είναι άρτιος, αλλά δείξαμε ότι είναι περιττός.

Άρα αν το $a^2$ είναι άρτιος, τότε ο $a$ είναι άρτιος.

$\blacksquare$

Σχετικά Θέματα

direct-proof contrapositive mathematical-induction prime-numbers