Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Jak policzyć?

No description
by

Michał Korch

on 15 September 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Jak policzyć?

Matematyka dla ciekawych świata
Część 1. Jak policzyć?
Michał Korch, MIMUW
Słów kilka o zbiorach
{ , , , }
A=
element należy do zbioru
{ , , , }
{ , } { , }=
{ , , , }
{ , }
jest podzbiorem
{ , , , }
{ , , }
{ , , }=
{ , }
suma
iloczyn
Hotel Hilberta
standardowy
skończenie wiele pokoi
może przyjąć tyle gości ile ma pokoi
jeśli wszystkie pokoje są zajęte, nie można zakwaterować nowego gościa
hotel w wersji
...
nieskończenie wiele pokoi
...
mimo tego, że wszystkie pokoje były zajęte, udało się zakwaterować nowego gościa
...
...
...
...
...
...
w jeden hotel Hilberta udało się zakwaterować tyle gości, ile zapełniłoby dwa hotele Hilberta!
Davida
1862-1943
przestrzeń Hilberta, system Hilberta, krzywa Hilberta...
problemy Hilberta
Międzynarodowy Kongres Matematyków, Paryż, 1900
Tyle samo elementów?
raz, dwa, trzy, cztery.
Cztery
raz, dwa, trzy, cztery.
Cztery
A co jeśli nie umielibyśmy liczyć do czterech?
Obserwacja: jeśli na sali balowej każdy tańczy w jakiejś parze, to jest tyle samo mężczyzn, co kobiet.
Wniosek (definicja):
powiemy, że dwa zbiory są równoliczne, jeśli ich elementy można ustawić w pary (ozn. |A|=|B|)
w przypadku hotelu Hilberta ustawialiśmy w pary gości i pokoje.
|N| = |N {-1}|
{0,1,2,3,4,5,6,...}
liczby naturalne
0 1 2 3 4 5 6 7 ...
-1 0 1 2 3 4 5 6 ...
|N| = |Z|
0 1 2 3 4 5 6 7 ...
0 1 -1 2 -2 3 -3 4 ...
liczby całkowite
{..., -3, -2, -1, 0, 1, 2, 3,...}
N i pary liczb naturalnych
(0,0) (0,1) (0,2) (0,3)...
(1, 0) (1, 1) (1, 2) (1, 3)...
(2,0) (2, 1) (2,2) (2,3)...
(3,0) (3, 1) (3,2) (3,3)...
... ... ... ...
0 1 2 3 4 5 6 7 ...

(0,0) (1,0) (0,1) (0,2) (1,1) (2,0) (3,0) (2,1) ...
|N| = |Q|
(dla uproszczenia zajmiemy się tylko dodatnimi)
liczby wymierne
liczby postaci p/q
gdzie p,q są całkowite i q jest różne od zera
1/1 1/2 1/3 1/4 ...
2/1 2/2 2/3 2/4 ...
3/1 3/2 3/3 3/4 ...
4/1 4/2 4/3 4/4 ...
... ... ... ...
0 1 2 3 4 5 6 7 ...

1 2 1/2 1/3 3 4 3/2 2/3 ...
troszkę dziwne, nie?
Twierdzenie Cantora
A może w takim razie wszystkie nieskończone zbiory są równoliczne?
Nie! |N|<|R|
N i nieskończone ciągi zer i jedynek
Dowód nie wprost
Załóżmy przeciwnie:
0
1
2
3
4
...
spórzmy na przekątną
i zróbmy na złość.
0 0 1 1 1 0 0 0 ...
0 1 0 0 1 0 0 0 ...
1 1 1 0 0 0 1 0 ...
0 0 0 0 1 0 0 1 ...
1 1 0 1 0 0 0 0 ...
...
1 0 0 1 1 ...
w ten sposób na n-tym miejscu
gwarantujemy, że nasz ciąg jest inny niż ten w n-tym miejscu!
Czyli nie ma go w tabelce!
Sprzeczność!
P(N)
zbiór wszystkich podzbiorów zbioru liczb naturalnych
{ , , }
A=
P(A)=
,{ }, { }, { },
{ , }, { , }, { , },
{ , , }
{ }
Każdy podzbiór liczb naturalnych można zakodować ciągiem zero-jedynkowym
{2, 3, 5, 7, 11, ...}
0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ...
a zatem podzbiorów liczb naturalnych jest tyle, co nieskończonych ciągów zerojedynkowych.
|N|<|P(N)|
Niech A będzie dowolnym zbiorem.
|A|<|P(A)|
Georg
1845-1918
przestrzeń Cantora,
twierdzenie Cantora, zbiór Cantora, funkcja Cantora
ojciec teorii mnogości
|N|=|Z|=|Q|
zbiory przeliczalne
|P(N)|=|[0,1]|=|R|
>
zbiory mocy continuum
Tego jeszcze nie udowodniliśmy.
Wskazówka: rozwinięcia binarne ułamków.
Pytanie: Czy istnieje nieskończony zbiór, który nie jest przeliczalny, ale ma mniej elementów niż zbiory mocy continuum?
Hipoteza continuum: Nie istnieje.
Tw. Cohen, Goedel (lata 60-te)
Jeśli matematyka jest niesprzeczna,
to
nie rozstrzyga
hipotezy continuum.
z aksjomatów matematyki nie da się udowodnić ani hipotezy continuum, ani jej zaprzeczenia
(o ile są one niesprzeczne)
Tw. Goedla
Na gruncie matematyki
nie da się wykazać, że jest ona niesprzeczna.
Nieskończenie wiele (bardzo nieskończenie wiele) nieskończoności.
A = P(N)
A = P(A )=P(P(N))
A = P(A )
....
|A |< |A |< |A |< |A |<...
0

