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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تاریخچه[ویرایش]

نظریه مجموعه‌ها در اواخر قرن نوزدهم به طور عمده توسط جرج کانتور بنیان گذاشته شد. زمانی که کانتور مفاهیم و استدلال‌های جدید و متهورانهٔ خود را منتشر کرد، اهمیت آن‌ها تنها توسط تعداد کمی از ریاضیدانان بزرگ درک شد. اما این نظریه بعدها، تقریباً در تمام شاخه‌های ریاضیات نفوذ کرد و تأثیری عمیق بر گسترش آن‌ها داشت. به‌طوری که حتی باعث تغییر نظریه‌های تثبیت شده گردید و ریاضیدانان سعی کردند مفاهیم ریاضی را بر اساس نظریهٔ مجموعه‌ها تعریف کنند. به عنوان مثال می‌توان به تعریف اعداد طبیعی توسط پئانو اشاره کرد. همچنین توسعه بعضی از نظام‌های ریاضی، از قبیل توپولوژی، اساساً به ابزار نظریهٔ مجموعه‌ها وابسته‌است. از این‌ها مهم‌تر، نظریهٔ مجموعه‌ها نیرویی متحد کننده بدست داده‌است که به تمام شاخه‌های ریاضیات، وضوح و دقتی تازه بخشیده‌است.

هنگامی که می‌خواهیم با مجموعه‌ها آشنا شویم می‌توانیم آن‌ها را به سه صورت مورد مطالعه قرار دهیم: مطالعهٔ مجموعه‌ها در حد آشنایی عمومی، که برای مطالعهٔ علوم پایه لازم است؛ مطالعهٔ مجموعه‌ها به روش طبیعی و مطالعهٔ مجموعه‌ها به روش بنداشتی. در نظریهٔ مجموعه‌ها دو واژهٔ طبیعی و بنداشتی دو واژهٔ متضاد هم هستند.

نظریهٔ طبیعی مجموعه‌ها[ویرایش]

نوشتار اصلی: نظریه طبیعی مجموعه‌ها

مطالعهٔ مجموعه‌ها به صورتی طبیعی به عنوان نظریه طبیعی مجموعه‌ها یا Naive set theory است و این همان نظریه‌ای است که در آغاز پیدایش نظریهٔ مجموعه‌ها توسط جرج کانتور مطرح گردید. اما در ادامه، این نظریه درگیر اشکالات و پارادکس‌هایی همچون پارادکس راسل شد، و به این ترتیب نیاز به یک تغییر در نظریهٔ مجموعه‌ها احساس شد و به این ترتیب ریاضیدانانی چون ارنست زرملو سعی کردند نظریهٔ مجموعه‌ها را در قالب یک دستگاه بنداشتی ارایه کنند که این به ایجاد نظریه بنداشتی مجموعه‌ها انجامید.

بنداشت مجموعهٔ توانی[ویرایش]

