وقتی می‌توان اطمینان یافت یک زنجیر استوار است که حلقه‌های

■ مقدمه:

این قسمت در ادامه قبل، اصول موضوعه در دستگاه ZF (۲)، سه اصل موضوع پایانی نظریه مجموعه‌ها را مرور می‌کند که نقش‌ آنها گشایش داستان انگاره بی‌نهایت و ایجاد سازواره مجموعه‌سازی بی‌نهایت و فراتر از بی‌نهایت، به شمول مجموعه اعداد و سرانجام جهان مجموعه‌ها موسوم به جهان فون نویمان و سرآخر خوش-بنیادی این سازواره است.

شش اصل قبلی به‌قرار ۱- گسترش؛ ۲- شمای جدایی؛ ۳- وجودی ۴- دوگانه سازی ۵- اجتماع ۶- مجموعه توانی را می‌توان در دو قسمت قبل یافت.

شرح کوتاهِ سه اصل پایانی دستگاه ZF
۷.اصل موضوع بی‌نهایت می‌گوید حداقل یک مجموعه استقرایی وجود دارد؛
۸.شمای (طرح‌واره) اصل موضوع جایگزینی می‌گوید برای هر مجموعه‌ای چون A مجموعه‌:
{A, Ƥ(A), Ƥ(Ƥ(A)), Ƥ(Ƥ(Ƥ(A))), . . .}
وجود دارد.
۹.
اصل موضوع بنیاد (یا اصل موضوع ترازمندی) می‌گوید اشتراک هر مجموعه با حداقل یکی از اعضای خود تهی است. به‌عبارت‌دیگر، هر مجموعه ناتهی با حداقل یک عضو خود از هم جدا‌ است؛
این اصل تضمین خوش-بنیادی مجموعه‌هاست، یعنی، مجموعه نمی‌تواند عضو خود باشد یا عضویت متقابل (A عضو B و B عضو A) ممکن نیست.


■ اصل موضوع بی‌نهایت:

اصل موضوع بی‌نهایت در ZF:

مجموعه استقرایی وجود دارد. به‌عبارت‌دیگر:

مجموعه‌ای وجود دارد که مجموعه تهی عضو آن و برای هر عضو، تالی آن عضو نیز عضو مجموعه باشد.

و به صورت فرمول:

X( X Y(Y X Y {Y} X))



مثال

مجموعه A در زیر یک مجموعه استقرایی است:

A = {∅,+, (∅+)+, ((∅+)+)+, . . .} =

= {, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, . . .}

زیرا؛ عضو A است و برای هر عضو A، به فرض x، تالی x، یعنی x+، نیز عضو  A است.


اشتراک دو مجموعه استقرایی خود استقرایی است.

• گیریم X و Y مجموعه‌های استقرایی باشند.

۱- باید نشان داد X∩Y. ازآنجاکه X و Y استقرایی‌اند پس X و Y؛ درنتیجه XY.

۲- و نیز باید نشان داد اگر zXY آنگاه z+XY. بنابراین، گیریم zXY؛ و درنتیجه zX و zY. ازآنجاکه X و Y استقرایی‌اند پس z+X و z+Y، که از این خواهیم داشت z+XY.


مجموعه استقرایی یکتایی وجود دارد که زیرمجموعه همه مجموعه‌های استقرایی است.

برهان

از اصل موضوع بی‌نهایت می‌دانیم مجموعه استقرایی وجود دارد. بنابراین گیریم  S هر مجموعه دلخواه استقرایی باشد. اکنون ویژگی «x عنصر S به قسمی که x عضو هر مجموعه استقرایی دلخواه است» را در نظر بگیرید. بنا بر اصل جدایی مجموعه‌ای، به فرض ω، با ویژگی گفته‌شده وجود دارد.

ازآنجاکه هر عضو ω در هر مجموعه استقرایی هست پس ω زیرمجموعه هر مجموعه استقرایی است. و نیز ازآنجاکه هر عضو ω به فرض z عضو هر مجموعه استقرایی است پس z+ نیز عضو هر مجموعه استقرایی است و درنتیجه عضو ω نیز است و بنابراین ω استقرایی است. بعلاوه بنا به اصل موضوع گسترش یکتا نیز است.

