Zoran Skoda zadarmat1test1onefile

Logika predikata

Uz ovu stranicu pročitajte i stranicu zaključivanje.

Sud (iskaz) je izjava koja ima točno određenu i nepromjenjivu vrijednost istinitosti, istina ili laž. Istinu označavamo s $\top$ ili $1$, a laž s $\perp$ ili $0$. Koristimo uobičajenu matematičku pokratu akko za sintagmu ‘ako i samo ako’.

Od jednostavnih sudova možemo sastavljati složene sudove, npr. ako je $P$ sud “3 je neparan broj” i Q sud “4 je paran broj” tada možemo sastaviti složeni sud $P\wedge Q$, “3 je neparan broj i 4 je paran broj”. Operator konjunkcije $\wedge$ čitamo “i” jer odgovara (do neke mjere) uporabi veznika i u prirodnom jeziku. Konjunkcija dvaju sudova je istinita akko je svaki od ta dva suda istinit.

Slično, konstruiramo disjunkciju sudova $P\vee Q$ i čitamo $P$ ili $Q$. Disjunkcija sudova je istinit sud onda i samo onda kad je barem jedan od sastavnih sudova istinit.

Implikacija sudova $P\implies Q$ je lažna onda i samo onda ako je $P$ istinit, a $Q$ lažan sud. Dakle čak iz laži možemo dobiti zaključak koji je istinit, ali iz istine nikako ne možemo ispravnim zaključivanjem dobiti laž. Jedino što je nemoguće je da istina implicira laž. $P\implies Q$ čitamo “iz $P$ slijedi $Q$” ili “$P$ implicira $Q$” ili “$Q$ ako $P$”.

Ekvivalencija sudova $P\Leftrightarrow Q$ je istinita ako oba sastavna suda $P$ i $Q$ imaju istu istinitosnu vrijednost, tj. ako su oba istina ili oba laž. $P\Leftrightarrow Q$ čitamo $P$ ako i samo ako $Q$ ili čitamo $P$ onda i samo onda kada $Q$ ili čitamo $P$ je ekvivalentno $Q$.

Konačno negacija suda $P$ je sud $\neg P$ koji je istinit ako je $P$ lažan i lažan ako je $P$ istinit.

Logika sudova ili račun sudova se bavi računanjem istinitosnih vrijednosti izraza koji se od jednostavnih sudova dobiju pomoću gornjih operacija negacije, disjunkcije, konjunkcije, implikacije i ekvivalencije. Pri tome smatramo da se negacija uže veže uz ime suda, a druge su operacije jednako vrijedne pa redoslijed moramo diktirati zagradama.

Dakle, imamo slijedeća gramatička pravila produkcija kako formiramo složene sudove

$$\array{ JEDNOSTAVNISUD \to \top \\ JEDNOSTAVNISUD \to \perp \\ SUD \to JEDNOSTAVNISUD \\ SUD \to (SUD \wedge SUD) \\ SUD \to (SUD \vee SUD) \\ SUD \to \neg SUD \\ SUD \to (SUD \implies SUD) \\ SUD \to (SUD \Leftrightarrow SUD) }$$

i naravno $JEDNOSTAVNISUD$ možemo zamijeniti imenom nekog jednostavnog suda.

Npr. pogledajmo slijedeće primjere složenih sudova

$(\top \implies \perp)\implies (\perp\implies\perp)$ je sud čija vrijednost je $\top$

$(P \implies R) \wedge (R\vee Q)$ gdje su $P,Q,R$ imena jednostavnih sudova. Istinitosna vrijednost tog suda zavisi od istinitosnih vrijednosti sudova $P,Q,R$, dakle o $2\times 2\times 2 = 8$ kombinacija njihovih istinitosnih vrijednosti.

Složeni sud čija vrijednost je istina za ma koju kombinaciju istinitosnih vrijednosti jednostavnih sudova u njegovoj strukturi zovemo tautologijom logike sudova.

Predikat (prirok) je izjava čija istinitosna vrijednost zavisi samo od vrijednosti nekog parametra. Dakle, za svaku vrijednost parametra dobijemo sud, pa je prirok kao familija sudova koja je parametrizirana tim parametrom. Ako je $x$ parametar (kažemo i argument priroka) tada predikat zovemo $P(x)$. Sam izraz $P(x)$ nema istinitosnu vrijednost, nema značenja, sam po sebi je besmislen. Parametar/argument $x$ mora biti iz neke kolekcije mogućih parametara, no ako ipak nismo odredili za koju vrijednost testiramo izraz tada kažemo da je $x$ slobodni ili nevezani parametar. Ako je $P$ predikat “biti paran broj” na skupu prirodnih brojeva tada je $P(1)$ laž, a $P(2)$ istina. Ako smo fiksirali koliko je $x$ tada znamo vrijednost $P(x)$. Zanima nas slučaj kad je $P(x)$ točan za svaku vrijednost od $x$, što izražavamo rečenicom: za svaki $x$ vrijedi $P(x)$ i pišemo $(\forall x) P(x)$. Taj izraz je istinit ako je za svaki broj stavljen umjesto $x$ izraz $P(x)$ istinit. Ovdje smo pretpostavili da je skup parametara koje gledamo skup (prirodnih) brojeva, no općenito to nije jasno. Zato bismo točnije trebali reći $(\forall x\in N) P(x)$ gdje je $N$ skup prirodnih brojeva. Ekvivalentno možemo reći da je $x$ varijabla općeg tipa i da naknadno specificiramo u kvantificiranoj formuli da je $x\in N$, tj. $(\forall x) (x\in N \wedge P(x))$. Simbol $\forall$ zovemo univerzalnim kvantifikatorom. U izrazu $(\forall x\in N)P(x)$ jasno je za koje vrijednosti testiramo $P(x)$ i kako je definirana istinitosna vrijednost cijelog izraza jer nema parametara koji lete slobodni u zraku i ne znamo na koje vrijednosti ih testiramo. Kažemo da je $x$ vezana varijabla (tj. nije slobodna). Ako gledamo samo izraz $P(x)$ onda nije jasno gdje leži $x$ i unutar tog izraza $x$ nije vezana nego slobodna varijabla. Pitamo se na primjer da li su svi prirodni brojevi parni ? $(\forall x\in N)(paran(x))$. Nisu, jer $1$ nije paran pa je cijeli izraz laž.

Izraz $(\exists x) P(x)$ (“postoji $x$ takav da je $P(x)$”) je drugi način određivanja kako testirati $P(x)$. Taj izraz ima vrijednost istina akko postoji vrijednost parametra $x$ za koju je $P(x)$ istina. Simbol $\exists$ označava egzistencijalni kvantifikator. Predikat ima određenu vrijednost samo ako su svi argumenti vezani.

Jednostavne predikate možemo kombinirati u složene predikate. Npr. ako su $P(x), Q, R(y,z)$ tri predikata (prvi ima jedan argument, drugi nema argumenata, a treći ima dva argumenta) tada slijedeći predikat

$$(\forall x) ((P(x) \cap Q) \implies ((\exists x')P(x') \vee (\forall y)(\forall z)R(y,z)))$$

ima neku istinitosnu vrijednost koja zavisi naravno o izboru predikata jer su svi argumenti vezani.

Primjetimo da uvijek ako vrijedi $(\forall x)P(x)$ tada vrijedi i $(\exists x)P(x)$ (pri čemu u računu predikata podrazumijevamo da univerzalni skup nije prazan, inače $P(x)$ ne bi imao niti jednu definiranu istinitosnu vrijednost pa ne bi bio predikat).

