New Foundations

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

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

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

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

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

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

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

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

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

• Th. Forster: Set Theory with a Universal Set. Clarendon, 1995² (1992¹).
• 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, 1961² (1953¹). 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

Stanford Encyclopedia of Philosophy szócikk

New Foundations-honlap

New Foundations-bibliográfia