Zoran Skoda mat1-171120-1

Zapis lekcije 17.11.2020. od 10:30 do 12:00. Za dio lekcije od 13 sati vidi mat1-171120-2.

Gradivo koje smo radili do sad:

logika, skupovi, relacije (općenito, uređaja, ekvivalencije), funkcije.

kardinalni brojevi: razredi ekvivalencije skupova s obzirom na relaciju ekvipotentosti

poslije toga dolazi drugi dio gradiva Matematike 1, BROJEVI (prirodni, cijeli, racionalni, realni i kompleksni brojevi)

spojnica prvog i drugog dijela gradiva (danas): kardinalni brojevi

Razredi ekvivalencije

Za to moramo najprije bolje promisliti o relacijama ekvivalencije.

Neka je sad ~ ma koja relacija ekvivalencije na nekom skupu S.

Definiramo razrede ekvivalencije preko particije skupa S (podjele) na disjunktne neprazne podskupove koje zovemo razredi ekvivalencije.

$$a,b \in S,$$

a i b su u istom razredu onda i samo onda ako a~b

$$R_a = [a] = [a]_~ = \{ x\in S | x~a \}$$

Drugim riječima, za $x\in S$ vrijedi x~a onda i samo onda ako $x\in R_a$.

TVRDNJA: $b,c\in R_a$, tada je b~c

koristimo tranzitivnost: $b\in R_a$ to znači b~a, $c\in R_a$ to znači da je c~a. Po simetriji onda i a~c. Pa imamo b~a i a~c i po tranzitivnosti zaključujemo b~c.

TVRDNJA: $a\in R_a$ tj. a~a (refleksivnost)

TVRDNJA: $R_a$ presjek $R_b$ je ili prazan ili su $R_a$ i $R_b$ jednaki (jednaki točno onda kad je a~b)

Imamo dvije mogućnosti: a~b i $\not a$~b.

Ako a~b tada je po definiciji $a\in R_b$. Sada želimo pokazati da R_a podskup od $R_b$ i obratno da je $R_b \subset R_a$. To znači da je $R_a = R_b$. Po simetričnosti dosta je pokazati samo jedno, recimo $R_a\subset R_b$ tj. ako je $x\in R_a$ onda je $x\in R_b$. Ajde da pokažemo to jedno.

$x\in R_a$ znači x~a, a pretpostavili smo a~b, dakle po tranzitivnosti slijedi x~b, dakle $x\in R_b$

Dovoljno je da postoji jedan zajednički element c u $R_a \cap R_b$ da bi $R_a$ bilo isto što i $R_b$

Zaista, c u $R_a$ znači c~a, $c \in R_b$ znači c~b pa i b~c po simetriji, dakle po tranzitivnosti b~a tj. $R_a = R_b$.

Ako $\not a$~b (a nije u relaciji s b) onda a nije u razredu $R_b$, dakle postoji element (naime a) koji je u $R_a$ a nije u $R_b$, pa onda nitko iz $R_a$ nije u $R_b$ jer smo malo prije dokazali da ako je samo jedan u presjeku da su svi iz $R_a$ tamo, pa kako a nije tamo to je nemoguće.

Kardinalni brojevi

Kardinalni broj je razred ekvipotentnosti skupova (to je jedna relacija ekvivalencije) gdje su po definiciji dva skupa ekvipotentna ako postoji bijekcija s jednog na drugi.

Relacija ekvipotentnosti je zaista relacija ekvivalencije.

A~A jer $id_A : A \to A$ je bijekcija

A~B tada je i B~A. Zaista, ako postoji $f:A\to B$ bijekcija tada je inverzna funkcija $f^{-1}:B\to A$ je također bijekcija

A~B i B~C to znači $f:A\to B, g: B\to C$, pa onda je ikompozicija $g\circ f : A\to C$ također bijekcija pa je A~C.

Npr. zašto je injekcija. Neka su dakle, $a,a'$ dva elementa koja idu u isti element za kompoziciju $g(f(a)) = g(f(a'))$. Kako je g injekcija to znači da $f(a)=f(a')$, sad kako je $f$ injekcija to znači $a=a'$. Dakle je injekcija.

$kard(A)$ je ta klasa kardinalnosti od $A$

npr. 3=kard(A) znači da A ima tri elementa odnosno da je u bijekciji sa svim skupovima koji imaju 3 elementa.

Beskonačan ako je ekvipotentan nekom svom pravom podskupu (sjetimo se da je $A$ pravi podskup od $B$ ako je $A$ podskup od $B$, a nije jednak $B$, drugim riječima svi elementi od $A$ su u $B$ ali nisu svi u $B$ u $A$ - postoji barem jedan iz $B$ koji nije u $A$). Skup je konačan ako nije beskonačan, drugim riječima ako nije ekvipotentan nekom svom pravom podskupu.

A je pravi podskup od B ako A nije isto što i B, a jest podskup od B.

Prirodni broj je kardinalni broj konačnog nepraznog podskupa. Skup svih takvih $\mathbf{N} = \{1,2,3,\ldots \}$ nije konačan i zovemo ga ponekad i skup prirodnih brojeva. Definirajmo njegov podskup $\mathbf{N}_{\geq 2} = \{x\in\mathbf{N} | x\geq 2\} = \{2,3,4,\ldots\}$. Klasu ekvipotentnosti skupa prirodnih brojeva $\mathbf{N}$ zovemo prebrojiva beskonačnost i pišemo $\aleph_0 = kard(\mathbf{N})$ te čitamo alef nula. Alef $\aleph$ je prvo slovo hebrejskog alfabeta.

Bijekcija $\mathbf{N}$ u $\mathbf{N}_{\geq 2}$ zadana s 1 ide u 2, 2 ide u 3 itd. (ova bijekcija je naprosto funkcija sljedbenika).

Skup je prebrojivo beskonačan ako ima točno onoliko elemenata koliko skup prirodnih brojeva.

Hilbertov hotel: ima prebrojivo mnogo soba, numeriranih prirodnim brojevima.

Popunimo ga. Pomaknuvši elemente/prebivatelje u stranu možemo smjestiti nove elemente u puni hotel! Čak prebrojivo mnogo njih ako je pomjeranje napravljeno na pametan način! Recimo svakog pomaknemo u sobu čiji redni broj je dvostruko veći i onda su nam sva neparna mjesta prazna i slobodna za popunjavanje.

Nastavak diskusije o kardinalnim brojevima je u lekciji mat1-171120-2. Vidi i stranicu kardinalni broj.

category: zadarmat1