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 11, a laž s \perp ili 00. 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 PP sud “3 je neparan broj” i Q sud “4 je paran broj” tada možemo sastaviti složeni sud PQP\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 PQP\vee Q i čitamo PP ili QQ. Disjunkcija sudova je istinit sud onda i samo onda kad je barem jedan od sastavnih sudova istinit.

Implikacija sudova PQP\implies Q je lažna onda i samo onda ako je PP istinit, a QQ 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ž. PQP\implies Q čitamo “iz PP slijedi QQ” ili “PP implicira QQ” ili “QQ ako PP”.

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

Konačno negacija suda PP je sud ¬P\neg P koji je istinit ako je PP lažan i lažan ako je PP 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

JEDNOSTAVNISUD JEDNOSTAVNISUD SUDJEDNOSTAVNISUD SUD(SUDSUD) SUD(SUDSUD) SUD¬SUD SUD(SUDSUD) SUD(SUDSUD)\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 JEDNOSTAVNISUDJEDNOSTAVNISUD 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

(PR)(RQ)(P \implies R) \wedge (R\vee Q) gdje su P,Q,RP,Q,R imena jednostavnih sudova. Istinitosna vrijednost tog suda zavisi od istinitosnih vrijednosti sudova P,Q,RP,Q,R, dakle o 2×2×2=82\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 xx parametar (kažemo i argument priroka) tada predikat zovemo P(x)P(x). Sam izraz P(x)P(x) nema istinitosnu vrijednost, nema značenja, sam po sebi je besmislen. Parametar/argument xx mora biti iz neke kolekcije mogućih parametara, no ako ipak nismo odredili za koju vrijednost testiramo izraz tada kažemo da je xx slobodni ili nevezani parametar. Ako je PP predikat “biti paran broj” na skupu prirodnih brojeva tada je P(1)P(1) laž, a P(2)P(2) istina. Ako smo fiksirali koliko je xx tada znamo vrijednost P(x)P(x). Zanima nas slučaj kad je P(x)P(x) točan za svaku vrijednost od xx, što izražavamo rečenicom: za svaki xx vrijedi P(x)P(x) i pišemo (x)P(x)(\forall x) P(x). Taj izraz je istinit ako je za svaki broj stavljen umjesto xx izraz P(x)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 (xN)P(x)(\forall x\in N) P(x) gdje je NN skup prirodnih brojeva. Ekvivalentno možemo reći da je xx varijabla općeg tipa i da naknadno specificiramo u kvantificiranoj formuli da je xNx\in N, tj. (x)(xNP(x))(\forall x) (x\in N \wedge P(x)). Simbol \forall zovemo univerzalnim kvantifikatorom. U izrazu (xN)P(x)(\forall x\in N)P(x) jasno je za koje vrijednosti testiramo P(x)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 xx vezana varijabla (tj. nije slobodna). Ako gledamo samo izraz P(x)P(x) onda nije jasno gdje leži xx i unutar tog izraza xx nije vezana nego slobodna varijabla. Pitamo se na primjer da li su svi prirodni brojevi parni ? (xN)(paran(x))(\forall x\in N)(paran(x)). Nisu, jer 11 nije paran pa je cijeli izraz laž.

Izraz (x)P(x)(\exists x) P(x) (“postoji xx takav da je P(x)P(x)”) je drugi način određivanja kako testirati P(x)P(x). Taj izraz ima vrijednost istina akko postoji vrijednost parametra xx za koju je P(x)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)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

(x)((P(x)Q)((x)P(x)(y)(z)R(y,z))) (\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 (x)P(x)(\forall x)P(x) tada vrijedi i (x)P(x)(\exists x)P(x) (pri čemu u računu predikata podrazumijevamo da univerzalni skup nije prazan, inače P(x)P(x) ne bi imao niti jednu definiranu istinitosnu vrijednost pa ne bi bio predikat).

Jednakost == i kratice \neq i !x\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)=(x,y) pišemo x=yx = 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 (x)(y)(z)((x=y)(y=z))(x=z)(\forall x)(\forall y)(\forall z)((x = y)\wedge(y=z))\implies (x = z) (ako je neki xx jednak nekom yy i taj yy jednak nekom zz tada je i taj xx jednak tomu zz)

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

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

  • jednakost čuva vrijednost predikata: ako za ma koji predikat PP vrijedi P(x)P(x) i vrijedi x=yx = y tada vrijedi i P(y)P(y).

