# data[].attributes.body
Osnovni zadatak matematičara je da dokažu (ili opovrgnu) različite tvrdnje o matematičkim objektima (celim i realnim brojevima, funkcijama, itd.)

U kompjuterskih naukama od interesa je jedna druga vrsta matematičkih zadataka, koja je zaokupljivala pažnju matematičara od najranijih vremena.

Radi se o problemu postojanja (egzistenciji) algoritama ili računskih procedura za rešavanje raznih zadataka. Pod algoritmom smatraćemo niz instrukcija koje sačinjavaju mehaničku proceduru pomoću koje se može rešiti svaki zadatak iz određene klase (na primer zadatak rešavanja kvadratnih jednačina). Instrukcije moraju biti takve da ne zahtevaju nikakvu kreativnost od onog ko ih izvršava. U principu, uvek je moguće konstruisati mašinu koja je u stanju da izvršava takve instrukcije. To zapravo i rade svremeni digitalni računari kada izvršavaju programe, koji se sastojr od niza instrukcija.

Kao instruktivan primer, posmatrajmo problem izračunavanja zbira dva višecifrena broja. Algoritam (postupak) za ovaj problem se može naći u udžbenicima za osnovnu školu, pa ćemo se lako složiti da je procedura potpuno mehanička i da je može sprovesti čovek obavljajući samo jednostavne operacije. Čak šta više postoje proste mašine koje mogu da sabiraju brojeve.

Postavlja se pitanje: Da li za svaki problem koji zahteva izračunavanje možemo naći algoritam za njegovo rešavanje. Odgovor je da ne možemo. Dakle, postoje algoritamski nerešivi problemi.

Dokazivanje da se neki problem rešava datim algoritam je relativno jednostavno. Sve što je potrebno je da se verifikuje da dati algoritam rešava posmatrani problem. U tom slućaju kažemo da je problem algoritamski rešiv.

Dokazivanje da ne postoji algoritam za rešavanje nekog problema, je značajno teže. Za takvo dokazivanje potrebna je preciznija (formalna) definicija algoritma. O tome će biti reči u nekoj sledećoj objavi. Problemi za koje ne postoji algorita zvaćemo nerešivim problemima.

Matematiči problemi, u kojima se određuje da li postoji algoritam za njihovo rešavanje nazivaju se problemima odlučivanja.

# data[].attributes.body
Matematičkim objektima nazivamo sve apstraktne pojmove (koncepte) koji se pojavljuju u matematici. Matematički objekat je bilo šta definisano na formalan način. Primeri matematičkih objekata su brojevi, skupovi, funkcije, izrazi, geometrijski objekti, relacije i transformacije objekata, prostori itd. Pod matematičkim objektima mogu se smatrati i vrlo složeni pojmovi kao što su teoreme, dokazi, pa čak i cele teorije. Ontologija matematičkih objekata je predmet izučavanja i rasprava u filozofiji matematike.

Matematička tvrdnja je jedna ili više rečenica sastavljenih od reči i matematičkih simbola. Tvrdnja može biti tačna ili netačna.

Polazeći od definicija matematičkih objekata i tvrdnji koje su već dokazane, korišćenjem logike dolazimo do dokaza za nove tvrdnje. Dokazivanje tvrdnji je jedan od glavnih ciljeva u matematici.

Tvrdnje koje su dokazano tačne nazivaju se teoremama. Neke jednostnije tvrdnje koje pomažu dokazivanju glavne tvrdnje nazivaju se pomoćnim teoremama ili lemama.

# data[].attributes.body
Postoji više načina da se pojam algoritma definiše kao matematički objekat. Pokazano je da su svi oni međusobno ekvivalentni, to jest da se svaki algoritam izražen na jedan od tih načina moše izraziti i u svim ostalim načinima.

Intuitivni pojam algoritma poznat je od prvih ljudskih poćetaka bavljenja matematikom, a sama reč vodi poreklo od imena iranskog matematičara Muhameda Al Horezmija (Muhammad ibn Mūsā al-Khwārizmī), koji je u devetom veku napisao knjigu o indijskim veštinama računanja.