Jednakost $=$ i kratice $\neq$ i $\exists! x$

Posebno zanimljiv predikat je jednakost $=$, posebno značajan predikat koji zavisi od dva argumenta.

Taj predikat tipično ima drukčiju sintaksu, umjesto $=(x,y)$ pišemo $x = y$.

U logici predikata možemo neke objekte smatrati jednakima. Kažem da je predikat jednakosti $=$ s dva argumenta istinit za one parove za koje su oba argumenta jednaka ili identična u nekom smislu. Npr. interpretiramo da su nazivi argumenata samo različiti nazivi za isti objekt u interpretaciji. Sintaktički, prije nego možemo osmisliti interpretaciju preko objekata, tražimo samo da jednakost zadovoljava svojstva

• tranzitivnost $(\forall x)(\forall y)(\forall z)((x = y)\wedge(y=z))\implies (x = z)$ (ako je neki $x$ jednak nekom $y$ i taj $y$ jednak nekom $z$ tada je i taj $x$ jednak tomu $z$)

• simetričnost $(\forall x)(\forall y) (x = y)\implies (y = x)$ (ako je neki $x$ jednak nekom $y$ tada je taj $y$ jednak tome $x$)

• refleksivnost $(\forall x)(x = x)$ (svaki $x$ je jednak sebi samom)

• jednakost čuva vrijednost predikata: ako za ma koji predikat $P$ vrijedi $P(x)$ i vrijedi $x = y$ tada vrijedi i $P(y)$. Postupak zamjene $x$ na $y$ je supstitucija, stoga kažemo da supstitucija argumenta čuva vrijednost predikata (invarijantnost predikata na supstituciju argumenta).

Npr. pogledajmo slijedeći izraz:

$$(\forall x)(\forall y)(x = y \implies P(x) = P(y))$$

Taj izraz je uvijek istinit, za ma koji predikat $P$ s jednim argumentom: ako u $P$ supstituiramo nešto ili nešto drukčije nazvano ali koje je “jednako” prvom argumentu dobit ćemo istu istinitosnu vrijednost. Govorimo o računu predikata s jednakošću.

Izraz $x \neq y$ je kratica za izraz $\neg(x = y)$.

Izraz $(\exists! x)P(x)$ (postoji točno jedan $x$ takav da je $P(x)$) je kratica za izraz

$$(\exists x)P(x) \wedge (\forall y)(\forall z)((P(y)\wedge P(z))\implies (y = z))$$

To je “logično”, naime u običnom jeziku ovaj izraz kaže: postoji $x$ takav da vrijedi $P(x)$ i ako vidimo bilo koja dva takva onda su oni jednaki. Dakle sve zajedno to znači da postoji točno jedan $x$ takav da vrijedi $P(x)$.

Kvantifikator s tipom

Ponekad kvantifikatori vrijede za varijable nekog tipa. U teoriji skupova možemo tip smatrati kao pripadnost nekom skupu. Npr. ako je $x$ tipa $A$ to je kao da $x\in AA$ gdje je AA skup svih $y$ tipa $A$. Možemo to promatrati i kao imati neko svojstvo $AAA$, tj. da vrijedi $AAA(x)$. Dakle, $AAA(x)$ je vrijednost predikata $AAA$ na varijabli $x$. No, moguće je direktno u kvantifikatoru napisati na koji tip se odnosi. Možda je dobro izbjeći pitanje postojanje skupa svih $z$ tako da vrijedi $AA(z)$ pa jednostavno reći da je $x$ tipa $A$ kao neki posebni sintaktički odnos, recimo $x:A$ ($x$ je tipa $A$). Dakle, neki pišu $\forall_A x$ umjesto $\forall x:A$ ili umjesto $\forall x, AAA(x)$ ili umjesto $\forall x, x\in AA$. Slično pišemo i $\exists_A x$ za $\exists x:A$ (postoji $x$ tipa $A$).

category: zadarmat1

Zaključivanje

Logika kao disciplina se bavi ispravnim (valjanim) zaključivanjem (Engl. valid reasoning). Formalna pravila valjanog zaključivanja čine neku konkretnu logiku kao sustav (logički sustav), npr. klasičnu logiku predikata. Deduktivni proces zaključivanja počinje od unaprijed danih pretpostavki (premisa, polaznih sudova koje smatramo točnim) i vodi na zaključak. Osnovni princip po kojem neki deduktivni sustav zaključivanja smatramo logičnim je slijedeći: Ako je premisa istinita i zaključivanje valjano tada je zaključak također istinit. Valjano zaključivanje koje počinje od istinitih premisa engleski se zove sound reasoning, vidi wikipedia:soundness.

Aristotel je razvio rani sustav formalnog deduktivnog zaključivanja koji nazivamo silogistika, a pojedina pravila zaključivanja u njemu su silogizmi. Deduktivno zaključivanje znači da se specijalizacijom opće činjenice (kod Aristotela to je tzv. glavna premisa, općenito to može biti cijeli niz prihvaćenih činjenica) zaključuje o posebnom slučaju. Najpoznatiji primjer je (s desne strane u jeziku predikata) ovaj

(glavna premisa) Svi su ljudi smrtni. $\forall x$, čovjek$(x)\implies smrtan(x)$

(sporedna premisa) Sokrat je čovjek. čovjek(Sokrat)

Dakle, (zaključak) Sokrat je smrtan. smrtan(Sokrat)

Očito smo umjesto čovjek(x) i smrtan(x) mogli uzeti bilo koja dva predikata s istim tipom argumenata. Ovdje je Sokrat primjer konstante.

Izdvojimo još neka najvažnija pravila zaključivanja.

Modus ponens

Ako su $P$ i $Q$ sudovi, i vrijedi $P$ i vrijedi $P\implies Q$ tada vrijedi i $Q$.

Kontrapozicija i modus tollens

Promatrajmo implikaciju $P\implies Q$. Njena kontrapozicija je implikacija $\neg Q\implies \neg P$. U klasičnoj logici ako vrijedi implikacija tada vrijedi njena kontrapozicija.

Modus tollens je tome blizak način zaključivanja. Ako vrijedi $P\implies Q$ i ako vrijedi $\neg Q$ tada vrijedi $\neg P$. Ponekad kažemo zaključivanje od suprotnog.

Ako vrijedi za svaki tada vrijedi za neki

Ako vrijedi $\forall x, P(x)$ tada zaključujemo $\exists x, P(x)$.

Ako vrijedi da nije za neki tada vrijedi da nije za svaki

Ako vrijedi $\neg (\exists x, P(x))$ tada vrijedi $\neg (\forall x, P(x))$.

Vidimo da je to kontrapozicija prethodnog pravila.

Pokazanje (demonstracija) postojanja

Ako je $c$ konstanta nekog tipa $Q$ i vrijedi $P(c)$ tada $c$ pokazuje da postoji neki $x$ za koji vrijedi $P(x)$ naime $x = c$ pa možemo ustvrditi $\exists_Q x, P(x)$. Ako sve varijable dolaze iz nekog univerzalnog skupa, tada možemo pripadnost nekom tipu gledati kao neki dodatni predikat $Q(x)$ pa ovaj isti način zaključivanja postaje:

$Q(c)$ Quito je slijepac.

$P(c)$ Quito nema novaca.

Zaključak: $(\exists x)(Q(x)\wedge P(x))$ (ili, u notaciji tipova, $\exists_Q x, P(x)$). Dakle, postoji slijepac koji nema novaca.

Tertium non datur (isključenje trećeg, the law of excluded middle)

