اصول موضوعه در دستگاه ZF (۳)

[قضیه نقطه برجا به عنوان قضیه بازگشت (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.

• اثبات:

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

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

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

g = ∩_A∈SA.

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

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

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

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

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

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

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

U = {x ∈ ℕ^*: (x, y), (x, z)∈g ⇒ x = z}

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

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

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

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

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

اما چون m⁺∉U پس افزون بر (m⁺,f(n))∈g دوتایی (m⁺,z)∈g وجود دارد، به قسمی که z≠f(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.

اگر n∈V آنگاه 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)).

y ← g(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.