Paradoks u teoriji skupova

"Paradoks" u teoriji skupova 27.04.2008. u 10:58 · pre 225 meseci #1

Svojevremeno sam smislio ovaj (naravno, nekorektan) dokaz da je aksioma izbora posledica ostalih aksioma teorije skupova. Zadatak je naći grešku u dokazu. Napominjem da me je mrzelo da kucam baš svaki korak, ali se sve može kompletirati i korektno sprovesti osim jedne "sitnice". Postoji samo jedna greška.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

ZF_paradox.pdf46.29k

Re: "Paradoks" u teoriji skupova 06.07.2008. u 03:30 · pre 223 meseca #2

Kad već niko neće, da pokušam ja.

Kažeš:

Citat:

Otuda za ma koje $a_1,\dots,a_n$ iz skupa nosača $M$ modela $\textbf{M}$ postoji $b$ iz $M$ takvo da u modelu $\textbf{M}$ važi formula $\varphi(x_1,\dots,x_n,y)$ pri valuaciji $v$ za koju je $v(x_i)=a_i$ i $v(y)=b$ . Dakle, postoji funkcija $g:M^n\rightarrow M$ takva da za ma koje $a_1,\dots,a_n\in M$ i $b=g(a_1,\dots,a_n)$ u modelu $\textbf{M}$ važi formula $\varphi(x_1,\dots,x_n,y)$ pri valuaciji $v$ za koju je $v(x_i)=a_i$ i $v(y)=b$ .

Prva rečenica konstatuje samo da su svi skupovi $B_{a_1,\dots,a_n}:=\{b\in M:\hbox{ u modelu }\textbf{M}\hbox{ va\v zi formula }\varphi(x_1,\dots,x_n,y)\hbox{ pri opisanoj valuaciji}\}$ neprazni. Da bi iz toga izvukao ono što tvrdiš u narednoj rečenici, moraš se pozvati na aksiomu izbora.

Doduše, formalizam mi nikad nije bio jača strana niti naročita ljubav.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: "Paradoks" u teoriji skupova 07.07.2008. u 09:21 · pre 223 meseca #3

Znao sam da ce neko na to da posumnja, ali taj deo uopste nije problem iz vise razloga.

1) Aksioma izbora jeste primenjena, ali na metanivou, koji se ne mesa sa objeknivoom. Dakle, ovde je ZF sistem posmatran kao formalna teorija (aksiome ZF + aksiome pred. racuna + pravila izvodjenjapred. racuna), ili preciznije teorija prvog reda. Ona nema pojma o tome na sta mi mislimo pod binarnim relacijskim znakom $\in$ . Jedino zna da ta relacija zadovoljava date aksiome, bas kao i da radimo sa nekom drugom teorijom sa jednim binarnim relacijskim znakom (npr. teorijom gustih linearnih uredjenja bez krajeva). Ovde ispitujemo da li je neki niz znakova (koji ne moras shvatiti kao aksiomu izbora) teorema jednog formalnog sistema i sasvim je svejedno da li na metanivou vazi ono sto u tvojoj glavi predstavlja tumacenje tog niza znakova. Preciznije,

Iz $ZFC\vdash(ZF\vdash AC)$ sledi $ZFC\vdash(ZF\vdash AC)$ , kao i $ZF\vdash AC$ (ovo poslednje pod pretpostavkom da je ZF neprotivrecna teorija).

2) Primena aksiome izbora se moze eliminisati, jer ja sam esencijalno koristio samo teoremu o postojanju modela neprotivrecne teorije prvog reda. No, ona ima varijantu i sa najvise prebrojivim domenima, gde domen modela teorije prvog reda najvise prebrojivog jezika uvek moze biti podskup skupa prirodnih brojeva, dakle dobro uredjen skup, tako da imamo funciju izbora na njemu vec u ZF.

3) Problem koji razmatramo je konacno kombinatorne prirode (moze se kodirati u univerzumu $V_\omega$ striktno konacnih skupova), a po teoremi apsolutnosti se sve eventualne primene AC, CH (pa i mnogo jace aksiome V=L) iz dokaza ovakvih tvrdjenja mogu eliminisati bez obzira da li smo u dokazu napustali konacno kombinatorni univerzum $V_\omega$ ili ne.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: "Paradoks" u teoriji skupova 07.07.2008. u 12:06 · pre 223 meseca #4

Ovo pod 1) znaci da sam sredstvima teorije ZFC "dokazao" da je AC posledica ZF, to jest $ZFC\vdash(ZF\vdash AC)$ . No, Pol Koen je dokazao da je $ZFC\vdash Con(ZFC)\rightarrow(ZF\not\vdash AC)$ , pa bi shodno prethodnom bilo $ZFC\vdash\lnot Con(ZFC)$ iz cega na osnovu Gedelovih teorema nepotpunosti sledi da je ZFC teorija $\omega$ -protivrecna (ili jos jace $\Sigma_1$ -protivrecna). No, mada tu jos nema pravog logickog paradoksa, to znaci da teorija skupova "laze" o prirodnim brojevima, to jest, da postoje netacni iskazi o prirodnim brojevima koji su teoreme ZFC sto je "skoro paradoks".

