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