Teorem logike sudova je da za svaki sud vrijedi $P\vee \neg P$. Do tog zaključka možemo npr. doći preko istinitostnih tablica.

Negacija negacije je afirmacija

Ako vrijedi $P$ tada vrijedi i $\neg\neg P$. U klasičnoj logici vrijedi i obrat: ako vrijedi $\neg \neg P$ tada vrijedi $P$.

Induktivno zaključivanje

Induktivno zaključivanje govori o poopćenju na osnovu neke množine posebnih slučajeva. Ta shema zaključivanja nema nužno istinit zaključak. Npr. ako vidimo da pet autobusa za redom ne stane pred nekom kućom mi očekujemo da i šesti ne stane. Takvo zaključivanje je korisno u životu no ono nije strogo u smislu logike. Logički je moguće da šesti autobus stane pred kućom.

Međutim, vjeruje se da je matematička indukcija (i neka njena poopćenja) logički stroga.

Terminologija nužnih i dovoljnih uvjeta

Ako iz nekog skupa premisa slijedi zaključak, kažemo da je taj skup premisa dovoljan za zaključak. Dakle, nije nam potrebno ništa više pretpostaviti (u danom logičkom sustavu).

Za neku premisu $P$ kažemo da je nužan uvjet za da tvrdnja $Q$ vrijedi ako je njena negacija proturječna s tom tvrdnjom, odnosno da $Q\wedge \neg P$ vodi na proturječje. Obično se kod takve tvrdnje podrazumijeva i neki kontekst dodatnih premisa.

category: zadarmat1

Definicija

Prema Aristotelu određenje (definicija) nekog pojma mora sadržavati dva elementa:

1) nadređeni pojam (sinonimi: opći pojam, pojam višeg reda) tako da definirani pojam obuhvaća posebne slučajeve tog općeg pojma

2) posebnost ili specifična razlika (Lat. diferentia specifica) – svojstvo po kojem se pojam koji se definira razlikuje od drugih slučajeva nadređenog pojma

Takve definicije se danas zovu intenzivne definicije (Engl. intensional definition). Uz njih se koriste i ekstenzijske definicije (Engl. extensional definition) koje definiraju novi pojam kao jedan od nabrojeno mnogo slučajeva poznatih pojmova. Npr. ‘zemlja Evropske Unije’ je jedna od 28 zemalja koje se nabroje u definiciji.

Definicije u praksi svakako stvaramo i gradimo prema potrebama koje odgovaraju nekoj ideji, nekom intuitivnom pojmu kojeg želimo proučavati. Definicija ne smije biti preširoka, tj. uključivati i slučajeve koje ne odgovaraju željenom pojmu, niti preuska, tj. takva da neki slučajevi željenog pojma nisu uključeni.

Prema Aristotelu, kategorije su početni najopćenitiji pojmovi od kojih se neki sustav znanja počne graditi i koji se ne definiraju. Njegov vlastiti filozofski sustav je imao 9 kategorija.

U aksiomatskim sustavima koji se baziraju na simboličkoj logici, objekti koji se razmatraju imaju oznake koje mogu označavati pripadnike nekih klasa razmatranih objekata. Klase od kojih se počinje i koje se ne definiraju, nego se za njih samo pretpostave (postuliraju) neki aksiomi zovu se primitivni pojmovi. Njihova uloga je vrlo slična ulozi kategorija u Aristotelovom sustavu. U aksiomatskim sustavima možemo uvoditi nove oznake koje služe kao pokrate za pojmove definirane u danom aksiomatskom sustavu u terminima primitivnih pojmova i drugih ranije definiranih pojmova.

category: zadarmat1, zadarmat2

Teorem

Skup tvrdnji (aksioma) u nekom fiksiranom logičkom sustavu zaključivanja nazivamo aksiomatskom teorijom. Svaki sustav aksioma je napisan u nekom formalnom jeziku koji podrazumijeva moguće oznake, dozvoljenu sintaksu, skup dozvoljenih varijabli i konstanti, predikate i nad čime je moguća kvantifikacija. U formalnom jeziku kombinacije simbola čine formule. Sintaksa govori koje su formule dopuštene u formalnom jeziku. Samo neke dopuštene formule mogu imati vrijednost istinitosti u nekoj interpretaciji. Npr. formula $(\forall x)$ nema istinitu vrijednost u jeziku predikata, nego je nepotpuna, naime za svaki $x$ vrijedi što ? One formule koje imaju istinitosnu vrijednost u nekoj interpretaciji primitivnih objekata teorije (tj. objekata koje supstituiramo za varijable u interpretaciji) zovemo rečenicama. Općenito u matematici, formula je kraći zapis nekog matematičkog ili logičkog zaključivanja ili sintaktičkog izražavanja, no u formalnoj logici to je samo neki izraz, isječak jezika u kojem je proces zaključivanja formaliziran i ne mora biti zapravo korak samog zaključivanja.

Ako je dan neki skup aksioma i pravila zaključivanja, svaka tvrdnja koja sintaktički slijedi iz aksioma primjenom pravila zaključivanja naziva se teoremom u širem smislu. Slijed primjena pravila zaključivanja kojima dolazimo do teorema zovemo dokaz (u formalnom smislu). U praksi zapisujemo samo dio tih zaključivanja ako je ostatak očit. To je dokaz u praktičnom smislu. Kontradikcija ili proturječje je tvrdnja tipa $P\wedge \neg P$ gdje je $P$ neki sud u jeziku te teorije. Aksiomatska teorija je proturječna (sinonimi: proturječiva, nekonzistentna) ako je proturječje teorem u toj teoriji. Teorija je neproturječna ili konzistentna ako proturječje nije teorem u toj teoriji. Teorija je potpuna ako za svaki sud $P$ koji je napisan u jeziku teorije vrijedi ili $P$ ili $\neg P$. Teorija je odlučiva ako postoji algoritamska procedura pomoću koje možemo za svaki sud $P$ odrediti da li vrijedi $P$ ili $\neg P$. Matematički smislene teorije trebaju biti neproturječne.

U matematičkoj praksi teoremima u užem smislu (ili poučcima) često nazivamo samo važne teoreme u formalnom (širokom) smislu. Pomoćne teoreme koji služe kao koraci u dokazivanju važnijih nazivamo leme. Korolari ili posljedice su teoremi koji lagano slijede iz već dokazanih većih teorema. Propozicije (u prijevodu nešto kao “tvrdnje”, stavke) su neki važni teoremi, ali koji nisu toliko važni da ih nazivamo teoremima u užem smislu u kontekstu nekog matematičkog teksta.

Interpretacija teorije nastaje tako da se svaka konstanta u teoriji zamjeni nekim realnim objektom, svaka varijabla postane oznaka za proizvoljni element nekog skupa, svaki predikat se zamjeni relacijom, jednakost jednakošću objekata. Svi aksiomi moraju vrijediti kao istine u toj interpretaciji. Ako je zaključivanje valjano tada bi i svi teoremi te teorije trebali vrijediti u toj interpretaciji. Ukoliko je teorija neproturječiva i potpuna tada u interpretaciji vrijede samo teoremi te teorije i ništa drugo. Ukoliko teorija nije potpuna tada neke rečenice u jeziku teorije vrijede u jednoj interpretaciji, a ne vrijede u drugoj. Npr. ako gledamo aksiomatiku planimetrije bez aksioma o paralelama (tzv. apsolutna planimetrija) tada postoje njene interpretacije u kojima taj aksiom vrijedi (euklidska planimetrija) i one u kojima taj aksiom ne vrijedi (neeuklidska planimetrija).

