Hiperrzeczywista

Przeprowadzanie prostego dowodu ma dużo z obliczania. Można je robić na kilka sposóbów, ja przedstawię dwa:

Mając daną formułę - np. (x+2)^2 + y i pewne parametry - np. (x, y) = (3, 2), to w pewnych wypadkach jesteśmy w stanie obliczyć wynik. Wychodząc z formuły i równościami, tożsamościami algebraicznymi dochodzimy do wyniku - wtedy obliczenia są wykonane.

Analogicznie: Mając daną tezę i pewne założenia, to w pewnych wypadkach jesteśmy w stanie udowodnić tę tezę. Wychodząc od niej i równoważnościami logicznymi dochodzimy do prawdy - wtedy twierdzenie jest udowodnione.

Jeżeli jesteśmy w ten sposób udowodnić, że teza jest równoważna prawdzie to jest prawdziwa. Tylko wtedy nie może być żadnego znaku wynikania, bo z fałszu prawda wynikać może.

Można też liczyć w drugą stronę. Tu pojawia się jedna różnica, bo obliczenia mają na celu doprowadzenie do wyniku, niezależnie jaki jest, a dowód musi do prawdy. Teoretycznie możesz zacząć od wyniku obliczeń, przekształcać algebraicznie i dojść do formuły. Tak samo w dowodzeniu, można wyjść od prawdy i rownoważnościami logicznymi przekształcać tak, aby uzyskać tezę. Wtedy możemy spokojnie używać wynikania - wszak z prawdy tylko prawda wynikac może.

Jest jedna generalna różnica pomiędzy równaniami algebraicznymi a dowodzeniem, którą starałem się . W równaniach nie mamy odpowiednika wynikania. Jeżeli a = b to b = a, tak jak równoważność - jeżeli a ↔ b to b ↔ a. Nie ma 'równości w jedną stronę', więc nie ma problemu z obiema metodami obliczania [choć druga jest trochę bezsensowna]. W pierwszej metodzie aby dowód był poprawny to muszą być albo równoważności albo wynikania w drugą stronę, bo tak naprawdę to musimy tak samo jak w drugiej metodzie dowieść, że z prawdy wynika teza.

Aby poznać inne metody dowodzenia polecam stronę How To Write Proofs.

Pewnie nie raz słyszeliście jedno z pytań faryzejskich - "Czy Bóg potrafi stworzyć taki kamień którego nie będzie potrafił podnieść?". Wydaje się, że pytanie nie ma odpowiedzi, gdyż zakłada się, że Bóg jest wszechmocny. Jednak ja udowodnię, że na to pytanie jest odpowiedź jednoznaczna i brzmi 'nie'.

Definicje:

f(x) - predykat na zbiorze wielkości kamieni: 'Czy Bóg potrafi stworzyć kamień o wielkości x'. Mówimy tutaj o wielkości, nie istotne jest czy to chodzi o promień, objętość czy masę.

g(x) - predykat na zbiorze wielkości kamieni: 'Czy Bóg potrafi podnieść kamień o wielkości x'.

Tak jak już mówiłem, zakładamy wszechmocność Boga:

1. ∀x f(x) - 'Bóg potrafi stworzyć kamień dowolnej wielkości'
2. ∀x g(x) - 'Bóg potrafi podnieśc kamień dowolnej wielkości'

Teza: ∼∃x (f(x) ∧ ∼g(x)) - 'nie istenie taki kamień, że Bóg go potrafi stworzyć i nie potrafi podnieść'.

Dowód:

1. Zaprzeczenie małego kwantyfikatora jest kwantyfikatorem wielkim zaprzeczenia: ∀x ∼(f(x) ∧ ∼g(x))
2. Prawo de Morgana: zaprzeczenie koniunkcji jest alternatywą zaprzeczeń: ∀x (∼f(x) ∨ g(x))
3. Prawy argument alternatywy jest prawdziwy z założenia. Alterantywa w której występuje jedna wartość prawdziwa jest cała prawdziwa.

QED.

Osobiście ostatni krok mi troszke nie pasuje, jest zbyt nieścisły, muszę się przyznać, że brakuje mi aparatu matematycznego, żeby go rozbić na dwie części. Więc mam dowód w drugą stronę:

1. Wychodzimy od założenia 2: ∀x g(x)
2. Wiemy, że alternatywa prawdy z dowolnym zdaniem logicznym daję dalej prawdę, wiec wybieramy sobie odgórne, fałszywe zdanie: ∀x ~f(x) ∨ ∀x g(x)
3. Wielki kwantyfikator można 'wyciągnąć przed nawias': ∀x (~f(x) ∨ g(x)) - to jest jedyne przejście które jest tylko wynikaniem, nie działa w drugą stronę. Wszystkie inne są tożsamościami.
4. Prawo de Morgana: ∀x ∼(f(x) ∧ ∼g(x))
5. Z zaprzeczenia wielkiego kwantyfikatora: ∼∃x (f(x) ∧ ∼g(x)) - teza.

Jaka jest największa liczba jaką widziałeś? Była ona większa niż 10³⁰? Ja myślałem, że widziałem duże liczby, zanim nie trafiłem na liczby Grahama.

Strzałka Knutha