بنداشت توان یکی از بنداشت های نگره کوده ها set theory است که می گوید برای هر کوده x کوده y می هستد که در بر دارنده همه زیر کوده های x، و نه هیچ کوده دیگر، می باشد. این y یکتا است. آن را توانکوده x نامیده با (P(x نشان می دهند.[۱]

نظریهٔ بنداشتی مجموعه‌ها[ویرایش]

در نظریه بنداشتی مجموعه‌ها، مجموعه به عنوان یک مفهوم اولیه و تعریف نشده در نظر گرفته شده و با چند بنداشت به بررسی خواص مجموعه‌ها پرداخته می‌شود. هدف این نظریه جلوگیری از پارادکس‌های نظریه مجموعه‌ها است.

بنداشت گسترش نخستین بنداشت نگره بنداشتی کوده ها (Axiomatic set theory) است و گویای این است که دو کوده x و y برابرند اگر و تنها اگر اندام های (member) یکسانی داشته باشند.

اگر x یک کوده و S یک ویژگی رایه نخست باشد آنگاه گردایه اندام های x که ویژگی S را دارند خود یک کوده است.

اگر x یک کوده باشد x\cup\{x\} را تالی x می نامند. بنداشت نا تهاد (infinity) می گوید کوده ای هست که در بر دارنده تهی است و اگر کودهای را در بر داشته باشد تالی ان را نیز در بر دارد.

برای هر دو کوده x و y کوده z می هستد که آنها را در بر دارد.

برای هر کوده x کوده y می هستد که در بر دارنده هر اندام هر اندام x است.

برای هر کوده x کوده y می هستد که در بر دارنده همه زیر کوده های x، و نه هیچ کوده دیگر، می باشد. این y یکتا است. آن را توانکوده x نامیده با (P(x نشان می دهند.

هر کوده نا تهی x دارای اندامی است که هیچ اندام x را در بر ندارد.

زیرکوده[ویرایش]

A زیرمجموعه B است.

کوده A زیرکوده ای از کوده B است هرگاه هر اندام A اندام B نیز باشد.

{A}\subseteq {B} :\Longleftrightarrow \forall x \left( {x} \in A \rightarrow x \in B \right).

در این حالت B ابرکوده A نامیده می‌شود.


حاصل جمع زیر مجموعه‌ها[ویرایش]

حاصل جمع زیر مجموعه‌ها مسئله‌ای در نظریه مجموعه‌ها است.[۲]

در این مسأله n عدد صحیح مثبت wi و یک عدد صحیح مثبت w داریم. هدف پیدا کردن تمامی زیر مجموعه‌هایی از این اعداد صحیح می‌باشد که حاصل جمع آنها برابر w است.

مثال ۱[ویرایش]

برای n=۵ و w=۲۱ مقادیر زیر:

w۱=۵,w۲=۶,w۳=۱۰,w۴=۱۱,w۵=۱۶

حل مسأله شامل جواب‌های زیر است:

w۱+w۲+w۳=۵+۶+۱۰=۲۱

w۱+w۵=۵+۱۶=۲۱

w۳+w۴=۱۰+۱۱=۲۱

پس الگوریتم باید مجموعه‌های {w۳وw۲وw۱}و{w۵وw۱}و{w۴وw۳} را به عنوان خروجی بدهد.

مسائلی مانند فوق را می‌توان به کمک ترسیم درخت فضای حالت و تکنیک عقب گرد حل کرد.

مثال۲[ویرایش]

برای n=۳ و w=۶ و مقادیر w۳=۵ و w۲=۴ و w۱=۲ درخت فضای حالت به صورت زیر است:



از ریشه که به طرف چپ می‌رویم یعنی w۱ را در مجموعه قرار می‌دهیم و هنگامی که به راست می‌رویم (عدد ۰) یعنی w۱ را داخل مجموعه قرار نمی‌دهیم. به همین ترتیب در سطوح دیگر نیز هنگامی که wi را در یال سمت چپ می‌نویسیم یعنی آن را در مجموعه وارد کرده‌ایم و هنگامی که در سمت راست ۰ می‌نویسیم یعنی آن را در مجموعه قرار نداده‌ایم.

اگر داخل گره‌های درخت فوق جمع اوزان انتخاب شده تا آن گره را بنویسیم با توجه به مقادیر w۱=۲، w۲=۴، w۳=۵ وW=۶ درخت فضای حالت زیر را به دست خواهیم آورد:

مسأله فوق یک جواب {w۱,w۲} دارد.

اگر وزن‌های wi را قبل از جستجو به صورت صعودی مرتب کنیم می‌توانیم یک ویژگی ساده برای غیر امید بخش بودن گره‌ها بیان کنیم. اگر وزن‌ها به صورت صعودی مرتب شده باشند و weight حاصل جمع wiها تا سطح i ام باشد، در این صورت اگر wi+۱ مقدار weight را از W بیشتر کند بدیهی است که وزن‌های بعدی آن نیز چنین خواهند کرد. لذا اگر weight مساوی W نباشد گره‌ای در سطح i ام به شرطی غیر امید بخش است که داشته باشیم:

weight +wi+۱ > W

یک ویژگی دیگر نیز برای غیر امیدبخش بودن یک گره می‌توان بیان کرد. اگر در یک گره معین، اضافه کردن همه وزن‌های قطعات باقی مانده به weight، آن را حداقل با W برابر نکند، در این حالت، مقدار weight در سطوح بعدی آن گره، هیچ گاه با W مساوی نمی‌شود. به عبارتی دیگر اگر total بربر مجموعه wiهای باقی مانده باشد، یک گره در صورتی غیر امیدبخش است که داشته باشیم:

weight+total < W

منابع[ویرایش]

  1. Set theory, T. Yech, Academic Press 1978
  2. درس و کنکور طراحی الگوریتم، مؤلف: حمیدرضا مقسمی، انتشارات: نشر گسنرش علوم
  • Enderton, H. B. Elements of Set Theory, ۲nd edition, ACADEMIC Press, Inc., ۱۹۷۷. ISBN 7-238440-12-0
  • T. Yech, Set theory, Academic Press 1978