T.D.D.K. - Tanuljunk Dimatra De Kurvagyorsan

[Never Ever Done] Edition

Eloszo

Na nezzuk. Dimathoz kell sok-sok tetel es fogalom. Ezen az oldalon ilyesmiket akarok egyszeruen elmagyarazni, ahogy en megertettem oket. A celom, hogy minden fogalmat azonnal egy eszkozkent, nem pedig akadalykent vezessek be. Igy a legtobb dolog ugy fog kinezni, hogy egy fogalom reszet (vagy egeszet) elso ranezesre valszeg nem erted meg, de utana minden reszet elmagyarazom. Ofkorsz en sem tudok mindent, igy ha valami hibas, a footerben van link az elerhetosegemhez. Amugy mocskosul sokat tanultam innen, illetve az eloadasok diasorabol. Meg figyeltem eloadason is nehafelfullel. Linalg itt.

/!\ Disclaimer /!\

Nagyon fontos, hogy az itt leirtak CSAK a megertest segitik. Sok helyen csak elmagyarazok dolgokat, es nem irom le formalisan, meg csak ugy megjegyzem, hogy "ja ennek ez a jele". Erosen ajanlom, hogy ha valaki nem tud formalizalni dolgokat, nem tudja a jeloleseket, akkor miutan megert itt egy temat, azonnal nezze meg hozza a formalizalast.

Tartalomjegyzek

Ha valami [WiP], akkor eppen dolgozok rajta.
Ha valami [SOONish], akkor meg el sem kedztem.
Ha valami [nFIX], akkor reszemrol kesz, de nem erzem teljesnek.
Az ilyen fejezetekben a linkek nem mindig mukodnek.
  1. Halmazok
  2. Reláciok
  3. Halmazok+
  4. Függvények
  5. Műveletek [nFIX]
  6. Halmazok++ [nFIX]
  7. Csoportok
  8. Gyűrűk
  9. Testek
  10. Komplex számok
  11. Logika <== Itt kezdd ha nem tudsz formalizalni!
  12. Oszthatóság [WiP]
  13. Bizonyítások [WiP]
  14. Egyeb [WiP]

Halmazok

Elegge Adam-Evatol kell kezdeni a tananyag felepiteset, harom okbol kifolyolag. Eloszor is, hihetetlenul sok sok sok kesobbi dolog lesz halmazokra visszavezeheto. Szinte minden. Masodszor mert baszottsok tetel ezekrol szol, es harmadszor pedig van aki ugysem tudja. Amugy ez a fejezet szandekosan hianyos, vannak olyan dolgok amiket csak az ert meg, aki mar tudja a relaciokat. Ha mar fasza vagy, ide katt.
Egy halmaz ugye elemek osszessege, sorrend nelkul. Ezek az elemek lehetnek szamok, karakterek, fuggvenyek (amik halmazok), halmazok, muveletek (amik halmazok), matrixok, testek (amik halmazok), stb. Az elemeket meg tudjuk szamolni, meg mindenfele muveleteket tudunk vegrehajtani halmazokon. A halmazokat egy nagy U (vagy X) univerzumban szokas elkepzelni, ami minden elkepzelheto dolgot magaba foglal.
Ket halmaz osszehasonlitasahoz az egyik alap fogalom a reszhalmaz. Ha A es B halmazok, es A minden eleme benne van B-ben, akkor A reszhalmaza B-nek, illetve ha ugyanez a relacio fennall, de B-nek vannak elemei A elemein kivul, akkor A valodi reszhalmaza B-nek (mert nem egyenloek). Formalisan, B = {x eleme A | F(x)} Az F(x) itt nem egy fuggveny (sortof de az), hanem egy formula, valoszinuleg a jelntese "eleme-e B-nek".
Trivi cucc, de emlitsuk meg az ureshalmazt. Jele athuzott karika, es nincsenek elemei. Leirva halmazosan: {}. Megjegyzem az ures halmaz hatvanyhalmaza nem lesz ures, mert az {{},{{}}} (az ureshalmaz, es az ureshalmazt tartalmazo halmaz) lesz. Ja igen, es ureshalmazbol csak egy van, a meghatarozottsagi axioma miatt, illetve az ureshalmaz minden halmaz reszhalmaza.
Az emlitett hatvanyhalmaz egy halmaz elemeinek osszes lehetseges halmazza valo permutalasa. Szoval ha a halmazom {0,1,2}, akkor a hatvanyhalmaza {{},{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}. Mindig az ureshalmaz az elso, es az eredeti halmaz az utolso eleme, illetve a hatvanyhalmaz elemeinek szama 2 az eredeti halmaz elemeinek szama hatvanyon. Itt 23 = 8. Ertelemszeruen H elemei kozul mind A reszhalmaza, es az utolsot leszamitva mind valos reszhalmaza.
Van ket nagyon alap muvelet, ami kb mindig a logikabol indul ki. Es, vagy. Ezek altalaban a szorzas es osszeadas, de halmazoknal a metszet es unio. Ha A es B halmazok, akkor A es B unioja (altalaban AUB) minden elem ami A vagy B eleme. Ismetlodes nincs. Formalisan {x | x eleme A ˇ x eleme B} (ˇ a logikai vagy jele).
Ha A es B halmazok, akkor a metszetuk az olyan elemek halmaza, amiben az osszes kozos elemuk benne van. Formalisan: {x eleme A | x eleme B}.
Na most, az unio es metszet alaptulajdonsagai szinte ugyanazok. Mindegyik kommutativ (A muvelet B = B muvelet A), asszociativ ((A muvelet B) muvelet C = A muvelet (B muvelet C)), disztributiv (A muvelet (B masikmuvelet C)) = (A muvelet B) masikmuvelet (A muvelet C)), es idempotens (A muvelet A = A). Ezen kivul A unio {} = A, illetve A metszet {} = {}. Vegul pedig ha A B reszhalmaza, akkor A unio B = B, illetve A metszet B = A.
Eddig csak sima elemekkel gondolkoztunk halmazokon belul. De egy elem, ahogy az elejen leirtam lehet egy egesz halmaz is (ilyen pl.: a hatvanyhalmaz is, aminek minden eleme halmaz). Ilyenkor az eredeti halmaznak minden benne levo elem tovabbra is egy eleme marad, de "osszetett tipuskent" gondolhatunk ra. Kesobb majd mindenfele kacifantos megfogalmazok meg szabalyok lesznek halmazokra (pl.: archimedeszien rendezett nullosztomentes egysegelemes kommutativ integritasi tartomany). Egy halmazokbol allo halmazt nevezhetunk halmazrendszernek. Az ilyen halmazrendszerekre kulon felirasa van az unionak es metszetnek. Ha H halmazrendszer, akkor UH az az olyan elemek osszessege, hogy H valamelyik elemeben benne vannak (mivel H elemei ugye halmazok). Hasonloan irhato fel a metszet, es hasonloan is kell vegigondolni. Az olyan elemek osszessege amelyek minden H beli halmazban bent vannak.
Halmazokat nem csak osszevonni, hanem kivonogatni is lehet. Ha A es B halmazok, akkor A es B kulonbsege A\B (A-bol B). Az olyan elemek, amik A-ban bennevannak, de B-ben nem. Formalisan: {x eleme A | x nemeleme B}. Egy masik dolog a szimmetrikus differencia, ami A es B halmaz minden elemet veszi, kiveve ami mindkettoben bennevan (ami ugye a metszetuk). Azaz olyan elemek, amik vagy A vagy B elemei. Ez a kizaro vagy, szoval formalisan: {x eleme A | x eleme A ¤ x eleme B}, es ez ugyanaz mint (A\B)U(B\A). Amugy nemtom, hogy ¤ a kizaro vagy jele-e, de eleg kozel all hozza. Vegul ilyen kivonogatosdi meg a komplementer. A komplementere minden elem, ami nincs A-ban. Szoval ha A valodi reszhalmaza B-nek (es nincs semmi mas a terben), akkor A komplementere B\A.
A legtobb muvelet ugyanolyan halmazt eredmenyez, mint amilyenre alkalmaztuk. Szal ha ket halmaz elemei szamok, akkor a metszetuk is az lesz. Viszont egy halmazrendszer metszete egy szamokbol allo halmaz. Na van meg egy par muvelet, ami masfajta halmazt eredmenyez. Ilyen generalo eszkoz a Descartes szorzat. Gyakorlatilag nehany rendezett szampar. Ha A = {0,1} es B = {2,3}, akkor AxB Descartes szorzat: {0,1}x{2,3} = {{0,2},{0,3},{1,2},{1,3}}. Formalisan: {(x,y) | x eleme A ^ y eleme B}. Egy Descartes szorzat mindig rendezett parokat allit elo. Az ilyen rendezett parok (x,y) formaban irhatoak fel (pl.: vektorok). Az elemeket koordinataknak (vagy komponensnek, miven nem biztos, hogy szamok az elemek) nevezzuk, itt x az elso, y a masodik koordinata. Formalisan: {{x},{x,y}}. Oszinten, ez a formalis leiras mogotti ertelmi tartalomra nem jottem ra, de biztos fasza. A rendezett parokban a rendezett szo fontos, szoval (1,2) (1-hez rendelem 2-t) nem ugyanaz mint (2,1) (2-hoz rendelem 1-t). A relacioknal ra fogunk jonni miert, most legyen eleg, hogy a sorrend szamit.

Reláciok

