Οι ποσοδείκτες $ , $ !, " ; αντιπαραδείγματα. H εις άτοπον επαγωγή.

Αρχή μαθηματικής επαγωγής: Εστω P(n) μια πρόταση για κάθε φυσικό αριθμό n. Αν (ι) η P(1) ισχύει και (ιι) η P(n) συνεπάγεται την P(n + 1), τότε η P(n) ισχύει για κάθε φυσικό αριθμό n.

Θεώρημα 2.1. (Αρχή καλής διάταξης). Κάθε μη κενό υποσύνολο του Ν έχει ελάχιστο ( πρώτο) στοιχείο.

2.1. " x R, έχουμε x^{2 >} 0.

Λύση

2.2. " x R, $ y R με xy = 1.

Λύση

2.3. " x R^*, $ y R^* με xy = 1.

Λύση

2.4. " x R⁺, $ ! y R⁺ με xy = 1.

Λύση

2.5. $ ! x R⁺ με x² = 1.

Λύση

2.6. (Μια άλλη μορφή της αρχής της καλής διάταξης). Να δείξετε ότι κάθε μη κενό, κάτω φραγμένο υποσύνολο Α του Ζ έχει ελάχιστο στοιχείο.

Λύση

2.7. Να δείξετε ότι κάθε μη κενό, άνω φραγμένο υποσύνολο Β του Ζ έχει μέγιστο στοιχείο.

Λύση

2.8. (Μια άλλη μορφη επαγωγής). Εστω k ακέραιος και για κάθε ακέραιο n ³ k, P(n) πρόταση τ.ω. (ι) η P(k) ισχύει και (ιι) η P(n) συνεπάγεται την P(n+1).

Χρησιμοποιώντας την 2.6. να δείξετε ότι η P(n) ισχύει για κάθε n ³ k.

Λύση

2.9. (Πλήρης επαγωγή). Εστω k ακέραιος και Q(n) πρόταση για κάθε ακέραιο n ³ k. Δεδομένου ότι 

(1) η Q(k) ισχύει και 

(2) οι προτάσεις Q(m), k £ m £ n μαζί συνεπάγονται την Q(n+1) για κάθε n ³ k, 

να δείξετε ότι η Q(n) ισχύει για κάθε n ³ k.

2.10. Να δείξετε ότι για κάθε φυσικό αριθμό n, 2 + 4 + 6 +...+ 2n = n(n+1).

Λύση

2.11. Να δείξετε ότι για κάθε φυσικό αριθμό n, 1 + 3 + 5 +...+ (2n – 1) = n².

Λύση

2.12. Να δείξετε ότι για κάθε φυσικό αριθμό n, το σύνολο {1, 2, 3, ... , n} έχει 2ⁿ υποσύνολα.

Λύση

2.13. Να δείξετε ότι για κάθε φυσικό αριθμό n ³ 10, 2ⁿ > n³.

Λύση