1 0

2 1
0 1 2 3
Ale to nie koniec:
A A A A ...
0 1 2 3
jest jeszcze większe...
I to też nie koniec. Świat matematyki rozciąga się
niesamowicie nieskończenie daleko.
Nieskończoność! Żadne inne pytanie nie poruszyło tak głęboko duszy człowieka.
David Hilbert
There are 10 types of people:
those who understand binary notation
and those who don't
np.:
0,101 1/2+0/4+1/8=5/8
0,0111 0/2+1/4+1/8+1/16=7/16
Łączymy w pary nieskończone ciągi zero-jedynkowe z liczbami rzeczywistymi z przedziału [0,1], których są binarnym rozwinięciem.
Uwaga: Bierzemy tylko takie ciągi, które od pewnego miejsca nie mają samych jedynek. Ale takich, które mają same jedynki od pewnego miejsca jest tylko przeliczalnie wiele (do sprawdzenia w domu lub na ćwiczeniach)
Łączymy w pary liczby:
x z liczbą (x-1/2)/x(1-x)
(nie połączyliśmy 0 i 1,
ale wiemy, że 2 punkty różnicy nie czynią)
Dodatek. A. Nieskończoność nieskończoności
zacznijmy od powtórzenia...
Jak konstruować coraz większe nieskończoności?
Metoda zbioru potęgowego
A
P(A)
z Tw. Cantora |P(A)|>|A|
w szczególności dla każdej liczby kadrynalnej istnieje liczba kadrynalna od niej większa
liczba kadrynalna - moc jakiegoś zbioru
...
mamy:
przeliczalnie wiele coraz większych liczb kardynalnych
Metoda sumowania nieograniczonego zbioru liczb kardynalnych
K
zbiór liczb kardynalnych, w którym nie ma liczby wśród nich największej, np:
dla uproszczenia tak samo będziemy nazywać przykładowy zbiór o danej mocy
Moc tej sumy jest większa niż jakakolwiek z liczb kardynalnych ze zbioru K
np:
bo:
Dwa mniej lub bardziej zaskakujące wnioski
1. Nie istnieje największa liczba kardynalna
Bo gdyby istniała bierzemy moc jej zbioru potęgowego. Ona jest jeszcze większa -- sprzeczność.
II. Nie istnieje zbiór wszystkich liczb kardynalnych
Załóżmy, że istnieje i nazwijmy go K. Nie ma w nim największej w nim liczby kardynalnej, bo taka nie istnieje.
Możemy więc skonstruować liczbę kardynalną większą od każdej ze zbioru K metodą sumowania. Ale ta liczba nie jest w zbiorze K -- sprzeczność.
Nurtujące pytanie
Czy korzystając z metod zbioru potęgowego, następnikowej i sumowania skonstruujemy każdą dowolnie gigantyczną liczbę kardynalną?
Dwie definicje
liczba kadrynalna jest
graniczna
jeśli wśród
wszystkich liczb ściśle mniejszych od niej nie
ma liczby spośród nich największej
np. |N|
czy continuum jest graniczna?
liczba kadrynalna jest
regularna
jeśli nie jest sumą mniejszego od niej zbioru zbiorów mniejszych od niej
np. |N|
ale i continuum
takich liczb nie da się skonstruować metodą sumowania
A jakiś przykład
nie-
?
najmniejsza liczba kardynalna większa
najmniejsza liczba kardynalna większa
...
najmniejsza liczba kardynalna większa
od tych wszystkich powyżej
Uwaga
Biorąc zbiór potęgowy niekoniecznie otrzymam najmniejszą liczbę kardynalną większą od danej -- patrz np. hipoteza continuum.
Ale oczywiście ponieważ już wiem, że dla każdej liczby kardynalnej istnieje od niej większa, mogę znaleźć też najmniejszą spośród nich.
Możemy to uznać za osobną metodę konstruowania większych liczb, nazwijmy to
metodą

następnikową
.
takich liczb nie da się skonstruować metodą następnikową
liczby kardynalne, które są
naraz graniczne i regularne
matematycy nazywają
słabo nieosiągalnymi
to oznacza, że nie da się do nich
"dojść" mając do dyspozycji metodą
następnikową i metodę sumowania
(nieużywając metody zbioru potęgowego)
Teoriomnogościowy wszechświat
No więc czy są liczby kardynalne, do których nie da się dojść nawet używając metody zbioru potęgowego?
Takie hipotetyczne liczby nazywamy
silnie nieosiągalnymi
Liczba silnie nieosiągalna ma następującą cechę: każdy zbiór potęgowy zbioru o mocy od niej mniejszej ma nadal moc od niej mniejszą.
Istnienie liczb silnie nieosiągalnych jest niezależne od
aksjomatów teorii mnogości (podobnie jak hipoteza continuum)
Wszechświat teorii mnogości
coraz większe zbiory
N
R
pierwsza liczba silnie nieosiągalna
(horyzont)
...
"wszechświat(y) równoległe"
I tak dalej. Istnieje
liczba p
należący do wszystkich tych coraz mniejszych odcinków.
Dowód
niewprost:
Skupmy się na odcinku [0,1]. I załóżmy przeciwnie, że wszystkie liczby z tego odcinka udało się zakwaterować w hotelu Hilberta.
0
1
1/3
2/3
Dzielimy odcinek na trzy części.
Bierzemy tę z nich, w której nie ma .
Wybrany odcinek znów dzielimy na trzy części.
Bierzemy tę z nich, w której nie ma .
Wybrany odcinek znów dzielimy na trzy części.
Bierzemy tę z nich, w której nie ma .
...
p
....
p nie jest na tej liście
Sprzeczność!
Full transcript