Ez a temakor volt szamomra legnehezebben megertheto, szoval mindent megprobalok majd nagyon szajbaragosan elmagyarazni, hogy az egesz nagymamabiztos legyen. Megjegyzem a relaciok gyakorlati anyaga sokkal egyszerubb mint a mogotte allo elmelet, de ha az ember egyszer raerez, akkor hirtelen sok minden ertelemszeru lesz.
A relacio szorol nekem elsore mindig a < > (kisebb-nagyobb relacio) jelek jutottak eszembe. Ez valahol helyes, es segit bizonyos dolgok megerteseben, de sok lenyegi dolgot kizar az ember goldolkodasmodjabol. A relaciok nem maguk a muveletek, nem csak a jelek ket ertek kozt. Az elozo fejezetben utaltam ra, hogy a relaciok (is) halmazok, egy halmaznak pedig elemei vannak. Egy relacio(halmaz) elemei altalaban rendezett parok, hogy a relacio(halmaz)on ertelmezett muvelet igaz rajuk. Az ilyen rendezett par elemek "erteke" pedig az az eredmeny, amit akkor kapunk, ha a rendezett par elemeire rahuzzuk a relaciot. Szoval ha R relacio az osszeadas muvelet, es R eleme (1,2) (rendezett par, nem {1,2} halmaz), akkor 1R2 ugyanaz, mintha azt irnam 1+2, es az erteke 3. A relaciok, mint fuggvenyek vagy lekepezesek, egy halmazbol egy masikba "visznek" minket. Itt rogton az is kiderul, hogy ezek a halmazok nem szuksegszeruen ugyanazon a dimenzion vagy "tipuson" vannak, hisz a kezdo halmazunkban rendezett parok voltak, az eredmenyhalmazban meg sima szamok.
Meg egyszer osszefoglalva, a legtobb relacio VALAMIBOL->VALAMIT csinal, es a VALAMIBOL-ok halmaza a relacio ertelmezesi tartomanya, a VALAMIT-ek halmaza a relacio ertekkeszlete. Ez majdnemformalisan felirva: {olyan VALAMIT EK-bol | hogy van VALAMIBOL ET-bol : es VALAMIBOL relacio VALAMIT}. Tenylegesen formalisan peldaul: {x eleme X | letezik y eleme Y : y = x2} (ez a masodfoku fuggveny definicioja relaciokent). Ez a leiras a relacio eredmenyeit/mukodeset irja le. Nem magat a relaciot, mert az altalaban ugye rendezett parokbol all. Ez az amit at kell latni. Ha R relacio (altalaban) rendezett parok halmaza, ami elemeire azok koordinatainak sorrendjeben igaz R relacioban foglalt szabaly (muvelet), akkor a relacio(halmaz) elemeibol tudunk egy masik halmazt lekepezni.Picit jobb megfogalmazas: Egy relacio egy eszkoz, amivel egy halmazbol (ertektartomany) egy masikba tudunk lepni (ertekkeszlet). Peldaul, most csak szamoknal maradva, legyen a kiindulo halmazunk a paros szamok halmaza, es mi a paratlan szamokat akarjuk. Akkor legyen a relacionk a rakovetes muvelet, ami minden szamhoz egyet ad. Vagy, legyen egy egyenes pontjai, tetszoleges koordinataval a kiindulohalmaz, amibe lekepezunk pedig legyen az x tengely. Ilyenkor a relacio egy linearis lekepezes, vagy definialhatunk sajat muveletet, ami legyen mondjuk az elso koordinata kivalasztasa (persze ha az az x tengelyen valo tavolsag).
Okes. Eddig mindig odabiggyesztettem, hogy a relaciok elemei altalaban rendezett parok. Az egyszeruseg kedveert egyelore mondjuk azt, hogy harom fele relacio van, es ez hatarozza meg az elemeik "tipusat" (igazabol az elemeik szamossagat). A biner relaciok ket dolog kozt allnak fent. EZRAZ, vagyis EZ R relacioban all AZal. Ezert is a biner relaciok elemei (mert ugye a relaciok halmazok) rendezett parok. Azert fontos, hogy rendezettek, mert vannak nem kommutativ muveletek. Pl. ha A es B matrix, es R a matrixszorzas muvelet, akkor ARB es BRA nagyon nem ugyanazt az eredmenyt adja. Akkor vannak az uner relaciok, amikhez csak egy dolog kell. Ilyen mondjuk a negacio. Ha R a negacio, akkor RVALAMI, az VALAMI negaltja. Aztan vannak a nuller relaciok, amik az ureshalmazbol indulnak ki (szoval R az ureshalmazt tartalmazo halmaz valami muvelettel), azaz nincsenek elemeik. De megiscsak elerheto az ilyen relaciokon at egy ertek. A felirasat ilyen egyszeruen nem tudom, de ha X halmazbol kepzek le valamit R nuller relacioval, akkor R:{{}}->X (R az ureshalmazt tartalmazo halmazbol valasztott elembol X-bol valasztott elemet kepez). Magyarul az ilyen relacio egy X halmaz egy elemenek kivalasztasa. Ja igen, a biner relaciokhoz meg egy fogalom jon. Ha R biner relacio elemeit egy XxX Descartes szorzattal csinaltuk, vagyis minden rendezett par koordinatai paronkent ugyanazok ({(1,1),(2,2),(5,5),(CICA,CICA),stb}) akkor R homogen biner relacio. Plusz aki mostanra atlatja picit a dolgot, az azt is eszreveheti, hogy ha R biner relacio XxY (Descartes szorzat) rendezett parokbol van, akkor R az XxY (Descartes szorzat) reszhalmaza. Nem biztos, hogy valos, mert lehet, hogy XxY nem minden elemere lesz ertelmezheto a relacio.
Most, hogy tudjuk, hogy egy relacio(halmaz) valami halmazbol valami mas halmazt csinal (akar az ureshalmazbol is), vezessunk be ket uj fogalmat, amik kb ugyanazt jelentik majd csak oda-vissza. Ha R es S is biner relacio, es S reszhalmaza R-nek, akkor S leszukitese R-nek, R pedig kibovitese S-nek. Ez mogott az az elmelet, hogy S az egy halmazbol egy masikat csinalt a benne levo elemek alapjan. Na R-ben megvan minden ilyen elem, es megtobb. Szoval megcsinalja ugyanazt mint S, es meg tobbet, ezzel kibovitve a kapott ertekek halmazat. Leszukiteni lehet sima halmazzal is, nem csak relacioval, es akkor annyi a kulonbseg, hogy ha R biner relacionak voltak elemei, amikbol lekepezett valami mas ertetkeket, es en egy mezei A halmazra akarom leszukiteni, akkor nem R ertelmezesi tartomanyabol fogom venni az elemeket, hanem A halmazbol. Szal ha R az XxY volt, akkor A szerint szukitve AxY lesz Formalisan: R|A = {(x,y) eleme R| x eleme A}.
Relaciot halmazzal nem csak szukiteni lehet, hanem valami halmaz szerinti kepet is lehet venni. Ez picit trukkosebb. Mig R|A a kiindulo halmazt modositotta, R(A) (R A szerinti kepe) ertekeket fog visszaadni. Ezek az ertekek ugy allnak elo, hogy ha R biner relaciobol egy (x,y) rendezett part kiveszunk, akkor ha x eleme A, akkor az y amit keresunk.
Egy relaciot es annak kepet is lehet invertalni. Ezt ket felekeppen lehet, amibol az egyik mocskosul egyszeru, a masik meg gondolkozos. Ha R biner relacio elemei (x,y) rendezett parok, amik XxY Descartes szorzassal jottek letre, akkor R-1 (R inverze) ugyanilyen (y,x) parok lesznek. R(A)-1 pedig olyan y elemek, hogy R-bol vett (y,x)-bol x eleme A. Ez az egyszeru invertalas. A gondolkodosabbat akkor lehet hasznalni, ha egy relacio muvelete is meg van adva a formalis leirasban. Pl korabban irtam a negyzetfuggveny definiciojat, ahol R muvelete y = x2 volt. Itt, mint fuggvenyt lehet invertalni, vagyis x-re rendezzuk: sqr(y) = x.
Ahogy a halmazoknal volt a metszet es unio, ugy relaciokat is lehet "osszevonni". Ennek a neve kompozicio. Ha R es S biner relaciok, akkor RoS az a kompoziciojuk. Ezt ugy kell erteni, hogy ha R-ben van valami (x,z) elem, es S-ben van (z,y), akkor a kompozicioban (x,y) lesz. Azaz ha van kozos z elem R ET es S EK kozt, akkor ertelmezheto a kompozicio (egyebkent is ertelmezheto, de az ureshalmaz lesz). A kompoziciok amugy asszociativak, az inverzuk pedig: (RoS)-1 = S-1oR-1
Most jon az egyik legfontosabb resz a relaciokbol. Lesz egy par csilli-villi kifejezes, amivel relaciokat illetni lehet. Jellemzoen csak biner relaciokat, uner meg nuller neha nem is ertelmes igy. Ha egy R relacioban van (x,y),(y,z) es (x,z), vagyis ha xRy es yRz -> xRz, akkor R tranzitiv. Ha van (x,x) akkor R reflexiv. Ha van (x,y) es (y,x), akkor szimmetrikus. Ez a harom alap jellemzesi pont, picit mindjart csavarunk rajtuk, de elobb valami nagyon fontos: Ha R biner relacio elemei kozt van x meg y meg z szam is, es van (x,x) meg (y,y) meg (y,z), akkor NEM reflexiv, mert nincs (z,z). Az nem baj, hogy van elem (rendezett par), aminek nem ugyanaz mindket koordinataja, de az baj, hogy z-re nem relexiv a relacionk. Hasonloan a tranzitivitas es szimmetria MINDENre igaza kell legyen.
Akkor bovitsuk kicsit tovabb. Ha valami nem reflexiv, akkor azt mondjuk ra, hogy irreflexiv. Ez meg okes. Szimmetria ugye az volt, hogy ha xRy akkor yRx. Na az antiszimmetria nem azt mondja, hogy nincs ilyen, hanem hogy ha xRy es yRx igaz, akkor x es y biztos ugyanaz. A szigoru antiszimmetria mondja azt, hogy ha xRy akkor y!Rx, vagyis ha van R-ben (x,y) akkor nincs (y,x). Azt eszrevehetjuk, hogy a reflexivitas (akar van, akar nincs) a kezdeti halmaz(ok)tol fugg, a tobbi pedig a relacioba foglalt szabalytol (muvelettol).
Van meg ket ilyen jellemzo, amiket ritkan kell megnezni. R biner relacio dichotom, ha a kezdeti X halmazbol minden elemhez van (x,y) vagy (y,x). Ez majdnem ugyanaz mint a szimmetria, de van ket kulonbseg. Lenyegeben az a dichotomia, hogy X minden eleme valahogy ossze van parozva R-ben, de ottvan. A szimmetria nem koveteli meg, hogy X minden eleme ott legyen, mert lehet, hogy X-nek vannak elemei amire R nem lesz ertelmezheto. A masik ilyesmi jellemzo a trichotomia. R biner relacio trichotom ha vagy (x,y) bennevan, vagy (y,x) bennevan, vagy x = y. Fontos, hogy ezek kizaro vagyok. Csak az egyik teljesulhet. A trichotomiat ilyen visszafele modon kell nezni, szoval inkabb azt mondja meg, hogy mi nem teljesul a relacioban. Ezek is a kiindulo halmazokon mulnak, nem a relacion.
Ezt a nehany jellemzot nagyon kell tudni, mert most jutunk el a relaciok nagyon nehezen emesztheto reszehez. Innentol igazabol szinte teljesen elvesztettem magyarazhatoan kovetni a dolgokat, szoval olyan osszefuggesek lesznek, hogy azt tudom ra mondani igy van, igy kell megtanulni. Mindenesetre megprobalom majd a megertest segiteni, nem a magolast.
Ha egy R biner relacio tranzitiv, reflexiv es szimmetrikus, akkor ekvivalenciarelacionak hivjuk. Ezt ugy kell elkepzelni mint univerzalis egyenloseg (mint ahogy a nullelem univerzalis 0).
Ha egy R biner relacio tranzitiv, reflexiv es antiszimmetrikus, akkor reszbenrendezesnek hivjuk. Ez az a pont ahol tenyleg elszall alolam a talaj, es nem tudom, hogy a megnevezes mit is jelent valojaban. Valami olyasmi, hogy ha X es Y halmazok ra reszbenrendezes relaciot huzunk, akkor X majdnem ugyanaz mint Y, mert ugyanazt a halmazt lehet elerni ha ezekbol a halmazokbol kulon-kulon vesszuk R biner relaciot, de X es Y-nak vannak kulonbozo elemei, csak eppen ugyanazt az erteket adjak R-re. Szal ha mondjuk X = {0,1} es Y = {1,2}, es X elemeibol osszerakott meg Y elemeibol osszerakott R lekepezessel is a {3,4} halmazt erjuk el, akkor X es Y R szempontjabol ekvivalens, de valojaban megis kulonbozo, es ezert reszbenrendezes. Szerintem. De ezt ugy gondoltam at ahogy irtam, szoval lehet butasag. Okes, ezt mostmar kicsit jobban ertem. Szoval ha R:X->Y ekvivalenciarelacio, akkor X es Y R szerint ugyanaz. Ha reszben van rendezve, akkor is "ugyanaz", de a szimmetria csak akkor teljesul, amikor x eleme X = y eleme Y. Meg egy dolog, hogy ekvivalencia ugye az egyenloseg. De nem feltetlenul a halmaz teljes egeszere, es nincs kisebb-nagyobb elem, megelozes es kovetes. Mert egyenloseg van. Na most, ha valami rendezes, akkor valami alapjan rendbe rakja az elemeket, vagyis lesz megelozes, kezdoszelet es minden ilyesmi. Ha teljes rendezes (vagyis dichotom reszbenrendezes), akkor raadasul a halmaz egeszet rendezi.
Amit az elobb irtam, hogy ha R relacio reszbenrendezes, de dichotom is, akkor (teljes) rendezes. Emogott az a lenyeg, hogy a dichotomia kimondja, hogy X minden elemet felhasznaltuk (ezert teljes). Es azert nem ekvivalencia, mert megiscsak egyfajta reszbenrendezes (csak eppen az egesz X halmazt kihasznaljuk).
Hasonloan, ha R relacio valamilyen (reszben vagy teljes) rendezes, de szigoruan antiszimmetrikus, akkor szigoru (reszben vagy teljes) rendezes. Illetve, ha R egy szigoru reszbenrendezes (szigoru relacio), akkor egy ugyanolyan, de nem antiszimmetrikus (hanem siman szimmetrikus) reszbenrendezes a hozza tartozo gyenge relacio lesz. Visszafele ha egy (gyenge) relaciora (reszbenrendezesre) ra tudjuk huzni az antiszimmetriat, akkor az igy kapott relacio lesz a hozza tartozo szigoru relacio (ami valszeg reszbenrendezes). Ez oda-vissza igy mukodik.

Halmazok+

