[SCRÂȘIT]
[FOSȘIT] [CLIC]
CASEY RODRIGUEZ: Deci ultima
dată când am vorbit despre...
am abordat seturi și inducție.  De
data aceasta, vreau să pun
o întrebare despre seturi,
care se pare că este de fapt
o întrebare destul de profundă.
Adică, nu am
venit eu însumi.
Această întrebare are probabil cel puțin
150 de ani.
Așadar, întrebarea pe care vreau să o
pun este dacă A și B sunt mulțimi -
sau haideți să o formulăm
astfel, cel puțin puțin mai
eficient.
Când două seturi, A și
B, au aceeași dimensiune?
Acum, acest lucru este
deosebit de interesant
dacă aceste două seturi
nu sunt finite,
adică
nu sunt cinci,
nu sunt opt,
dar există infinit de
mulți membri,
orice înseamnă asta.
Și voi defini de fapt
ce înseamnă asta.
De exemplu,
numerele naturale și numerele întregi
au aceeași dimensiune?
Numerele naturale
și numerele raționale
au aceeași dimensiune?
Dar
numerele raționale și numerele reale?
Chiar dacă nu am
definit încă acest lucru,
poți totuși să ții cont de
noțiunea ta despre numerele reale
din calcul.
Și deci această întrebare este...
de ce este adâncă?
Pentru că depinde
de acest cuvânt aici,
„mărime” și ce
înseamnă exact asta.
Deci nu sunt
un răspuns atât de bun,
asta se datorează lui George Cantor.
El a spus că două seturi -
deci nu un răspuns, ci
un mod de a defini dimensiunea
sau un mod de a spune că cele două
seturi au aceeași dimensiune.
El a spus că două seturi au
aceeași dimensiune atunci când cele două seturi --
elementele celor două seturi
pot fi împerecheate, adică --
și voi face acest lucru mult mai
precis într-un minut sau cam așa ceva.
Ce vrea sa spuna?
Sau ce vreau să spun?
De exemplu, mulțimea a, b
și c și mulțimea 1, 2 și 3.
Deci acesta, acest set, este format
din trei litere -- a, b și c.
Acest set este format
din trei numere întregi--
1, 2 și 3.
Au aceeași dimensiune,
deoarece în esență
le pot împerechea.
Deci a și 1 merg împreună,
b și 2 merg împreună,
iar c și 3 merg împreună,
ceea ce înseamnă că fiecare membru al acestui set
este asociat cu
un element din acest set.
Și fiecare element al
acestui set este asociat
cu un element unic
din acest set.
Acum, pentru a face... și deci
aceasta merge sub numele
de teoria cardinalității sau
numerele cardinale, dacă vrei.
Dar nu vom intra
prea adânc în ea.
Deci, modul în care faceți...
sau modul în care faceți
această pereche de afaceri
mai precisă este utilizarea
limbajului funcțiilor.
Și ai de-a face
cu funcții de când
faci calcul.
Așa că voi
reintroduce sau revizui rapid
o terminologie care merge
împreună cu funcțiile care
vor fi sensul precis
al acestei afaceri de împerechere
pe care o scriu aici.
Dar doar cu privirea
către viitor,
acesta este motivul pentru care trec în revistă o parte
din această terminologie legată
de funcții.
Deci, o scurtă trecere în revistă a
terminologiei pentru funcții -
deci permiteți-mi doar să-mi amintesc
că, dacă A și B sunt mulțimi,
atunci funcția f A B -
deci o funcție este de obicei scrisă
ca f două puncte A săgeată la B,
ceea ce înseamnă că ia elemente
din A  în elemente din B.
Aceasta este o mapare care--
sau, dacă doriți, o misiune.  Îi
atribuie fiecărui x din
A un element unic pe care îl
notăm f din x în B.
Deci o singură intrare, x,
îmi oferă o singură ieșire.
Și intrarea nu
îmi dă trei ieșiri.
Acum, aceasta este ceea ce s-ar numi
o definiție naivă, probabil,
nu neapărat
complet lipsită de ambiguitate.
Dar pentru noi este suficient.
În manual,
puteți căuta o funcție
definită fără ambiguitate sau ca o
submulțime a produsului cartezian
al lui A și B, pe care l-
ați recunoaște
ca descriind în esență
graficul funcției.
Dar atunci nu mai folosiți niciodată
această definiție.
Și, în esență,
utilizați această definiție
atunci când vă gândiți la
funcții și când
demonstrați proprietățile funcției.
Deci asta o vom
lua doar ca definiție.
Și va fi
suficient de clar pentru noi.
Deci, să fie f o
funcție de la A la B.
Dacă C este o submulțime a lui
A, definim o mulțime -
deci aceasta este f din capitalul C.
Deci C nu este un element al lui A.
Este o submulțime a lui A.
Și aceasta  este un subset
al lui B. Acesta este...
permiteți-mi să-l scriu puțin
diferit aici.
Aceasta este o mulțime a tuturor
y din B astfel încât să
existe un x în C astfel
încât y să fie egal cu f din x.
Și aș putea scrie acest lucru
puțin mai eficient, deoarece acesta
este mulțimea tuturor
elementelor f ale lui x
ca intervale x peste
elementele acestei submulțimi C.
Și dacă D este o submulțime a lui B,
definim mulțimea f inversă a lui D.
Aceasta  este setul de tipi
care sunt mapați în D.
Așa că ar trebui să spun că aceasta este
imaginea inversă a lui D,
nu inversul
acestei funcție f.
Deci inversul, orice
înseamnă asta pentru moment,
nu
există neapărat întotdeauna.
Deci această imagine inversă a
mulțimii D există întotdeauna.
Aceasta este mulțimea tuturor elementelor
din A astfel încât f din x este în D.
Deci, de exemplu, să mă--
deci 1, 2, 3, 4 și a, b, c, d.
Și să presupunem că 1 merge
la a, 2 merge la a, 3 merge
la c, 4 merge la d.
Atunci f din mulțimea 1,
2, aici este unde-- care
este mulțimea care primește--
deci aceasta este submulțimea--
așa că ar trebui să vă gândiți la aceasta ca
B, a, b și c și D. Și  apoi
1, 2 și 3, acesta este A.
Deci f din mulțimea lui 1, 2--
deci 1 este mapat la a.
2 este mapat la a.
Deci, acesta este doar mulțimea 2.
f a mulțimii-- să
mergem cu 1 și 3.
1 este mapat la a.
Deci asta ar trebui să fie un.
1 este mapat la a.
Și 3 este mapat
este mapat la c.
Și deci câteva
imagini inverse --
dacă mă uit la
imaginea inversă a lui a,
aceasta este egală cu setul
tuturor tipilor care se mapează la a.
Aceasta este, ei bine, 1 hărți
la a și 2 hărți la a.
Deci, acesta este 1, 2.
Acum, dacă mă uit la
imaginea inversă a lui a,
c, d, ce elemente sunt
mapate la a, c și d?  Ei
bine, 1 și 2 sunt mapate la a.
3 devine harta la c.
4 este mapat la d.
Deci totul se mapează
în a, C și d.
Deci acesta este doar
setul original sau setul A--
1, 2, 3, 4.
Bine, deci există
mai multă terminologie.
Și aceasta este ceea ce vom
înțelege prin momentul în care
două seturi pot fi împerecheate.
Sau asta face ca asta să fie mai precis.
Fie f o funcție de la A la
B. Spunem că f este injectivă,
sau voi scrie unu-la-unu.  Ar
trebui citit
unu-la-unu dacă f satisface
următoarea proprietate.
f din x1 este egal cu f din x2
implică x1 este egal cu x2.
Deci injectiv, sau
unu-la-unu, înseamnă că
dacă iau două intrări diferite,
obțin două ieșiri diferite.  În
esență,
asta înseamnă.
Adică, luând echivalentul -
deci echivalent, din
punct de vedere logic,
această afirmație care
implică această afirmație
este echivalentă cu
negația acestei afirmații care
implică negația
acestei afirmații.
Deci, în mod echivalent, aceasta înseamnă că x
nu este egal cu x2 implică f din x1
nu este egal cu f din x2.
Deci poate că acest lucru este clar.
Dacă ar fi să definesc f ca
injectiv dacă satisface
această proprietate, poate
că ar fi
fost mai clar că f ia
două elemente diferite la două
elemente diferite.
Dar această condiție aici este
de obicei mai ușor de verificat,
sau cel puțin mai simplu
de afirmat și verificat.
Deci f este surjectiv sau
pe dacă imaginea lui A
este B. Așa că permiteți-mi să scriu acea
afirmație puțin
mai mult.
Totul din mulțimea B este
mapat de ceva din A.
Deci, în mod echivalent, aceasta
spune că pentru tot y din B
există un x în A,
astfel încât f din x este egal cu y.
f este bijectiv dacă f este
unu-la-unu și pe.
Deci f este bijectiv dacă este
atât injectiv cât și surjectiv.
Deci, de exemplu, această hartă pe
care tocmai am desenat-o aici și
care trimite 1 la a, 2 la b--
Adică 2 la a, 3
la c, 4, la d, aceasta
nu este nici injectivă,
nici surjectivă.
Nu este injectiv deoarece ia
două elemente diferite
la imaginea din B și anume a.
Deci este nevoie de 1 și 2 la a.
Nu este surjectiv
pentru că nimic nu este
mapat la elementul b aici.
Deci am văzut că
nu este surjectiv.
Desigur, această hartă, dacă iau... din
nou, imaginați-vă că acesta
este 1, 2, 3 a, b, c, d.
Această hartă de aici, această funcție de
aici care ia 1 la a, 2
la b, 3, la c, aceasta este de fapt
injectivă, dar nu surjectivă.
Și apoi, desigur, am
putea schimba ușor acest lucru.
Și 1 merge la a, 2 merge
la b și 3 merge la b.
Atunci acesta este surjectiv,
dar nu injectiv.
Acum, harta care trimite-- să
schimbăm laturile aici--
a, b și c, 1, 2, 3--
a la 1, b la 2, c la 3, aceasta
este o bijecție, bijectivă.
Deci, dacă spun că ceva este
o injecție sau surjecție
sau bijecție, înseamnă doar că
este o hartă care este injectivă
sau, respectiv, surjectivă sau
bijectivă.
Și acum, o definiție--
deci aceasta este într-adevăr--
nu este mare lucru
în această definiție,
ci doar definirea a câteva
funcții înrudite
care sunt legate de
o funcție dată.
Dacă f trece de la A la
B, g trece de la B la C,
compoziția g a lui f este
funcția care merge de la A la C
este definită de g din f din
x egal cu g din f din x.
Și 2, dacă f este bijectiv -
deci aceasta este compoziția
a două funcții.
Nu am scris cuvântul
compoziție, dar g din f
înseamnă compoziție sau se face
referire la compoziție.
Dacă f este bijectivă, atunci
definim funcția inversă
la f, B la A, prin următoarele.
Dacă y este în B, atunci
f inversul lui y în A
este elementele unice din A, astfel
încât, dacă iau acest element,
îl bag în f, primesc înapoi y.
Deci inversul unei
funcții există doar
pentru
funcțiile bijective sau cel puțin
este definit doar pentru
funcțiile bijective.  Tine
cont de asta.
Nu confundați asta cu
imaginea inversă a seturilor.
Deși, acele două
notații arată la fel.
Aveți o
f inversă la minus 1.
f la minus 1,
dacă este o funcție,
aceasta este funcția inversă.  Cu
toate acestea, dacă duc f
la minus 1 al unui set,
asta înseamnă imaginea inversă a
acelui set așa cum este definită acolo.
Deci, bijecțiile, adică
funcțiile bijective,
vor fi ceea ce ne referim când
spunem că două seturi pot fi împerecheate.  La asta ne
referim când noi...
sau cel puțin ce a fost răspunsul lui Cantor la
întrebarea inițială
, când două seturi
aveau aceeași dimensiune.
Deci aceasta este noțiunea de
cardinalitate la care am făcut aluzie.
Așa că spunem că două
mulțimi, A și B, au
aceeași cardinalitate
dacă există
o bijecție sau o
funcție bijectivă f de la A la B. Așa că
permiteți-mi doar să fac o
notație aici.  deci nu sunt
obiecte noi pe care le
definesc sau operațiuni.
Aceasta este doar o notație.
Deci, atunci când două mulțimi au
aceeași cardinalitate, scriem--
deci aceasta este doar o scurtă modalitate
de a scrie că două funcții
au aceeași cardinalitate.
Nu ar trebui să
credeți că acest lucru înseamnă să luați
valoarea absolută a unui set.
Asta nu înseamnă
nimic, bine?
Aceasta este doar o
notație scurtă pentru a spune că două
seturi au aceeași cardinalitate.
Dacă A are aceeași cardinalitate
ca mulțimea 1, 2, 3 până la n,
scriem A este egal cu n.
Aceasta este doar prescurtarea
pentru a spune că o mulțime are
aceeași cardinalitate ca
numerele naturale până la n.
Deci, dacă există o
funcție injectivă - sau voi
spune adesea fie
funcție, fie hartă.  Ar
trebui să
le iei ca sinonime.
Există o
funcție injectivă f--
dacă există o
funcție injectivă f de la A la B,
scriem acest lucru.
Din nou, nu citiți acest lucru ca
luând valoarea absolută
a unui set și
acea valoare absolută
este mai mică sau egală cu
valoarea absolută a celuilalt set,
deoarece nu are sens.  Nici măcar
nu am spus ce
înseamnă asta.
Aceasta este doar notație scurtă.
Și dacă există o
injecție de la A la B
dar nu au aceeași
cardinalitate, scriem asta.
Deci, chiar dacă această notație
a acestor lucruri cu valoare absolută
aflate în
exteriorul mulțimii te
face să te gândești la
valoare absolută sau ar trebui interpretată
ca valoare absolută,
este în regulă să te gândești
ca o anumită
ordonare fiind acolo,
ca A având o dimensiune mai mică decât B.
Noi  scrie asta pentru că
existența unei injecții de la un
set la altul înseamnă că
pot asocia elementele lui A
cu unele elemente
ale lui B. Poate că nu
primesc toate elementele lui
B. Dar pot asocia
unele dintre elementele lui  A cu
unele dintre elementele lui B.
De exemplu, prima
hartă pe care am scris-o acolo,
care spune că
mărimea mulțimii 1, 2, 3
este mai mică sau egală
cu dimensiunea lui a, b, c,
d pentru că  a găsit o
injecție, o hartă injectivă
de la primul set
la al doilea set.
Această a treia hartă ar spune că
dimensiunea mulțimii a, b, c este
egală cu 3, scrisă aici,
sau scurtă scrisă aici.
Și, de fapt, prima hartă pe care
am scris-o acolo, din nou, este--
deci din prima hartă, aceasta spune
că mulțimea de 1, 2, 3--
în notația noastră scurtă
, valoarea absolută
este mai mică decât
dimensiunea unui  , b, c, d.
Deci, nu vă gândiți la acestea ca
spunând valoarea absolută.  Cel
mai bine este să vă gândiți la
asta ca spunând dimensiunea de.  În regulă
, deci dacă există
o hartă sau o funcție injectivă
de la un set la altul,
atunci dimensiunea lui A
este mai mică sau egală cu
dimensiunea lui B. Dacă dimensiunea lui A
este mai mică sau egală
cu dimensiunea lui B,
dar  dimensiunea lui A și
B nu sunt aceleași,
scriem că dimensiunea lui A este
mai mică decât dimensiunea lui B.
Așa că cel mai bine să ne gândim la acestea--
acest
lucru care arată valoarea absolută
ca fiind prescurtare pentru
rostirea cuvintelor dimensiunea.
Acum, nu am de gând
să dovedesc asta.
Depășește puțin
sfera acestei clase.
Dar permiteți-mi doar să spun că această
ordonare, această inegalitate,
aceste simboluri pe care le
scriem
au un fel de asemănare cu
ordonarea numerelor reale,
prin aceea că, dacă am două
numere reale, unul este mai mic
sau egal cu
celălalt și  viceversa.
Deci A este mai mic sau egal
cu B și B este mai mic
sau egal cu A, atunci
A trebuie să fie egal cu B.
Acest lucru este, de fapt, adevărat și
pentru această noțiune elementară
de dimensiune a mulțimilor.
Și aceasta este...
Adică, nu ar trebui să
te surprindă neapărat pentru seturi finite
.
Dacă am o pereche de A, dacă
A nu este mai mare decât n și n
nu este mai mare decât dimensiunea lui A,
atunci a ar trebui să aibă n elemente.
Dar este nevoie de puțin
mai mult pentru a demonstra
pentru mulțimi care nu sunt finite.
Așa că am uitat să notez asta.  De
asemenea, spunem că
dacă dimensiunea lui A
este egală cu mărimea
acestei mulțimi finite de la 1 la n,
spunem că A este finit.
Deci, această teoremă pe care o
afirm aici
este teorema lui Cantor Schroeder
Bernstein,
care afirmă că
dacă dimensiunea lui A
este mai mică sau egală cu
dimensiunea lui B și dimensiunea lui B
este mai mică sau egală cu
dimensiunea lui A,  atunci dimensiunea lui A
este egală cu dimensiunea lui B. Deci, din nou,
dacă vă gândiți la acestea
în contextul
numerelor reale, unul fiind mai mic
sau egal cu
celălalt și invers,
desigur, asta implică faptul că
acele două numere reale.  numerele sunt
egale între ele.
Dar nu vorbim
despre numere reale.
Din nou, aceasta este doar o
notație scurtă
pentru a spune că există o
hartă bijectivă de la A la B. Aceasta
înseamnă că există o
hartă bijectivă de la A la mulțime.
Aceasta înseamnă că există o
hartă injectivă de la A în aceasta,
de la a la acest set.
Deci aceasta nu este o afirmație
despre numere reale.
Aceasta este o afirmație despre
cardinalitate, bine?
BINE.
Deci seturile finite sunt seturi pe care le
poți număra dacă ai avea n degete.
Acum, ne-am dori să putem
defini ce înseamnă
să poți număra un set.
Deci, ce vreau să spun
prin numărarea unui set?
Adică, dacă aș avea
timp infinit, aș
putea trece prin
setul numărându-i--
1, 2, 3, 4, 5, 6, 7,
8, 9, 10 și așa mai departe.
Nu mai trebuie să merg.
Dar ce
înseamnă acest proces de numărare?
Asta înseamnă că pentru fiecare
element al mulțimii pe care
încerc să îl
număr, îl pot asocia
cu un număr natural -
1, 2, 3 și așa mai departe.
Deci, așa
definim seturile numărabile.
Deci, dacă A are aceeași dimensiune
ca numerele naturale,
adică există o bijecție
de la A la numerele naturale,
atunci spunem că A este
infinit numărabil.
Dacă A este finit, sau numărabil --
folosesc și o mulțime de stenografie,
dar nu este stenografie inteligentă.
Așa că ar trebui să fii
capabil să suni ce--
dacă doar suni asta,
vei înțelege ce cuvânt vreau să spun,
numărabil, numărabil infinit.
Spunem că A este numărabil.
Deci numărabil infinit înseamnă că am
nevoie de toate numerele naturale
pentru a putea număra
elementele mulțimii A.
Numărabil înseamnă că poate
mă opresc după un moment
și le-am numărat pe toate.
Deci A este finit sau este
numărabil infinit.
În caz contrar, dacă un set
nu este numărabil,
spunem că este nenumărabil.
OK, deci haideți să aruncăm o privire la
câteva seturi numărabile
care poate nu se dovedesc a
fi numărabile.
Setul de... de fapt,
asta e o problemă de teme.
Mulțimea
numerelor întregi pare este numărabilă.
Setul de impar... așa că am spus
numere întregi acum un minut.
Poate ar trebui să
spun doar numere naturale.
Mulțimea numerelor naturale impare
este numărabilă.
Deci, de fapt... deci aceasta
este doar o deoparte.
Deci acestea sunt două
submulțimi disjunse
care alcătuiesc
numerele naturale,
numerele naturale pare și impare.
Și ambele au aceeași dimensiune
ca și setul pe care îl alcătuiesc.
Deci este aproape ca și cum ai
spune că cardinalitatea
numerelor naturale
este de două ori mai mare decât cardinalitatea
numerelor naturale,
deoarece ai crede
că dimensiunea lui N ar trebui
să fie dimensiunea acestei mulțimi
plus dimensiunea acestei mulțimi,
deoarece sunt disjunctive
și fac  sus decorul.
Dar nu așa
funcționează cardinalitatea.
Nu adăugați doar cardinalități
pentru a obține cardinalitățile.
Așadar, acesta este un lucru subtil și interesant
despre cardinalități.
Așa că Richard Feynman,
care a câștigat Premiul Nobel
în anii '60 pentru munca sa
despre QED, a descris acest lucru
ca spunând că există de două ori mai
multe numere decât numere.
OK, deci haideți să dovedim asta.
Deci, ce înseamnă asta?
Aceasta înseamnă că trebuie să putem
găsi o funcție bijectivă
de la acest set la acest set sau
de la acest set la acest set, una
sau alta.
Și de fapt, poate că ar trebui... Ei
bine, voi spune ceva
despre asta într-un minut.  Ei
bine, lasă-mă să fac o pauză.
Lasă-mă să fac o pauză
pentru un minut.
Și permiteți-mi să fac câteva
comentarii despre cardinalitate,
pe care poate ar trebui să le fac.
Deci, la asta te poți gândi
ca la o mică teoremă.
Dacă am două seturi, A
are aceeași dimensiune ca B,
atunci B are aceeași dimensiune
ca A. Așa că ține minte, vreau să spun,
ceea ce tocmai am spus în
engleză nu este exact
ceea ce înseamnă acele simboluri.
Amintiți-vă, asta înseamnă că
există o bijecție de la A la B.
Aceasta înseamnă că există
o bijecție de la B la A.
Deci, care este dovada
acestei afirmații?
Deci, să începem
cu ipoteza.  Să presupunem că
atunci
există o hartă bijectivă,
funcția bijectivă
f de la A la B.
Acum, dacă am o bijecție
de la A la B, atunci
care ar fi o bijecție care
merge de la B la A?
Asta ar fi doar invers.
Deci aceasta nu este
imaginea inversă a mulțimilor,
așa cum am descris-o, ci
inversa reală,
pe care am definit-o acolo.
Este o bijectie.
Deci B are aceeași dimensiune ca A. O
altă afirmație - deci dacă A
și B au aceeași dimensiune și B
și C au aceeași dimensiune -
deci din nou, A, B și C sunt mulțimi.  Ar fi trebuit să
scriu
asta la început.
Dar din acest context,
ar trebui să înțelegeți
că A, B și C sunt mulțimi -
atunci A și C au aceeași dimensiune.
Deci haideți să facem o dovadă în acest sens.
Deci, să începem cu
ipoteza,
adică A are aceeași dimensiune ca
B și B are aceeași dimensiune ca C.
Deci, ce au
însemnat aceste două afirmații
în ceea ce privește definiția?
Asta înseamnă că există
o bijecție de la A la B
și o bijecție de la B la
C. Și această afirmație - așa că
permiteți-mi să termin asta.
Și apoi voi spune ce
voiam să spun.
Apoi există bijecții f
de la A la B și g de la B la C.
Așa că ar fi trebuit să
mai spun câteva cuvinte
despre de ce este adevărat.
Dar voi lăsa
asta ca un exercițiu
doar pentru a întrerupe prelegerea
și a o face singur.
Și ceea ce voi scrie în scurt timp --
pentru acest caz, de
fapt voi dovedi
că lucrul pe care îl voi
defini este bijecția.
Asta ar trebui să te ajute.
Așa că lasă-mă să trag
aici, în lateral.
Avem, din nou,
1, 2, 3, a, b, c.
Deci, gândiți-vă la asta ca f.
Acesta este setul meu A.
Acesta este setul meu B.
Și apoi am
alfa, beta, gamma.
Și a este mapat la alfa,
b, este mapat la beta,
c este mapat la gamma.
Deci, care ar fi harta care merge
de la A în jos la mulțimea C?  Ei
bine, poate compoziția.
1 este mapat la a, care
este mapat la alfa.
Deci 1 este mapat la alfa.
2 este mapat la beta.
3 este mapat la gamma.
Cum construiesc această funcție
din lucrurile pe care le cunosc, și
anume acest f și g?  Ei
bine, această funcție care
merge de la A la C
este doar compoziția
acestor două funcții.
Așa că asta e pe o parte.
Aceasta nu face parte din dovadă.
Fie h de la A la C
funcția g a lui f a lui x.
Așa că susțin că această
funcție este o bijecție.
Deci vrem să demonstrăm că este
unul-la-unu și mai departe, bine?
Deci, să facem mai întâi unu-la-unu.
Deci, aceasta este
partea în care voi
pune asta între paranteze,
adică ceea ce facem acum.
Deci vom demonstra
că h este unul la unu.
Deci asta înseamnă că trebuie să
verificăm definiția pe care am
șters-o.
Deci, amintiți-vă definiția.
Deci hai să scriem totul.  Mai
întâi arătăm că h este unu-la-unu.
Și ce înseamnă asta,
conform definiției pe care o
scriu acum, dacă h de x1 este egal cu
h de x2, atunci x1 este egal cu x2.
Deci asta este ceea ce
vrem să dovedim.
Aceasta este definiția
lui h fiind unu-la-unu.
Asadar, hai sa incepem.
Dacă h din x1 este egal cu h
din x2, atunci, în ceea ce privește
modul în care am definit
h, care este g
din f din x, deci compoziția,
atunci aceasta înseamnă că g din f din x1 este
egal cu g din f din x2.
Tocmai asta este h.
Acum, această afirmație aici...
acum știm că este o bijecție.
Știm că g este unul la unu.
Și deoarece g de ceva este egal cu
g de altceva și g
este unu-la-unu, acest lucru implică faptul
că f din x1 este egal cu f din x2.
Aceasta deoarece g este unu-la-unu.
Deci, începând cu aceasta
și definiția lui h
fiind compoziția,
concluzionăm că f din x1
trebuie să fie egală cu f din x2
deoarece g este unu-la-unu.
Acum, deoarece f este,
de asemenea, unu-la-unu -
presupunem că f
și g sunt bijecții.
Deoarece f este unu-la-unu,
aceasta implică că x1 este egal cu x2,
deoarece f este unu-la-unu.
Și asta am
vrut să dovedim.  Am
vrut să începem prin a
presupune că h de x1 este egal cu h de x2
și să demonstrăm că x1 este egal cu x2,
ceea ce am făcut.
Astfel, am demonstrat
că h este unul la unu.
Acum, trebuie să arătăm că este
surjectiv, că este pe.
h din A este egal cu C. Și din nou,
voi scrie ce înseamnă asta.
Aceasta înseamnă că pentru tot y în C--
bine, să-i
spun [?  z-- ?]
există un x în A
astfel încât h din x este egal cu z.
Acum, am folosit
faptul că f și g
au fost injective pentru a concluziona că
compoziția este injectivă.
Deci, este de la sine
înțeles că vom
folosi faptul că
ambele sunt surjective
pentru a demonstra că h este surjectiv.
Deci trebuie să demonstrăm
că pentru tot z din C
există un x în A
astfel încât h din x este egal cu z.
Deci, să fie z în C. Acum,
trebuie să găsim un
x în A care este mapat la z.
Vom folosi că g și
f sunt ambele surjective.
Și care este imaginea
care merge împreună cu asta?
Iată seturile C, B și
A. Avem un element al lui z
Și știm că,
deoarece g este surjectiv,
există un element în B
care este mapat la z de către G.
Dar acum, deoarece f care merge
de la A la B este surjectiv  ,
există un
x care se mapează la y.
Și atunci acesta este
tot argumentul.
Asta este.
Am desenat această poză.
Dar acum, trebuie doar
să-l transform în engleză
folosind proprietățile și
ipotezele pe care le am.
Deoarece g este surjectiv,
există un y în B astfel încât g din y este
egal cu z.
Deoarece f este surjectivă,
există un x în A, astfel încât f din x este
egal cu y.
Dar atunci, dacă mă uit
la h din x, acesta
este egal cu g din f din x,
care este egal cu g din y,
care este egal cu z prin
modul în care am definit y.
Amintiți-vă, g din y este egal cu z, cum
am găsit y și cum am găsit x.
Amintiți-vă, f din x este egal cu acest y.
Și, prin urmare,
această hartă h este pe.
Și prin urmare, h este o
bijecție, demonstrând această teoremă.
Deci asta ar trebui să te ajute.
Vă voi da multe
exerciții pentru a demonstra
că inversul unei
bijecții este o bijecție.
Așa că revenim la ceea ce
făceam pentru început.
Vrem să arătăm că mulțimea
numerelor naturale pare are
aceeași dimensiune ca și
numerele naturale,
are aceeași cardinalitate, ca și
numerele naturale și la fel
pentru cele impare.
Așa că o să le
fac doar pe cele ciudate.
Din nou, acesta va fi un
mic exercițiu de făcut pentru a
demonstra numărul 2,
afirmația pentru cele impare.
Așa că o să le
fac pe cele pare.
Și le poți face pe cele ciudate.
Dacă intenționați să
studiați mai mult matematica, ar trebui să vă
obișnuiți ca instructorul,
profesorul, scriitorul de lucrări de cercetare
, autorul de manuale să
ofere mici exerciții
pentru a vă asigura că
urmați
și că puteți face o
sarcină minoră la un moment dat
în timpul  discutia.
Deci vom găsi...
așa că vrem să arătăm că
numerele naturale au
aceeași dimensiune ca
numerele naturale pare, care
este aceeași cu această afirmație a
primei teoreme pe care am scris-o
acolo.
Acum, asta înseamnă că trebuie
să găsim o bijecție
de la numerele naturale la
mulțimea numerelor naturale pare.
Acest lucru nu ar trebui să fie prea rău.
Adică, din nou, acest lucru
este pe o parte.
Aceasta nu face parte din dovadă.
Care ar fi harta care merge
de la acești tipi la acești tipi?
Ei bine, vreau să spun, sunt
mai multe pe care le-ai putea alege.
Dar poate cel mai simplu
este că 1 este mapat la 2,
2 este mapat la 4, 3 este
mapat la 6,
4 este mapat la 8, 5 la 10,
6 la 12 și așa mai departe.
Acum, ce este harta?
Și acum, voi
continua dovada.  Fie
f funcția în
numerele naturale pare definite
de f din n este egal de 2 ori n.
Și deci n este un număr natural.
Deci, aceasta este doar scrierea formală a
funcției care ia de la 1 la 2,
2 la 4, 3 la 6, 4, la
8 și așa mai departe, și așa mai departe.
Eu susțin că f este o bijecție.
Deci trebuie să arăt că f
este unu-la-unu și pe.
Așa că mai întâi vom arăta
f este unu-la-unu.
Deci asta înseamnă că trebuie să
presupun că f din n1 este egal cu f din n2
și să concluzionez că n1 este egal cu n2.
Așa că permiteți-mi să scriu de fapt
ce înseamnă asta din nou pentru a
spune că f este unu-la-unu.
Este unu la unu-- adică
dacă f din n1 este egal cu f din
n2, atunci n1 este egal cu n2.
Dar acest lucru este ușor de
verificat pentru această funcție pe
care am notat-o, deoarece
dacă f din n1 este egal cu f din n2 - deci
reține, asta este ceea ce
vrem să arătăm, bine?
Așa că, pentru a arăta, încep
cu presupunerea mea.
Și trebuie să
concluzionez că n1 este egal cu n2.
Deci, să presupunem că f din
n1 este egal cu f din n2,
presupunerea mea, ipoteza mea.
Și trebuie să
concluzionez că n1 este egal cu n2.
Atunci acest lucru implică, prin
definiția lui f, de
2 ori n2 egal cu
2 ori n2, care,
prin algebra eliminării
celor 2, n1 este egal cu n2, care
este concluzia pe care o vreau.
Deci am demonstrat afirmația
că dacă f din n1 este egal cu f din n2,
atunci n1 este egal cu n2.
Prin urmare, f este unu-la-unu.
Deci, f este unu-la-unu.
Deci acum, vrem să arătăm că
f este pe, surjectiv.
Voi scrie asta din nou.  adică
pentru toate elementele care
n sunt un număr par,
există un n astfel
încât f din n este egal cu m.
Acum, să fie m un număr întreg par.
Și ca să nu ne încurc,
lasă-mă să scriu de 2 ori k.
Acesta este același set.
Folosesc doar o
variabilă dummy diferită în loc de n
în descrierea
numerelor naturale pare.
Și hai să facem asta și aici.
Din nou, acest lucru nu
schimbă nimic.
Aceasta înseamnă doar schimbarea
litera pe care o
folosesc pentru a descrie setul,
ceea ce este lipsit de importanță.
Dar nu vreau să ai
impresia falsă că, cumva,
nu fac nimic.
OK, deci să presupunem că am un
număr întreg par, atunci există --
pur și simplu prin
definiția acestei mulțimi,
există un număr natural n,
astfel încât m este egal de 2 ori n.
Atunci f din acest număr natural,
care este de 2 ori n, este egal cu m.
Și prin urmare, obțin
ceva care se mapează la m.
Prin urmare, f este pe.
Prin urmare, f este o
bijecție și cele două mulțimi
au aceeași cardinalitate.
Bine, deci hai...
unde suntem?
Unde sa scriu?
Să scriem aici.
Poate voi lăsa asta
pentru că nu vreau să--
acum, folosind asta-- și
probabil că voi pune asta
în teme--
Adică, se poate arăta și-- Ar
trebui să spun că folosesc
asta, dar  se poate
arăta, de asemenea, că numerele întregi
au aceeași dimensiune
ca și numerele naturale,
ceea ce, din nou, este puțin
surprinzător, deoarece
numerele naturale sunt
un subset strict al lui Z.
Care este, deci, dovada?
Așa că o să
fac o imagine, apoi o să