اکنون، یعنی بعد از نشان دادن وجود و یکتایی چنین مجموعه‌ای، نماد خاص ω (امگا) را به آن نسبت داده و می‌نویسیم

ω = {Y Ƥ(X): Y x ∈ Y (x+ Y)}

درواقع، ω قدر مشترک همه زیرمجموعه‌های استقرایی است.


نتیجه

گیریم C یک مجموعه که تهی در آن و تالی هر عضو آن نیز در آن باشد. در این صورت ωC. به‌عبارت‌دیگر، ω کوچک‌ترین زیرمجموعه استقرایی همه مجموعه‌های استقرایی است.


■ اعداد طبیعی و اصول موضوعه پئانو:

در این بند، با توجه به زمینه‌ای که از اعداد طبیعی [ ۰, ۱, ۲, . . .] و نیز از دستگاه حساب پئانو داریم، بر آنیم نشان دهیم هر عدد طبیعی همچون اشیای مشخص و یکتا و نیز مجموعه همه اعداد طبیعی در ZF قابل ساختن‌اند (یا وجود دارند.) بعلاوه، نشان دهیم اصول موضوعه دستگاه حساب پئانو در ZF قابل استنتاج‌اند.

■تعریف عدد طبیعی:

قدر مشترک همه مجموعه‌های استقرایی، یعنی ω را که نشان داده شد وجود دارد و یکتاست، مجموعه اعداد طبیعی می‌نامیم (ω را با ℕ نیز نشان می‌دهند). به هر یک از اعضای ω نیز یک عدد طبیعی گفته.

آنچه به عدد ۰ (صفر یا ۰) موسوم است را مجموعه تهی () گرفته (یا برعکس) و نوشته:

۰ = ,

۱  را ۰+ گرفته و نوشته:

۱ = ۰+ = ∅ ∪ {∅} = {∅} = {۰},

 ۲  را ۱+ گرفته و نوشته:

۲ = ۱+ = {∅, {∅}} = {۰, ۱},

۳  را ۲+ گرفته و نوشته:

 ۳ = ۲+ = {∅, {}, {∅, {}}} = {۰, ۱, ۲},

۴  را ۳+ گرفته و نوشته:

۴ = ۳+ = {۰, ۱, ۲, ۳},

. . .
. . .

و سرانجام نوشته

ω = {۰, ۰+, ۰++, ۰+++, . . .} = {۰, ۱, ۲, ۳, . . .} = ℕ


تعریف کوچک‌تر

برای هر n و m عضو  ωگوییم m اکیداً کوچک‌تر از n است و نوشته m<n:

اگر و فقط اگر m∈n [به‌عبارت‌دیگر، m زیرمجموعه سره n باشد].

و نیز گوییم m کوچک‌تر (یا کوچک‌تر مساوی) از n است و نوشته m≤n اگر و فقط اگر m⊆n [به‌عبارت‌دیگر، m<n یا m=n].


تعریف کوچک‌ترین

گیریم n و m دو عدد طبیعی؛ کوچک‌ترین آن‌ها را عدد طبیعی m∩n گرفته.


تعریف مجموعه تراگذر

مجموعه X را یک مجموعه تراگذر گفته، اگر برای هر xX داشته باشیم xX.

↓•

می‌توان نشان داد مجموعه X تراگذر است اگر:

YZ(ZY YX ZX)

↓•

 مجموعه ω تراگذر است.


دنباله

مجموعه U را یک دنباله عناصر مجموعه S گفته اگر U یک تابع از عدد طبیعی در S باشد.


چند نتیجه

۱- برای هر n∈ ω داریم n∈n+ [چون n+=n∪{n}]. بنابراین:

۰∈۱∈۲∈۳∈ . . .


۲- برای هر n∈ω داریمn ⊆ n+ [چون n+=n∪{n}]. بنابراین:

۰⊆۱⊆۲⊆۳⊆ . . .


۳- برای هر n∈ω داریمn+۰ . ( اصل موضوع ۳ پئانو را ببینید.)

ازآنجاکه برای هر n داریم n∈n+ و ۰ = ∅ پس n+ ممکن نیست ۰ (تهی) باشد.