Bizonyos dolgokat (halmazok egyenlosege es annak tulajdonsagai, vegesseg, korlat, hatar, szamossag) elso nekifutasra nem irtam a halmazok koze, mert ehhez ismerni kell a relaciok cuccosait. Itt ezek lesznek. De lesz meg mindig olyan, amit kihagyok, mert ahhoz mar a fuggvenyek is kellenek.
Az elozo tema vegen megneztuk relaciok jellemzeset, es azt, hogy ezek a jellemzok alapjan milyen megnevezeseket huzhatunk rajuk. Egy ilyen a halmazok egyenlosege, vagyis az ekvivalencia. Ugye arrol tudjuk, hogy reflexiv, szoval egy halmaz mindig egyenlo onmagaval. Tranzitiv is, szal ha egy A halmaz = B halmaz, es B halmaz egyenlo C halmaz, akkor A meg C is egyenlo. Szimmetrikus es antiszimmetrikus is, mert ha A = B akkor B = A, es akkor ugye ugyanazok.
Elvileg mostanra ertjuk a reszbenrendezes es szigorusag fogalmat. Azt is sokszor eszrevettuk, hogy a relaciok is halmazok. Meg ugye azt is eszrevettuk, hogy relaciok valami szabaly alapjan kepeznek eredmenyt, es lehetnek effektive fuggvenyek is. Gondoljunk a negyzetfuggvenyre, vagy egy egyenlotlensegre, amiknek nem egy kifejezett szam az eredmenye, hanem eredmenyek halmaza, intervallumok. Na most az intervallumokat is meg lehet relaciosan fogalmazni. Ha X egy reszbenrendezett halmaz, vagyis R reszbenrendezes relacio ertelmeze van rajta, es x,y,z elemei X-nek, akkor ha zRx es yRz (pl kisebb relacional ha z > x es y > z) akkor z az x es y koze esik, vagyis a lehetseges z elemek halmaza az x-tol y-ig terjedo intervallum. [x,y] ha sima relacio, ]x,y[ ha szigoru relacio. Na ezek az intervallumok.
Megint jon egy fogalom amit kicsit nehezen ertettem meg, de az intervallum ha okes, akkor ezt is megerthetjuk. Ugye ha R reszbenrendezes, vagyis X reszbenrendezett halmaz (innen igy fogom irni), es x,y eleme X, es xRy, akkor minden olyan x elem, amire xRy felirhato (es ertelmezheto), az minden ilyen y kezdoszelete lesz (vagyis minden ilyen x megeloz minden ilyen y-t, es minden ilyen y kovet minden ilyen x-t). Felirva ]<-,y]. A nyilt/zart intervallum, meg hogy merre kezdoszelet az ugy jon ki, hogy: Ha a relacio szigoru, akkor ugye nyitottak az intervallumok az ertekeknel, a kezdoszelet oldalan pedig mindig azok.
Most mar ertjuk, hogy megeloz/kovet. Ezt felfoghatjuk majdnem ugy, mint kisebb vagy nagyobb, csak ugye az adott relaciora ertelmezve mindig. Pl ha R az oszthatosag, es az alaphalmazban benne van 2,4,8, akkor mivel 2R4 es 2R8 felirhato, igy 2 es 4 megelozi 8-t. Ha R relacio nem az oszthatosag, hanem az "osztoja" relacio, akkor forditva, 8R2 es 4R2 irhato fel, vagyis 8 es 4 megelozi 2-t, vagyis 8 es 4 R relaciora kisebb, mint 2. Ha egy halmazbol megkeressuk az elemet, ami mindent megeloz, az a legkisebb elem, es forditva, ami mindent kovet, az a legnagyobb. Megjegyzem nem biztos, hogy van ilyen elem, de lehet akar tobb is.
Ha egy elemet nem eloz meg semmi, vagyis o a legkisebb, akkor minimalis elemnek hivjuk. Ha nem koveti semmi, vagyos a legnagyobb, akkor maximalis. Ha ezt X halmaz elemein keressuk, akkor min(X) es max(X) a jelolese. Mivel lehet tobb olyan amit ugyanannyi kovet/eloz meg (magyarul ugyanaz a kezdoszeletuk, vagy ugyanolyan kezdoszeletei valaminek), ezek kozul minhez az "elsot" maxhoz az "utolsot" kell valasztani. Ha nincs legkisebb vagy legnagyobb elem, akkor {}.
Az ilyen kisebbsegnek/nagyobbsagnak van egyfajta felhasznalasa. Ha vannak X es Y (reszbenrendezett) halmazaink, es Y reszhalmaza X-nek, akkor X minden olyan eleme, ami nagyobb Y osszes elemenel (vagy max(Y)-nal), az felso korlat lesz Y-ra. Visszafele van az also hatar. Szal ha Y reszhalmaza X-nek, es X minden elem megelozi Y miden elemet (vagy a minimumjat), akkor minden ilyen x also hatar Y-ra. Egyertelmuen a relacio szempontjabol kell nezni. Na most, ha egy nem ureshalmaz halmaz felulrol korlatos, es van is felso korlatja, akkor felso hatar tulajdonsagu. Also korlattal ugyanez. Azt amugy nem tudom, hogy mi az, hogy felulrol korlatos ES van is felso korlatja, de biztos jo. Gondolom ha valami nem meghatarozhato intervallumba megy ki, akkor nem biztos, hogy van is korlat eleme, csak tudjuk, hogy korlatos. Gondolom.
Na most kombozzuk ossze az utobbi par fogalmat, es vezessunk be ket ujat. Megint legyen X es Y es Y legyen X reszhalmaza. Igy ha azt mondom, hogy Y alulrol korlatos, akkor X-ben lesznek olyan elemek, amik minden Y-t megeloznek. Az ilyen elemeket vegyuk egy kepzeletbeli kulon halmazba, es keressuk meg ugyanaz a relacio szerinti legnagyobb elemuket (nem maximumukat). Na az ilyenek lesznek Y infimumjai. Forditva, ha Y felulrol korlatos, szoval vannak X elemek, amik Y minden elemet kovetik, akkor ezek az X elemek kozul a legkisebb(ek) lesz(nek) Y supremumjai. Ezeknek a jelei inf(Y) es sup(Y)
Megint egy olyan fogalom ami egy kis fejtorest okozott nekem. Legyen X egy (reszbenrendezett) halmaz. Akkor ugye X hatvanyhalmaza megadja az osszes lehetseges X reszhalmazt (meg az ureshalmazt, de az most nem kell). Ha minden ilyen reszhalmazban van legkisebb elem, akkor X jolrendezett halmaz, es a rajta ertelmezett (reszbenrendezes) relacio jolrendezes.

Függvények

Ahogy a relacioknal es halmazoknal tobbszor mondtam, a fuggvenyek is relaciok, es cserebe halmazok. Jobban szolva olyan relaciok, amik szabalya "fugvenykent" van megfogalmazva, es fuggvenykent is viselkednek. Lenyegeben egy fuggveny egy olyan relacio, amibe ha ugyanazt a szamot berakod, csak ugyanazt dobja ki ra. Leirva: f:X->Y. Itt dmn(f) (altalaban X), az ertelmezesi tartomany, es rng(f) (altalaban Y) az ertekkeszlet. Ezeket a felirasokat relaciokhoz is lehet hasznalni, de itt lesz erdemleges haszna is.
Na most, ugye mar tudunk a reszhalmazokrol, meg ilyenek. El tudjuk kepzelni, hogy van egy nagy X es nagy Y halmaz, amik kozt f fuggveny (relacio) fennall. De nem minden X elembol tud csinalni valamit, es nem is er el minden Y elemet. Ezert irtam, hogy dmg meg rng csak altalaban X meg Y. Alapertelmezetten dmn(f) csak eleme (reszhalmaza) X-nek, es rng ugyanigy Y-nak. Ha nem valos reszhalmazok, tehat dmn(f) != X, akkor f is csak eleme X->Y-nak. Ha valosak, akkor lesz f pontosan a jo lekepezes, vagyis akkor mondhatjuk, hogy f : X->Y, egyebkent f eleme X->Y.
Ahogy kb minden temaban, itt is van nehany fogalom ami fontos sok dolog megertesehez. Eloszor is, egy fuggveny lehet kolcsonosen egyertelmu, azaz injektiv. Ez azt jelenti, hogy ha f : X->Y, akkor minden x-hez csak egy y tartozik, es mindegyik kulonbozo. Szal ha x -> y es x' -> y, akkor x = x'. Ilyenkor f-1 (f inverze) letezik. Aztan ugye irtam korabban, hogy f nem minden esetben eri ez az osszes Y erteket. Ha megis, akkor szurjektiv. Ha injektiv es szurjektiv is, akkor bijektiv. Majd kombinatorikanal meglatjuk, hogy a permutacio valojaban az, hogy ha egy halmazt rahuzunk egy injektiv fuggvenyre.
Relacioknal ugye volt a kompozicio, azaz egymasba gyurtunk ket relaciot. Fuggvenyekkel is ezt meg lehet tenni, es osszetetelnek hivjuk. f es g fuggvenyek osszetetelet gof-el jeloljuk (es az is fuggveny lesz). Lenyegeben f(g(x)). Ha f es g injektiv volt, akkor az osszeteteluk is az lesz, illetve ha sajat halmazaikra f es g szurjektiv volt, akkor gof is az lesz (ez azt jelenti, hogy ha f: X->Y es g:Y->Z akkor gof:X->Z szurjektiv lesz). Nyilvan bijekcio is igy mukodik.
Megint uj dolgok akkor, es itt osszetalalkozunk a halmazokkal nagyon. Ugye volt, hogy mit jelent hogy valami relacio szerint kisebb es nagyobb elemek. Megelozes es kovetes. Ha X es Y reszbenrendezett halmazok, es f : X->Y, akkor ha x megelozi (kisebb) y-t, es f(x) is megelozi (kisebb) f(y)-t, akkor f monoton novekvo. Ha x megelozi y igaz, de f(x) koveti f(y)-t, akkor f monoton csokkeno. Nyilvan ha f egy szigoru relacio, akkor szigoru monotonitas all fent. Amugy ha valami szigoru monoton, akkor biztos injektiv is, mert biztos minden elemehez mas ertek tartozik.

Műveletek [nFIX]

A relaciok fogalma jo volt ahogy volt, de nehol tul tag. Szukitsuk le a fogalmunkat most muveletekre. Ugye ezek lehetnek biner, uner es nuller relaciok. Ezt, es meg sok mindent a muveletekrol mar leirtam a relacioknal, de vannak dolgok, amiket csak a fuggvenyek utan ertunk.
Nezzuk is meg. Legyen X es Y halmaz, de Y-on legyen egy * biner muvelet ertelmezve. * helyett lehetne R, mivel az ugye egy relacio, de itt ez a jeloles szokasos, csoportoktol tovabb mar ez is lesz majd, es tudni fogjuk, hogy kifejezetten olyan relaciokra gondolunk, amire a muveletes cuccosok igazak lesznek. Szoval X es (Y,*), illetve legyen f es g fuggvenyek, amik X->Y. Na most vegyunk az osszes olyan f(x) es g(x) elemet, hogy f(x)*g(x)-t fel lehessen irni (es ertelme is legyen). Ugye f(x) meg g(x) is Y-beli lesz, mert rng az legalabbis reszhalmaza Y-nak. Na az ilyen x elemek halmazara azt a felirast hasznaljuk, hogy (f*g)(x). Na most, nezzuk csak az f fuggvenyt, ami ugye X->Y, ahol Y-on van * muvelet. Ha f(x*x') = f(x)*f(x'), akkor * (lekepezes) muvelettarto. Pl ha X es Y valos szamokon van, es * az a szorzas, vagyis x->x2, akkor * muvelettarto lekepezes, mert (ab)2 = a2b2

Halmazok++ [nFIX]

Egy kis follow-up a halmazokhoz, ide csak a legdurvabb fogalmak jonnek. Ezekhez sok mindent kell tudni a relaciokbol es fuggvenyekbol.
Ugye lattuk a halmazok ekvivalenciajat, azaz egyenloseget. Akkor nem hoztam be egy fogalmat, de nem is kellett. Ha ket halmaznak nincs kozos eleme, akkor az a ket halmaz diszjunkt. Meg volt ugye a hatvanyhalmaz is. A ketto osszerakva lesz az osztalyozas. Vagyis olyan hatvanyhalmazt csinalunk, amiben csak diszjunkt elemek vannak, amik kozul egyik sem az ureshalmaz. Csak eppen nem egy halmazba pakoljuk be ezeket az uj halmazokat, hanem egy halmazrendszert alkotunk beloluk. A jele O (ilyen furcsa O betu). X hatvanyhalmazanak elemeinek unioja ugye visszaadta X-t. Annak a jele ugye UH (unio H) volt. Mivel az osztaly kezdobetuje o, igy az osztalyok halmazrendszerenek uniojanak a jele UO (unio cifra O betu) lesz, es szinten visszaadja X-t.
A kovetkezo dolog az osztalyozasok es ekvivalencia kapcsolata lesz, de komolyan mondom, ez a legosszetettebb fogalom az egesz oldalon. Megprobalom a legerthetobben elmagyarazni, de en a fejem fogtam mire rajottem mi is van (az eloszoban linkelt oldalon 37-es feladat). Legyen egy X halmazunk, es egy R ekvivalenciarelacionk (szepen jelolve ~ lenne, de msot R lesz). Szoval a lenyeg, hogy minden ekvivalenciarelaciohoz tudunk rendelni egy osztalyozast. Es az osztalyozasban ugye halmazok lesznek. A halmazok elemei pedig olyan X beli x elemek lesznek, hogy valami mas X beli y elemre igaz a relacio, hogy xRy (x~y). Tehat minden x-re megnezzuk, hogy a halmaz melyik elemeivel ekvivalens, es berakjuk kulon halmazokba, aztan ezek a halmazok valahogy diszjunktak lesznek. Amugy ez elvileg forditva is igaz, szoval nem csak az ekvivalencia miatt lehet osztalyozas, de minden osztalyozas is megad egy ekvivalencia relaciot, ami olyan halmazrendszerunio lesz, hogy az osztalyozas elemeinek (amik halmazok) a Descartes-szorzatat kepzi, majd veszi az uniojukat. Ami valoban ertelemszeru, mert ha az osztalyozasban ugy voltak X elemei, hogy mindegyikben kulonbozo (de X beli) elemek vannak, akkor a Descart-szorzatuk, ami mindenhez mindent hozzarendel, minden X elemet visszaad, raadasul tobbszor is, es ezert kell az ilyen cuccok uniojat venni, hogy ne legyen ismetlodes, hanem a tenyleges X halmazt kapjuk vissza.