Npr. pogledajmo slijedeći izraz:

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

Taj izraz je uvijek istinit, za ma koji predikat PP s jednim argumentom: ako u PP 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 xyx \neq y je kratica za izraz ¬(x=y)\neg(x = y).

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

(x)P(x)(y)(z)((P(y)P(z))(y=z)) (\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 xx takav da vrijedi P(x)P(x) i ako vidimo bilo koja dva takva onda su oni jednaki. Dakle sve zajedno to znači da postoji točno jedan xx takav da vrijedi P(x)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 xx tipa AA to je kao da xAAx\in AA gdje je AA skup svih yy tipa AA. Možemo to promatrati i kao imati neko svojstvo AAAAAA, tj. da vrijedi AAA(x)AAA(x). Dakle, AAA(x)AAA(x) je vrijednost predikata AAAAAA na varijabli xx. No, moguće je direktno u kvantifikatoru napisati na koji tip se odnosi. Možda je dobro izbjeći pitanje postojanje skupa svih zz tako da vrijedi AA(z)AA(z) pa jednostavno reći da je xx tipa AA kao neki posebni sintaktički odnos, recimo x:Ax:A (xx je tipa AA). Dakle, neki pišu Ax\forall_A x umjesto x:A\forall x:A ili umjesto x,AAA(x)\forall x, AAA(x) ili umjesto x,xAA\forall x, x\in AA. Slično pišemo i Ax\exists_A x za x:A\exists x:A (postoji xx tipa AA).

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) 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.

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. x\forall x, čovjek(x)smrtan(x)(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 PP i QQ sudovi, i vrijedi PP i vrijedi PQP\implies Q tada vrijedi i QQ.

Kontrapozicija i modus tollens

Promatrajmo implikaciju PQP\implies Q. Njena kontrapozicija je implikacija ¬Q¬P\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 PQP\implies Q i ako vrijedi ¬Q\neg Q tada vrijedi ¬P\neg P. Ponekad kažemo zaključivanje od suprotnog.

Ako vrijedi za svaki tada vrijedi za neki

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

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

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

Vidimo da je to kontrapozicija prethodnog pravila.

Pokazanje (demonstracija) postojanja

Ako je cc konstanta nekog tipa QQ i vrijedi P(c)P(c) tada cc pokazuje da postoji neki xx za koji vrijedi P(x)P(x) naime x=cx = c pa možemo ustvrditi Qx,P(x)\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)Q(x) pa ovaj isti način zaključivanja postaje:

Q(c)Q(c) Quito je slijepac.

P(c)P(c) Quito nema novaca.

Qx,P(x)\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¬PP\vee \neg P. Do tog zaključka možemo npr. doći preko istinitostnih tablica.