Dużych liczb raczej się nie da przedstawić w zapisie dziesiętnym. Żeby zapisać dziesięć do milionowej, musiałbym użyć miliona znaków [prawie megabajt danych]. Na szczęście na tyle małą liczbę mogę zapisać używając notacje potęgowej: 10^1000000. Wykładnik też mogę zapisać w postaci potęgowej: 10¹⁰⁶. Jednak czasem nawet taki zapis nie wystarcza. Przykładowo, chcielibyśmy zapisać dwa do drugiej do drugiej do drugiej... - i tak 256 razy. Aby zapisać tę liczbę musiałbym użyć 256 stopni potęgowania: 2^222..2. Aby uniknąć tego rodzaju problemów Knuth wprowadził 'strzałke'.

Definicja jest kontynuacją mnożenia i potęgowania:

a·b = a+a+a+...+a [b razy]

a↑b = ab = a·a·a·a·...·a [b razy]

a↑↑b = aaa..a [b razy]

Dalej można definiować podwójną, potrójną i n-krotną strzałkę Knutha:

a↑↑b = a↑a↑a↑...↑a [b razy]

a↑↑↑b = a↑↑a↑↑a↑↑...↑↑a [b razy]

a ↑n b = (((a ↑n-1 a) ↑n-1 a) ↑n-1 ...) ↑n-1 a [b razy]

Jak duże może to generować liczby? Dla przykładu: 4↑↑↑4 = ((4↑↑4)↑↑4)↑↑4 = ((4444)↑↑4)↑↑4 = (340282366920938463463374607431768211456↑↑4)↑↑4 = ...

Następnym krokiem byłoby podniesienie powyższej liczby trzydziestodziewięciocyfrowej wykorzystując cztery poziomy potęgowania. Wychodzi z tego jakaś liczba, z którą trzeba zrobić te same obliczenia [cztero poziomowe potęgowanie] i mamy 4↑↑↑4.

Liczby Grahama

Największą liczbą użytą w dowodzie matematycznym była liczba Grahama. Dawała ona górne ograniczenie problemu Grahama: Mamy n-wymiarową hiperkostkę, której wierzchołki łączymy i kolorujemy brzegi albo na czerwono albo na czarno. Jaka jest najmniejsza liczba n, taka, że niezależnie od wybranego schematu kolorowania zawsze istniały cztery wierzchołki połączone brzegami o tym samym kolorze leżące na jednej płaszczyźnie?.

Definiujemy ciąg Grahama przez rekurencje:

g1 = 3↑↑↑↑3

gn = 3 ↑gn-1 3

Tak, tam jest g_n-1-krotna strzałka Knutha pomiędzy trójkami. Czyli w g₂ jest 3↑↑↑↑3 strzałek.

W tym ciągu liczba Grahama jest 64. Czytelnikowi pozostawiam ocenę wielkości tej liczby.

Dziś troszkę zabawy z matematyką. Na pewno spotkaliście się z czymś takim jak 'szyfr cezara', w świecie komputerowym znany także jako 'rot n'. Jest to prosty algorytm, który pozwala szyfrować wiadomość tak, żeby nie była w prosty sposób możliwa do odczytania. .

Szyfr cezara działa na zasadzie 'przekręcania' alfabetu. 'Przesuwamy' każdą literę o n znaków do przodu, jeżeli wyszliśmy poza ostatni znak, to zaczynamy liczyć od pierwszego. Oryginalnie Juliusz Cezar szyfrował przy n = 3. Co najciekawsze, przy n = 13 ten sam algorytm szyfruje wiadomość a także ją odszyfrowuje po ponownym użyciu. Ten algorytm działa jak należy na literach łacińskich, ponieważ jest ich 26.

Zastanówmy się jak można by go przedstawić matematycznie. Pierwsze co musimy to zdefiniować sobie zbiór liter - nowej 'jakości'. To jest naprawdę proste: ζ - zbiór liter.

A teraz w podobny sposób definiujemy sobie literę: α ∈ ζ: α - litera.

Jak na razie idzie nam wyśmienicie. Ale zbiór liter to jeszcze nie alfabet. Potrzebujemy jeszcze porządku. Niestety, tutaj po raz trzeci będziemy musieli zrobić to aksjomatycznie, ostatecznie musielibyśmy wypisać wszystkie pary w relacji większości. Tak więc ≼ - relacja zwrotna, asymetryczna i przechodnia. Tak więc para (ζ, ≼) - alfabet.

Teraz wyłuskamy sobie litery łacińskie ze zbioru liter: L ⊂ ζ, L = {'a', 'b', 'c', ..., 'z'}. Wiadomo: |L| = 26, a także (L, ≼) - alfabet łaciński.

Zdefiniujmy sobie normę na alfabecie w ten sposób, że 'wartość' litery, to jest ilość liter przed nią:

|·|: ζ → N; |α| = |{x: x≼α ⋀ x≠α}|

Uwaga: pierwsza norma to nasza norma na literze, druga to moc zbioru.

Ponieważ relacja ≼ jest porządkiem liniowym na ζ, więc norma jest różnowartościowa, więc istnieje funkcja |·|^-1 - słowami można powiedzieć, że przypisuje liczbie literę, która się znajduje na odpowiedniej pozycji.

Następnie zdefiniujemy sobie funkcje, która literę przesuwa w alfabecie o n pozycji:

ρ: A⊂ζ × N → A; ρ(α, n) = |(|α| + n) mod |A||^-1.

Szczególny przypadek A = L i n = 3 to szyfr cezara a przy n = 13 to sławny 'rot13'.