Csoportok

Okes, az elso dolog amit tudni kell az abra megertesehez, hogy mi ez: *:GxG->G. * egy biner relacio, egy lekepezes, talan fuggveny. A lenyege, hogy VALAMIBOL->VALAMIT csinal. Pl.: a sin fv az ugye [-1,1]->[-360,360]. * az nevezetesen egy GxG Descartes szozratbol sima G-ket csinal. * az ebbol a halmazbol csinal sima G elemet. Mondjuk ha * relacio az az osszeadas, akkor {1,2} *-ra lesz 1*2 (vagy 2*1), es az eredmeny 3. Igy lesz egy GxG elembol sima G elem.
Na, ez akkor elvileg tiszta. A kovetkezo az asszotiativitas es kommutativitas. Ha * kommutativ, akkor EZ*AZ ugyanaz mint AZ*EZ. Ha asszociativ, akkor EZ*(AZ*AMAZ) = (EZ*AZ)*AMAZ.
Most nezzunk a diagram jobb oldalara, es induljunk el befele. Semleges elem, mas neven egysegelem, az egy halmaz (a halmaz lehet relacio, fuggveny stb) olyan eleme, hogy ha valamit a halmazon ertelmezett relacioval veszed, akkor onmagat kapod. Legyen * most a szorzas relacio (ami ugye biner relacio, mert ket cucc kell bele). Ugye altalaban 1*5 = 5, igy 1 egysegelem G-ben (lehet tobb is). Ha * az osszeadas, akkor 1*5 = 6, igy 1 nem lesz egysegelem. De ha a halmazunkban matrixok az elemek, akkor ugye teljesen mashogy kell elkepzelni az egysegelemet (egy matrixkent). Ilyenkor, ha feltesszuk hogy * egy nem kommutativ muvelet, vagyis EZ*AZ nem ugyanaz mint AZ*EZ, akkor az egysegelemrol mondhatjuk, hogy jobboldali, illetve baloldali. Attol fugg, hogy a relacio melyik oldalan allva viselkedik egysegelemkent. Ha egy elem egyszerre jobb es baloldali egysegelem is, akkor szimplan egysegelemnek hivjuk.
Ez kicsit sok volt egybe, de a fogalom egeszet leirtam. Ez valami 4-5 tetel egyben. Nem is olyan durva. Na akkor jon az inverz elem. Nagyon hasonlo az egysegelemre, es sok koze is van hozza. Ha EZ*AZ = egysegelem, akkor EZ AZ-nak a baloldali inverze, AZ pedig EZ-nek a jobboldali inverze. Ha valami egyszerre jobb es bal inverz is, akkor siman inverzelemnek mondjuk. A diagramon levo megfogalmazasban az inverz lehet jobb, bal, vagy mindket oldali is, csak legyen valamilyen.
Ide egy kis raadast adok, mert szerintem ezek marha jo fogalmak. Gondoljunk picit bele a valos szamokon vett muveletekbe. Majd mindjart a gyuruknel lesz addicio meg multiplikativitas. Nah a lenyeg, hogy ezeket osszeadasnak es szorzasnak fogjuk hivni. A valos szamoknal az osszeadas a nullelemhez: x+y = 0, akkor y biztos -x, vagyis x ellentettje, mert ugye + "visszafele" -. Ez az additiv inverz. Ha szorzas az egysegelemre, vagyis x*y = 1, akkor y biztos 1/x. Ez a multiplikativ inverz, mert ugye * "visszafele" :. De majd latni fogjuk, hogy a szorzas es osszeadas, ugyan a nevuk ez marad, majd lehetnek teljesen mas relaciok (muveletek) is, de akkor is igy kell majd erteni az additiv es multiplikativ inverzet. Ezt ha az ember aterzni, akkor lehet megerteni, hogy miert kell sok tetelben azt irni, hogy "integritasi tartomanyban vagyunk", nem siman pl R alatt. Mert ugyan naggggyon sok mindenben hasonlitanak, ha azt mondanam R-ben (vagy Q,C, stb) vagyunk, azzal a multiplikacio es addicio muveletet megfeleltetnem a szorzassal es osszeadassal. Elleben minden olyan muvelet, amire az integritasi tartomanyok szabalyai megfelelnek, mar csak attol, hogy integritasi tartomanyban vagyunk, igaz lesz, es ugy is fog viselkedni ahogy R alatt a szorzas es osszeadas. Csak igy generalizalunk, ami mindig fasza.

Gyűrűk

Itt egy kicsit tobbet kell magyarazni, hogy el lehessen kezdeni megerteni a dolgokat. Egy csomo dolog azert az elobbrol ismeros, es feltetelezem, hogy a fentiek tudva is vannak. Ahol olyan fogalom van, amit mar korabban kifejtettem, ott mindig megprobalok odalinkelni.
Ahogy az elobb, * es ° relaciok. Az egyik egy Abel-csoportra, a masik egy felcsoportra van ertelmezve. A zarojelben az van, hogy a Gyurun belul minek hivjuk ezeket a csoportokat. Jellemzoen az Additiv csoport relaciojat osszeadasnak, a Multiplikativ csoportet pedig szorzasnak szoktak hivni. De ez korantsem jelenti, hogy azt a szerepet toltik be. Lehet, hogy osszeadasnak hivjuk, de pont kivonas muvelet.
A gyuru definiciojanak maradeka csak a mindket oldali disztributivitas. A zarojelezes azert felemas, mert igazabol mindegy (de jobb kitenni, mert nem biztos, hogy a muvelet kommutativ es/vagy disztributiv).
Az egysegelemhez nagyon hasonlo a nullelem (vagy zeruselem). Szinte osszekeverheto is, mert a definicioja kozel ugyanaz. EZ°AZ = AZ. De mivel a * es ° relaciok (muveletek, lekepezesek, stb) szabalyai kulonboznek, igy az elemek altal betoltott szerep is (Pl.: nullelem lehet a nullvektor, es semlegeselem az egysegvektor). A legegyszerubb ugy gondolni rajuk, mint univerzalis 0 es 1. Namarmost, ha EZ*AZ = nullelem akkor EZ es AZ nullosztopar; EZ AZ-nak a baloldali, AZ EZ-nek a jobboldali nullosztoja. Itt van ket fasza megnevezes/fogalom: nullgyuru amiben egy elem van, es az nullelem, (altalaban a 0). Zerogyuru az olyan Abel-csoport, hogy rendre minden eleme nullosztopart alkot (szal mindegyik mindegyikkel).
Az integritasi tartomanynal bejon az a fogalom, hogy "rendezett". Egy integritasi tartomany rendezett, ha az osszeadas (vagyis *) es szorzas (vagyis °) (CSAK EZ A NEVUK) monoton. Vagyis ha EZ <= AZ, akkor EZ * AMAZ <= AZ * AMAZ (pl.: 4 <= 5 akkor 4 - 1 <= 5 - 1) (ez az osszeadas monotonitasa); illetve ha EZ >= 0 es AZ >= 0, akkor EZ°AZ >= 0 (pl.: 2 >= 0 es 3 >= 0, akkor 2 + 3 >= 0) (ez a szorzas monotonitasa). Ezen felul, ez csak egy altalanos feltetel. De ha az egyenloseget nem engedjuk meg, vagyis a szorzas es osszeadas is szigoru monoton, akkor az a szukseges feltetel. Jah amugy ez egy olyan dolog, hogy mocskosul nem vagyok biztos benne, hogy tenyleg a csoportra ertelmezett relaciokra kell megnezni (mint szorzas es osszeadas), vagy a hetkoznapi szorzas es osszeadas. De ertelemszerunek tunik.

Testek

Ide nincs tokjo grafika. Nade! Vegyunk egy (G,*,°) nullelemes gyurut. * neve tovabbra is osszeadas (de csak a neve, lehet mas muvelet is), ° pedig szorzas. G-bol kivesszuk a nullelemet, vagyis legyen F = G\{0} (0 nem nulla, hanem nullelem). Ha igy (F,°) Abel-csoport, akkor (F,*,°) test (Pl.: Q,R,C).
Ha (F,*) valamint (F,°) is Abel-csoport, illetve igaz a muveletek disztributivitasa, vagyis az uj csilli-villi fogalmainkkal elve (F,*,°) rendezett test, es gyuru, azon belul pedig integritasi tartomany, akkor rendezett integritasi tartomanynak hivjuk. A komplex szamok halmazan ilyen nem letezik, de Q es R tovabbra is okes.
Megint egy uj fogalom ami ide valo. (F,*,°) test, archimedeszien rendezett, ha F beli EZ es AZ olyan, hogy ha EZ > 0 akkor van olyan n termeszetes szam, hogy n°EZ >= AZ. Magyarul F-en belul van ket olyan szam, hogy az egyik valamilyen szorzata (nem mezei szorzas hanem ° relacio) nagyobb (vagy egyenlo) mint a masik. Azt tudjuk meg, hogy ha egy test archimedeszien rendezett, akkor felso hatar tulajdonsagu. Ez fuggvenyek hatarertekenel fasza lehet. Gondolom. Visszafele nem igaz, mert Q archimedeszi, de nincs felso hatara.

Komplex számok

