توجه:

عناصر نظریه مجموعه‌ها:  استقرای ریاضی و تعریف‌های بازگشتی  آخرین ویرایش: ۱۳۹۵/۰۷/۰۱ 

عناصر نظریه مجموعه‌ها

۱۸.۱  دنباله

فرض کنید S مجموعه و D یک زیرمجموعه R* باشد. به یک تابع از D در S یک دنباله گفته می‌شود.  اگر SZ دنباله را صحیح و اگر SR دنباله را حقیقی گویند.

 برای مثال، اگر S={a, c, f}؛ آنگاه تابع u در زیر یک دنباله‌ را تعریف می‌کند.

u : {۱, ۲, ۳}S;

تعریف دنباله u
۳ ۲ ۱ eU
u۳=a u۲=a u۱=c u(e)S
به u۱, u۲, u۳ عناصر دنباله U۳ می‌گویند.

ازآنجاکه مجموعه عزیمت یک دنباله همیشه زیرمجموعه R است، معمولاً عناصر یک دنباله را به‌صورت: v1, v2, . . ., vn یا  <v1, v2, . . ., vn> نمایش می‌د‌هند تا بتوان به عنصر خاصی از دنباله با توجه به موقعیت آن اشاره کرد. وقتی مجموعه عزیمت دنباله R باشد دنباله را نامتناهی گفته. عناصر یک دنباله نامتناهی را معمولاً با جمله عمومی دنباله تعریف می‌کنند. در زیر چند مثال از دنباله نامتناهی آمده است:

دنباله جمله عمومی
 <۱, ۴, ۸, . . .> Un=n۲
 <۱, ۲, ۶, . . .> Vn=۱×۲×...×n

به‌آسانی می‌توان دریافت که هر فهرست از اعداد نشان‌دهنده یک دنباله (تابع) است.


۱۹.۱  استقرا در ریاضیات:

....۱.۱۹.۱ اصل استقرای ریاضی:

اصل استقرای ریاضی: گیریم خاصیت P برای عدد ۰ برقرار است و هرگز برای هر عدد طبیعی n برقرار نخواهد بود مگر آنکه برای n+۱ برقرار باشد. در این صورت P برای همه اعداد طبیعی برقرار خواهد بود.


۲.۱۹.۱ استقرای کامل:

استقرای کامل: گیریم خاصیت P برای هر عدد طبیعی n وقتی برقرار است که برای همه اعداد طبیعی کوچک‌تر از n برقرار باشد؛ آنگاه P برای همه اعداد طبیعی برقرار است.

 . هم‌ارزی اصل استقرای ریاضی، استقرای ریاضی کامل و خوش-ترتیبی: اصل استقرای ریاضی و استقرای ریاضی کامل دو بیان متفاوت و هم‌ارز هستند، یعنی با فرض یکی دیگری را می‌توان اثبات کرد. همچنین اصل خوش‌ترتیبی اعداد طبیعی (هر زیرمجموعه ناتهی اعداد طبیعی دارای کوچک‌ترین عنصر است) با اصل استقرای ریاضی هم‌ارز است.

 . استقرای ریاضی: همچنین گیریم خاصیت P برای ۱ برقرار و اگر برای عدد طبیعی n برقرار، برای n+۱ نیز برقرار است؛ آنگاه P برای همه اعداد طبیعی برقرار است.


۲۰.۱  دنباله‌ها، مجموعه‌ها و توابع بازگشتی:

....۱.۲۰.۱  دنباله‌های بازگشتی:

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

۱.۲۰.۱.۱  روش تعریف بازگشتی:

تعریف بازگشتی دنباله در سه گام به شرح زیر انجام می‌شود:

۱- (گام مبنایی) یک یا تعداد محدود از عناصر دنباله معرفی می‌شود؛

۲- (گام استقرایی) اعمالی معرفی که به‌موجب آن اعمال عنصری از دنباله برحسب عناصر موجود (فعلی) دنباله حاصل می‌گردد؛

۳- (گام نهایی) تأکید می‌شود که فقط آنچه از دو مرحله ساخت ۱ و ۲ حاصل می‌شود عنصر دنباله است و نه هیچ‌چیز دیگر.

در مثالی که می‌آید دنباله‌ای بنام Fin را به روش بازگشتی می‌سازیم:

در گام اول می‌گویی ۱ و ۱ ازجمله عناصر این دنباله هستند.
در گام دوم می‌گوییم اگر Fik  و Fik-۱  عناصر این دنباله باشند آنگاه Fik-۱+Fik نیز عنصر این دنباله است.
در گام سوم می‌گوییم فقط آنچه از دو گام اول ساخته می‌شود عنصر Fin است.