notez funcția
și apoi o voi
lăsa ca...
de fapt,
o voi pune în teme pentru ca tu să
verifici asta  această funcție
este unu-la-unu și pe.
Deci, să presupunem că există
atâtea numere naturale
câte vreau să scriu și câte
numere întregi vreau să scriu.
OK, deci care ar
fi o modalitate de a mapa
numerele întregi într-un mod
unu-la-unu și
pe numerele naturale?  Ei
bine, ce am putea face... în
primul rând, să trimitem 0 la 1
doar pentru a scoate 0 din drum.
Și de atunci încolo,
acum trebuie doar
să găsim o modalitate de a mapa
numerele întregi pozitive
și negative pe
numerele naturale mai mari
decât 2.
Și într-un fel,
mental, ar trebui să
simțim că putem face asta pentru că
am cam făcut-o.  acolo,
dar nu în mod explicit.
Deci ce zici să luăm 1
la 2, 2 la 4, 3 la 6?
4 ar merge apoi la 8.
Și vom lua de la 1
la 3, minus 2 la 5.
Sunt încrucișat.
Și apoi minus 3
va fi trimis la 7.
Așa că vedeți că
numerele întregi pozitive
sunt mapate la
numerele naturale pare,
iar numerele întregi negative
sunt mapate la
numerele naturale impare mai mari decât 1.
Deci nici măcar nu voi
scrie dovada  .
Aceasta va face parte
din teme.
Acum, este puțin surprinzător
că există de două ori mai
multe numere decât
numere, nu prea
surprinzător din moment ce aceste
subseturi, dacă le imaginezi
așa cum am făcut eu ca
subseturi ale liniei reale,
știi că sunt
cam discrete.
Deci ar trebui să
le poți număra.
Ceea ce nu este -- ce este
mai surprinzător --
este dacă pot sau nu număra
submulțimi care, într-un anumit sens,
nu sunt discrete.
De exemplu, cum rămâne cu
numerele raționale?
Deci aceasta este o teoremă care--
și permiteți-mi să mă uit doar la acele
numere raționale pozitive.
De fapt, aș putea lua
toate numerele raționale.
Dar pentru enunțul
acestei teoreme,
dacă mă uit la acele
numere raționale care sunt pozitive,
atunci aceasta are aceeași dimensiune
ca și numerele naturale.
Puteți număra
numerele raționale pozitive, ceea ce este puțin
nebunesc pentru mine, deoarece
aici, cel puțin pentru a spune
numerele întregi, odată ce sunt
la un număr întreg,
pot trece la următorul cel mai mare
și îl pot număra într-un fel.  ,
dreapta?
Și astfel încât să fie credibil
că pot număra numerele întregi.  Numerele
întregi au aceeași
dimensiune ca și numerele naturale,
chiar dacă,
la prima vedere,
se pare că sunt de
două ori mai multe.
Dar pentru
numerele raționale, între oricare două
numere raționale, există un
alt număr rațional
între ele.
Luați doar media
acelor două numere raționale.
Așa că acum, această idee de
a fi la un număr rațional
și apoi de a trece la următorul
număr mare, nu poți face asta acum.
Deci, acum, este puțin în
aer cel puțin dacă pot sau nu
număra numerele raționale.
Și ceea ce spun este
că într-adevăr poți.
Iar asta va face
parte din teme.  Vă
voi da cel puțin o
idee despre cum va
decurge dovada, ce vom
putea nota de fapt,
o hartă bazată pe un simplu fapt.
Deci, permiteți-mi să nu notez dovada,
ci lăsați-mă să notez o remarcă.
Așa că vom putea de fapt să
scriem o hartă bazată
pe un fapt simplu, care
este această teoremă fundamentală
a aritmeticii, care spune că--
deci aceasta este doar o discuție acum.
Mai multe lucruri vor fi scrise
în temei despre asta.
Așa că încearcă doar să urmezi.
Deci,
teorema fundamentală a aritmeticii
spune că dacă aveți un
număr natural pozitiv,
îl puteți scrie într-un mod unic
ca produs al numerelor prime.
Acum, pentru
numerele raționale, folosind asta,
înseamnă că puteți scrie
fiecare număr rațional în mod unic
ca un produs al
numerelor prime împărțit la un
alt produs
al numerelor prime,
unde nu există două numere prime -
unde numerele prime
sus și numerele prime la
jos,
niciunul nu este în comun,
adică ați simplificat
cât mai mult posibil.
Deci, în loc de 15 peste 3...
nu, asta nu e bine.  Să
spunem 15 peste 30.
Ai 1/2.
Deci, harta pe care aș lua--
deci ceea ce spun aici este
că fiecare număr rațional
poate fi scris ca un produs.
Deci, permiteți-mi să nu folosesc acea
notație, ci un produs p
r1 pN rN q1 s1 qn sM unde
p1, p2 și pN, acestea sunt toate
prime.
q1 până la qN, toate sunt numere prime.
r1, rN, aceștia sunt toți exponenți,
numere naturale pozitive.
Deci rj, sk, acestea
sunt numere naturale.
p1 pN q1 la qM sunt numere prime.
Și pentru toate jk, qj
nu este egal cu pk.
Deci nu există niciun prim care să apară
atât aici, cât și aici.
Am
simplificat deja asta.
Deci, ca să nu
crezi că te păcălesc,
9/2, care este un
număr rațional pozitiv,
acesta este 3 la pătrat peste 2, da?
Nu am de gând să mai fac.
Asta este.
Deci harta pe care o vom lua
de la acest număr rațional
la un număr natural
va fi aceasta este
mapată la numărul natural
p1 la r1, pN la rN ori acum q1
la 2s 1 minus 1 qM 2Sn minus 1.
Deci, practic, o mapez
la numărul întreg care
are această expansiune în termeni
de numere prime, unde acum
exponenții
acestor numere prime
sunt pari în funcție de
acești exponenți de sus
și exponenții
acestuia sunt impari, în
funcție de acest
exponent de sus.
Deci, de exemplu, 3 pătrat peste
2, acest lucru ar fi mapat la 3
la 4 ori 2.
Deci ceea ce vom face la
teme este să arătăm
că această hartă este, de
fapt, o bijecție.
Deci acele două teoreme pe care le
vei demonstra la teme.
Nu vor fi prea rele.
Voi lăsa destule indicii.
Deci ne-am ocupat de z.  Ne-am
ocupat de q, în esență.
Vreau să spun, deci permiteți-mi să
scriu de fapt...
acesta este într-adevăr un corolar
al acestor două teoreme
de aici, pe care nu le-am
demonstrat, dar
veți demonstra în temei.
Deci asta spune că
rațiunile sunt numărabile,
toate rațiunile, nu
doar cele pozitive.
Și care este dovada?  Deci
știm că...
așa că o să-ți
fac o schiță.  Ar
trebui să o schițez sau să
scriu totul?
Am un
pic de timp.
Așa că poate vă voi spune doar
de ce este adevărat.
Adică, toate detaliile
sunt în esență aici.
Doar că nu o voi scrie
cu atâta atenție cum am
notat dovezile înainte.
Așa că permiteți-mi să scriu asta
ca schiță de probă.
Desigur, puteți scrie acestea--
puteți folosi
definițiile și scrieți asta.
Dar aceasta este ideea esențială.
Deci avem aceeași dimensiune
a numerelor raționale -
așa că permiteți-mi - aceasta are aceeași
dimensiune ca și numerele raționale
care sunt negative.
Și cum stabilim asta?
Sau în loc să folosim
aceeași literă,
să spunem r, deoarece f
din Q este egal cu minus Q
este o bijecție de la
primul set la al doilea.
Dacă iau doar un
număr rațional, pozitiv 1,
iau minusul lui, atunci obțin
un element din al doilea set.
Și aceasta este o bijecție.
OK, deci, din moment ce
acesta are aceeași dimensiune
ca numerele naturale
și prin acea teoremă pe care am
demonstrat-o acolo,
dimensiunea acestei mulțimi
este aceeași cu
numerele naturale --
deci este numărabilă --
atunci există
bijecții f  mergând de la Q--
deci
numerele raționale pozitive--
la numerele naturale și g
mergând de la cele negative
la numerele naturale.
Deci imaginea de aici este... ei
bine, să nu desenăm
încă imaginea.
OK, deci am aceste
două bijecții
de la
rațiunile pozitive la numerele întregi --
aceasta de la
rațiunile negative
la numerele naturale.
Cum obțin o hartă
care merge de la toate q
acum la numerele naturale?  Ei
bine, să mergem între ele
și să trecem la numerele întregi.
Apoi definesc o funcție h,
care merge acum de la toate Q
la numerele întregi prin h de
x este egal cu 0 dacă x este egal cu 0;
este egal cu f din x dacă x este
pozitiv;  și g negativ
al lui x dacă x este negativ.
Și h este o bijecție.
Deci, până
în acest moment, totul a
fost complet în regulă,
cu excepția faptului că am
verificat că
această hartă este o bijecție
și această hartă este o bijecție.
Așa că acestea sunt singurele
părți pe care le
las pentru a le verifica.
Atunci h este o bijecție.
Deci Q are aceeași cardinalitate
ca și numerele întregi, despre care am arătat că
are aceeași cardinalitate
ca și numerele naturale.
Și, prin urmare, raționalele
au aceeași cardinalitate
ca și numerele naturale.
Deci sunt infinit infinit.
Deci o întrebare firească este...
Adică, există ceva
mai mare decât numerele naturale?
Pentru că tot ce am
scris,
acesta are dimensiunea
numerelor naturale.
Nu am definit cu adevărat
numerele reale încă suficient de bine
pentru a face vreo afirmație de genul
acesta despre numerele reale.
Și acum, există
vreun set care
este mai mare ca dimensiuni decât
numerele naturale?
Răspunsul la asta era necunoscut.
Și este destul de
surprinzător că da, de fapt.
Așa că lasă-mă să formulez această întrebare.
Există o mulțime A
astfel încât A să aibă o
cardinalitate strict mai mare decât
numerele naturale, deci A
este nenumărabil?
Așa că, pentru a răspunde uimitor la această întrebare,
permiteți-mi să definesc mai întâi
pentru un obiect general.
Dacă A este o mulțime,
definim scriptul p al lui A.
Acesta este mulțimea de puteri a lui A.
Aceasta este o mulțime care constă
din toate submulțimile lui A. Deci aceasta este
o mulțime de toate mulțimile B astfel încât B
este o submulțime a lui A.  Deci, de
exemplu, dacă A este setul gol,
setul de putere -
deci A este gol.
Care sunt submulțimile mulțimii
goale?  Ei
bine, există un singur subset
al setului gol, setul gol.
Și chiar dacă
setul gol nu are membri,
setul său de putere are un membru.
Dacă A este egal cu 1,
atunci mulțimea de puteri
a lui A, mulțimea tuturor submulțimii,
constă din mulțimea goală
și mulțimea în sine, 1.
Și să mai facem una.
Dacă A este mulțimea 1, 2,
atunci mulțimea de putere a lui A,
aceasta este mulțimea care
constă din mulțimea goală,
deoarece aceasta este o
submulțime a acestei mulțimi,
mulțimea constând din 1, deoarece
aceasta este o submulțime a acestei mulțimi  ,
sau 2, 1, 2.
Acum, observați ceva.
Acest set avea cardinalitate.
Strict vorbind, ar fi
trebuit să definesc asta
ca având cardinalitatea 0.
Cu toate acestea, setul său de putere
are cardinalitatea 1.
A are dimensiunea 1 deoarece este
în corespondență unu-la-unu
cu doar 1.
Și setul său de putere
are două elemente.
Deci are cardinalitatea 2. Le-aș
putea număra--
1, 2.
A are dimensiunea 2, are două elemente.
Și setul de puteri
a lui A are dimensiunea 4.
Are patru elemente diferite --
mulțimea goală, 1, 2, 1, 2.
Deci ceea ce se poate dovedi în
general și care va apărea
pe teme este
dacă A are dimensiunea n-  -
deci este o mulțime finită de mărimea
n, adică este în corespondență unu-la-unu
cu
numerele de la 1 până la n--
atunci setul său de putere
este, de asemenea, finit
și are cardinalitatea 2 la n.
Și puteți demonstra prin inducție,
dacă doriți, că 2 la n
este întotdeauna mai mare decât n.
Și deci o teoremă pe care o voi
demonstra data viitoare, care
va termina discuția noastră
despre mulțimi și cardinalitate,
și apoi vom trece
la numerele reale,
este această teoremă datorată
lui Cantor, care
spune că nu doar
pentru mulțimi finite
au setul de putere
fiind, într-un anumit sens, strict
mai mare decât
setul original, dar pentru orice set.
Deci această teoremă datorată lui
Cantor este dacă A este o mulțime,
atunci cardinalitatea lui
A este strict mai mică
decât cardinalitatea mulțimii
sale de puteri.
Deci asta
răspunde cu siguranță la întrebarea noastră.
Există o mulțime
cu cardinalitate mai mare
decât numerele naturale?
Așa că permiteți-mi să scriu
asta ca o remarcă.
De fapt, poate voi afirma
asta ca o altă teoremă, care
urmează imediat
din această
utilizare din nou și din nou,
este că cardinalitatea