Ez a tema nincs tul nagy osszefuggesben az elozokkel, igy nem igazan feltetel tudni a fentebb leirtakat. Ellenben, hogy megis azok megerteset segitsem (es kibovitsuk a fogalmakat a komplex szamokra is), zarojelezve lesznek kiegeszito megjegyzesek, amiket csak az ert meg akinek mennek a fentiek. Az ilyenek majd szogletes zarojelek lesznek.
Kezdjuk rogton egy ilyesmi dologgal, es ezt nem zarojelezem meg. A valos szamok gyakorlatilag egy felso hataros rendezett test. Ez az eddigi legetagasabb halmazunk, inverzalhato multiplikacioval es addicioval, rakovetkezessel, kivonassal, szorzassal es osztassal. Egy muvelet, amit nem tudunk egyertelmuen rahuzni, a hatvanyozas, es annak is a gyokvonas resze. Nevezetesen nem tudjuk negativ szamok gyoket venni. Ezert lepunk at a komplex szamok halmazara, az ossszes eddigi muveletunket "magunkkal vive", bevezetve az i "szamot", ami nevezetesen -1 negyzetgyoke.
Komplex szamokat legegyszerubben vektorokkent lehet elkepzelni, ugyanis szinte minden esetben rendezett parok. Gyakorlatilag teljesen minden esetben, ugyanis egy komplex szam ket reszbol all elo. A valos, vagyis realis resz es a kepzetes, vagyis imaginarius reszbol. Ha z komplex szam, akkor z = (a+bi). Itt Re(z) = a, a valos resz, illetve Im(z) = b (nem bi!), a kepzetes resz. Az (a+bi) alak az ugynevezett algebrai alak, de irhatunk tenyleg rendezett part is: (a,b). Itt ha a vagy b nulla [nullelem], akkor olyan mintha a szam nem rendezett par lenne. Peldaul a valos szamok elkepzelhetoek imaginarius resz nelkuli komplex szamokkent, illetve a (0,b) komplex szamok, ahol persze b nemnull, tisztan imaginariusak [egyebkent a valos szamok komplex szamokka "kepzese", csak annyi, hogy megnezzuk a "valos szam alaku" komplex szamok alteret alkotnak-e a komplex szamok halmazan]. Szoval roviden formalisan C:RxR.
Most, hogy mar le tudjuk irni a komplex szamokat, kezdjuk el nezni a muveleteket. Ugye mondtam, hogy a legtobb muveletunket a valos szamoktol hozzuk tovabb. Vagyis tudunk osszeadni es szorozni (meg visszafele is). Egyelore csak az osszeadast nezzuk meg, mert szorozni nem szokas algebrai alakban. Legyen z = (a+bi) es z' = (a'+b'i). Ilyenkor z + z' = ((a+a') + (b+b')i). Termeszetesen kivonasnal kivonni kell, es nem osszeadni, de latjuk, hogy csak a megfelelo reszeket (valos es imaginarius).
Algebrai alakban van meg egy muvelet amit el tudunk vegezni. Konjugalas. Amolyan "ellentett" kepzes. Oszinten szolva en mindig elfelejtem, hogy egy komplex szam kongujaltja mi is, de a legegyszerubb megjegyezni, hogy ha egy komplex szamot osszeadunk a konjugaltjaval, akkor valos szam lesz, ilyen egyszeru. Vagyis ha z = (a+bi), akkor z = (a-bi). Persze igy a konjugalt konjugaltja onmaga, mert csak ketszer elojelet valt a kepzetes resz. Aztan az is ertelemszeru, hogy ha osszeadunk egy komplex szamot a konjugaltjaval, akkor a valos reszt kapjuk ketszer, mig ha kivonjuk, akkor a imaginarius reszt ketszer. Sot, egy osszes es szorzat konjugaltja is eloall a tagok konjugaltjabol. Vagyis ha z es w komplex szamok, akkor z*w = z*w, illetve z+w = z+w [ez amugy azert van, mert a tesben a multiplikacio es addicio monoton, gondolom]. Ja igen, es egy komplex szam reciprokanak konjugaltja a komplex szam reciproka lesz [mert multiplikativ inverz]. Szoval 1/z = 1/z.
Mondtam, hogy a komplex szamok, reven, hogy rendezett parok, elkepzelhetoek vektorokkent is. Meg azt is, hogy szorzashoz majd valami mas alakot hasznalunk. Ez a trigonometrikus alak lesz majd, de elobb meg egy muveletet meg kell nezni, ami mashogy mukodik, mint valos szamokkal, meghozza az abszolut ertek. Egy rendezett par abszolut erteke pont az ot kepviselo vektor hossza. Szoval ha maradunk a z = (a,b) alaknal, akkor |z| = (a,b) = sqr(a2 + b2). Ez konkretan a Pithagorasz tetelbol jon. Altalaban r betuvel jeloljuk. Vannak osszefuggesek az abszolut ertek es konjugalt kozt is. Peldaul z*z = |z|2, meg hogy z es z abszolut erteke ugyanaz, mert b es -b negyzete ugyanaz. Ezen kivul van egy csomo azonossag, amiket nem tudok szepen strukturalni, szoval csak sorolom: Ha z-nek nincs kepzetes resze, az abszolut erteke a valos resz abszolut erteke (magyarul valos szamkent viselkedik). Persze, csak ha a valos resz nemnull. Ha egyik resz sem null, akkor az abszolut ertek mindig nagyobb mint nulla [azaz kovetik a nullelemet]. Aztan ha egyik elem sem null, akkor a komplex szam abszolut erteke mindig nagyobb lesz, mint a reszek kulon-kulon. Persze ha a masik resz null, akkor pont egyenlo. Es vegul, ket komplex szam osszegenek abszolut erteke mindig kisebb vagy egyenlo mint ket komplex szam abszolut ertekenek osszege [ha belegondolunk, hogy "vektorok", akkor a haromszog egyenlotlenseg miatt].
Vegre eljutunk a szorzashoz, azzal pedig a trigonometrikus alakhoz. Az elobb a hossz, ami a Pithagorasz tetelbol jott. Az ehhez felrajzolhato derekszogu haromszog befogoi (ha z = (a+bi)) a es b, atfogoja r = |z|. Ha kiszamoljuk az a es b oldal kozti szoget, megkapjuk a szoget amivel (altalaban) a vektorunk el van forgatva. Ezt a szoget a komplex szam argumetumanak hivjuk, jele: arg(z). Legyen t = arg(z). Ilyenkor z trigonometrikus alakja: r(cos(t) + i*sin(t)). Fontos, hogy osszeadas van, kivonas esetnem NEM trigonometrikus alak (meg persze, hogy mi sin mi cos).
Na most, szorozni ilyen alakban mar eleg egyszeru lesz. Legyen z,w komplex szam, t = arg(z),s = arg(w). Ilyenkor zw = |zw|(cos(s+t) + i*sin(s+t)). Osztaskor z/w = |z/w|(cos(s-t) + i*sin(s+t)). Persze ilyenkor w nem lehet nulla, mert nullaval nem osztunk [nullelemnek nincs multiplikativ inverze]. Egyebkent ez az addicios tetelekre vezetheto le.
Lassan a tema vegere erunk, igy eljutunk a szerintem legbonyolultabb reszre, de egyben a komplex szamok lenyegehez. Ugye azert volt szuksegunk erre az uj szamhalmazra, hogy tudjunk barmibol gyokot vonni. Marmost, komplex gyokot vonni nem nehez, de az elmelet mogotte nekem vegig zavaros volt egesz ev alatt, es ahogy vizsgan tapasztaltam, fontos tudni. Szoval innen nagymamabiztos probalok lenni, de nagyon.
Legyen z,w komplex szam, n pozitiv egesz szam. Ilyenkor ha zn = w, akkor z lesz w n. komplex gyoke. De nem csak egyfajta alakban all elo, hanem tobben, meghozza mindig annyi lesz, amennyiedik gyokoket keressuk. Ez azert van, mert az egyseg sugaru kort, amibe belekepzelhetjuk a trigonometrikus alakot argumetumostul-hosszastul, azt pont n darabra osztjuk fel a gyokokkel. Ezert is, majd jeleznunk kell ezt a fajta periodicitast z minden alakjaban. Nezzuk: zk = sqrn(|w|)(cos((t+2kπ)/n) + i*sin((t+2kπ)/n)), ahol k = {0,...,n-1}. Vagyis ha barmelyik zk szamot n. hatvanyra emelunk, akkor w-t kapunk.
Na most, ha en specialisan az (1,0), vagyis 1 komplex gyoket nezem, akkor az ugynevezett egyseggyokoket kapom. Legyen w komplex szam, ilyenkor wn = 1(cos((2kπ)/n) + i*sin((2kπ)/n)), k = {0,...,n-1}. Az ilyen alaku komplex szamok az n-edik komplex egyseggyokok. Egy fontos fogalom van meg, de elobb picit nezzuk ezeket. Masodik egyseggyokok: 1 es -1. Negyedik egyseggyokok: i, -1, -i, 1. A sorrendjuk fontos, vagyis nem irhatoek fel -1 es 1 alakban a masodik egysegygyokok, hiszen k mas erteket kap a kulonbozo iteraciokban, es mas periodusban vagyunk. Ez azert nagyon fontos, mert minden ilyen felrihato sorozatbol a legelso primitiv egyseggyok. Vagyis masodik primitiv egyseggyok 1, negyedik primitiv egyseggyok i.
Van egy felhasznalasa is a primitiv egyseggyokoknek. Most jeloljuk az egyseggyokoket E-vel, illetve legyen megint w es z komplex szamaink, ahol z w valami n-edik gyoke. Ilyenkor zk = zEk, k = {0,...,n-1}.

Logika

Ez a legegyszerubb temakor, rovid is lesz. Itt nincs elokovetelmeny semmihez, es nem olyan, hogy mast nem ertesz meg ha ezt nem tudod. Ellenben szinte mindenhol van formalizalas, amit itt magyarazok majd el valamilyen szinten.
A lekisebb logikai egyseg nekunk a predikatum. Nagyon hasonlo mint egy fuggveny. Mondjuk E(x) jelentse, hogy x egyenes. Ugyanigy E(y) azt, hogy y egyenes. De barmit irhatnank, csak legyen elmagyrazva. Egy nagyon abszurd pelda lehetne, hogy: PONT(x) jelentse, hogy x egyenes. Itt E es PONT predikatumok, parameteruk a peldakban x es y voltak. De lehet tobb parameteres predikatum is. Mondjuk M(x,y) jelentse, hogy x es y egyenesek merolegesek. Ami fontos viszont, hogy ha en definialom, hogy M parameterei egyenesek, akkor nem rakhatok bele semmi mast. Mintha azt mondanam, hogy f(x) az egesz szamok halmazan valami fuggveny, aztan belerakok -4.68-t. De lehetnek kulonbozo predikatumok is, csak fontos a sorrendjuk. Mondjuk legyen RAJTA(e,x) az, hogy e egyenesen x pont rajtavan. Igy RAJTA(x,e) ertelmezhetetlen, mert az egyenes "helyere" rakom a pontot, es forditva.
Ezekkel a predikatumokkal ki lehet fejezni dolgokat. Maradjunk most az E(x) peldanal, ami azt jelentse, hogy x egyenes. Igy ha azt akarom mondani x nem egyenes, akkor nem kell csinaljak egy uj NE(x) predikatumot, hanem tagadom az eredetit. Ezt a negacioval tehetem meg: ¬E(x). Egy ¬ utani allitas azt jelenti "nem allitas". Mondjuk legyen h hetfo, es SZN(h) jelentse, hogy hetfo szep nap, vagy picit formalisabban: szep nap hetfo. Igy is kell kiolvasni. Igy ¬SZN(h) kiolvasva: nem szep nap hetfo, vagyis hetfo nem szep nap (amugy a negacio uner relacio). Ezen kivul van meg nehany logikai jel/muvelet. Es (^), vagyis konjunkcio. Vagy (ˇ), vagyis diszjunkcio. Ha ... akkor ... (==>), vagyis implikacio. Akkor es csak akkor (<=>), vagyis ekvivalencia. Vagy ... vagy ... (¤), vagyis kizaro vagy. Ezutobbi jelolese nalam nem korrekt, de ez a legkozelebbi amit talaltam. Nezzuk predikatumokkal. Legyen E(x), hogy x egyenes es P(y), hogy y pont, illetve RAJTA(x,y) hogy x egyenesen y pont rajta van. Igy ha azt akarom mondani "Ha x egyenes es y pont, akkor x-en y rajta van.", igy teszem: (E(x) ^ P(y)) ==> RAJTA(x,y). Fontos a zarojelezes, es ha megnezitek a mondatban is el van vesszovel valasztva. Kulonben ugy is lehetne ertelmezni, x egyenes es ha y pont, akkor x-en y rajtavan. Ez mar csak azert is igy van, mert ezek muveletek, amiknek vannak szabalyaik. Szerencsere a diszjunkcio es konjunkcio is asszociativ, kommutativ es disztributiv. Ezen kivul minden ilyen muveletnek van egy ugynevezett igazsagtablaja, amivel le lehet irni a viselkedeset, es igy lehet kiertekelni ilyen hosszabb mondatokat. Ide nem fogom beilleszteni, de elegge fontos tudni, foleg programozoknak.
A predikatumokbol logikai jelekkel (muveletekkel) osszefuzott "mondatokat" formulaknak hivjuk, vagyis egy formula predikatumok es logikai jelek osszessege. Na most, lattuk, hogy a tagolas, zarojelezes nagyon fontos. Ugyanugy a kiolvasas mint a kiertekeles szempontjabol. Ezt tudjuk meg fokozni. Peldaul ha azt akarom mondani minden P(x) (x pont) eseten van olyan E(y) (y egyenes), hogy RAJTA(y,x) (y x-re esik), akkor hasznalnom kell az univerzalis kvantort: ∀. Egyelore mondjuk ki, hogy minden gyerek fiu. Legyen x gyerek, es jelentse F(x) hogy x fiu. Ilyenkor ∀x:F(x). Kiolvasva: "Minden x gyermekre igaz, hogy fiu.", vagy "Barmely x gyermekre igaz, hogy fiu." A kettospont formalizalaskor altalaban "valamivalami, hogy". Peldaul: Igaz, hogy ... . Vagy: Felirhato, hogy ... . Most mondjuk ki, hogy "van olyan gyermek, aki fiu" (azert lanyok is leteznek na). Ilyenkor az egzisztencialis kvantort fogom hasznalni: Ǝ. Szoval: Ǝx:F(x). Kiolvasva: "Van olyan x gyermek, hogy fiu.", vagy "Letezik olyan x gyermek, hogy fiu." Olyan, hogy mindig letezik, nem irhato fel ∀Ǝ jelolessel, ∀ magaban is jelenti ezt. Viszont felirhatom, hogy egertelmuen letezik: !E.
Picit lepjunk tovabb. Az elobb volt egy formulank, hogy "Ha x egyenes es y pont, akkor x-en y rajta van.", (E(x) ^ P(y)) ==> RAJTA(x,y). Ha azt akarom mondani, "Ha x egyenes, akkor mindig van olyan y pont, hogy x-en y rajta lesz." Itt kvantorokat kell hasznalni, vagyis kvantalni kell a formulat. Szoval E(x) ==> ∀y:(P(y) ^ RAJTA(x,y)). Kiolvasva: "Ha x egyenes, akkor minden y-ra igaz, hogy pont, es x-en rajta van y." Ez pontosan ugyanaz, mint az eredeti allitas. Persze, kiolvasva mas, de a logikai erteke ugyanaz. Na most, mondjuk azt, hogy "Ha x egyenes, akkor mindig van olyan y pont, amire letezik olyan z egyenes, hogy metszi x-t." Legyen M(x,y) hogy x es y metszi egymast. Ilyenor: E(x) ==> ∀y:(P(y) ^ Ǝz:M(x,z)). Itt mar y es z is kvantalt. Ha egy formulaban minden kvantalt, akkor az egy zart formula. Ellenkezo esetben nyitott vagy nyilt.