۳.۱- برای هر n و m عضو  ωاگر m∈n+ آنگاه m∈n یا m=n.

اگر m∈n+ آنگاه m∈n یا m∈{n} [چون n+=n∪{n}].
اما {n} تکینه است و m∈{n} اگر و فقط اگر m=n.


۴- برای هر n و m عضو  ωاگرn+ = m+  آنگاه n = m .

داریمn∈n+ . پس با توجه به فرض داریم n∈m+.
ازاینجا بنا به نتیجه ۱.۳ داریم n∈m یا n=m.
به همین ترتیب داریم m∈n یا m=n.
اگر m=n که نتیجه حاصل است.
اگر n≠m آنگاه  m∈n و  n∈m و درنتیجه n⊆m و mn و بنابراین n = m. ( اصل موضوع ۴ پئانو را ببینید.)


■ قضیه استقرای ریاضی:

قضیه استقرای ریاضی

گیریم مجموعه A زیرمجموعه ω، به قسمی که :

آ. ۰ ∈ A.

ب. اگر nA آنگاه n+A.

در این صورت داریم A.

به‌عبارت‌دیگر:

[۰A n(n ∈ A ⇒ n+ ∈ A)] ω = A.

برهان

بنا به آ و ب مجموعه A یک مجموعه استقرایی است.
اما ω کوچک‌ترین مجموعه استقرایی است. پس ω⊆A.
اما بنا به قرض A⊆ω.
پس A.


↓•

اگر در قضیه استقرا شرط «A زیرمجموعه ω» در مقدمات نبود آنگاه

[۰ ∈ A ∀n(n ∈ A ⇒ n+ A)] ⇒ ω A.


■ استنتاج حساب از ZF ↓

همان‌طور که نشان داده شد همه اصول موضوعه پئانو در این رهیافت، برای ساختن عدد طبیعی و مجموعه اعداد طبیعی، به‌قراری که در پی می‌آید برقرارند. بنابراین همه نتایج دستگاه پئانو، یعنی حساب، نیز در ZF برقرار خواهند بود.

آ.  اصول موضوع ۱ و ۲ دستگاه پئانو نتیجه بی‌واسطه استقرایی بودن ω است.

ب. اصل موضوع ۳ همان نتیجه ۳ در بالا است.

ج. اصل موضوع ۴ همان نتیجه ۴ در بالا است.

د. اصل موضوع ۵ همان قضیه استقرای ریاضی در بالا است.

اکنون دو هدف آمده در ابتدای این بند، یعنی بیان هر عدد طبیعی n همچون یک شیئ‌ مشخص و یکتا با معرفی نکردن هیچ انگاره آغازین و استنتاج اصول موضوعه دستگاه حساب پئانو در ZF، برآورده شده‌اند.


■ شمای اصل موضوعی جایگزینی:

شمای اصل موضوعی جایگزینی در ZF:

تصویر هر مجموعه تحت هر تابع یک مجموعه است.

به‌عبارت‌دیگر

هرچه باشد مجموعه X و تابع دلخواه f با دامنه X، مجموعه‌ای وجود دارد به قسمی که اعضای آن تصاویر اعضای X تحت f باشد.

توضیح

پیش از ادامه بحث درباره شمای اصل موضوعی جایگزینی ارائه توضیح کوتاهی که در پی می‌آید ضرورت دارد.

گیریم A یک مجموعه؛ پس بنا بر اصل موضوع مجموعه توانی مجموعه Ƥ(A) وجود دارد. دوباره با کارزدن  اصل موضوع توانی مجموعه Ƥ(Ƥ(A)) را داریم. به همین شیوه می‌توان ادامه داد و کلاس زیر را ساخت:

{A, Ƥ(A), Ƥ(Ƥ(A)), Ƥ(Ƥ(Ƥ(A))), . . .}

اکنون می‌پرسیم؛ آیا این کلاس یک مجموعه هم است؟