Pitanjima mogućnosti mehaničkog izračunavanja i rezonovanje bavili su se mnogi filozofi i matematičari tokom cele istorije. Ali tek u dvadesetom veku, Post, Church, Tjuring, Klini i niz drugih naučnika uspeli su da pojam algoritma definišu matematički precizno, i tako utrli put novoj nauci - kompjuterskim naukama.

Oni su, uprošćeno rečeno, pokazali ekvivalenciju između rekurzivnih funkcija, programskih jezika i Tjuringove mašina.

Teorija rekurzivnih funkcija nam pokazuje koje su funkcije izračunljive, a koje nisu. Programski jezici, kao što je Church-ov lambda kalkulus ( iz kojeg je proizišao LISP), nam daju način da izrazimo algoritme za izračunavanje rekurzivnih funkcija. Turingova mašina, kao apstraktni model savremenih računara, daje nam model mašine koja može mehanički i automatski da izvršava algoritme. Time je zatvoren krug matematikči problem -> algoritam za njegvo rešavanje -> mašna koja izvršava algoritam i daje rešenje za konkretan problem.

Od sredine dvadesetog veka, stvar je tehnike da kompjuterske mašine (hardver) učini sve boljim i boljim, pre svega stalnim povečanjem memorije i brzine računara. Razvoj algoritama (softvera) je postao predmetom svih nauka koje u domenu svojih istraživanja pronalaze načine za automatizaciju njihovih pronalazaka na dobrobit ljudi i prirode, nadajmo se.

# data[].attributes.body
Koji je najnapredniji rezultat o osnovama matematike? Moja opcija je Godelova Teorema o nekompletnosti (nepotpunosti). Ona je apsolutno temeljna za Matematiku, i svakako nije bila očigledan ili očekivan rezultat.

Izložiću je na ne-tehnički način:

Ako imamo skup konzistentnih (neprotivurečnih) aksioma o prirodnim brojevima, sa aksiomima dovoljno moćnim da izraze bilo koju tvrdnju koja se bavi prirodnim brojevima, postoje neke istinite tvrdnje koje ne mogu biti dokazane kao istinite.

To je tužno.

Evo jedne tvrdnje o prirodnim brojevima: Postoji beskonačno mnogo prostih brojeva. Ovo je dokazao Euklid pre oko 2500 godina, i još uvek je zabavan dokaz.

Evo još jedne nazvane Teorema o blizancima prostim brojevima. (Blizanci prosti brojevi su dva uzastopna neparna broja kao što su 3 i 5, ili 11 i 13, ili 41 i 43).

Teorema kaže: "Postoji beskonačno mnogo blizanaca prostih brojeva".

Matematičari misle da je ovo istina i da može biti dokazano koristeći standardne aksiome koje koristi većina matematike, nazvane ZFC Aksiomi.

Ali još uvek nema dokaza. I moguće je da nema dokaza, čak i ako je teorema istinita!

Možda bismo mogli dodati više aksioma tako da bismo mogli dokazati sve što je istinito. Ne. Godel je pokazao da ovo nije moguće.

Prilično kul rezultat. (Moja kćerka mi kaže da je reč kul ponovo u trendu).

S poštovanjem, penzionisani profesor Tim Farage, Computer Science Department at The University of Texas at Dallas

# data[].attributes.headline
Šta je ZFC (Zermelo-Fraenkel teorija skupova) i zašto je važna?

# data[].attributes.subject
Šta je ZFC (Zermelo-Fraenkel teorija skupova) i zašto je važna?

# data[].attributes.body
Alon Amit, Quora

Pokušaću da kažem nešto o ZFC-u iz malo drugačije perspektive. Namerno ću izbegavati ono što je pokriveno u članku na Vikipediji o Zermelo-Fraenkel teoriji skupova, ne zato što je nešto loše s tim, već zato što već tamo stoji. Isti slučaj je i sa veoma dobrim odgovorom Qiaochu Yuana.

Da biste dobili predstavu o tome šta je ZFC i zašto je važan, korisno je razmotriti dva potpuno odvojena matematička tematska područja:

Pojam skupa.

Pojam sistema aksioma.

To je zato što je ZFC sistem aksioma za skupove.

Skupovi