Oszthatóság [WiP]

Ahogy a logikanal, ide sincs "elokovetelmeny", inkabb ez is egy onallo kis fejezet. Azonban amit kellhet tudni, az a megelozes es kovetes fogalma. Ha lesz megvalami, persze fogok linkelni a korabbi anyagokhoz, illetve itt is fogok szogleteszarojeles megjegyzeteseket tenni, hogy ami olyan dolog, azt hozza tudjam kotni az eddigiekhez. Megjegyzem, nekem nagyon sokat segitenek az ilyen zarojeles megjegyzesek, mert a tananyag egeszet osszekotik, ugymond egyben latom a kirakost, nem darabokban.
Ahogy komplex szamoknal, itt is egy kis halmazelmeletesdivel kezdek. Tudjuk, hogy vannak halmazok es rajtuk ertelmezett muveletek, hogy egyre tagabb halmazban egyre tobb a muvelet. Az osztas es oszthatosag legeloszor a racionalis szamok halmazan lesz ertelmezheto, ezzel bovitjuk ki az egesz szamok halmazat. Ha a,b racionalis szam, akkor a/b is az. De ha a es b egesz, az osztasuk eredmenye nem biztos, hogy egesz. Persze b semmi esetben sem lehet nulla [mert a nullelemnek nincs multiplikativ inverze]. Vagyis a,b racionalis es c egesz szamokra a osztja b-t (a|b), ha van olyan c, hogy a*c = b, illetve ha a nemnull, akkor b\a ertelmezheto [amugy ez komplex szamokkal is mukodik].
Na most, itt van egy dolog amit fontos lesz folyamatosan eszben tartani, "latni". Mivel a racionalis szamok negativ szamokat is tartalmaz, de egy szam es ellentettje [additiv inverze] ugyanazokat a szamokat osztja, oszthatosag szempontjabol 666 es -666 mocskosul ugyanaz. Ez eleg ertelemszeru, de fontos lesz majd egy picit kesobb, de ehhez a fogalomhoz is jo tudni mar: Egy szam, ami minden mas osztoja, egyseg. Racionalis szamok(tol felfele) eseten ez 1 es -1 [amugy ezek az oszthatosag relacioban egysegelemek, hiszen ha a|b akkor (a*1)|b (1 itt nem egy, hanem egysegelem, es * nem szorzas hanem multiplikacio)].
Amit az elobb irtam, hogy szam es -szam oszthatosagnal ugyanaz, erre van egy kifejezes: asszocialtak. Egy szam meg egy masik asszocialt, ha egymas egysegszeresei. Mashogy mondva: a|b es b|a. Ebbol majdnem egyertelmu, hogy a ket szam ugyanaz, de mivel oszthatosag relacio, ezert az elojelet nem igazan vesszuk figyelembe. Vegyuk amugy azt eszre, hogy ugye tudjuk, hogy a|b es (a*1)|b mindig igaz. De ha asszocialtak, akkor b|a es (b*1)|a meg b|(a*1) meg mindenfele feliras igaz. Ez azert van, mert egy szamnak az asszocialtjai es az egysegek mindig osztoi, ezert is a nevuk trivialis osztok.
Na most, ha a szamunk nem nulla [nem a nullelem], es a trivialis osztokon kivul nincs semmi mas osztoja, akkor irreducibilis, vagyis felbonthatatlan (ami nem ilyen, az osszetett szam). Ez kisertetiesen hasonlit a primszamokhoz, mert egy primszamnak definicio szerint csak az egyseg es onmaga osztoja. A felbonthatatlansagnal annyi a kulonbseg, hogy a szam negativ is lehet, hiszen az asszocialtakat is figyelembevesszuk. Igy minden primszam irreducibilis, de nem minden irreducibilis szam primszam. Ja igen, megjegyzem vannak a torzsszamok is, de amennyire en eszrevettem, ugyanazok mint a primszamok, csak mas szempontbol nezzuk: nem torzsszam az, ami osszetett, vagyis febonthato. A primszamhoz meg egy definicio, hogy ha p nemnull es nem egyseg, akkor p|ab eseten vagy p|a vagy p|b.
Emelekzzunk, hogy az osztas ertelmezesehez azert kellett halmazbovitest vegrehajtanunk, mert nem volt mindig ertelmezheto. Ez a "nem mindig" azt jelenti, hogy a maradek nekuli osztas ugymond igaz az egesz szamokon is (ha nem csak nem vesszuk figyelembe a maradekot hanem tenyleg nincs). De nekunk a maradekos osztas nagyon fontos lesz. Ez azt jelenti, hogy ha a,b egesz, akkor van olyan r racionalis szam, hogy a|(b+r), vagy megjobb megfogalmazasban, ha a es b egesz, es b nemnull, akkor a = b*q+r, ahol 0 <= r < |b|. Na ilyenkor irhatjuk fel, hogy a mod b = r, vagyis a\b osztas maradeka r.
Ezt az uj muveletet peldaul egy szamrendbol masikra atteresnel hasznalhatjuk. Peldaul ha en 123 egesz szamot tizes szamrendszerbol kettesbe akarom atirni, megnezem, hogy 123 mod 2 mennyi maradekot ad. Ez persze 1 vagy 0. Leirom, majd (123-1)/2 ((szam-maradek)/szamrendszer) lesz a kovetkezo, arra is mod 2, es tovabb igy amig olyan szamot kapok, amig az egysegig el nem jutok, ami itt persze 1 lesz.
Lassan eljutunk az osszetettebb fogalmakhoz. Az egyik ilyen a kituntetett kozos oszto, vagyis legnagyobb kozos oszto. Fontos, hogy meg mindig szemelott tartsuk az asszocialtsag fogalmat, szoval ha a es b szamok kituntetett kozos osztoja c, akkor persze -c is az, pedig tudjuk, hogy -c < c (persze ha c alapbol pozitiv volt) [jah amugy lehet, hogy mocskosul nem, de most nem csakugyintegritasitartomanyban vagyunk sajat muveletekkel, hanem racionalis szamokon]. Van egy jeloles, amit itt bevezetunk: lnko(a,b) az a es b legnagyobb kozos osztoja, de csak a nemnegativ. Ha ilyenkor csak az egyseget kapjuk meg, akkor a es b relativ prim, vagyis viszonylagos trozsszam.
Van egy tetel ami kimondja, hogy a legnagyobb kozos oszto mindig letezik (szoval barmely ket egesz szamra), es meghatarozhato az euklideszi algoritmussal. Na most, az euklideszi algoritmus alap es bovitett valtozatanak sem fogom ide leirni a menetet, de kovetkezik belole par dolog. Peldaul egy uj feliras: (a,b) = (|b|,a mod |b|), ha a es b nemnull. Na ilyenkor a,b,c egesz szamokra (ac,bc) = c(a,b), illetve barmely a,b egeszekre leteznek olyan x,y egeszek, hogy (a,b) = ax+by.
Van egy masik tetel, ami elegge fontos. Ez a szamelmelet alaptetle. Eloszor leirom a "lite" verziot, aztan picit kiegeszitjuk. Minden egesz szam sorrendtol eltekintve egyertelmuen felirhato primszamok szorzatakent. A kiegeszites elott ertelmezzuk. A lenyeg, hogy minden egesz szam felbonthato, es a primek amikre bontjuk szorzata visszadja a szamot. Tudjuk, hogy a szorzas kommutativ meg minden, szoval a sorrend tenyleg mindegy. Na most, a "minden egesz szam felbonthato" nem annyira igaz. Peldaul az irreducibilis szamok definiciobol nem azok. Szoval bovitsunk: Minden nemnull nem egyseg egesz szam a sorrendtol es asszocialtaktol eltekintve egyertelmuen felirhato primszamok szorzatakent. Igy mar sokkal jobb, hiszen az elobbi megfogalmazasban, egy negativ szamot sosem kaptunk volna meg, hisz nincsenek negativ primszamok. Azt is megodjuk ezzel, hogy mig az elobb egy irreducibilis szamot, ha negativ, nem tudtam volna felirni ugyanezen okbol.
Most jon egy definicio, ami eleg egyszeru, de a mogotte levo elmeletet nem annyira ertem. Szoval r(n) jelentse n pozitiv osztoinak szamat. Azaz az asszocialtakat itt sem vesszuk figyelembe. Persze n legyen nemnull es nem egyseg. Ezt kanonikus alakkal lehet felirni es szamolgatni, de erre nezzunk inkabb peldat. Szoval ha 6 osztoinak szama kell, akkor r(6) = r(2*3). Mivel 2 es 3 is elso hatvanyon van, igy (1+1)*(1+1) = 4. De mondjuk r(25*3) = (5+1)*(1+1) = 12. Szoval primtenyezokre bontjuk a szamot, aztan kulonbozo primtenyezok hatvanyai+1 ertekeket osszeszorozgatjuk.
A primekkel van meg egy dolog. Tetel szerint vegtelen sok prim van, es egy adott [0,x] intervallumon a primek szama megkozelitoleg x/ln(x). Ez a primszamtetel. A kiszamolgatashoz hasznalhato Erasztothenesz szitaja. Leirunk 2-tol x-ig minden szamot, aztan elkezdjuk 2 es 2 tobbszoroseit lehuzni. Aztan 3, aztan (4 lehuzva) 5, aztan (6 lehuzva) 7, igytovabb sqr(x)-ig. Aminek a tobbszoroseit lehuzzuk, azt leirjuk. Mire a vegzunk, minden leirt szam prim.
Vegre eljutottunk a temakorhoz ami miatt valszeg olvasod ezt a fejezetet. Kongruenciak! Szoval a lenyeg, hogy mint asszocialtaknal a szam es ellentettje gyakorlatilag ugyanaz (az oszthatosag szempontjabol), ugy a mod muveletre is vannak ekvivalens szamok. Peldaul 4 mod 3 = 1, mert 4 osztva 3-al maradeka 1. De 16 mod 3 is 1, igy 16 es 4 ugyanaz, ha mod 3 muveletre nezzuk. Ezt ugy mondhatjuk, hogy 16 es 4 kongruens modulo 3 alatt. De mondjuk 15 es 4 mod 3 mar inkongruens. A legalapvetobb dolog megmondani, hogy mi kongruens mivel, hogy ha "el tudunk lepni oda". Szoval 4+3+3+3+3 = 16. Harmasaval lepkedunk, hiszen mod 3 vagyunk. Amugy mod 3 azt jelenti, hogy igazabol csak a {0,1,2} halmaz elemeit hasznalhatjuk, hiszen harommal valo osztas nem adhat mas maradekot. Szoval 16 kongruens 4 kongruens 1 (mod 3). A kongruencianak van eleg sok tulajdonsaga, ezeket most nem sorolom fel. Kihagyom a diofantikus egyenleteket es kinai maradektetelt is, hiszen ezek gyakorlati anyagok.
Na most, az elobb irtam, hogy modulo valami az ugye a nullatol valami-1 intervallumon az egesz szamok halmaza, mivel ennyi fajta maradek lehet. Egy kongruencia "egyenletben" elmeletileg annyifajta megoldas lehetne, ahanyfele maradekot kaphatok. Nem jellemzo, de elvileg lehetne ennyi. Illetve azt is tudjuk, hogy nem csak egy kifejezett szam, hanem a szam es annak tobbszorosei a megoldasok, mert azok is ugyanazt a maradekot adjak. Ezt a ket tenyt osszevetve, elvileg minden kulonbozo maradekhoz vegtelensok szam tartozik, mert vegtelensok tobbszoros van (altalaban). Ezeket hivjuk maradekosztalyoknak. Szoval ha egy kongruencia megoldasai 14 tobbszorosei es 3 tobbszorosei, mert ezek adnak kulonfele maradekot, akkor 3 es 14 a ket maradekosztaly, ami a megoldasokat tartalmazza. Ertelemszeruen, ha ketfele megoldas jon ki, ket maradekosztaly, de ugyanazt a maradekot adjak, akkor a ket osztaly megegyezik. Na most, ha minden maradekosztalybol veszunk egy elemet, akkor kapjuk az adott moduloban a teljes maradekrendszert. Aztan az is igaz, hogy ha a maradekrendszer legalabb egy eleme relativ prim a modulushoz, akkor az osszes eleme az. Ezeket redukalt maradekosztalyoknak nevezzuk. Ha csak ilyen elemeket veszunk a maredekrendszerbe, akkor az redukalt maradekrendszer lesz. Szoval mondjuk 3 kulonbozo maradekai {0,1,2}. Itt, mig 1 es 2 relativ prim haromhoz, nulla nem az, igy ez nem lesz redukalt maradekrendszer.
Meg egy uj muvelet/jeloles, az Euler-fuggveny, ami egy egesz szamhoz relativ primek szamat adja meg. En most e()-vel fogom jelolni. Szoval e(5) = 4, hiszen 5-re relativ primek {1,2,3,4}. Ez majdnem ugyanaz, mint a "mod 5 halmaz". Gyakorlatilag az is, csak a nulla nelkul. Ezt azert ne vessuk kobe, mert csak primeknel mukodik igy. e(6) = 2, es ezek {1,5}. A kiszamolas hasonlo, mint az osztok szamanal volt. e(6) = e(2*3) = (2-1)(3-1) = 1*2 = 2. De mondjuk 12 (ami 6*2): e(12) = e(22*3) = (22-2)(3-1) = 4.
Vegul eljutunk az Euler-Fermat tetelhez is, de [WiP].

