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\ne x$	$x^1\ne x^1$
(3)	$x=u\vee x=v$	$x^1=u^1\vee x^1=v^1$
(4)	$\mathrm{\exists }y(x\in y\wedge y\in u)$	$\mathrm{\exists }{y}^1(x^0\in y^1\wedge y^1\in u^2)$
(5)	$\mathrm{\forall }y(y\in x\to y\in u)$	$\mathrm{\forall }{y}^1(y^1\in x^2\to y^1\in u^2)$
(6)	$\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_n(y_1\ne y_2\wedge \dots \wedge y_{n-1}\ne y_n\wedge$ $\mathrm{\forall }z(z\in x\leftrightarrow (z=y_1\vee \dots \vee z=y_n)))$	$\mathrm{\exists }{y}_1^1\dots \mathrm{\exists }{y}_n^1(y_1^1\ne y_2^1\wedge \dots \wedge y_{n-1}^1\ne y_n^1\wedge$ $\mathrm{\forall }{z}^1(z^1\in x^0\leftrightarrow (z^1=y_1^1\vee \dots \vee z^1=y_n^1)))$
(7)	$\mathrm{\exists }y(y\in u\wedge \mathrm{\forall }z(z\in x\leftrightarrow y=z)$	$\mathrm{\exists }{y}^0(y^0\in u^1\wedge \mathrm{\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\vee x\in y$	$x^1=y^1\vee x^1\in y^{?}$

NF axiómái

1. axióma (extenzionalitás) – Két halmaz egyenlő, ha ugyanazok az elemeik.

$\mathrm{\forall }z(z\in x\leftrightarrow z\in y)\to x=y$

2. axióma (rétegzett komprehenzió) – Ha $\varphi (x)$ rétegezhető formula, akkor létezik egy y halmaz, melynek pontosan azok az x halmazok az elemei, melyekre $\varphi (x)$ teljesül.

$\mathrm{\exists }y\mathrm{\forall }x(x\in y\leftrightarrow \varphi (x))$

Néhány halmazmeghatározás

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

	elnevezés	meghatározás
(1)	univerzális halmaz	$\mathrm{V}=\{x|x=x\}$
(2)	üres halmaz	$\mathrm{\varnothing }=\{x|x\ne x\}$
(3)	párhalmaz	$\{u,v\}=\{x|x=u\vee x=v\}$
(4)	unióhalmaz	$\bigcup u=\{x|\mathrm{\exists }y(x\in y\wedge y\in u)\}$
(5)	hatványhalmaz	$𝒫(u)=\{x|\mathrm{\forall }y(y\in x\to y\in u)\}$
(6)	az n elemű halmazok halmaza	$n_{\mathrm{F}\mathrm{r}}=\{x|\mathrm{\exists }{y}_1\dots \mathrm{\exists }{y}_n\mathrm{\forall }z(z\in x\leftrightarrow (z=y_1\vee \dots \vee z=y_n)\}$
(7)	egy halmaz egyelemű részhalmazainak halmaza	$\mathrm{S}(u)=\{x|\mathrm{\exists }y(y\in u\wedge \mathrm{\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\iff \mathrm{\exists }f(f\subseteq x\times y\wedge (\mathrm{\forall }u\in x)(\mathrm{\exists }!v\in y)⟨u,v⟩\in f\wedge (\mathrm{\forall }v\in y)(\mathrm{\exists }!u\in x)⟨u,v⟩\in f)$

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

NF $⊬\mathrm{\forall }xx\nsim 𝒫(x)$

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

NF $⊢\mathrm{\forall }x\mathrm{S}(x)\nsim 𝒫(x)$

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

NF $⊬\mathrm{\forall }xx\sim \mathrm{S}(x)$

Az univerzális halmaz esetében ez ment meg bennünket a Cantor-paradoxontól. Ugyanis $\mathrm{V}=𝒫(\mathrm{V})$, tehát $\mathrm{V}\nsim 𝒫(\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{F}\mathrm{r}}=\{y|x\sim y\}$

A fenti táblázat (6) sorában bevezetett $1_{\mathrm{F}\mathrm{r}},2_{\mathrm{F}\mathrm{r}},\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{o}\mathrm{r}{\mathrm{d}}_{\mathrm{F}\mathrm{r}}(x_R)=\{y_{R^{\prime }}|x_R\cong y_{R^{\prime }}\}$

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 Sablon:Wayback

New Foundations-bibliográfia