در زیر تعدادی از عناصر این دنباله آمده است:

 <Fi۱, Fi۲, Fi۳, Fi۴, Fi۵, Fi۶, Fi۷, . . .>
 <۱, ۱, ۲, ۳, ۵, ۸, ۱۳, . . .>
 <۱ ۱ ۱+۱=۲ ۱+۲=۳ ۲+۳=۵ ۳+۵=۸ ۵+۸=۱۳, . . .>

۲.۲۰.۱ مجموعه‌های بازگشتی

مجموعه‌ها را می‌توان به روش بازگشتی مشابه با آنچه درباره دنباله‌ها (بازگشتی) گفتیم تعریف کرد. مجموعه‌ای که به روش بازگشتی قابل‌تعریف‌ باشد به مجموعه بازگشتی موسوم است. هر مجموعه بازگشتی در سه گام به شرحی که می‌آید تعریف می‌شود:

۱- (گام مبنایی) یک یا تعداد محدودی از اعضای مجموعه معرفی می‌شود؛

۲- (گام استقرایی) اعمال (یا قواعدی) معرفی که به‌موجب آن‌ها عضوی از مجموعه برحسب اعضای موجود (فعلی) مجموعه ساخته می‌شود؛

۳- (گام نهایی) تأکید می‌شود که فقط آنچه از دو مرحله ساخت ۱ و ۲ ساخته شود عضو مجموعه است و نه هیچ عنصر دیگر.

مجموعه‌های بازگشتی

فرض کنید می‌خواهیم مجموعه‌ای بنام N را به روش بازگشتی تعریف کنیم.

۱- در گام مبنایی می‌گوییم:

 ۰N؛

۲- در گام استقرایی می‌گوییم:

 اگر xN آنگاه xN؛

۳- در گام نهایی می‌گوییم:

 فقط و فقط آنچه از ۱ و ۲ حاصل می‌شود عضو N است.

به ۰ عنصر سازنده مجموعه N می‌گوییم. می‌توان دید N همان Z+ است. بنابراین مجموعه اعداد طبیعی یک مجموعه بازگشتی است.

 

برای مثال دیگر فرض کنید می‌خواهیم مجموعه‌ای بنام N' را به روش بازگشتی تعریف کنیم.

۱- در گام مبنایی می‌گوییم ۰N'.

۲- در گام استقرایی ابتدا تابع s را در N' به قسمی تعریف می‌کنیم که s(x) مخالف ۰ و نیز مخالف اعضای تاکنون ساخته‌شده در N' باشد و می‌گوییم اگر xN' باشد آنگاه s(x)N'.

۳- در گام نهایی می‌گوییم:

 فقط و فقط آنچه از ۱ و ۲ حاصل می‌شود عضو N' است.

بنابراین

N'={۰, s(۰), s(s(۰)), s(s(s(۰))), . . .}.

 

 . به تابعی با کارکرد تابع s در بالا تابع تالی [پی-آمد] گفته و آن را معمولاً با succ نشان داده. در این مثال می‌توان نوشت:

succ(n) = n + ۱ .

برای مثال دیگر فرض کنید می‌خواهیم مجموعه‌ای بنام N'' را به روش بازگشتی تعریف کنیم.

۱- در گام مبنایی می‌گوییم:

 øN''.

۲- در گام استقرایی می‌گوییم:

 اگر xN'' باشد آنگاه x{x}N''. [در اینجا succ(x)=x{x}.]

۳- در گام نهایی می‌گوییم:

 فقط و فقط آنچه از ۱ و ۲ حاصل می‌شود عضو N'' است.

بنابراین:

N''={ø, ø∪{ø}={ø}, {ø}∪{{ø}}=, {ø}}, , {ø},{ø,{ø}}}, . . . }.

اگر در این مثال ø را با نماد ۰، {ø} را با ۱،  {ø, {ø}} را با ۲ نشان دهیم و همین‌طور مانند آن‌ها، آنگاه مجموعه {۰, ۱, ۲, . . .} را در پی خواهیم داشت که ø عنصر سازنده آن است [دستگاه اصل موضوعی اعداد .]


۳.۲۰.۱ توابع بازگشتی:

ازآنجاکه توابع مجموعه هستند، توابع بازگشتی  را نیز می‌توان به همان سیاق مجموعه‌های بازگشتی تعریف کرد. توابع بازگشتی ازجمله در دانش کامپیوتر (الگوریتم، ماشین، محاسبه‌پذیری، هوش مصنوعی و جاهای دیگر) دارای اهمیت اساسی هستند. در یک رهیافت (رهیافت موسوم به آلونزو چرچ/ Alonzo Church ریاضیدان و منطقی آمریکایی- ۱۹۹۵-۱۹۰۳) یک روند را روش کارآمد (یا الگوریتم و نیز، روش مکانیکی) گوییم اگر قابل‌بیان توسط تعداد محدود توابع بازگشتی باشد. در هنگام بحث الگوریتم و ماشین به این بحث بازمی‌گردیم.


ادامه: . . . . .

 

© 1987 - 2017 KHcc Sc.