Skupovi su sveprisutni matematički objekti, što znate ako ste bili izloženi nekoj "višoj matematici". Naivno govoreći, skup je upravo ono što mislite da jeste: kolekcija objekata grupisanih zajedno i označenih kao jedna celina. Mnogi udžbenici i kursevi počinju "definisanjem" skupa kao što sam upravo učinio, kao "kolekcija objekata", ali je ispravno razmišljati da ovo nije prava definicija; ovo samo zamenjuje termin koji želite da definišete ("skup") drugim sinonimom ("kolekcija").

Ipak, nakon što vide neke primere skupova poput {jabuka, banana, Kalifornija} ili {1, 2, 3, ...} ili "skup svih engleskih reči koje ne opisuju same sebe", većina ljudi dobije predstavu o tome šta se podrazumeva pod "skupom", i zadovoljni su da rade s njima i dokazuju stvari o njima.

Zapravo, mnogi studenti matematike i mnogi profesionalci u matematici nikada ne osećaju potrebu za nečim formalnijim od ovoga, iako je činjenica da su skoro svi matematički objekti koje proučavamo poput grupa, funkcija, Hilbertovih prostora, relacije uređenja, polja algebarskih brojeva i grafovi skupovi sa nekom dodatnom strukturom.

Da bismo pokrenuli mnoge ideje u matematici, moramo biti sposobni da radimo sa skupovima. Moramo da ih spajamo, razdvajamo, razmatramo podskupove (sve skupove sadržane u datom skupu), i, važno je - kreiramo skup kao "sve stvari koje zadovoljavaju neki uslov". Ako se osvrnete na neke od dokaza ili definicija koje ste videli, možda ćete primetiti da se ovo često dešava. "Od svih mogućih sparivanja tačaka, razmotrite ono sa minimalnom dužinom" može biti korak u dokazu, i prva stvar koju ovde radite je izgradnja skupa svih mogućih sparivanja. To se često dešava.

Poslednja stvar koju treba spomenuti je suština odgovora Qiaochu-a: ljudi su brzo otkrili da ako sebi dozvolite da proizvoljno izvodite takve operacije, posebno ako zamislite da je uvek u redu reći "Skup svih foo takvih da bar", dobijate paradoksalne rezultate, što se uglavnom smatra lošom stvari. Zato su se uputili da preciznije definišu šta je u redu i šta nije u redu raditi sa skupovima. To nas prirodno vodi do sledeće teme, ideje o aksiomima.

Aksiomi

Primetite kako nisam rekao "uputili su se da preciznije definišu šta je skup". Matematičari generalno vide malu potrebu (ili sposobnost) da definišu šta nešto jeste, radije birajući da definišu šta nešto radi, ili šta možete uraditi s tim. (Otuda i Gowers-ov slogan "Matematički objekat je ono što radi" iz "Matematika: Veoma kratka uvod").

To je svrha aksioma. Uvodimo neke objekte proučavanja, poput "tačaka" i "linija", možda i neke odnose među njima, poput "tačka može ili ne može biti na liniji". Zatim, izjavljujemo određene stvari (aksiome) kao istinite za te objekte i odnose (na primer, "za bilo koje dve različite tačke postoji jedna linija kojoj obe pripadaju"). Zatim istražujemo posledice tih aksioma. To je ideja aksiomatske metode.

Šta su zapravo "tačke" i "linije" nije ni najmanje bitno; mogli bismo ih nazvati "igre" i "troni" koliko god nam stalo. Ideja nazivanja njih "tačkama" i "linijama" je da se namerava modelirati neki aspekt naše intuicije, ali to nema nikakve implikacije na teoriju koja se razvija dok logički istražujemo aksiome. Imajući na umu namereno značenje (ako postoji) može biti korisno, ali može biti i opasno zbunjujuće.

Dakle, imamo sistem aksioma za prstene, i za metričke prostore, i za matroide, i za mnoge druge stvari. Ti sistemi nisu namenjeni da modeliraju određeni objekat, niti bilo koju intuitivnu predstavu. Oni stvaraju univerzum nadamo se lepih stvorenja u koje možemo uživati. Skoro svi matematički objekti proučavani su na ovaj način. Postoji mnogo prstena (svaki koji zadovoljava aksiome prstena) i mnogo metričkih prostora (svaki koji zadovoljava aksiome metričkog prostora) i to je dobra stvar.