category: zadarmat1

Skup

Skup je primitivan pojam u matematici. Dakle mi ga ne definiramo, ali imamo neku interpretaciju i pravila služenja tim pojmom. Ta pravila mogu biti zadana aksiomatski (aksiomatska teorija skupova), ali ih obično implicitno izvodimo analizom interpretacije. Naime skup gledamo (interpretiramo) kao neku zamišljenu skupinu (kolekciju) objekata koje nazivamo elementi skupa. Ako je $e$ element skupa $A$ tada pišemo $a\in A$. Za negaciju iskaza $a\in A$ pišemo $a\notin A$ ($a$ nije element skupa $A$). Skupovima možemo davati razna imena. Više imena mogu biti korištena za isti skup i imena ne utiču na svojstva i jednakost skupova. Jednakost skupova je binarna relacija među skupovima koju označavamo $=$.

Po definiciji, dva su skupa jednaka ako imaju jednake elemente. Dakle, u gornjoj notaciji, $A = B$ ako i samo ako $(\forall a) (a\in A \Leftrightarrow a\in B)$.

Tako definirana jednakost skupova ima uobičajena svojstva jednakosti (vidi logika predikata), naime uvijek vrijedi $A = A$ i iz $A = B$ slijedi $B = A$ te

$$((A = B) \wedge (B = C)) \implies (A = C).$$

Često koristimo pokratu $A\neq B$ ($A$ nije jednak $B$) za iskaz $\not (A = B)$. Drugim riječima $\neq$ je relacija komplementarna relaciji $=$.

Postoji jedinstveni skup, kojeg zovemo prazan skup i označavamo $\emptyset$, sa svojstvom $(\forall a)(a\notin\emptyset)$. Riječima, za svaki objekt vrijedi da nije u tom skupu, dakle ništa nema svojstvo da je element tog skupa.

Ako su $A$ i $B$ skupovi, i svaki element iz $A$ je ujedno u $B$, tada kažemo da je $A$ podskup od $B$ i pišemo $A\subseteq B$ ili, ekvivalentno, da je $B$ nadskup od $A$ i pišemo $B\supseteq A$. Dakle,

$$A\subseteq B \Leftrightarrow B\supseteq A \Leftrightarrow (\forall e)(e\in A\implies e\in B)$$

Ponekad se (posebno u naprednoj matematičkoj literaturi i inozemstvu) relacija biti podskup od označava s $\subset$. Očito je $A\subseteq A$. Kažemo da je $A$ pravi podskup od $B$ ako je $A$ podskup od $B$ i različit od $B$.

Relacija “biti pravi podskup” se ponekad također označava s $A\subset B$. To može zbuniti s obzirom da nekad $\subset$ označava podskup. Osim toga ta relacija se koristi mnogo rjeđe nego relacija biti podskup pa je zgodno imati jednostavniju notaciju za ono što se češće koristi. Tada je dobro naglasiti “pravi” podskup znakom nejednakosti ispod: Dakle,

$$(A\underset\neq\subset B) \Leftrightarrow ((A\subseteq B) \wedge (A\neq B))$$

Drugim riječima, svi elementi od $A$ su elementi u $B$ i postoji barem jedan element od $B$ koji nije u $A$.

Ako je $P$ svojstvo koje ima smisla za elemente u $A$, tj. pojedini elementi skupa $A$ mogu ili imati ili ne imati to svojstvo, tada postoji skup svih elemenata $a\in A$ za koje $a$ ima svojstvo $P$, pišemo $P(a)$ (čitaj: $a$ ima svojstvo $P$). Taj skup je podskup od $A$ i označavamo ga oznakom

$$\{ a\in A | P(a) \}$$

Svojstvo $P$ se tipično zapisuje kao istinitost neke logičke tvrdnje/suda čija jedina nevezana varijabla je $a$.

Ako su $a,b,c,\ldots, z$ imena nekih objekata tada s $\{a,b,c,\ldots,z\}$ označavamo skup $S$ čiji elementi su $a,b,c,\ldots, z$ i ni jedan drugi objekt. Ako dva imena označavaju jednaki objekt tada je činjenica da je jedan od njih u $S$ ekvivalentna činjenici da je drugi u $S$ pa ga dakle možemo i izostaviti iz spiska. Npr. $\{a,a,b\}$ i $\{a,b\}$ imaju iste elemente pa su dakle jednaki skupovi.

Često promatramo skupove u nekom kontekstu gdje su elementi svih promatranih skupova ujedno elementi nekog velikog skupa kojeg nazivamo univerzalni skup (za dani kontekst). Ako je univerzalni skup $U$, tada $\forall a \in U$ ima praktički isto značenje kao i $\forall a$. Također tada $\{a | P(a)\} = \{ a\in U | P(a)\}$.

Operacije na skupovima

Neka su $A, B$ skupovi, oba sadržana u nekom univerzalnom skupu $U$. Tada definiramo nove skupove,

• presjek $A\cap B$ skupova $A$ i $B$,
  $$A \cap B := \{ x | x\in A \wedge x\in B \},$$
• uniju $A\cup B$ skupova $A$ i $B$,
  $$A \cup B := \{ x | x\in A \vee x\in B \},$$
• skupovnu razliku $A\backslash B$ skupova (ili diferenciju skupova) $A$ i $B$,
  $$A \backslash B := \{ x | x\in A \wedge x\notin B \},$$
• simetričnu razliku $A\triangle B$ skupova $A$ i $B$,

$$A \triangle B := \{ x | (x\in A \wedge x\notin B)\vee(x\in B \wedge x\notin A)\} = (A\backslash B) \cup (B\backslash A),$$

• nadopunu ili komplement $A^c$ skupa $A$ u univerzalnom skupu $U$,
  $$A^c = U \backslash A = \{ x| x\notin A\}.$$

Lako je zaključiti cijeli niz svojstava tih operacija, npr. za sve $A,B,C\subseteq U$ vrijedi

• $A\cap (B\cap C) = (A\cap B)\cap C$ (asocijativnost presjeka)

• $A\cup (B\cup C) = (A\cup B)\cup C$ (asocijativnost unije)

• $A\cup B = B\cup A$ (komutativnost unije)

• $A \cap B = B\cap A$ (komutativnost presjeka)

• $A\cap (B\cup C) = (A \cap B)\cup (A\cap C)$ (distributivnost presjeka prema uniji)

• $(A^c)^c = A$ (idempotentnost nadopune)

• $(A\cap B)^c = A^c\cup B^c$ (de Morganov zakon)

• $A \triangle B = (A\cup B)\backslash (A\cap B)$

• $A\cap \emptyset = \emptyset$

• $A\cup \emptyset = A$

• $\emptyset^c = U$

Ali, treba biti oprezan i nikako ne pogađati “slične” formule bez pažljivog zaključivanja. Lako je npr. konstruirati primjere skupova $A$ i $B$ kad je $A\backslash B\neq B\backslash A$ (što je logično i kad se raspišu definicije). U onim slučajevima u kojima vrijednost izraza ne zavisi od položaja zagrada možemo izostaviti zagrade. Dakle, zbog $A\cap (B\cap C) = (A\cap B)\cap C$ možemo naprosto pisati $A\cap B\cap C$ bez zagrada. Međutim, izraz $A\cup B\cap C$ nema smisla, jer općenito $A\cup (B\cap C)\neq (A\cup B)\cap C$ pa ne znamo na koji od ta dva izraza mislimo.

Familije skupova

