Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 12
Arytmetyka Peano i Systemy formalne liczb naturalnych
ZakÅ‚adamy, że wiadomo co oznaczajÄ… symbole ƒÄ… " =
1. Liczba 10 jest liczbÄ… parzystÄ….
2. 3 jest mniejsze od 7.
3. 2 nie jest kwadratem liczby naturalnej.
4. 5 jest liczbÄ… pierwszÄ….
" x śą xƒÄ…x =10źą
1.
" x śą3ƒÄ…1ƒÄ… x=7źą
2.
" x Źśą x"x=2źą
3.
Ź" x " y śą x" y=5źą Ź" x" y śą xƒÄ…1źąśą yƒÄ…1źą=5 Ź" x " y śą xƒÄ…2źąśą yƒÄ…2źą=5
4.
Istnieje nieskończenie wiele liczb pierwszych:
" x" z śąŹ"t , u z=śątƒÄ…2źąśą uƒÄ…2źą '" " s śą xƒÄ…s=zźąźą
Aksjomaty, reguły wnioskowania i twierdzenia
Aksjomaty Arytmetyki Peano
1. " x [ŹS x=0] S  następnik
" x śą xƒÄ…0=xźą
2.
" x" y śą xƒÄ…S yźą=S śą xƒÄ… yźą
3.
" x śą x"0=0źą
4.
" x" y śą x"S y=xyƒÄ… zźą
5.
Reguły wnioskowania: zwykłe reguły wnioskowania plus:
x= y
- symetria
y=x
x= y , y=z
- przechodniość
x=z
x= y S x=S y
, - reguły następstwa
S x=S y x= y
" x Aśą xźą
- reguła podstawienia
Aśątźą
Dwa dowody:
" x" y śą xƒÄ…S yźą=S śą xƒÄ… yźą
1. Aksjomat 3
" y śą S 0ƒÄ…S y źą=S śą S 0ƒÄ… yźą
2. Wiersz 1 + podstawienie S 0/ x
śąS 0ƒÄ…S 0źą=S śąS 0ƒÄ…0źą
3. Wiersz 2 + podstawienie 0 / y
" x śą xƒÄ…0źą= x
4. Aksjomat 2
śąS 0ƒÄ…0źą=S 0
5. Wiersz 4 + podstawienie S 0/ x
S śą S 0ƒÄ…0źą=S S 0
6. Wiersz 5 + reguła następstwa
śąS 0ƒÄ…S 0źą=S S 0
7. Wiersze 3 i 6 + przechodniość
Poufne: 1ƒÄ…1=2
" x" y śą x"S yźą=śą xyƒÄ…xźą
1. Aksjomat 5
" y śą S 0"S yźą=śą S 0"yƒÄ…S 0źą
2. Wiersz 1 + podstawienie S 0/ x
S 0"S 0=śąS 0"0ƒÄ…S 0źą
3. Wiersz 2 + podstawienie 0 / y
" x" y śą xƒÄ…S yźą=S śą xƒÄ… yźą
4. Aksjomat 3
" y śą S 0"0ƒÄ…S yźą=S śąS 0"0ƒÄ… yźą
5. Wiersz 4 + podstawienie S 0"0/ x
śąS 0"0ƒÄ…S 0źą=S śąS 0"0ƒÄ…0źą
6. Wiersz 5 + podstawienie 0 / y
" x śą xƒÄ…0=xźą
7. Aksjomat 2
śąS 0"0ƒÄ…0źą=S 0"0
8. Wiersz 7+ podstawienie S 0"0/ x
" x śą x"0=0źą
9. Aksjomat 4
10. S 0"0=0 Wiersz 9 + podstawienie S 0"0/ x
11. S 0"0ƒÄ…0=0 Wiersze 8 i 10 + przechodniość
S śą S 0"0ƒÄ…0źą=S 0
12. Wiersz 11 + reguła następstwa
śąS 0"0ƒÄ…S 0źą=S 0
13. Wiersze 6 i 12 + przechodniość
14. S 0"S 0=S 0 Wiersze 3 i 13 + przechodniość
Poufne: 1"1=1
0ƒÄ…0=0
0ƒÄ…S 0=S 0
- nie umiemy udowodnić
" x śą0ƒÄ… xźą= x 0ƒÄ…S S 0=S S 0
0ƒÄ…S S S 0=S S S 0
itd.
Do aksjomatów TRZEBA dodać:
[´Ä…śą0źą'"[" x ´Ä…śą xźąÒ! ´Ä…śą S xźą]]Ò! " x ´Ä…śą xźą
6. SCHEMAT algorytmu indukcji:
Twierdzenia Gödela o niezupeÅ‚noÅ›ci
Jeżeli aksjomaty dadzą się od nie-aksjomatów odróżniać w sposób danym systemie
śą N , ƒÄ… , "źą
arytmetyki liczb naturalnych w sposób algorytmiczny, to system tej jest
niezupełny, tzn. istnieją zdania prawdziwe niedowodliwe.