New Foundations

A Wikipédiából, a szabad enciklopédiából

A New Foundations (NF) egy alternatív halmazelmélet. Legegyszerűbb változatában mindössze két kézenfekvő axiómából áll, amelyek nagyon hasonlítanak a naiv halmazelmélet két alapelvéhez. A ZF-hez hasonlóan az NF is számos változatban létezik; ezért aztán helyesebb elméletcsaládról beszélni. Legizgalmasabb sajátossága, hogy létezik benne univerzális halmaz, amelynek minden halmaz eleme, beleértve saját magát is.

Története[szerkesztés | forrásszöveg szerkesztése]

Eredeti változatát Willard Van Orman Quine publikálta 1937-es New Foundations for Mathematical Logic (A matematikai logika új megalapozása) című cikkében. Kezdeti népszerűségének rosszat tett, hogy Ernst P. Specker 1953-ban az NF axiómáiból cáfolta a kiválasztási axiómát. Ezzel az NF konzisztenciája is komolyan gyanúba került. Máig nyitott kérdés NF relatív konzisztenciája a standard matematikai elméletekhez képest. Ronald Jensen 1969-ben bebizonyította, hogy az NF atomos változatától, NFU-tól már független a kiválasztási axióma. Ráadásul kiderült, hogy ha a Peano-aritmetika konzisztens, akkor az NFU is az. Ezek a megnyugtató eredmények azonban már nem befolyásolták érdemben a New Foundations megítélését a matematikus társadalomban. Jelenleg aktív kutatói közül kiemelkedik Thomas Forster és Randall M. Holmes.

Nyelvi keretek[szerkesztés | forrásszöveg szerkesztése]

A New Foundations elméletcsalád a halmazelméletben szokásos azonosságjeles elsőrendű logikai nyelvet használja. Az eredeti NF elméletben az egyetlen primitív nem-logikai konstans a kétargumentumú  \in relációjel. A változók értékei itt halmazok. Az atomos (urelementes) változatokban van még egy egyargumentumú halmazpredikátum is:  \mathrm{M} .  \mathrm{M}(x) szándékolt jelentése: x halmaz. A változók megengedett értékei itt atomok és halmazok.

Formulák rétegzése[szerkesztés | forrásszöveg szerkesztése]

A komprehenziós axiómasémában használni fogjuk a rétegezhető formula fogalmát. Egy halmazelméleti formula rétegzése során az összes változóelőfordulást ellátjuk a 0, 1, 2 stb. számindexekkel a következő szabályok szerint:

(i) egyazon kvantor által kötött változóelőfordulások ugyanazt az indexet kapják;
(ii) a = szimbólum két oldalán szereplő változók ugyanazt az indexet kapják;
(iii) az  \in szimbólum bal oldalán szereplő változó eggyel kisebb indexet kap, mint a jobb oldalán szereplő;
(iv) egyazon változó szabad előfordulásai ugyanazt az indexet kapják;

Egy formulát rétegezhetőnek mondunk akkor és csak akkor, ha változóelőfordulásai (i)-(iv) szerint indexezhetőek.

Példák rétegezhető formulákra:

eredeti formula rétegzett változat
(1)  x = x  x^1 = x^1
(2)  x \neq x  x^1 \neq x^1
(3)  x = u \lor x = v  x^1 = u^1 \lor x^1 = v^1
(4)  \exists y \, ( x \in y \land y \in u )  \exists y^1 \, ( x^0 \in y^1 \land y^1 \in u^2 )
(5)  \forall y \, ( y \in x \rightarrow y \in u )  \forall y^1 \, ( y^1 \in x^2 \rightarrow y^1 \in u^2 )
(6)  \exists y_1 \dots \exists y_n \, ( y_1 \neq y_2 \land \dots \land y_{n-1} \neq y_n \land  \forall z \, ( z \in x \leftrightarrow ( z = y_1 \lor \dots \lor z = y_n )))  \exists y_1^1 \dots \exists y_n^1 \, ( y_1^1 \neq y_2^1 \land \dots \land y_{n-1}^1 \neq y_n^1 \land  \forall z^1 \, ( z^1 \in x^0 \leftrightarrow ( z^1 = y_1^1 \lor \dots \lor z^1 = y_n^1 )))
(7)  \exists y \, ( y \in u \land \forall z ( z \in x \leftrightarrow y = z )  \exists y^0 \, ( y^0 \in u^1 \land \forall z^1 ( z^1 \in x^2 \leftrightarrow y^1 = z^1 )

Példák nem rétegezhető formulákra:

eredeti formula rétegzési kísérlet eredménye
(8)  x \notin x  x^1 \notin x^?
(9)  x = y \lor x \in y  x^1 = y^1 \lor x^1 \in y^?

NF axiómái[szerkesztés | forrásszöveg szerkesztése]

1. axióma (extenzionalitás) – Két halmaz egyenlő, ha ugyanazok az elemeik.
 \forall z \, ( z \in x \leftrightarrow z \in y ) \rightarrow x = y
2. axióma (rétegzett komprehenzió) – Ha  \phi (x) rétegezhető formula, akkor létezik egy y halmaz, melynek pontosan azok az x halmazok az elemei, melyekre  \phi (x) teljesül.
 \exists y \forall x \, ( x \in y \leftrightarrow \phi (x))

Néhány halmazmeghatározás[szerkesztés | forrásszöveg szerkesztése]

A második axióma feljogosít bennünket a szokásos  \{x|\,\phi(x)\} halmazabsztrakciós séma használatára, amennyiben  \phi(x) rétegezhető formula.

elnevezés meghatározás
(1) univerzális halmaz  \mathrm{V}=\{x|\; x = x\}
(2) üres halmaz  \emptyset =\{x|\; x \neq x \}
(3) párhalmaz  \{ u,v\} =\{x|\; x = u \lor x = v \}
(4) unióhalmaz  \bigcup u =\{x|\; \exists y \, ( x \in y \land y \in u ) \}
(5) hatványhalmaz  \mathcal{P}(u) =\{x|\; \forall y \, ( y \in x \rightarrow y \in u ) \}
(6) az n-elemű halmazok halmaza  n_\mathrm{Fr} =\{x|\; \exists y_1 \dots \exists y_n \forall z \, ( z \in x \leftrightarrow ( z = y_1 \lor \dots \lor z = y_n ) \}
(7) egy halmaz egyelemű részhalmazainak halmaza  \mathrm{S}(u) =\{x|\; \exists y \, ( y \in u \land \forall z ( z \in x \leftrightarrow y = z )  \}

A paradoxonok kezelése[szerkesztés | forrásszöveg szerkesztése]

Szokásos halmazelméleti keretek között (ZF-ben vagy NBG-ben) az előző szakasz (1), (6), (7) meghatározásai valódi osztályokat vezetnének be. NF-ben ezek is halmazok. Mégsem lépnek fel a szokásos halmazelméleti paradoxonok:

  • a Russell-paradoxon azért nem, mert az x\notin x formula nem rétegezhető, ezért nem vezethető be a Russell-halmaz;
  • a Cantor-paradoxon azért nem, mert a Cantor-tétel eredeti formájában nem bizonyítható;
  • a Burali-Forti-paradoxon azért nem, mert a Frege-rendszámok halmaza nem jólrendezett.

A Cantor-tétel[szerkesztés | forrásszöveg szerkesztése]

Valamely x és y halmazt ekvivalensnek (egyenlő számosságúnak) mondunk akkor és csak akkor, ha létezik egy olyan f halmaz, amely bijektív módon rendeli egymáshoz x és y elemeit:

x \sim y \Leftrightarrow \exists f (f \subseteq x \times y \,\land\, (\forall u\in x ) (\exists ! v\in y ) \langle u,v\rangle\in f  \,\land\, (\forall v\in y ) (\exists ! u\in x ) \langle u,v\rangle\in f )

A Cantor-tétel eredeti formája nem bizonyítható:

NF \nvdash\,\forall x\, x \nsim \mathcal{P}(x)

A Cantor-tétel szokásos diagonális bizonyítása az alábbi tételhez vezet:

NF \vdash\,\forall x\, \mathrm{S}(x) \nsim \mathcal{P}(x)

Kissé zavarba ejtő módon nem bizonyítható azonban az alábbi – szokásos halmazelméleti kontextusban triviális – összefüggés:

NF \nvdash\,\forall x\, x \sim \mathrm{S}(x)

Az univerzális halmaz esetében ez ment meg bennünket a Cantor-paradoxontól. Ugyanis \mathrm{V}=\mathcal{P}(\mathrm{V}), tehát \mathrm{V} \nsim \mathcal{P}(\mathrm{V}) ellentmondás lenne.

Rendszámok és számosságok[szerkesztés | forrásszöveg szerkesztése]

NF-ben a szokásos Neumann-rendszámok és Neumann-számosságok nem definiálhatók (lásd például a fenti (9) formulát). Bevezethetők viszont a Frege-számosságok és Frege-rendszámok:

  • Egy x halmaz Frege-számossága az x-szel ekvivalens halmazok halmaza:
|x|_\mathrm{Fr}=\{y|\, x \sim y\}
A fenti táblázat (6) sorában bevezetett 1_\mathrm{Fr},2_\mathrm{Fr},\dots halmazok a Frege-féle természetes számok.
  • Egy x_R jólrendezett halmaz Frege-rendszáma a vele izomorf (egyazon rendtípusba tartozó) jólrendezett halmazok halmaza:
\mathrm{ord_{Fr}}( x_R ) =\{ y_{R'} |\, x_R \cong y_{R'}\}

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • Th. Forster: Set Theory with a Universal Set. Clarendon, 19952 (19921).
  • R. M. Holmes: Elementary Set Theory with a Universal Set. Cahiers du Centre de logique 10. kötet. Academia, 1998.
  • R. Jensen: „On the consistency of a slight(?) modification of Quine's NF”. Synthese 19 (1969), 250-263.o.
  • W. V. O. Quine: „New foundations for mathematical logic”. The American Mathematical Monthly 44 (1937). 15-24.o. Újabb megjelenés in: Quine: From a Logical Point of View. Harvard UP, 19612 (19531). 81-101.o.
  • J. B. Rosser: „Set Theory for Mathematicians”. McGraw-Hill, 1953.
  • E. Specker: „The axiom of choice in Quine's new foundations for mathematical logic”. Proceedings of the National Academy of Sciences of the U.S.A. 39, 972-975.o.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Stanford Encyclopedia of Philosophy szócikk
New Foundations-honlap
New Foundations-bibliográfia