No, ovde se radi o necem drugom. Ako bude zainteresovanih, objavicu resenje.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: "Paradoks" u teoriji skupova 07.07.2008. u 15:17 · pre 223 meseca #5

U redu, prihvatam tvoje obrazloženje dela za koji sam smatrao da je sporan. Zahvaljujem.

Ipak, voleo bih da vidim gde je zaista greška u tvom dokazu.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: "Paradoks" u teoriji skupova 07.07.2008. u 17:35 · pre 223 meseca #6

I ja bih bas voleo da vidim o cemu se radi...

Re: "Paradoks" u teoriji skupova 07.07.2008. u 17:38 · pre 223 meseca #7

Problem je u koraku u kome se primenjuje shema zamene. Dakle, skup $A$ je konstruisan kao $A=\{f(y)\,:\,y\in x\}$ . Sta kaze shema zamene? Ako je $\varphi(x,y)$ ma koja formula jezika teorije skupova, onda je formula $(\forall a)((\forall x\in a)(\exists_1y)\varphi(x,y)\Rightarrow(\exists z)(\forall y)(y\in z\Leftrightarrow(\exists x\in a)\varphi(x,y))$ jedna instanca sheme zamene. Ovo je jedna od njenih mogucih formulacija. Slobodnije receno, ako imamo funkciju definisanu na nekom skupu formulom teorije skupova, onda postoji skup ciji su elementi tacno slike elemenata domena te funkcije.

E, pa funkcija $f$ nije definisana formulom teorije skupova. No, to sto se koristi neki dodatni simbol koji je uveden teoremama o definicionim ekstenzijama nije uvek problem. Ako za neku formulu $\varphi(x,y)$ jezika ${\cal L}$ teorije $T$ vazi $T\vdash(\forall x)(\exists_1y)\varphi(x,y)$ onda se novi funkcijski znak (prosirenog jezika ${\cal L}^*$ tim novim funkcijskim simbolom) uveden (novom) aksiomom $(\forall x)\varphi(x,f(x))$ (prosirene teorije $T^*$ tom novom aksiomom) moze eliminisati iz svakog iskaza u smislu da za ma koju formulu $\psi$ prosirenog jezika ${\cal L}^*$ postoji formula $\theta$ jezika ${\cal L}$ koja je njoj ekvivalentna u prosirenoj teoriji $T^*$ . Takodje, novouvedeni simbol se moze eliminisati iz svakog dokaza u smislu da je svaka teorema na jeziku ${\cal L}$ prosirene teorije $T^*$ takodje teorema teorije $T$ .

Medjutim, ako znamo samo da za formulu $\varphi(x,y)$ jezika ${\cal L}$ vazi $T\vdash(\forall x)(\exists y)\varphi(x,y)$ , onda za uz prethodnu simboliku mozemo zakljuciti samo da je prosirenje konzervativno za dokaze, ali ne i za iskaze. Da je aksioma izbora bila korektno dokazana u prosirenoj teoriji $ZF^*$ , sve bi bilo u redu. Medjutim, u dokazu je koriscena formula uljez, koja nije aksioma teorije $ZF$ , pa cak ni ekvivalentna nekoj od aksioma, vec je samo prerusena u ruho sheme zamene. Stoga dokaz nije bio korektan ni u teoriji prosirenoj $ZF^*$ (jer je kao aksioma koriscena formula koja nije aksioma te teorije), pa se zakljucak samim tim ne moze primeniti ni na teoriju $ZF$ .

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: "Paradoks" u teoriji skupova 07.07.2008. u 17:52 · pre 223 meseca #8

Ja sam prvo pomislio na shemu zamene, medjutim kada sam konsultovao literaturu nisam uspeo da vidim sta nije dobro... U sustini, problem je sto zapravo ono f nije ni funkcija, jer moze da uzima vise vrednosti za isto x? a u shemi zamene mora biti jedinstveno to sto nam treba da bi primenjivali? ili sam pogresno rastumacio...

Re: "Paradoks" u teoriji skupova 07.07.2008. u 19:06 · pre 223 meseca #9

f jeste funkcijski simbol. No, u datom modelu teorije skupova ZF njegova interpretacija nije jednoznacno odredjena. Jeste funkcija, ali nije jednoznacno odredjena. Postoji vise funkcija koje mogu da zadovolje definicionu formulu u modelu teorije ZF.

Dakle, formula $(\forall x)(\exists_1 y)f(x)=y$ je valjana formula (jer je f funkcijski znak), pa je samim tim i teorema teorije ZF.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: "Paradoks" u teoriji skupova 07.07.2008. u 19:17 · pre 223 meseca #10

E super, mislim da smo se sada lepo razumeli...

Forum kao aplikacija na telefonu

Srodne teme