Imamo i sisteme aksioma za specifične objekte za koje imamo intuiciju. Na primer, Peanovi aksiomi (PA) deklarišu određene stvari kao istinite za "prirodne brojeve", i sigurno znamo šta treba da znači "skup prirodnih brojeva". Zapravo, Peanovi aksiomi ne obuhvataju sve što je istinito za prirodne brojeve: postoje istinite tvrdnje koje se ne mogu logički izvesti iz tih aksioma. Stoga, aksiomi se ne odnose samo na skup prirodnih brojeva; baš kao što postoji mnogo prstena, postoje mnogi različiti "modeli PA" koji svi zadovoljavaju Peanove aksiome. Ne nazivamo svaki od tih modela "Skup-prirodnih-brojeva" jer nijedan od njih nije ono što smo nameravali, pa u ovom slučaju obilje objekata koji zadovoljavaju aksiome može se smatrati lošom stvari.

To je slabost deduktivnog okvira zvanog "Logika prvog reda" što ne možemo imati sistem aksioma koji se precizno primenjuje na prirodne brojeve i ni na šta drugo (drugi okviri, poput Logike drugog reda, ne pate od ove određene slabosti, ali pate od drugih). Mnogi ljudi se zbunjuju misleći da Peanovi aksiomi "definišu" ili "generišu" prirodne brojeve. Ne mogu baš to učiniti, iako pokušavaju: deklarišu postojanje broja, 0, i operaciju ("naslednik" ili "sledeći broj") koja se može koristiti za generisanje više brojeva. Problem je što PA ne zna kada da stane: lako generiše sve poznate prirodne brojeve, ali ne može sprečiti da ubacite neprirodne brojeve dok i dalje zadovoljavate sve aksiome. Ovo je korisna analogija koju treba imati na umu dok razmišljate o ZFC-u.

Aksiomi ZFC-a nastoje da preciznije definišu dozvoljene operacije sa skupovima, kako bi ispravili navedene nedostatke o paradoksima. Među ostalim, oni deklarišu da određeni skupovi postoje (prazan skup i beskonačan skup), i pružaju metode za konstrukciju novih skupova iz postojećih. Dakle, postoje univerzumi skupova koji zadovoljavaju aksiome ZFC-a; ali, na bolje ili gore, baš kao i kod PA, ne postoji jedinstven takav univerzum.

Postoji minimalni univerzum L skupova stvoren ZFC-om, nazvan Konstruktibilni univerzum. Međutim, za razliku od PA, ljudi obično ne osećaju da je L pravi univerzum skupova dok su ostali artefakti. Zapravo, većina ljudi veruje da je L previše mali da bi se ozbiljno smatrao ispravnim univerzumom. Odličan članak o ovom pitanju je "Da li je V jednako L?" Penelope Maddy, koja detaljno piše o osnovnim pitanjima u teoriji skupova.

Ovde ljudi počinju da se razlikuju filozofski: neki veruju da postoji "pravi" univerzum skupova i naš zadatak je da dodajemo više aksioma kako bismo ga sve preciznije uhvatili; drugi misle da je ovo lažno verovanje i da postoje mnogi univerzumi skupova baš kao što postoje mnogi prstenovi, i da je to dobra stvar.

Kako god bilo, neizbežno bogatstvo strukture nametnuto nam nedostatkom jedinstvenosti univerzuma skupova znači da teorija skupova, a posebno ZFC teorija skupova, postaje matematička disciplina sama po sebi. Postoje stvari koje se mogu dokazati iz aksioma u ZFC-u, uključujući sve rezultate koje većina matematičara smatra "običnom matematikom", ali postoje i stvari koje se ne mogu dedukovati iz ZFC-a, i one stvaraju različite fascinantne alternativne matematičke svetove. Najčešće proučavani takvi svetovi uključuju "Velike Kardinalne brojeve", i neki ljudi - možda najznačajnije Harvey Friedman - intenzivno proučavaju odnos između tih "egzotičnih" objekata i najobičnijih entiteta koje poznajemo, poput prirodnih brojeva.