numerelor naturale, aceasta este mai mică
decât cardinalitatea mulțimii de
puteri
a
numerelor naturale,  care este mai mică
decât cardinalitatea

setului de puteri a setului de puteri a
numerelor naturale, nu?
Acum pot să iau asta ca un
set și să-i iau setul de putere.
Și primesc un nou set
cu o dimensiune mai mare,
care este mai mică decât
setul de putere al setului de putere unde--
câte avem acum-- din
setul de putere al numerelor naturale
și așa mai departe.
Și formal, asta înseamnă că există
o infinitate de infinitudini.
Există un
număr infinit de dimensiuni infinite,
una care devine strict --
într-un anumit sens, strict
mai mare decât dimensiunea anterioară.
Și poate că vă întrebați... mai
este o
întrebare care este oarecum
cuprinsă între ele
aici, un joc de cuvinte, este... să ne
uităm la primul tip.
Există o mulțime A
astfel încât să aibă o dimensiune mai mare
decât numerele naturale -- deci
este de nenumărat -- dar să aibă o
dimensiune strict mai mică
decât
setul de putere al numerelor naturale.
Și această întrebare se numește
ipoteza continuumului,
ipoteză deoarece
este independentă de unul
dintre tratamentele axiomatice standard
ale teoriei mulțimilor.
Dar nu ne vom
atinge de această întrebare.
Acest lucru depășește
scopul acestei clase,
dar este o întrebare interesantă pe care

oamenii pur și
simplu nu o știu.