Bizonyítások [WiP]

Innentol csak bizonyitasok jonnek. Amennyire tudom, az oldal eddigi hangvitelet fogom hasznalni, de termeszetesen innen egyre tobb lesz a formalizalas. Ugyanakkor a disclaimerbe foglaltak itt is allnak. Az eddigiek, azaz a tetelek ismerete feltetelezett a bizonyitasok soran, es kevesbe magyarazosan fogom oket hasznalni. Feltetlezem, hogy aki idaig eljutott, az annyira erti a dolgokat, hogy barmilyen "szakszot" hasznalok, legalabbis tudja egy temahoz kotni, ha nem is tud rola mindent. Ja igen, eddig a feltrol-lefele strukturat hasznaltam vegig, de mivel a bizonyitasoknak nincs feltetlenul koze egymashoz, igy ez a resz csak ugy omlesztve lesz. Hogy a temak megis elkulonuljenek, kisebb cimeket fogok hasznalni. /!\ jelet fogok hasznalni, ha olyan bizonyitas amit teljesen sajat kutfobol irtam le (szoval nem 100%, hogy jo).

Unio es metszet tulajdonsagai

Ha emlekszunk, halmazok unioja es metszete par kozos (es ket extra) tulajdonsaggal rendelkezett. Asszociativitas, kommutativitas, disztributivitas, idempotencia illetve a De-Morgan azonossagok (ezekrol a tetelek kozt nem volt szo). Ezek eleg egyszeru bizonyitani. Ha A, B, C (valos) halmazok. Lenyegeben mindenhol csak formalizalni kell, es a halmazmuveleteket logikai jelekkel irni. Mivel a logikai muveletekrol tudjuk ugyanezeket a tulajdonsagokat, onnan mondhatni kesz is.
Unio Asszociativitasa: (AUB)UC = AU(BUC). A baloldal eleme egy x elem, ha (x ϵ A ˇ x ϵ B) ˇ x ϵ C, a jobboldalnak pedig ha x ϵ A ˇ (x ϵ B ˇ x ϵ C). Mivel a ˇ muvelet asszociativ, a ket oldal megegyezik.
Metszet Asszociativitasa: (A∩B)∩C = A∩(B∩C). A baloldal eleme egy x elem, ha (x ϵ A ^ x ϵ B) ^ x ϵ C, a jobboldalnak pedig ha x ϵ A ^ (x ϵ B ^ x ϵ C). Mivel a ^ muvelet asszociativ, a ket oldal megegyezik. Mocskosul az elozo copypasteje ez, annyira hasonloak.
Unio Kommutativitasa: AUB = BUA. A baloldal eleme egy x elem, ha x ϵ A ˇ x ϵ B, a jobboldalnak pedig ha x ϵ B ˇ x ϵ A. A ˇ muvelet kommutativitasa miatt az oldalak megegyeznek.
Metszet Kommutativitasa: A∩B = B∩A. A baloldal eleme egy x elem, ha x ϵ A ^ x ϵ B, a jobboldalnak pedig ha x ϵ B ^ x ϵ A. A ^ muvelet kommutativitasa miatt az oldalak megegyeznek.
Idempotencia: Itt osszevonom a ket bizonyitast, szival tegyuk fel, hogy R az unio es a metszet is lehet. ARA = A. Mindket oldalon levo halmaznak x akkor eleme, ha x ϵ A.
/!\ Disztributivitas: (A∩B)UC = (AUC)∩(BUC). Eloszor is, mivel tudjuk, hogy az unio kommutativ, nem kell kulon esetekre venni AUC es CUA, stb halmazokat. Baloldal eleme x, ha (x ϵ A ˇ x ϵ B) ^ x ϵ C. Jobboldal eleme x, ha (x ϵ A ˇ x ϵ C) ^ (x ϵ B ˇ x ϵ C). ˇ muvelet disztributivitasa miatt a ket oldal megegyezik. Ez az unio disztributivitasa volt, de metszete ugyanez, csak mas jelolesekkel.
De-Morgan azonossagok (unio): (AUB) = AB. x akkor eleme a baloldalnak, ha ¬(x ϵ A ˇ x ϵ B), vagyis ha ¬(x ϵ A) ^ ¬(x ϵ B). Ez pont megegyezik a jobboldallal.
De-Morgan azonossagok (metszet): (A∩B) = AUB. x akkor eleme a baloldalnak, ha ¬(x ϵ A ^ x ϵ B), vagyis ha ¬(x ϵ A) ˇ ¬(x ϵ B). Ez pont megegyezik a jobboldallal.

Relaciok