Množina je stara riječ koja se nekad također koristila za skup. Danas je upotrebljavamo uglavnom samo kada govorimo o nekom skupu skupova, dakle množini skupova. Množine skupova često indeksiramo nekim razlikovnim oznakama, npr. s $1$, $2$, $3$, pa pišemo $A_1, A_2, A_3$ za tri skupa u nekoj množini $A$. Indeksiranu množinu nazivamo još i familija skupova, a skupove $A_i$ nazivamo članovima familije $A$. Izraz $A_i$ zovemo općim članom familije. Za indeks $1$ imamo $A_1$, za indeks $2$ imamo $A_2$ itd. Dakle samo indeksiranje, odnosno familija skupova je naprosto funkcija $A$ iz nekog skupa indeksa $I$ u neku (još neindeksiranu) množinu skupova. U ovom slučaju $\{1,2,3\}\to \{A_1, A_2, A_3\}$. Zgodno je indeksirati množine skupova jer možemo o općem elementu množine govoriti kao o nekom $A_i$ gdje je $i$ element skupa indeksa. Npr. promatramo familiju skupova $\{A_1, A_2, A_3, A_4,\ldots\} = \{ A_n\}_{n\in\mathbb{N}}$, tada možemo reći npr. da neka tvrdnja vrijedi za sve $A_i$ gdje je $i$ paran broj, a ne vrijedi ako je $i$ neparan broj. Kako je $i\mapsto A_i$ funkcija iz skupa indeksa u množinu skupova, to možemo pisati indeks i kao argument funkcije, pa ponekad pišemo $A(i)$. Odabir među $A_i$ i $A(i)$ samo je pitanje jasnoće i sugestivnosti oznake.

Definiramo presjek ma kakve familije skupova

$$\bigcap_{i\in I} A_i = \{ a | (\forall i\in I) (a\in A_i)\}$$

i njenu uniju

$$\bigcup_{i\in I} A_i = \{ a | (\exists i\in I) (a\in A_i)\}.$$

Dakle, element je u presjeku familije skupova ako je element svakog člana familije. Element je u uniji familije ako je element barem jednog člana familije. Kažemo da familija ima $K$ elemenata ako je kardinalnost skupa indeksa $K$. Primijetimo da neki indeksi mogu indeksirati jednake skupove, recimo $A_1 = A_2$, no ipak ih brojimo kao dva člana familije. Ako je familija dvočlana to se svodi na ranije definicije presjeka i unije dva skupa. Ako je familija jednočlan skup, tada je njegova unija i presjek taj sam skup. Ako razmislimo o značenju kvantifikatora, presjek prazne familije skupova po gornjoj definiciji je univerzalni skup, a njena unija je prazan skup. No, unije i presjeke praznih familija nećemo razmatrati u kolegiju.

Par elemenata je skup koji ima točno dva različita elementa, npr. $\{3,4\}$. Uređeni par $(a,b)$ je neformalno par kojem znamo koji je prvi, a koji je drugi element i gdje dozvoljavamo i slučaj da su ta dva elementa isti. To možemo postići tako da promatramo ta dva elementa $a$ i $b$ kao familiju od dva elementa, tj. funkciju $\{1,2\}$ u neki skup $S$ iz kojeg biramo elemente para. Slično možemo govoriti o uređenim $n$-torkama elemenata iz $S$ kao familijama $\{1,2,\ldots,n\}\to S$. Kartezijev produkt skupova $A\times B$ je skup uređenih parova iz $A\cup B$ kojima je prvi element iz $A$, a drugi element iz $B$. Kuratowski definira uređeni par $(a,b)$ kao skup $\{\{a\},\{a,b\}\}$. Dakle daje informaciju skupa $\{a,b\}$ u kojem je posebno izdvojeno koji je prvi element $\{a\}$. Ako je prvi i drugi element isti onda je u tom pristupu $(a,a) = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}$.

Disjunktni skupovi i disjunktne unije

Kažemo da su skupovi $A$ i $B$ disjunktni ako $A\cap B = \emptyset$. Drugim riječima dva su skupa disjunktna ako nemaju ni jedan zajednički element. Engleski izraz je disjoint sets (wikipedia). Ako razmatramo više od dva skupa $A_1, A_2, A_3, \ldots, A_n$ tada kažemo po konvenciji da su oni disjunktni (stari izraz poparno disjunktni; engl. pairwise disjoint ili mutually disjoint sets) ako su svaka dva međusobno disjunktna. To je jači uvjet nego tražiti da nema zajedničkog elementa od njih svih, odnosno da je $\cap_{i\in I} A_i = \emptyset$. Npr. presjek tri skupa $\{a,b\}$, $\{b,c\}$, $\{a,c\}$ je prazan, ali čak svaka dva od njih imaju neprazan presjek, dakle postoji par koji nisu disjunktni, pa cijela množina nije disjunktna.

Ako su dva skupa $A$ i $B$ disjunktna onda kažemo za njihovu uniju $A\cup B$ da je disjunktna unija i disjunktnost ponekad naglašavamo točkom nad znakom unije, dakle $C = A\overset\cdot\cup B$ znači da je istovremeno $C = A\cup B$ i da je $A\cap B = \emptyset$. Slično možemo govoriti o disjunktnoj uniji $\overset\cdot\cup_{i\in I} S_i$,ma koje množine disjunktnih skupova $\{S_i\}_{i\in I}$. No, što ako skupovi nisu disjunktni? Ponekad moramo formirati “na silu” disjunktnu uniju tako da eventualne elemente u presjeku učinimo različitim u procesu, npr. tako da im dodamo neki dodatni simbol. Npr. kod unije dva skupa $A$ i $B$ možemo elementima prvog skupa dodati oznaku $A$, a drugog skupa oznaku $B$. Dakle neka je $A = \{ 1, 2,3\}$ i $B = \{ 1, 2, c, d\}$ tada možemo gledati uniju $\{ 1_A, 2_A, 3_A\} \cup \{ 1_B, 2_B, c_B, d_B\} = \{ 1_A, 2_A, 1_B, 2_B, 3_B, c_B, d_B\}$. Naravno, pri tome $1_A$ možemo formalizirati kao uređeni par $(1,A)$. Takvu disjunktnu uniju pišemo $A \coprod B$ i ona se koristi kod definicije zbroja kardinalnih brojeva, u jednom od mogućih pristupa. Zaista, $kard(A) = 3$, $kard(B) = 4$, $kard(A \cup B) = 3+4 - 2 = 5$ (jer su dva elementa u presjeku) i $kard(A\coprod B) = 7 = kard(A)+kard(B)$. Zbroj dva kardinalna broja je po standardnoj definiciji razred ekvivalencije unije predstavnika ta dva broja koji su međusobno disjunktni i ona ne zavisi od izbora predstavnika. No, mogli smo uzeti bilo koja dva predstavnika, makar oni nisu disjunktni i napraviti ovu umjetnu disjunktnu uniju s unošenjem razlikovnih oznaka. Cijela ta priča s razlikovnim oznakama prenosi se i na disjunktnu uniju $\coprod_{i\in I} A_i$ ma koje množine skupova $\{A_i\}_{i\in I}$ koji dakle ne moraju na početku biti disjunktni.

Particija skupa $S$ je prikaz skupa $S$ kao disjunktne unije $\overset\cdot\cup_{i\in I} S_i$, tj. unije neke množine već disjunktnih podskupova $S_i\subseteq S$. Npr. $\{1,2,3,4,5,6\} = \{1,2\}\cup\{3,5\}\cup\{4,6\}$.

