Relacija (R) na skupu S je antisimetricna ako razliciti elementi nisu u odnosu

TEORIJA SKUPOVA, MATEMATICKA LOGIKA

- Skup je konacna ili beskonacna kolekcija objekata u kojem raspored nema znacaja, i ponavljanje je takodje ignorisano. Clanovi skupa se nazivaju elementima i notacija se upotrebljava da kaze da je a element skupa A.

- Pod partitivnim skupom nekog skupa A podrazumevacemo skup svih njegovih podskupova:

- Unija dva skupa A i B je skup stvoren kombinovanjem clanova oba skupa. Unija skupova do se pise .

- Presek dva skupa, A i B, je skup elemenata zajednickih za A i B. Ovo se pise i naziva se i inkluzija. Presek skupova do pise se .

- Skup B je podskup skupa A, ako svaki clan skupa B je clan skupa A. Ovo je ekvivalentno logickoj operaciji implikacije, cija je definicija «ako je A tacno, onda je B takodje tacno». Implikacija je jednaka .

- Dati skup S sa podskupom E, komplement skupa E definisan je kao: ako je .

- Razlika skupova se definise kao: a pise se i kao .

- Neka postoje skupovi E, F, i G. Onda operacije nad ovim skupovima upotrebljavajuci i su:

1) komutativne: ,

2) asociativne: ,

3) distributivne: ,

- Teorema teorije skupova i logike kaze da za sve skupove A i B, a za sve elemente Recima, Poretskijev zakon kaze «q je jednako [(p i ne q) ili (ne p i q)] ako p je netacno.

P	Q	(P and not Q) or (not P and Q)
0	0	0
0	1	1
1	0	1
1	1	0

- Familija je termin za kolekciju objekata i pise se . Unija i presek familije, odnosno funkcije skupova pisu se . Prema definiciji, ako termini pripadaju skupu X, funkcija skupova je mapa , gde za sve . Kako je svaki skup X daje funkciju skupova

- Ako A «postoji», ovo se pise kao (egzistencijalni kvantifikator). Slicno tome, «A ne postoji» pise se . Operacija «za sve» je (univerzalni kvantifikator).

- Imamo beskonacne distributivne zakone:

, , gde ide kroz bilo koji index skup . Index skup je skup ciji clanovi indeksiraju (obelezavaju) clanove drugog skupa. Na primer, u skupu , skup K je index skup skupa A.

- Relacija je bilo koji podskup kartezijskog produkta. Na primer, podskup , zvan «binarna relacija od A do B», je kolekcija uredjenih elemenata (a,b) sa prvom komponentom od A i drugom komponentom od B, i podskup od zovemo «relacijom od A». Za binarnu relaciju R, cesto se pise , da oznaci da (a,b) je u R.

- Relacija (R) na skupu S je antisimetricna ako razliciti elementi nisu u odnosu. Drugim recima xRy i yRx zajedno dokazuju da je x=y.

- Relacija R skupa S je refleksivna ako za svako x u S. Refleksivno zatvaranje binarne relacije R skupa X je minimalna refleksivna relacija od X koja sadrzi R. Tako, za svaki element a skupa X i za distinktivne elemente a i b, . Ovo je relacija jednakosti na bilo kom skupu.

- Relacija R skupa S je simetricna ako za svako x i y u S imamo ako . Ova relacija je relacija paralelnosti u skupu pravih jedne ravni. Dolazi do preslikavanja svake prave iz skupa A preko X=Y prave i nastaje skup od beskonacno paralelnih pravi koji je inverzan skupu A.

- Relacija R skupa S je transitivna ako za svako x,y, i z u S, i , tako da je

Graf G je tranzitivan ako bilo koje tri koordinate (x,y,z) su takve da strane sto dokazuje . Ova relacija je relacija slicnosti u skupu trouglova.

- (R) Relacija <= je relacija potpunog poretka na skupu racionalnih brojeva Q.

(A) Ako je X proizvoljan skup i P(X) njegov partitivni skup, relacija inkluzije je relacija poretka na P(X) koji nije totalni.

(T) U skupu prirodnih brojeva N relacija deljivosti | je relacija poretka koji nije totalni.

- Ako postoji majoranta skupa A koja pripada tom skupu ona se naziva maksimumom skupa A.

Relacija ekvivalencije

- Za relaciju na skupu X kazemo da je relacija ekvivalencije ako zadovoljava (R),(S),(T):

(R) – Relacija jednakosti na bilo kom skupu je relacija ekvivalencije.

(S) – Relacija paralelnosti u skupu pravih jedne ravni je relacija ekvivalencije.

(T) – Relacija slicnosti u skupu trouglova je relacija ekvivalencije.

- Neka je r relacija ekvivalencije na skupu X. Tada je jednoznacno odredjena podela skupa X na podskupove Ai tako da vazi:

Klase Ax, xeX, definisemo na sledeci nacin: Ax={yeX|xRy}. Tada svojstva (1) i (2) slede iz refleksivnosti relacije R (jer xeAx za svako x). Ako je (3) netacno, odnosno ako klase nisu disjunktivne, noe se poklapaju – preko simetrije i tranzitivnosti. Svojstvo (4) je na drugi nacin iskazana definicija klase Ax.

- Skup svih klasa ekvivalencije naziva se kolicnicki skup i oznacava se sa X/r. Za (R) on se moze poistovetiti sa samim skupom na kome je jednakost definisana, za (S) to je skup svih pravaca u ravni, a za (T) to je skup klasa koje cine svi medjusobno slicni trouglovi. Prema zakonu slicnosti trouglova, dva trougla su slicna ukoliko su im sve stranice proporcionalne, ukoliko su uglovi isti, ukoliko je jedan ugao jednak i dve stranice proporcionalne, ili ako su dva ugla jednaka i duzina jedne strane definisana, sto dokazuje tranzitivnu teoremu: ako je jedan element u relaciji sa drugim, drugi sa trecim, onda je i prvi element u relaciji sa trecim elementom, tako da slicnost postoji.

-Svaka relacija ekvivalencije skupa deli taj skup na disjunktivne, neprazne podskupove cija je unija citav skup. Takva podela naziva se particija skupa.