Itt mindenfele tulajdonsagokat kell bizonyitgatni. Ha valaki nem erti a halmazok formalis felirasat, ezeket a bizonyitasokat nehez lesz ertelmezni. Nagy altalanossagban itt is formalizasalas, logika(i azonossagok) es relacios tetelek amit felhasznalunk.
Biner relaciok kompoziciojanak inverze: Ha R es S biner relaciok, (RoS)-1 = S-1oR-1. Tudjuk, hogy RoS = {(x,y) | Ǝz((z,x) ϵ R ^ (y,z) ϵ S)}. Inverze: {(y,x) | Ǝz((z,x) ϵ R ^ (y,z) ϵ S)}. Vagyis ha "disztributaljuk" az inverzt, azaz egyesevel vesszuk a relaciokra, akkor: {(y,x) | Ǝz((x,z) ϵ R-1 ^ (z,y) ϵ S-1)}. Ez pedig pontosan a jobboldal.
Biner relaciok kompoziciojanak asszociativitasa: R, S, T biner relaciok, Ro(SoT) = (RoS)oT. Haladjunk bentrol kifele.
SoT = {(x,y) | Ǝz((z,y) ϵ S ^ (x,z) ϵ T)}.
Ebbe R-t is beveve (mas betukkel):
Ro(SoT) = {(x,y) | Ǝz((z,y) ϵ R ^ (x,z) ϵ SoT)} = {(x,y) | Ǝz((z,y) ϵ R ^ (x,z) ϵ {(x,z) | Ǝw((w,z) ϵ S ^ (x,w) ϵ T)})}.
Osszefoglalva, van olyan z es w, amire igaz, hogy (z,y) R beli, (w,z) S beli, es (x,w) T beli. Formalisan:
{(x,y) | Ǝz,w((z,y) ϵ R ^ (w,z) ϵ S ^ (x,w) ϵ T)}.
Ha megnezzuk, most (z,y) ϵ R ^ (w,z) ϵ S pont RoS definicioja. Ha visszafele elvegezzuk az elozo atalakitast, pontosan a jobboldalt kapjuk.
Ekvivalenciarelacio es osztalyozas: Minden ekvivalenciarelaciohoz rendelheto egy osztalyozas, es minden osztalyozas megad egy ekvivalenciarelaciot. Legyen X halmaz, ~ ekvivalenciarelacio es x = {y ϵ H | y ~ x ϵ X}. Ilyenkor azt kell megmutassuk, hogy {x | x ϵ X} tranzitiv, refelexiv es szimmetrikus, hiszen akkor lesz ekvivalenciarelacio. Legyen R relacio.
1, Legyen x osztalya Y, vagyis x legyen Y beli, es Y legyen egy O osztalyozas beli. Formalisan: x ϵ Y ϵ O. Ilyenkor (x,x) ϵ YxY, vagyis R reflexiv.
2, Ha (x,y) ϵ R, vagyis x ϵ Y es y ϵ Y, akkor O azon Y osztalya, amiben x es y elemek, legyen (x,y) ϵ YxY. Igy R szimmetrikus.
3, Legyen (x,y) es (y,z) R eleme. Legyen O ket specialis osztalya {(x,y)} es {(y,z)}. Mivel tudjuk, hogy egy osztalyozasban az elemek paronkent diszjunktak, z = x. Igy {(x,z)} is egy osztaly, s R tranzitiv.
Belatva, hogy R tranzitiv, refelxiv es szimmetrikus, R biztos ekvivalenciarelacio.
Reszbenrendezes es szigoru reszbenrendezes: Egy reszbenrendezes szigoru, ha tranzitiv es szigoruan antriszimmetrikus (vagyis irreflexiv is). Vagyis mig egy reszbenrendezesnel x <= y es y <= x megengedett, szigoru reszbenrendezes eseten csak az egyik. Vagyis ha x < y es y < z, akkor x <= y es y <= z, vagyis x <= z. Ha x = z igaz lenne, akkor y <= x teljesulne. De tudjuk, hogy egy szigoru reszbenrendezes irreflexiv, vagyis ez nem teljesulhet. Osszefoglalva, ha egy reszbenrendezesbol kivesszuk a reflexivitas tulajdonsagat, az ehhez a relaciohoz tartozo szigoru relaciot kapjuk. Visszafele, ha egy szigoru reszbenrendezeshez hozzaadjuk a reflexivitast, sima (gyenge) reszbenrendezest kapunk.
/!\ Szigoru monotonitas es injektivitas: Ha egy f:X->Y fuggveny szigoruan monoton no, akkor amennyiben x ϵ X > x' ϵ X, f(x) > f(x'). Ha f szigoruan monoton csokken, x > x' eseten f(x) < f(x'). Mivel az egyenloseget nem engedjuk meg, a kulonbozo x ertekekhez kulonbozo y ϵ Y (f(x)) fog tartozni. Definicio szerint, ha egy f:X->Y fuggveny injektiv, ugyanez all fent, vagyis ha x,x' ϵ X, es y ϵ Y, akkor ha f(x) = y es f(x') = y, akkor x = x'. Igy megallapithato, hogy minden szigoruan monoton novekvo vagy csokkeno fuggveny injektiv (kolcsonosen egyertelmeu).
Monoton fuggveny iverze: Egy szigoruan monoton novekvo fuggveny inverze is szigoruan monoton novekvo lesz, es forditva. Ertelemszeruen, ha f:X->Y, x,x' ϵ X, valamint x < x', akkor f(x) < f(x'), de f(x) = f(x') nem lehetseges. Igy ha u,v ϵ Y, u < v, illetve x = f-1(u) es x' = f-1(v) akkor x >= x' nem lehet, hiszen akkor f(x) > f(x'), vagyis u > v kovetkezne.

Csoportok, gyuruk, testek, integritasi tartomanyok

Ezek lesz talan a legnehezebben bizonyithato dolgok, ide nagyon pontosan kell tudni, hogy az ilyen csoportositgatasoknak milyen szabalyai vannak, mi jelent mit, es milyen hierarchiaban vannak a dolgok. Maga a bizonyitas menete igazabol nem olyan nehez, csak ra kell jonni, hogy mit is kell bebizonyitani, es hogy mibol mi kovetkezik. Itt mindig le fogom irni, hogy a tetelben levo szavak mit is jelentenek, de ajanlom atolvasgatni a Csoportok, Gyuruk, es Testek fejezeteket.
/!\ Termeszetes szamok es <= jolrendezett: A termeszetes szamok halmaza azt hiszem nyilvanvalo. A jelen N, es annyit kell tudni, hogy a kivonas muvelet nincs rajta ertelmezve. Vagyis ha x ϵ N, akkor x+1 ϵ N. De visszafele nem igaz, szoval ha x ϵ N, akkor nem biztos, hogy x-1 ϵ N, hiszen igy hamar eljutnank a nullaba es az ala. Legyen A nemures halmaz N reszhalmaza. Legyen B = {b ϵ N | ∀a ϵ A(b <= a)}, persze 0 ϵ B. Vagyis ha a ϵ A, akkor a+1 !e B. Szoval lesz olyan B beli b elem, hogy b+1 !ϵ B. Azt kell belatnunk, hogy minden b A also korlatja. Viszont a legnagyobb b ϵ B biztos A legkisebb eleme, hiszen ha a ket halmaz diszjunk lenne, mindig lenne egy b+1 elem, ami A also korlatja. Igy biztos lesz egy b ϵ A, ami A also korlatja es legkisebb eleme. Igy ha A N beli tetszoleges reszhalmaz, mindig lesz legkisebb eleme, ez pedig a jolrendezettseg feltetele.
Rendezett integritasi tartomany feltetele: Ezt eleg pontosan leirtam a tetelek kozt is. Egy integritasi tartomany akkor rendezett, ha az addicio es multiplikativitas monoton. Ha monoton, az a szukseges feltetel, ha szigoru monoton, az az elegseges feltetel. Vagyis nezzuk: x,y,z ϵ R. Ha x < y, akkor x+z < y+z. Illetve: Ha x,y > 0, akkor xy > 0. Ha xy = 0 lenne, akkor x es y nullosztopar lenne, de tudjuk, hogy minden integritasi tartomany nullosztoparmentes.
Egyenlotlenesegek egy intergritasi tartomanyban: Ez egy eleg hosszadalmas bizonyitas. Lenyegeben csak azt kell mindent megmutatni, hogy egy egyenlet/egyenlotlenseg megoldasa kozben mit szabad es mit nem, csak altalanosan. Vagyis nem "nullaval nem osztunk" hanem "nullelemmel nem osztunk". Illetve az addiciot, multiplikativitast, invertalhatosagot. Megjegyzem, a bizonyitas tobbi reszen 0 az integritasi tartomany nulleleme, < es > relaciok, + az addicio es * a multiplikativitas (vagyis az integritasi tartomany Abel csoportjanak es felcsoportjanak muveletei). Kezdjuk az alapnal: addicio. Ha x > 0, akkor -x + x = 0. (Additiv inverz.) Kovetkezzen a multiplikacio: x > y es z > 0, akkor xz > yz. Tudjuk, hogy integritasi tartomanyokban a szozras monoton, vagyis ha x < y es z < 0 xz > yz. Ha x != 0, akkor x2 > 0, sot, ha az integritasi tartomanyban van egysegelem, akkor x2 pozitiv. Vegul nezzuk az inverzeket: Ha 1 az egysegelem, es 0 < x < y, illetve x-nek van multiplikativ inverze, akkor 0 < 1/x < 1/y, es x * 1/x = 1 (> 0). Vegul pedig ha x > y, akkor 1/y > 1/y.
/!\ Van-e racionalis szam, aminek negyzete 2? A racionalis szamok ket egesz szam hanyadosakent allnak fent. Mivel 2 irreducibilis, igy nincs ket olyan szam, melyen hanyadoskent eloallna. Igy nincs olyan n ϵ Q, hogy n2 = 2.
Archimedeszi rendezettseg: Ha (F,*,°) test, es van olyan x,y ϵ F, n ϵ N, hogy n°x >= y, akkor F archimedeszien rendezett. Ilyenkor F felso hatar tulajdonsagu. Ellenkezo esetben, legyen A = {x°n | n ϵ N}, es y A felso korlatja. Ha ez igaz lenne, illetve z = sup(A), akkor x-z < z, akkor z-x mar nem lenne felso korlat, es van olyan n ϵ N, hogy n°x > z-x. Viszont erre (n+1)x > z-x ellentmondas. Oszinten ezt a bizonyitast nagyon nem ertem, van ez igy.

Halmazok, kombinatorika

Komplex szamok halmaza: Legyen (C,+,*) test. Az addicio itt osszeadas, a multiplikacio pedig szorzas, C elemei legyenek rendezett RxR parok. Igy (x,y) + (x',y') = (x+x',y+y'), illetve (x,y) * (x',y') = (xx' - y'y,y'x + yx'). Bizonyitas: Legyen (0,0) a nullelem, es (1,0) az egysegelem. Igy (x,y) additiv inverze: (-x,-y), illetve multiplikativ inverze: (x/(x2 + y2),y/(x2 + y2)).
Komplex szamok abszoluterteke: Ez megint elegge hosszadalmas lesz, ugyanis minden tulajdonsagot bizonyitani kell. Osszesen van 10, illetve a fogalom bevezetese. Kezdjuk is ezzel: Legyen (x,y) = z = (a+bi).
1, zz = |z|2. (a+bi)(a-bi) = a2 - (bi)2 = a2 + b2 = |(a+bi)|2
2, z != 0 eseten, 1/z = z/|z|2. (1,0)-ra trivialis.
3, |(a,0)| = |a|. |(a,0)| = sqr(a2 + 0) = x = |x|.
4, |0| = 0 es z != 0 |z| > 0. Negyzetgyok erteke mindig pozitiv.
5, |z| = |z|. |z| = sqr(a2 + (-b)2) = sqr(a2 + b2) = |z|
6, |zw| = |z||w|. Mindket oldalon zzww all.
7 es 8, |Re(z)| <= |z| es |Im(z)| <= |z|. |a| es |b| <= |sqr(a2 + b2)|, mert a negyzetgyok fuggveny szigoruan monoton novekvo.
9 es 10, |z + w| <= |z| + |w| es |z - w| <= |z| - |w| Haromszog egyenlotlenseg.
/!\ Nincs reszhalmaz ekvivalencia N-en: Nem a legpontosabb megfogalmazas a cim, de nagyon hosszu lett volna. Ha n ϵ N, es A = {1,2,...,n} es B valodi reszhalmaza A-nak, akkor nincs A ~ B. Nyilvan ha n = 0, akkor egyszeru, mert az ureshalmaznak nincs valodi reszhalmaza (meghatarozottsagi axioma kovetkezmenyebol). Indirekt, mutassuk meg, hogy A ~ B tranzitiv, reflexiv es szimmetrikus, felhasznalva, hogy n ϵ N eseten n+1 ϵ N. Tranzitivitas: Ha m = min(B), es k ϵ A, akkor n > k es k > m eseten n > m. Reflexivitas: ha n > m, akkor m > n. Ez soha sem teljesul, igy a szimmetria sem tud.
Veges halmazok es elemszamuk tulajdonsagai: Itt ot tulajdonsagot kell felsoroljunk es bizonyitsunk.
1, X es Y halmazok es X veges. Ha Y reszhalmaza X-nek, akkor Y is veges, valamint |Y| <= |X|.
/!\ 2, X veges, es Y valodi reszhalmaza X-nek, igy |Y| < |X|. Biz: Ha Y valodi reszhalmaza X-nek, akkor egy f:Y->X lekepezes nem lehet injektiv, igy a skatulya-elv kovetkezmenyekepp |Y| < |X|.
3, Ha X es Y veges es diszjunkt, akkor XUY is veges, es |XUY| = |X|+|Y|. Biz: X~{1,2,...,m} es Y~{1,2,...,n}. X es Y ~ {m+1,m+2,...,m+n}.
4, Ha X es Y veges, akkor |XUY| + |X∩Y| = |X| + |Y|. Biz: Elozo pont alapjan: |XUY| = |X\Y| + |X∩Y| + |Y\X|. Igy |XUY| + |X∩Y| = |X\Y| + |X∩Y| + |X∩Y| + |Y\X| = |X| + |Y|.
/!\ 5, Ha X es Y veges, akkor XxY is veges es |XxY| = |X| * |Y|. Mivel XxY-ba pontosan X minden elemere kepzunk egy elemet Y-bol, igy |X| * |Y| muveletet hajtunk vegre, ez pedig |X| * |Y| rendezett part fog alkotni. Mivel XxY elemei pont ezek, igy |XxY| elemszama megegyezo lesz |X| * |Y|-el.
/!\ Skatulya-elv: Ha X es Y vegtelen halmazok, es |X| < |Y| akkor nincs olyan f:X->Y lekepezes ami injektiv lenne. Biz: Ha f:X->Y injektiv, de |X| < |Y| akkor f szurkejtiv is lenne, es {1,2,...|X|} egy valodi reszhalmaza ekvivalens lenne onmagaval, ez pedig ellentmodas.
Veges halmaz minimalis es maximalis eleme: Reszbenrendezett halmaz barmely nem ures veges reszhalmazanak van minimalis es maximalis eleme. Biz: Ha |A| = 1, ertelemszeru. Ha |A| > 2, legyen a ϵ A, illetve A' = {a}. Legyen a' = max(A'). Ilyenkor ha a <= a', a' lesz a maximalis elem, kulonben pedig a. Hasonloan minimalis elemre.
Veges halmaz permutacioi: Legyen A egy n elemu halmaz. Ilyenkor n elem parmutacioinak szama: Pn = n!, ugyanis n elembol az elso helyre n felekeppen, valaszhatunk, a masodikra n-1, ... . Igy az osszes lehetoseg szama n(n-1)(n-2)...2*1. Ismetleses permutacio eseten minden elem kozt kulonbseget teszunk. Ha B halmaz elemei kozt vannak azonos tipusuak (pl zold labdak vagy kek labad), legyenek ezek kn reszhalmazok. Igy x = (|k1|+|k2|+...+|k1|)! sorrend letezik. Azonban igy y = k1!*k2!*...*kn! sorrend azonos. A lehetseges kulonbozo sorrendek szama igy: x/y.
Veges halmaz variacioi: Legyen A egy n elemu halmaz. Ilyenkor k <= n elemet Vnk = n!/(n-k)! felekeppen valaszthatunk ki, ugyanis az elso valasztaskor n, masodszor n-1, k-adszor n-k+1 elem kozul valaszthatunk. Ha ugyanazt az elemet tobbszor is kivalaszthatjuk, vagyis sorozatokat kepzunk, ugy egy n elemu halmaz k hosszu sorozatai iVnk = nk felekepp allhatnak elo.
Veges halmaz kombinacioi: Legyen A egy n elemu halmaz. Ilyenkor A k elemu reszhalmazainak szama Cnk = (n k) (n alatt a K) = n!/(k! * (n-k)!), ugyanis egy reszhalmazba k elemet n!/(n-k)! felekeppen valaszthatunk, de minden reszhalmaz pont k! fog szerepelni, ezzel meg le kell osztani. Amennyiben egy elemet tobbszor is kivalaszthatunk, iCnk = (n+k-1 k).

Egyeb

Binomialis tetel: (x+y)n = SUM k = 0-tol n-ig : (n k)xkyn-k. Biz: (x+y)n = (x+y)*(x+y)*...*(x+y). Ha a szorzast elvegezzuk, xkyn-k alaku tagokat kapunk, meghozza annyiszor, ahanyszor n tenyezobol k darab x-et valasztunk.
Polinomialis tetel: Legyen r ϵ N, x1,x2,...,xr ϵ R kommutativ egysegelemes gyuru (nullosztos "integritasi tartomany"), n ϵ N. Ilyenkor (x1+x2+...+xr)n = az a rohadt szumma amit nem igazan ertek. Mashol nezzetek meg, ide ugyse tudnam legepelni. Biz: r = 0 es 1 eseten 0 vagy 1, r = 2 eseten binomialis tetel, r > 2 eseten meg indukcio.
Algebra alaptetele: Minden legalabb elsofoku komplex polinomnak (polinomfuggvenynek) van gyoke. Biz: Legyen n ϵ N+, valamint c0,c1,...,cn ϵ C, es cn != 0. Ilyenkor Ǝz ϵ C, melyre SUM k = 0-tol n-ig : ck*zk = 0.
Szamelemelet alaptetele: Minden pozitiv termeszetes szam a sorrendtol eltekintve felirhato primszamok szorzatakent. Indirekt bizonyitas: Legyen n a legkisebb nem egyertelmuen felbonthato szam. n = p1*p2*...*pm = q1*q2*...*qk. Mivel p1|n, vagyis p1|q1*q2*...*qk, de mivel p1 prim, igy lesz olyan qi (i <= k), hogy p1|qi. Ilyenkor ennek a ket szamnak egyenlonek kell lennie, mert qi torsszam. Vagyis egy olyan p1 < n szamot kapunk, hogy nem lesz egyertelmu a felbontasa Ez azonban ellentmond az eredeti feltevesnek.
Fermat-tetel: Legyen p primszam. Ha a ϵ Z es p!|a, akkor ap-1 ≡ 1 (mod p). Ha a ϵ Z (tetszoleges), akkor ap ≡ a (mod p). Biz: Mivel φ(p) = p - 1, igy az elso alak az Euler-Fermat tetelbol kovetkezik. Masodik esetben, ha p!|a, ugy az elso alakbol kovetkezik, ellenkezo esetben mindket oldal oszhato p-vel.
Az legutobbi nehany, illetve "kimaradt" bizonyitasokat egyszeruen nem ertettem meg annyira, hogy elmagyarazzam. A jovoben valoszinuleg ezeket is bepotlom, addig is elnezest emiatt.

Egyeb [WiP]

Bovitett eukliszedi algoritmus pelda