Russelov paradoks

Naivna teorija skupova u kojima dozvoljavamo da je skup element samog sebe (npr. skup svih skupova) dovodi do proturječja koje zovemo antinomije teorije skupova. Prva od njih je tzv. Russelov paradoks.

Ako postoji skup svih skupova tada možemo govoriti i o njegovom podskupu $S$ čiji elementi su svi skupovi koji nisu elementi samog sebe. $S$ je element u $S$ ili $S$ nije element u $S$. Ako $S\in S$ tada po definiciji skupa $S$ mora biti da $S\notin S$. Ako pak $S\notin S$ tada po definiciji skupa $S$ mora biti da $S\in S$. To je paradoks kojeg je primijetio Bertrand Russel i time uništio dojam da je Cantorova teorija skupova, tadašnji “Cantorov raj” dobar sustav za matematiku što je rezultiralo s nekoliko varijanti suvremene aksiomatske teorije skupova u kojima nije nađeno proturječje.

Zermelo-Frenkelova aksiomatika teorije skupova

Vidi članak u online izdanju hrvatske enciklopedije aksiomatska teorija skupova.

category: zadarmat1, zadarmat2, zadarmat3, zadarmat4

Funkcije i relacije

Funkcija ili preslikavanje iz skupa $A$ u skup $B$ je pravilo koje svakom elementu skupa $A$ pridružuje točno određeni element skupa $B$. Kažemo da funkcija svakom elementu u $A$ pridružuje jedan i samo jedan element skupa $B$ (to znači jedan i ništa više, tj. točno jedan). Skup $dom(f) = A$ zove se domena ili područje definicije funkcije $f$, a skup $cod(f)=B$ kodomena ili područje vrijednosti funkcije $f$. Kažemo također da je $f$ definirana na skupu $A$ i da prima vrijednosti u skupu $B$. Pišemo $f : A\to B$ (ili, grafički naglašenije, $A\overset{f}\longrightarrow B$), a rezultat pridruživanja $f$ na elementu $a$ je $f(a)$. Ako je $f(a)$ zadano (recimo kao formula) onda pišemo $f : a \mapsto f(a)$. Primijetite razliku simbola $\to$ i $\mapsto$. Neki pojmovi vezani uz funkcije su slika funkcije, praslika, restrikcija funkcije.

U teoriji skupova sve se formalizira kao skup pa se i neformalan koncept “pravila” (koji je jasan na konačnim skupovima, a možda malo manje jasan na zamišljenim objektima kao što su beskonačni skupovi) formalizira preko funkcijske relacije.

(Binarna) relacija $R$ iz $A$ u $B$ je bilo koji podskup $R\subseteq A\times B$ Kartezijevog produkta $A\times B = \{(a,b) \,|\,a\in A, b\in B\}$, odnosno skupa svih uređenih parova kojima je prvi element iz prvog skupa $A$, a drugi element iz drugog skupa $B$. Ako je neki $(a,b)\in R$ pišemo $a R b$ i kažemo da je $a$ u relaciji $R$ s $b$. (Binarna) relacija na skupu $A$ je bilo koja relacija iz $A$ u $A$. Slično tome, ako je $n$ prirodni broj, $n$-arna relacija na skupu $A$ je bilo koji podskup Kartezijevog produkta $A\times A\times \ldots \times A$ ($A$ se pojavljuje $n$-puta).

Npr. jedna binarna relacija na (neformalnom) skupu drveća sastoji se od parova u kojima je prvo drvo u paru manje od drugog drveta u paru. To je relacija koju “manje”. Prvo drvo je manje od drugog u običnom smislu ako je prvo drvo u relaciji “manje” s drugim drvetom i pišemo prvo drvo “manje” drugo drvo.

Važne vrste binarnih relacija na skupu $S$ su relacije ekvivalencije i uređaja? ili poretka. Obje su tranzitivne relacije ali se razlikuju po drugim svojstvima, značenju i primjenama.

Funkcijska relacija $f$ iz $A$ u $B$ je binarna relacija $f\subseteq A\times B$ s dva svojstva

• ako je $a\in A$ tada postoji element $b\in B$ takav da $a f b$

• ako je $a f b$ i $a f c$ tada je $b = c$ (drugim riječima, postoji najviše jedan element u $B$ koji je u relaciji $f$ s $A$)

Ta dva svojstva zajedno daju da za svaki element $a$ u $A$ postoji točno jedan element $b$ u $B$ takav da je $a f b$.

Uvjerimo se da je funkcija i funkcijska relacija suštinski jedno te isto. Ako je $f$ funkcijska relacija tada je $f(a) = b$ u jeziku funkcija točno onda kad je $a f b$ u jeziku relacija. Ako je $g:A\to B$ funkcija onda je pripadna funkcijska relacija

$$\Gamma_f = \{ (a,f(a)) | a\in A\}\subseteq A\times B.$$

Tu funkcijsku relaciju zovemo graf funkcije $f$. Nekad je označavamo naprosto s $f$. Alternativno možemo pisati i $\Gamma f = \{ (a,b)\in A\times B \,|\, b = f(a)\}$ [to je o;ito ekvivalentno gornjoj definiciji.]

Za svaku binarnu relaciju $R$ iz $A$ u $B$ može se definirati inverzna relacija $R^{-1}$ iz $B$ u $A$ ovako: $b R^{-1} a$ onda i samo onda ako $a R b$. Ako je $R$ funkcijska relacija to ne znači da će inverzna relacija biti funkcijska: oba svojstva funkcijske relacije iz definicije mogu pasti. Nužan i dovoljan uvjet da inverz zadane funkcijske relacije bude funkcijska relacije je da je zadana funkcijska relacija bijekcija.

To je jedan od razloga zašto za funkcije (ili, ekvivalentno, za funkcijske relacije) uvodimo pojmove injekcije, surjekcije i bijekcije. Funkcija $f:A\to B$ je injekcija ako iz $a\neq a'$ slijedi $f(a)\neq f(a')$. Drugim riječima, injekcija je funkcija koja nikad dva različita elementa ne šalje u isti element. Slika po funkciji $f$ nekog podskupa $X\subset A$ je skup $f(X)= \{b\in B\,|\,\exists x\in X,\,f(x) = b\}$, dakle skup svih elemenata koji su pridruženi barem jednom elementu iz $X$. Ako je $A = X$ kažemo da je $f(A) = Im(f)$ slika domene od $f$ ili kratko slika funkcije $f$. Funkcija je surjekcija ili “preslikavanje na” ako je $Im(f) = B$. Tada kažemo i da je funkcija $f:A\to B$ funkcija s $A$ na $B$, što je jača tvrdnja nego kad kažemo da je iz $A$ u $B$ (ovo potonje ne znači da je $f$ surjekcija). Funkcija je bijekcija ako je injekcija i surjekcija istovremeno. Inverzna relacija za danu funkciju je funkcijska relacija (dakle također funkcija) onda i samo onda ako je zadana funkcija bijekcija. Inverz bijekcije je bijekcija.

Vidi definicije u Struni: funkcija, injekcija, surjekcija, bijekcija.

Ako su $f:A\to B$ i $g:B\to C$ funkcije (primijetimo: domena od $g$ se podudara s kodomenom od $f$), tada je definirana složena funkcija (sinonim: kompozicija funkcija) $g\circ f:A\to C$ funkcija s domenom $A$ i kodomenom $C$ i zadana pravilom

$$(g\circ f)(a) = g(f(a)) \,\,\,\,\,\,\forall a\in A.$$