Negacija negacije je afirmacija

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

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.

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.

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 (x)(\forall x) nema istinitu vrijednost u jeziku predikata, nego je nepotpuna, naime za svaki xx 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¬PP\wedge \neg P gdje je PP 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 PP koji je napisan u jeziku teorije vrijedi ili PP ili ¬P\neg P. Teorija je odlučiva ako postoji algoritamska procedura pomoću koje možemo za svaki sud PP odrediti da li vrijedi PP ili ¬P\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).

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 ee element skupa AA tada pišemo aAa\in A. Za negaciju iskaza aAa\in A pišemo aAa\notin A (aa nije element skupa AA). 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=BA = B ako i samo ako (a)(aAaB)(\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=AA = A i iz A=BA = B slijedi B=AB = A te

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

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

Postoji jedinstveni skup, kojeg zovemo prazan skup i označavamo \emptyset, sa svojstvom (a)(a)(\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 AA i BB skupovi, i svaki element iz AA je ujedno u BB, tada kažemo da je AA podskup od BB i pišemo ABA\subseteq B ili, ekvivalentno, da je BB nadskup od AA i pišemo BAB\supseteq A. Dakle,

ABBA(e)(eAeB) 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 AAA\subseteq A. Kažemo da je AA pravi podskup od BB ako je AA podskup od BB i različit od BB.

Relacija “biti pravi podskup” se ponekad također označava s ABA\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,

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

Drugim riječima, svi elementi od AA su elementi u BB i postoji barem jedan element od BB koji nije u AA.

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

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

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

Ako su a,b,c,,za,b,c,\ldots, z imena nekih objekata tada s {a,b,c,,z}\{a,b,c,\ldots,z\} označavamo skup SS čiji elementi su a,b,c,,za,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 SS ekvivalentna činjenici da je drugi u SS pa ga dakle možemo i izostaviti iz spiska. Npr. {a,a,b}\{a,a,b\} i {a,b}\{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 UU, tada aU\forall a \in U ima praktički isto značenje kao i a\forall a. Također tada {a|P(a)}={aU|P(a)}\{a | P(a)\} = \{ a\in U | P(a)\}.

Operacije na skupovima

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

  • presjek ABA\cap B skupova AA i BB,
    AB:={x|xAxB}, A \cap B := \{ x | x\in A \wedge x\in B \},
  • uniju ABA\cup B skupova AA i BB,
    AB:={x|xAxB}, A \cup B := \{ x | x\in A \vee x\in B \},
  • skupovnu razliku A\BA\backslash B skupova (ili diferenciju skupova) AA i BB,
    A\B:={x|xAxB}, A \backslash B := \{ x | x\in A \wedge x\notin B \},
  • simetričnu razliku ABA\triangle B skupova AA i BB,
AB:={x|(xAxB)(xBxA)}=(A\B)(B\A), 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 cA^c skupa AA u univerzalnom skupu UU,
    A c=U\A={x|xA}. A^c = U \backslash A = \{ x| x\notin A\}.

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

  • A(BC)=(AB)CA\cap (B\cap C) = (A\cap B)\cap C (asocijativnost presjeka)

  • A(BC)=(AB)CA\cup (B\cup C) = (A\cup B)\cup C (asocijativnost unije)

  • AB=BAA\cup B = B\cup A (komutativnost unije)

  • AB=BAA \cap B = B\cap A (komutativnost presjeka)

  • A(BC)=(AB)(AC)A\cap (B\cup C) = (A \cap B)\cup (A\cap C) (distributivnost presjeka prema uniji)

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

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

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

  • A=A\cap \emptyset = \emptyset

  • A=AA\cup \emptyset = A

  • c=U\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 AA i BB kad je A\BB\AA\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(BC)=(AB)CA\cap (B\cap C) = (A\cap B)\cap C možemo naprosto pisati ABCA\cap B\cap C bez zagrada. Međutim, izraz ABCA\cup B\cap C nema smisla, jer općenito A(BC)(AB)CA\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 11, 22, 33, pa pišemo A 1,A 2,A 3A_1, A_2, A_3 za tri skupa u nekoj množini AA. Indeksiranu množinu nazivamo još i familija skupova, a skupove A iA_i nazivamo članovima familije AA. Izraz A iA_i zovemo općim članom familije. Za indeks 11 imamo A 1A_1, za indeks 22 imamo A 2A_2 itd. Dakle samo indeksiranje, odnosno familija skupova je naprosto funkcija AA iz nekog skupa indeksa II u neku (još neindeksiranu) množinu skupova. U ovom slučaju {1,2,3}{A 1,A 2,A 3}\{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 iA_i gdje je ii element skupa indeksa. Npr. promatramo familiju skupova {A 1,A 2,A 3,A 4,}={A n} n\{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 iA_i gdje je ii paran broj, a ne vrijedi ako je ii neparan broj. Kako je iA ii\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)A(i). Odabir među A iA_i i A(i)A(i) samo je pitanje jasnoće i sugestivnosti oznake.

Definiramo presjek ma kakve familije skupova

iIA i={a|(iI)(aA i)} \bigcap_{i\in I} A_i = \{ a | (\forall i\in I) (a\in A_i)\}

i njenu uniju

iIA i={a|(iI)(aA i)}. \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 KK elemenata ako je kardinalnost skupa indeksa KK. Primijetimo da neki indeksi mogu indeksirati jednake skupove, recimo A 1=A 2A_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}\{3,4\}. Uređeni par (a,b)(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 aa i bb kao familiju od dva elementa, tj. funkciju {1,2}\{1,2\} u neki skup SS iz kojeg biramo elemente para. Slično možemo govoriti o uređenim nn-torkama elemenata iz SS kao familijama {1,2,,n}S\{1,2,\ldots,n\}\to S. Kartezijev produkt skupova A×BA\times B je skup uređenih parova iz ABA\cup B kojima je prvi element iz AA, a drugi element iz BB. Kuratowski definira uređeni par (a,b)(a,b) kao skup {{a},{a,b}}\{\{a\},\{a,b\}\}. Dakle daje informaciju skupa {a,b}\{a,b\} u kojem je posebno izdvojeno koji je prvi element {a}\{a\}. Ako je prvi i drugi element isti onda je u tom pristupu (a,a)={{a},{a,a}}={{a},{a}}={{a}}(a,a) = \{\{a\},\{a,a\}\} = \{\{a\},\{a\}\} = \{\{a\}\}.

Disjunktni skupovi i disjunktne unije

Kažemo da su skupovi AA i BB disjunktni ako AB=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,,A nA_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 iIA i=\cap_{i\in I} A_i = \emptyset. Npr. presjek tri skupa {a,b}\{a,b\}, {b,c}\{b,c\}, {a,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 AA i BB disjunktna onda kažemo za njihovu uniju ABA\cup B da je disjunktna unija i disjunktnost ponekad naglašavamo točkom nad znakom unije, dakle C=ABC = A\overset\cdot\cup B znači da je istovremeno C=ABC = A\cup B i da je AB=A\cap B = \emptyset. Slično možemo govoriti o disjunktnoj uniji iIS i\overset\cdot\cup_{i\in I} S_i,ma koje množine disjunktnih skupova {S i} iI\{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 AA i BB možemo elementima prvog skupa dodati oznaku AA, a drugog skupa oznaku BB. Dakle neka je A={1,2,3}A = \{ 1, 2,3\} i B={1,2,c,d}B = \{ 1, 2, c, d\} tada možemo gledati uniju {1 A,2 A,3 A}{1 B,2 B,c B,d B}={1 A,2 A,1 B,2 B,3 B,c B,d B}\{ 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 A1_A možemo formalizirati kao uređeni par (1,A)(1,A). Takvu disjunktnu uniju pišemo ABA \coprod B i ona se koristi kod definicije zbroja kardinalnih brojeva, u jednom od mogućih pristupa. Zaista, kard(A)=3kard(A) = 3, kard(B)=4kard(B) = 4, kard(AB)=3+42=5kard(A \cup B) = 3+4 - 2 = 5 (jer su dva elementa u presjeku) i kard(AB)=7=kard(A)+kard(B)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 iIA i\coprod_{i\in I} A_i ma koje množine skupova {A i} iI\{A_i\}_{i\in I} koji dakle ne moraju na početku biti disjunktni.

Particija skupa SS je prikaz skupa SS kao disjunktne unije iIS i\overset\cdot\cup_{i\in I} S_i, tj. unije neke množine već disjunktnih podskupova S iSS_i\subseteq S. Npr. {1,2,3,4,5,6}={1,2}{3,5}{4,6}\{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 paraoks.

Ako postoji skup svih skupova tada možemo govoriti i o njegovom podskupu SS čiji elementi su svi skupovi koji nisu elementi samog sebe. SS je element u SS ili SS nije element u SS. Ako SSS\in S tada po definiciji skupa SS mora biti da SSS\notin S. Ako pak SSS\notin S tada po definiciji skupa SS mora biti da SSS\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 suvremenom aksiomatskom teorijom skupova u kojoj nije nađeno proturječje.

Funkcije i relacije

Funkcija ili preslikavanje iz skupa AA u skup BB je pravilo koje svakom elementu skupa AA pridružuje točno određeni element skupa BB. Kažemo da funkcija svakom elementu u AA pridružuje jedan i samo jedan element skupa BB (to znači jedan i ništa više, tj. točno jedan). Skup dom(f)=Adom(f) = A zove se domena ili područje definicije funkcije ff, a skup cod(f)=Bcod(f)=B kodomena ili područje vrijednosti funkcije ff. Kažemo također da je ff definirana na skupu AA i da prima vrijednosti u skupu BB. Pišemo f:ABf : A\to B (ili, grafički naglašenije, AfBA\overset{f}\longrightarrow B), a rezultat pridruživanja ff na elementu aa je f(a)f(a). Ako je f(a)f(a) zadano (recimo kao formula) onda pišemo f:af(a)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 RR iz AA u BB je bilo koji podskup RA×BR\subseteq A\times B Kartezijevog produkta A×B={(a,b)|aA,bB}A\times B = \{(a,b) \,|\,a\in A, b\in B\}, odnosno skupa svih uređenih parova kojima je prvi element iz prvog skupa AA, a drugi element iz drugog skupa BB. Ako je neki (a,b)R(a,b)\in R pišemo aRba R b i kažemo da je aa u relaciji RR s bb. (Binarna) relacija na skupu AA je bilo koja relacija iz AA u AA. Slično tome, ako je nn prirodni broj, nn-arna relacija na skupu AA je bilo koji podskup Kartezijevog produkta A×A××AA\times A\times \ldots \times A (AA se pojavljuje nn-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 “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.

Funkcijska relacija ff iz AA u BB je binarna relacija fA×Bf\subseteq A\times B s dva svojstva

  • ako je aAa\in A tada postoji element bBb\in B takav da afba f b

  • ako je afba f b i afca f c tada je b=cb = c (drugim riječima, postoji najviše jedan element u BB koji je u relaciji ff s AA)

Ta dva svojstva zajedno daju da za svaki element aa u AA postoji točno jedan element bb u BB takav da je afba f b.

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

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

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

Za svaku binarnu relaciju RR iz AA u BB može se definirati inverzna relacija R 1R^{-1} iz BB u AA ovako: bR 1ab R^{-1} a onda i samo onda ako aRba R b. Ako je RR 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:ABf:A\to B je injekcija ako iz aaa\neq a' slijedi f(a)f(a)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 ff nekog podskupa XAX\subset A je skup f(X)={bB|xX,f(x)=b}f(X)= \{b\in B\,|\,\exists x\in X,\,f(x) = b\}, dakle skup svih elemenata koji su pridruženi barem jednom elementu iz XX. Ako je A=XA = X kažemo da je f(A)=Im(f)f(A) = Im(f) slika domene od ff ili kratko slika funkcije ff. Funkcija je surjekcija ili “preslikavanje na” ako je Im(f)=BIm(f) = B. Tada kažemo i da je funkcija f:ABf:A\to B funkcija s AA na BB, što je jača tvrdnja nego kad kažemo da je iz AA u BB (ovo potonje ne znači da je ff 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:ABf:A\to B i g:BCg:B\to C funkcije (primijetimo: domena od gg se podudara s kodomenom od ff), tada je definirana složena funkcija (sinonim: kompozicija funkcija) gf:ACg\circ f:A\to C funkcija s domenom AA i kodomenom CC i zadana pravilom

(gf)(a)=g(f(a))aA. (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,CA,B,C različiti, gfg\circ f je definirano, a fgf\circ g nije ni definirano, a kamoli jednako gfg\circ f. Naime, gg prima vrijednosti u skupu CC, pa odande ne možemo nastaviti funkcijom ff, jer funkcija ff ima za domenu ACA\neq C.

Identiteta na skupu AA je funkcija id A:AAid_A:A\to A zadana “tautološkim” pravilom id A:aaid_A :a\mapsto a. Ako je f:ABf:A\to B funkcija, tada fid A=f=id Bff\circ id_A = f = id_B\circ f.

Ako je CDC\subseteq D tada formula

i C:cc, i_C : c\mapsto c,

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

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

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

Ekvipotentni skupovi i kardinalni brojevi

Dva skupa AA i BB su ekvipotentni ako postoji bijekcija s AA na BB. Biti ekvipotentan je relacija ekvivalencije. Zaista,

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

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

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

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 55 je apstraktno svojstvo koje karakterizira sve skupove od 55 elemenata. Skup od 55 salveta je predstavnik te klase, dakle predstavnik kardinalnog broja 55. 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)kard(T)kard(S)\leq kard(T) ako postoji injekcija iz SS u TT. U teoriji skupova (s aksiomom izbora) svaka dva skupa su usporediva u smislu da ili kard(S)kard(T)kard(S)\leq kard(T) ili kard(T)kard(S)kard(T)\leq kard (S), a (prema Cantor-Schroeder-Bernsteinovom teoremu) oboje vrijedi akko kard(S)=kard(T)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<H(LHLH).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 0\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 02^{\aleph_0}, tj. postoji bijekcija 𝒫()\mathbb{R}\to \mathcal{P}(\mathbb{N}).

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

P ϕ={sS|ϕ(s)=1}. P_\phi = \{ s\in S | \phi(s) = 1\}.

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

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

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

Dokaz. To je očito ako je K=0=kard()K=0 = kard(\emptyset) (postoji injekcija u svaki skup, ali ne postoji injekcija iz jednočlanog skupa {}\{\emptyset\} u \emptyset).

Neka je K=kard(S)>0K = kard(S)\gt 0. Tada postoji injekcija iz SS u 𝒫(S)\mathcal{P}(S) zadana formulom x{x}x\mapsto \{ x\}, xS\forall x\in S. Trebamo pokazati da SS nije ekvipotentan s 𝒮\mathcal{S}. Pretpostavimo suprotno, dakle da neka surjekcija f:S𝒮f: S\to\mathcal{S} postoji. Promatrajmo skup R𝒫(S)R \in\mathcal{P}(S),

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

Tada postoji element uSu\in S takav da je f(u)=Rf(u) = R (jer je ff surjekcija). Ako je uRu\in R tada uf(u)u\in f(u) pa uRu\notin R po definiciji od RR, a ako uRu\notin R onda uf(u)u\notin f(u) pa uRu\in R po definiciji od RR. Dakle, ni jedna od mogućnosti uRu\in R, uRu\notin R nije konzistentna. Dakle, nije moguće da postoji surjekcija s SS na 𝒫(S)\mathcal{P}(S).

Konačni i beskonačni skupovi

Skup SS je konačan ako ne postoji bijekcija f:SPf:S\to P na neki pravi podskup PSP\subseteq S. Drugim riječima, skup je konačan ako nije ekvipotentan ni jednom svom pravom podskupu. Skup SS je beskonačan skup ako nije konačan, dakle ako postoji bijekcija s SS na neki pravi podskup PSP\subseteq S. Npr. skup prirodnih brojeva \mathbb{N} je beskonačan jer je skup parnih brojeva PP ekvipotentan s \mathbb{N}. Zaista, pridruživanje koje prirodnom broju nn pridružuje parni broj 2n2 n je bijekcija s \mathbb{N} na PP (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}.

Partitivni skup

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

𝒫(S)={P|PS} \mathcal{P}(S) = \{ P | P\subseteq S\}

Kardinalni broj skupa 𝒫(S)\mathcal{P}(S) je 2 kard(S)2^{kard(S)}. Npr. kardinalnost praznog skupa je 00, 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>K2^K\gt K.

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

P ϕ={sS|ϕ(s)=1}. P_\phi = \{ s\in S | \phi(s) = 1\}.

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

Created on November 6, 2017 at 09:55:50. See the history of this page for a list of all contributions to it.