گرچه ممکن است به‌نظر بدیهی بیاید ولی توسط آبراهام فرانکل و دیگران (۱۹۲۲) نشان داده شد نمی‌توان از اصول موضوعه ارائه‌شده تاکنون (اصول ارائه‌شده توسط تسرملو) به مجموعه بودن کلاس موردنظر رسید. از طرفی مجموعه بودن آن برای مبحث اعداد کاردینال نامتناهی (ارائه‌شده توسط کانتور)، اردینال‌ها و گسترش نظریه مجموعه‌ها ضروری است. بنابراین شمای اصل موضوعی جایگزینی توسط فرانکل به فهرست اصول موضوعه تسرملو اضافه گردید و حرف F در ZF نیز از همین‌جاست. در پی خواهیم دید چگونه از شمای اصل موضوعی جایگزینی به مجموعه مورد پرسش خواهیم رسید. بعلاوه شمای اصل موضوع جدایی از شمای اصل موضوع جایگزینی قابل استنتاج است.


ویژگی و تابع

گیریم α(x, y) یک ویژگی باشد. گوییم ویژگی α یک تابع را معین می‌کند (به فرض f از X در Y) اگر برای هر x متعلق به X و y۲ ،y۱ متعلق به Y داشته باشیم:

α(x, y۱)α(x, y۲)y۱ = y۲.

صورت دیگر و دقیق شمای اصل موضوع جایگزینی:

گیریم α(x, y) یک ویژگی باشد، به قسمی که گردایه همه x و yهای مشمول این ویژگی یک تابع باشد [یعنی، α یک تابع را معین کند.] در این صورت برای هر مجموعه داده‌شده U مجموعه V به قسمی که شامل همه تصاویر اعضای U تحت این تابع شود وجود دارد.

بیان شمای اصل موضوع جایگزینی به‌ فرمول:

a[U V w [α(U, V) α(U, w) ⇒ V = w]
b y[yb ⇔ ∃x[xaα(x, y)]]].



↓•

اصل موضوعی جایگزینی (مانند اصل موضوع جدایی) شماتیک است. یعنی، به ازای هر ویژگی α خود یک اصل موضوع است (درواقع این اصل موضوع به تعداد نامحدود مورد اصل موضوعی دارد) و ازاین‌جهت به آن شمای اصل موضوعی گفته.


نتیجه

بنا به شمای اصل موضوعی جایگزینی نشان می‌دهیم گردایه

= {A, Ƥ(A), Ƥ(Ƥ(A)), Ƥ(Ƥ(Ƥ(A))), . . .}

یک مجموعه است.
تابعی با دامنه اعداد طبیعی در نظر بگیرید به قسمی که، به ۰ مجموعه A، به ۱ مجموعه Ƥ(A) و بطور کلی به n>۰  مجموعه Ƥn(A) به شرح زیر:

Ƥ(Ƥ(Ƥ(. . . Ƥ(A))))
۱  ۲  ۳  . . . n

را نظیر کند.
اکنون بنا به شمای اصل موضوعی جایگزینی می‌گوییم گردایه که اعضای آن تصاویر تابع مفروض است یک مجموعه است.


■ استنتاج جدایی از جایگزینی:

قضیه: شمای اصل موضوعی جدایی از شمای اصل موضوعی جایگزینی دست آمدنی است:

فرض کنید A مجموعه و α(x) یک ویژگی باشد. در این صورت بنا بر شمای جدایی مجموعه:

 وجود دارد. {xA: α(x)}

 اکنون ویژگی β(x, y) را  به‌قرار:

β(x, y):: x=y α(x)

در نظر بگیرید. کارکرد این ویژگی مانند یک تابع است که اعضای آن دوتایی‌های مرتب با مؤلفه‌های یکسان هستند، به قسمی که ویژگی α را برقرار می‌کنند. اما مجموعه:

W = {y:∃x(x∈A β(x, y)}

بنا بر شمای جایگزینی وجود خواهد داشت و با توجه به تعریف ویژگی β(x,y) مجموعه W همان مجموعه:

است. ■ {y ∈A: α(y)}


توضیح بی‌نیازی نیاز به اصل جدایی

در قضیه قبل دیدیم شمای جدایی از شمای جایگزینی قابل استنتاج است. بنابراین، با وجود اصل جایگزینی دیگر نیاز به وجود اصل جدایی در فهرست اصول موضوعه ZF نیست. اما نقش آن در روند مجموعه‌سازی به‌عنوان یک قدم آغازین اجرایی در روند موجب شده تا در این فهرست بماند.


قضیه نقطه برجا ( Fixed-point Theorem)

[قضیه نقطه برجا به عنوان قضیه بازگشت (Recursion Theorem) نیز شناخته می‌شود.]

• گیریم f یک تابع از *ℕ در *ℕ باشد، نیز c∈ℕ* یک عدد برجا (تثبیت شده) باشد. در این صورت تابع یکتای g وجود دارد، به قسمی که:

g =
g(۱) = c,
g(x+) = f(g(x)).

•. Ethan D. Bloch. Proofs and Fundamentals A First Course in Abstract Mathematics; Springer; 2011, p286.

•. John M. (Jack) Lee. University of Washington Department of Mathematics.

[یادآوری]:

* = ℕ / {۰};

g:ℕ* → ℕ*; g⊆ℕ*× ℕ*;

g(۱) = c ↔ (۱, c) ∈ g.

قضیه نقطه برجا ( Fixed-point theorem) - قضیه بازگشت (Recursion theorem)

اثبات:

مجموعه S را مطابق زیر تعریف می‌کنیم:

S = {A ⊂ ℕ* × ℕ*: (۱, c)∈A (x, y)∈A ⇒ (x+, f(y))∈A}.

از آنجا که *×ℕ*S پس S تهی نیست. اکنون قدر مشتر عناصر A به قسمی که AS، یعنی مجموعه زیر را در نظر بگیرید:

g = ASA.

از آنجا که AS است، پس (۱,c)∈g است.

افزون بر آن، اگر (x,y)∈g آنگاه برای هر AS داریم (x,y)∈A. از اینجا برای همه Aها، به قسمی که AS داریم (x+,f(y))∈A. بنابراین (x+,f(y))∈g.

از آنچه گفته شد نتیجه می‌گیریم g عضو S و نیز کوچکترین عضو آن است.

اکنون می‌گوییم g یک تابع، یعنی g:ℕ*→ℕ*، است. برای اثبات ابتدا نشان می‌دهیم دامنه g مجموعه *ℕ است.

فرض کنید T زیرمجموعه nهای متعلق به *ℕ باشد به قسمی که a∈ℕ* وجود داشته باشد که برای آن (a,z)∈g باشد. از (۱,c)∈g داریم ۱∈T.

فرض کنید nT. در این صورت برای برای برخی z∈ℕ* داریم (n,z)∈g. که در نتیجه (n+,f(z))∈g و از این رو n+T. اکنون با استقرای ریاضی خواهیم داشت T=ℕ*. این یعنی دامنه g مجموعه *ℕ است.

اکنون نشان می‌دهیم هر عضو دامنه g به یک عنصر یکتا در *ℕ نظیر می‌شود. برای این کار مجموعه U در زیر را در نظر بگیرید:

U = {x ∈ ℕ*: (x, y), (x, z)∈gx = z}

نشان می‌دهیم ۱∈U. فرض می‌کنیم چنین نباشد. یعنی برای zc افزون بر (۱,c) نیز داشته باشیم (۱,z)∈g. بنابراین:

g / {(۱, z)} ∈S,

که این امکان ندارد، چرا که g کوچکترین عنصر S است. پس ۱∈U.

از طرفی اگر xU آنگاه x+U چرا که، اگر چنین نباشد آنگاه عنصری مانند mU هست که m+U.

اما چون  mU است یک n∈ℕ* یکتا وجود دارد، به قسمی که (m,n)∈g. پس، (m+,f(n))∈g.

اما چون m+U پس افزون بر (m+,f(n))∈g دوتایی (m+,z)∈g وجود دارد، به قسمی که zf(n).

در این صورت g / {(m+,z)} یک عضو S است که از g کوچکتر است که ممکن نیست. با استقرای ریاضی نشان داده می‌شود U=ℕ*. و سرانجام این که g یک تابع است.

اکنون نشان می‌دهیم g یکتا است.

فرض کنید دو تابع g۱ و g۲ وجود دارد به قسمی که:

g۱ = c , g۱(x+) = f(g۱(x))

و

g۲ = c , g۲(x+) = f(g۲(x)).

مجموعه V را در زیر در نظر بگیرید:

V = {n*: g۱(n) = f(g۲(n))}.

از آنجا که g۱(۱) = g۲(۱) = c پس ۱∈V.

اگر nV آنگاه g۱(n) = g۲(n)، بنابراین:

 g۱(n+) = f(g۱(n)) = f(g۲(n) = g۲(n+).

و در نتیجه، n+V. اکنون بنا به استقرای ریاضی *=V، که این یعنی g۱=g۲.

مثال ۱.

 c یک عدد برجا (fixed) است.
f(x) = x + c 
g(۱) = c.
g(x+) = f(g(x)).
yg(x).
y =
c اگر x = ۱:
f(y) وگر نه:
g(x) = cx.

مثال ۲.

 c یک عدد برجا (fixed) است.
y = f(x) = cx,
g
(۱) = c.
g
(x+) = f(g(x))
y
= g(x).
y =
c اگر x = ۱:
f(y) وگر نه:
g(x) = cx.

■ روند مجموعه‌سازی (سلسله‌مراتب تجمعی مجموعه‌ها / جهان فون نویمان)، سازگاری و تمامیت در ZF:

می‌توان به دستگاه ZF همچون یک سازواره مجموعه‌سازی بر بنیاد مجموعه تهی نگاه کرد. گام‌های این سازوارگی چون یک روند بی‌‌کران مجموعه سازی در زیر آمده:

۰.
O۰;
⤥⤣OnƤ(On-۱); [n]
S۰{On: n }
S۰ = {, Ƥ(), Ƥ(Ƥ()), Ƥ(Ƥ(Ƥ())), ...}
بنا به اصل موضوع جایگزینی، S۰ یک مجموعه است.
با برچسب زدن به اعضای S۰ به‌قرار:
⥃ V۰
Ƥ() ⥃ V۱
. . . ,
Ƥn
() ⥃ Vn
. . .
می‌نویسیم:
S۰ = {V۰, V۱, V۲, . . . Vn, . . .}
۱.
O۰S۰;
OnƤ(On-۱); [n]
S۱{On: n}
S۱ = {S۰, Ƥ(S۰), Ƥ(Ƥ(S۰)), ...}
بنا به اصل موضوع جایگزینی، S۱ یک مجموعه است.
با برچسب زدن به اعضای S۱ به‌قرار:
S۰ ⥃ Vω
Ƥ(S۰) ⥃ Vω+۱
. . . ,
Ƥn
(S۰) ⥃ Vω+n
. . .
می‌نویسیم:
S۱ = {Vω, Vω+۱, . . .,Vω+n, . . .}
۲.
O۰S۱;
⤥⤣OnƤ(On-۱); [n]
S۲{On: n}
S۲ = {S۱, Ƥ(S۱), Ƥ(Ƥ(S۱)), ...}
بنا به اصل موضوع جایگزینی، S۲ یک مجموعه است.
اکنون با برچسب زدن به اعضای S۲ به‌قرار:
S۲ ⥃ V۲ω
Ƥ(S۱) ⥃ V۲ω+۱
. . . ,
Ƥn
(S۱) ⥃ V۲ω+n
. . .
 می‌نویسیم:
S۲ = {V۲ω, V۲ω+۱, . . .,V۲ω+n, . . .}
.... . . .
. . . .
. . . .
. . . .

خروجی آنچه را در بالا سازوارگی مجموعه‌ها نامیدیم به صورت دنباله مجموعه‌ای زیر می‌نویسیم:

, Ƥ(), Ƥ۲(), ..., S۰, Ƥ(S۰), Ƥ۲(S۰), ...,S۱, Ƥ(S۱), Ƥ۲(S۱), ...,S۲, Ƥ(S۲), Ƥ۲(S۲), ...

یا:

V۰ , V۱ ,V۲ , . . . ,Vω , Vω+۱ , . . .,V۲ω , V۲ω+۱ , . . .,V۳ω ,V۳ω+1 , . . .

گرچه هر عنصر این دنباله یک مجموعه است، اما می‌توان نشان داد (پارادوکس بورالی فورتی) اجتماع همه این عناصر یک مجموعه نیست بلکه صرفاً یک کلاس سره است. به این کلاس، یعنی اجتماع همه مجموعه‌های دست آمده در روند مجموعه‌سازی، که معمولاً آن را با V نشان می‌دهند، سلسله‌مراتب تجمعی مجموعه‌ها و نیز جهان فون نویمان می‌گویند.



سازگاری و ناتمامیت ZF

در بحث صورت و معنی در سلسله یادداشت‌های روند منطق از دو قضیه تاریخ‌ساز ناتمامیت گودل یاد شد. برای یادآوری، در زیر صورت این دو قضیه آمده:

قضیه اول ناتمامیت: سازواره ماشینی [Machinery] سازگاری که بتواند همه گزاره‌های درست و فقط درست حساب را تولید کند وجود ندارد.

قضیه دوم ناتمامیت: سازواره ماشینی [Machinery] سازگاری (در حساب) که بتواند سازگاری خود را ثابت کند وجود ندارد.

ازآنجاکه حساب، یعنی دستگاه پئانو، درون نظریه مجموعه‌هاست پس دو قضیه ناتمامیت گودل برای نظریه مجموعه‌ها برقرار است. به‌عبارت‌دیگر، در درون نظریه مجموعه‌ها (برای ساکن جهان فون نویمان) اثبات سازگاری نظریه مجموعه‌ها ناشدنی است و این بدین معنی نیست که نظریه مجموعه‌ها ناسازگار است. در عمل و در بیشترین ریاضیات جاری (موسوم به ریاضیات کلاسیک) فرض بر سازگاری نظریه مجموعه‌ها است.

قضیه‌های اول و دوم ناتمامیت گودل در نظریه مجموعه‌ها

قضیه اول ناتمامیت: فرمولی در نظریه مجموعه‌ها هست که نابسته به اصول موضوعه نظریه مجموعه‌ها است.

قضیه دوم ناتمامیت: اگر نظریه مجموعه‌ها سازگار باشد آنگاه نخواهد توانست سازگاری خود را اثبات کند.

■ اصل موضوع بنیاد:

تعریف: عنصر -∈کمینه

به آن اعضای مجموعه که با خود مجموعه اشتراک تهی دارند یک عنصر کمینه‌ای عضویتی [یا عنصر -∈کمینه] آن مجموعه گفته.

توضیح

توجه داریم که در ZF اعضای مجموعه خود مجموعه هستند. عضویت.


اصل موضوع بنیاد در ZF:

هر مجموعه ناتهی دارای عنصر کمینه‌ای عضویتی است.

به‌عبارت‌دیگر:

برای هر مجموعه ناتهی X، مجموعه Y که عضو X باشد وجود دارد به قسمی که X Y = .

به‌عبارت‌دیگر:

X ⇒ Y(Y X XY = ∅)


توضیح

اصل موضوع بنیاد به اصل ترازمندی نیز موسوم است.


مثال

مجموعه B در زیر را در نظر بگیرید:

B = {{۱}, {۱, ۳}, {{۱}, ۲, {۱, ۳}}}

همان‌طور که در زیر می‌توان دید B اصل موضوع بنیاد را برمی‌آورد و دو عنصر -∈کمینه دارد.

B {۱} =

B {۱, ۳} =

B {{۱}, ۲, {۱, ۳}}


مثال

مجموعه A در زیر را در نظر بگیرید:

A = {, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}

همان‌طور که در پایین می‌توان دید A اصل موضوع بنیاد را برمی‌آورد و تنها عنصر -∈کمینه آن است.

A {∅} = {} ≠

A {∅, {∅}} = {∅, {∅}}

A {∅, {∅}, {∅, {∅}}} = {∅, {∅}, {∅, {∅}}}

A ∩ =


■ خود-عضوی در ZF:

 هیچ مجموعه‌ای عضو خود نیست.

برهان

۱. فرض کنید X یک مجموعه ناتهی و XX.
۲. از تکینه‌سازی داریم {X}مجموعه است.
۳.اما داریم X∈{X} و طبق فرض XX.
۴.پس {X}X تهی نیست.
۵.از ۴ نتیجه می‌شود در مجموعه {X} عنصری که اشتراک آن با {X} تهی باشد وجود ندارد.
۶.نتیجه ۵ خلاف اصل موضوع بنیاد است.

■ عضویت متقابل در ZF:

به‌عبارت‌دیگر:

x و y وجود ندارند به قسمی که: x y y x.

برهان

۱. فرض کنید A و  B وجود دارند به قسمی که: A B B A.
۲. از اصل موضوع دوگانه سازی مجموعه C به قسمی که C={A,B} را داریم.
۳.A C B
۴.B C A
۵.از ۳ و ۴ نتیجه می‌شود در مجموعه C عنصری که اشتراک آن با خود C تهی باشد وجود ندارد.
۶.نتیجه ۵ خلاف اصل موضوع بنیاد است.

■ زنجیره‌ عضویتی بی‌پایان کاهنده (Infinite Descending ∈_Chain)

نظریه مجموعه‌ها: زنجیره‌های عضویتی کاهنده بی‌پایان
نظریه مجموعه‌ها: زنجیره‌های عضویتی کاهنده بی‌پایان

فرض کنید X۰ یک مجموعه؛ این مجموعه ممکن است دارای عضوی به فرض X۱ باشد. پس می‌نویسیم:

X۱ X۰.

X۱ ممکن است دارای عضوی به فرض X۲ باشد. پس می‌نویسیم:

X۲ X۱ X۰;

X۲ ممکن است دارای عضوی به فرض X۳ باشد. پس می‌نویسیم:

X۳ X۲ X۱ X۰;

. . .
. . .

در ادامه این روند و بطور کلی عضوی مانند Xn-۱ (متعلق به Xn-۲) ممکن است دارای عضوی به فرض Xn باشد. پس می‌نویسیم:

XnXn-۱ . . . X۳ X۲ X۱ X۰;

به عبارت بالا یک زنجیره عضویتی کاهنده مجموعه X۰ گفته. در نمودار زیر زنجیره‌های عضویتی کاهنده مجموعه {∅, {∅, {∅}}} نشان داده‌شده:

نظریه مجموعه‌ها: زنجیره‌های عضویتی کاهنده
زنجیره‌های عضویتی کاهنده

 آیا روند ساختن یک زنجیره عضویتی برای هر عضو هر مجموعه پایان‌پذیر است یا ممکن است برای بعضی اعضای بعضی مجموعه‌ها این روند بی‌پایان باشد و بتوان نوشت:

. . . Xn Xn-۱ . . . X۳ X۲ X۱ X۰?

پاسخ در ZF نه است. آنچه وجود چنین زنجیره‌ای که به زنجیره‌ عضویتی کاهنده بی‌پایان موسوم است را در ZF نشدنی می‌کند قضیه‌ای بر پایه اصل موضوع بنیاد، که بلافاصله در پی خواهیم دید، است. و از همین‌جا است که اصطلاحاً  گفته می‌شود سازواره مجموعه‌سازی در ZF خوش-بنیاد است. در غیر این صورت ممکن بود بعضی زنجیره عضویتی کاهنده در ZF بی‌پایان باشد. از ناشدنی بودن چنین زنجیره‌ای می‌توان نتیجه گرفت برای هر مجموعه مانند B داریم BB. اگر چنین نباشد آنگاه 

. . . B B

شدنی بود. همین‌طور می‌توان نتیجه گرفت عضویت متقابل (A∈B و B∈A) نیز ناشدنی است. اگر چنین نباشد آنگاه:

. . . A B A B

شدنی بود.


قضیه: در ZF زنجیره‌های عضویتی بی‌پایان کاهشی ناشدنی است.

برهان

مجموعه X را X = {Xn : n∈ ω} گرفته و فرض کرده زنجیره عضویتی کاهنده بی‌پایان شدنی باشد. بنابراین زنجیره زیر شدنی است:

. . . XnXn-۱ . . . X۳ X۲ X۱ X۰.

 اما بنا به اصل موضوع بنیاد عضوی به فرض A در X هست به قسمی که XA=. ازآنجاکه A در X است پس برای بعضی n باید A=Xn که در این صورت Xn+۱ عضو هم X و هم A خواهد بود ( Xn+۱Xn). و ازاینجا داریم Xn+۱XA که خلاف XA= است. بنابراین زنجیره عضویتی کاهنده در ZF پایان‌پذیر هستند.