Slaganje (tj. operacija kompozicije) funkcija nije komutativno. Npr. u ovom slučaju, ako su $A,B,C$ različiti, $g\circ f$ je definirano, a $f\circ g$ nije ni definirano, a kamoli jednako $g\circ f$. Naime, $g$ prima vrijednosti u skupu $C$, pa odande ne možemo nastaviti funkcijom $f$, jer funkcija $f$ ima za domenu $A\neq C$.

Identiteta na skupu $A$ je funkcija $id_A:A\to A$ zadana “tautološkim” pravilom $id_A :a\mapsto a$. Ako je $f:A\to B$ funkcija, tada $f\circ id_A = f = id_B\circ f$.

Ako je $C\subseteq D$ tada formula

$$i_C : c\mapsto c,$$

definira preslikavanje $i_C:C\to D$. Dakle svaki element u $C$ se preslikava u samog sebe, ali shvaćenog kao elementa u nadskupu $D$. Tu funkciju zovemo inkluzija. Za inkluziju strelicu često pišemo na način koji podsjeća na relaciju biti podskup. Dakle, $i_C: C\hookrightarrow D, i_C:c\mapsto c$.

Ako je $S\subseteq dom(f)$ tada definiramo suženje funkcije $f|_S:S\to cod(f)$, formulom $f|_S(s) = f(s)$ za sve $s\in S$, vidi suženje funkcije. Uoči da je inkluzija $i_C:C\hookrightarrow D$ naprosto suženje identite $id_D:D\to D$ na podskup $C\subseteq D$.

Ako je $A$ skup i $P\subseteq A$ podskup od $A$. Tada postoji funkcija $\chi_P:A\to \{0,1\}$ zadana pravilom $a\mapsto 0$ ako je $a\notin P$ i $a\mapsto 1$ ako je $a\in P$. Tu funkciju nazivamo karakteristična funkcija podskupa $P\subseteq A$. Svaka funkcija $A\to \{0,1\}$ je karakteristična funkcija nekog i ujedno jedinstvenog podskupa $P\subseteq A$. Dakle, podskupovi od $A$ su u bijekciji s funkcijama iz $A$ u dvočlani skup $\{0,1\}$. Vidi više o tome na stranici partitivni skup.

category: zadarmat1, zadarmat2, zadarmat3, zadarmat4

Ekvipotentni skupovi i kardinalni brojevi

Relacija ekvipotentnosti

Dva skupa $A$ i $B$ su jednakobrojni ili ekvipotentni ako postoji bijekcija s $A$ na $B$. Biti ekvipotentan je relacija ekvivalencije na klasi svih skupova. Zaista,

• (TRANZITIVNOST) Moramo pokazati da ako su $A$ i $B$ ekvipotentni i $B$ i $C$ ekvipotetni, tada su $A$ i $C$ ekvipotentni. Zaista, ako su $A$ i $B$ ekvipotentni tada postoji bijekcija $f:A\to B$. Ako postoji bijekcija $f:A\to B$ i bijekcija $g:B\to C$ tada je kompozicija $g\circ f: A\to C$ također bijekcija, dakle $A$ i $C$ su zaista ekvipotentni.

• (SIMETRIČNOST) Ako su $A$ i $B$ ekvipotentni tada postoji bijekcija $f:A\to B$. Inverzna funkcija je tada također bijekcija $f^{-1}:B\to A$. Dakle $B$ i $A$ su ekvipotentni.

• (REFLEKSIVNOST) Identiteta $id_A:A\to A$ je injekcija i surjekcija, dakle bijekcija. Dakle za svaki skup $A$ postoji barem jedna bijekcija s $A$ na $A$ (naime identiteta) pa je $A$ ekvipotentan sa samim sobom.

Kardinalni brojevi

Razredi (klase) ekvivalencije s obzirom na relaciju ekvipotentnosti zovemo kardinalni brojevi ili kardinali. Kardinalni broj je dakle klasa svih skupova za svaki par kojih postoji bijekcija s jednog na drugi. Intuitivno, kardinalni broj $5$ je apstraktno svojstvo koje karakterizira sve skupove od $5$ elemenata. Skup od $5$ salveta je predstavnik te klase, dakle predstavnik kardinalnog broja $5$. Ako je skup $S$ predstavnik kardinalnog broja $\kappa$, kažemo da je $S$ kardinalnosti $\kappa$.

Prazan skup je ekvipotentan samom sebi; kažemo da prazni skup ima nula elemenata. Sve ostale kardinalnosti imaju mnogo predstavnika.

Kardinalnosti skupova možemo uspoređivati: $kard(S)\leq kard(T)$ ako postoji injekcija iz $S$ u $T$. U teoriji skupova (s aksiomom izbora) svaka dva skupa su usporediva u smislu da ili $kard(S)\leq kard(T)$ ili $kard(T)\leq kard (S)$, a (prema Cantor-Schroeder-Bernsteinovom teoremu) oboje vrijedi akko $kard(S) = kard(T)$. Dakle, $\leq$ je relacija nestrogog linearnog uređaja na klasi svih kardinala, štoviše taj uređaj je dobar (svaki podskup ima minimalni element). Kao i obično, nestrogom uređaju $\leq$ odgovara relacija strogog linearnog uređaja $\lt$

$$K\lt H \Leftrightarrow (L\leq H \wedge L\neq H).$$

Skup je konačan ako nije ekvipotentan ni jednom svom pravom podskupu (podskup nekog skupa je pravi podskup ako je podskup i različit od tog skupa). Inače je beskonačan. Za kardinalni broj kažemo da je konačan ako je on kardinalni broj konačnog skupa, te kažemo da je beskonačan inače. Kardinalne brojeve nepraznih konačnih skupova možemo identificirati s prirodnim brojevima. Zbrajanje prirodnih brojeva odgovara kardinalnom broju disjunktne unije. Nulu tada identificiramo s kardinalnim brojem praznog skupa. Kako svaka klasa kardinala ima minimalni element, to postoji najmanji beskonačni kardinal, a to je kardinalni broj skupa prirodnih brojeva. Taj kardinal zovemo $\aleph_0$ (hebrejski znak koji se čita alef nula). Ako je skup ekvipotentan sa skupom prirodnih brojeva kažemo da je prebrojivo beskonačan ili da je prebrojiv. Skup je najviše prebrojiv ako je konačan ili prebrojiv. Kardinalnost skupa realnih brojeva je $2^{\aleph_0}$, tj. postoji bijekcija $\mathbb{R}\to \mathcal{P}(\mathbb{N})$ (notacija $2^\kappa$ gdje je $\kappa$ kardinalni broj je objašnjena niže).

Jedan prikaz teme o kardinalnim brojevima je u dijelu lekcije mat1-171120-1 i u lekciji mat1-171120-2.

Kardinalnost partitivnog skupa i skupa funkcija

Ako je $K = kard(S)$ kardinalnost nekog skupa $S$ tada je kardinalnost partitivnog skupa $\mathcal{P}(S)$ (tj. skupa svih podskupova od $S$) označena s $2^K$. Ako je $K$ konačan broj, onda je $2^K$ zaista broj koji dobijamo običnim potenciranjem? broja $2$. Zaista, svaki podskup $P$ skupa $S$ određuje karakterističnom funkcijom tog skupa, $\chi_P:S\to \{0,1\}$ koja je zadana s $\chi_P(s) = 1$ ako je $s\in P$ i $\chi_P(s) = 0$ ako je $s\notin P$. S druge strane, svaka funkcija $\phi: S\to \{0, 1\}$ je karakteristična funkcija nekog skupa, naime skupa

$$P_\phi = \{ s\in S | \phi(s) = 1\}.$$

Drugim riječima, vrijednost $\phi(s) = 1$ je signal da je $s\in P$; kako je svaki skup određen svojim elementima to znači da su podskupovi od $S$ u bijekciji s funkcijama iz $S$ u $\{0, 1\}$. Koliko ima takvih funkcija ? Pa za svaki element imamo dva izbora: zadati $0$ na tom elementu i zadati $1$ na tom elementu. Dakle, za dva elementa imamo $2\times 2$ načina, za tri elementa, $2\times 2\times 2$ načina itd. Na kraju za $K$ elemenata, ako je $K$ konačan imamo $2^K$ elemenata.

Ako je kardinal $K$ beskonačan, onda je $2^K$ samo oznaka kardinalnosti partitivnog skupa od skupa s $K$ elemenata (to možemo uzeti kao definiciju potenciranja za moguće beskonačne kardinale).

Općenitije, ako su $A$ i $B$ skupovi, tada s

$$B^A = \{ funkcija\,\,\,f: A\to B \}$$

označavamo skup svih funkcija iz $A$ u $B$.

Za konačne brojeve vrijedi da je $kard(B^A) = kard(B)^{kard(A)}$ pa tako definiramo potenciranje kardinalnih brojeva koji mogu biti i beskonačni, a $2^{kard(A)}$ je poseban slučaj kad je $kard(B) = 2$. Riječima, potencija $L^K$ kardinalnog broja $L$ na kardinalni broj $K$ je kardinalni broj skupa funkcija $B^A$ iz (ma kojeg) skupa $A$ koji je predstavnik od $K$ u (ma koji) skup $B$ koji je predstavnik od $L$.

Cantorov teorem

Cantorov teorem. Za svaki kardinal $K$ vrijedi $K\lt 2^K$.

Dokaz. Tvrdnja je očita ako je $K = 0 = kard(\emptyset)$ (postoji injekcija iz praznog skupa u ma koji skup, ali ne postoji injekcija iz jednočlanog skupa $\{\emptyset\}$ u $\emptyset$).

Neka je $K = kard(S)\gt 0$. Tada postoji injekcija iz $S$ u $\mathcal{P}(S)$, naime funkcija zadana formulom $x\mapsto \{ x\}$, $\forall x\in S$ je injekcija. To znači da je $kard(S)\leq 2^{kard(S)}$. Preostaje pokazati $kard(S)\neq 2^{kard(S)}$. To znači da $S$ nije ekvipotentan s $\mathcal{P}(S)$. Pretpostavimo suprotno, dakle da neka bijekcija $f: S\to\mathcal{P}(S)$ postoji; mi ćemo sad pokazati da čak i slabija tvrdnja da postoji surjekcija $f:S\to\mathcal{P}(S)$ vodi na proturječje. Promatrajmo skup $R \in\mathcal{P}(S)$,

$$R := \{ x\in S | x\notin f(x)\}.$$

Tada postoji element $u\in S$ takav da je $f(u) = R$ (jer je $f$ surjekcija). Ako je $u\in R$ tada $u\in f(u)$ pa $u\notin R$ po definiciji od $R$, a ako $u\notin R$ onda $u\notin f(u)$ pa $u\in R$ po definiciji od $R$. Dakle, ni jedna od mogućnosti $u\in R$, $u\notin R$ nije konzistentna. Dakle, nije moguće da postoji surjekcija s $S$ na $\mathcal{P}(S)$. Time je Cantorov teorem dokazan. Ova ideja dokaza poznata je kao Cantorov dijagonalni argument.

category: zadarmat1, zadarmat4

Konačni i beskonačni skupovi

Skup $S$ je konačan ako ne postoji bijekcija $f:S\to P$ na neki pravi podskup $P\subseteq S$. Drugim riječima, skup je konačan ako nije ekvipotentan ni jednom svom pravom podskupu. Skup $S$ je beskonačan skup ako nije konačan, dakle ako postoji bijekcija s $S$ na neki pravi podskup $P\subseteq S$. Npr. skup prirodnih brojeva $\mathbb{N}$ je beskonačan jer je skup parnih brojeva $P$ ekvipotentan s $\mathbb{N}$. Zaista, pridruživanje koje prirodnom broju $n$ pridružuje parni broj $2 n$ je bijekcija s $\mathbb{N}$ na $P$ (razmislite o tome). Prazan skup je konačan skup (kažemo da ima nula elemenata).

Umjesto skup je konačan kažemo također skup je konačne kardinalnosti ili skup ima konačno mnogo elemenata.

Oprez: nemaju svi beskonačni skupovi istu kardinalnost. Skupovi koji imaju istu kardinalnost kao skup prirodnih brojeva zovu se prebrojivo beskonačni skupovi ili, kraće, prebrojivi skupovi. No već, partitivni skup $\mathcal{P}(\mathbb{N})$ skupa prirodnih brojeva ima veću kardinalnost od skupa prirodnih brojeva $\mathbb{N}$. Dakle, intuitivno govoreći, $\mathcal{P}(\mathbb{N})$ je veći beskonačni skup od prebrojivo beskonačnog skupa $\mathbb{N}$.

category: zadarmat1

Partitivni skup

Neka je $S$ skup. Skup čiji elementi su svi mogući podskupovi skupa $S$ zovemo partitivni skup skupa $S$ (etimološki bi to mogli tumačiti kao skup svih dijelova skupa $S$ (Lat. pars (fem.), gen. partis ‘dio’); ili skup svih podskupova od $S$). Engleski naziv je power set. Tako se i u hrvatskom i u engleskom uvriježila notacija $\mathcal{P}(S)$. Simbolički,

$$\mathcal{P}(S) = \{ P | P\subseteq S\}$$

Kardinalni broj skupa $\mathcal{P}(S)$ je $2^{kard(S)}$. Npr. kardinalnost praznog skupa je $0$, a partitivni skup praznog skupa ima jedan element i taj element je upravo prazan skup. Dakle $\mathcal{P}(\emptyset) = \{\emptyset\}\neq \emptyset$. Za svaki skup (konačan ili beskonačan), kardinalnost partitivnog skupa je strogo veća od kardinalnosti početnog skupa. Dakle, $2^K\gt K$.

Ako je $K$ konačan broj, onda je $2^K$ zaista broj koji dobijamo potenciranjem broja $2$. Zaista, svaki podskup $P$ skupa $S$ određuje karakterističnom funkcijom tog podskupa, $\chi_P:S\to \{0,1\}$ koja je zadana s $\chi_P(s) = 1$ ako je $s\in P$ i $\chi_P(s) = 0$ ako je $s\notin P$. S druge strane, svaka funkcija $\phi: S\to \{0, 1\}$ je karakteristična funkcija nekog podskupa od $S$, naime skupa

$$P_\phi = \{ s\in S | \phi(s) = 1\}.$$

Drugim riječima, vrijednost $\phi(s) = 1$ signalizira da je $s\in P$; kako je svaki skup određen svojim elementima to znači da su podskupovi od $S$ u bijekciji s funkcijama iz $S$ u $\{0, 1\}$. Koliko ima takvih funkcija ? Pa za svaki element imamo dva izbora: zadati $0$ na tom elementu i zadati $1$ na tom elementu. Dakle, za dva elementa imamo $2\times 2$ načina, za tri elementa, $2\times 2\times 2$ načina itd. Na kraju za $K$ elemenata, ako je $K$ konačan imamo $2^K$ elemenata.

category: zadarmat1