جبر مجموعه‌ها

جبر مجموعه‌ها خواص و قوانین مجموعه، تقاطع و متمم و روابط برابری و شمول مجموعه‌ها را بیان می‌کند. همچنین روشی اصولی برای ارزیابی عبارات و انجام محاسبات شامل این عملیات و روابط فراهم می‌کند. هر مجموعه‌ای تحت عملیات نظریه مجموعه‌ها یک جبر بولی را تشکیل می‌دهد. (عملگر ${\displaystyle +}$ همان اجتماع، عملگر ${\displaystyle .}$ همان اشتراک و عملگر متمم بیانگر متمم مجموعه است.)

پایه

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

جبر مجموعه ها، جبری از عملیات اجتماع، اشتراک و متمم، و روابط برابری و شمول نظریهٔ مجموعه‌ها است. برای یک آشنایی ساده با مجموعه ها، به مقالات مجموعه (ریاضی) نگاه کنید، برای یک آشنایی بیشتر و عمیق تر، نظریه طبیعی مجموعه‌ها را ببینید ، و برای بررسی دقیق و کامل نظریهٔ مجموعه ها، نظریه مجموعه‌ها را ببینید.

قوانین بنیادی جبر مجموعه‌ها

عملیات باینری اجتماع(∪) و اشتراک(∩) خواصی را به وجود آورده اند که برخی از این خواص یا "قوانین" دارای نام‌های به خصوص و مشهوری هستند:

قانون جابه جایی:

• ${\displaystyle A\cup B=B\cup A\,\!}$
• ${\displaystyle A\cap B=B\cap A\,\!}$

قانون شرکت پذیری:

• ${\displaystyle (A\cup B)\cup C=A\cup (B\cup C)\,\!}$
• ${\displaystyle (A\cap B)\cap C=A\cap (B\cap C)\,\!}$

قانون پخشی:

• ${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)\,\!}$
• ${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\,\!}$

شباهت بین اجتماع و اشتراک مجموعه ها، و جمع و ضرب اعداد، کاملاً قابل توجه است. مانند جمع و ضرب، عملیات اجتماع و اشتراک دارای خواص جابجایی و شرکت‌پذیری هستند، و اشتراک بر روی اجتماع پخش پذیر است.البته بر خلاف جمع و ضرب، اجتماع نیز بر روی اشتراک پخش پذیر است.

دو قانون دیگر شامل مجموعه‌های خاصی با نام مجموعه ی تهی (∅) و مجموعه جهانی (U) می‌شود؛ که متمم یکدیگرند. مجموعه ی تهی هیچ عضوی ندارد، و مجموعه ی جهانی است شامل همهٔ اعضای امکان پذیر است (در یک زمینه خاص).

قانون هویت:

• ${\displaystyle A\cup \varnothing =A\,\!}$
• ${\displaystyle A\cap U=A\,\!}$

قانون متمم:

• ${\displaystyle A\cup A^{C}=U\,\!}$
• ${\displaystyle A\cap A^{C}=\varnothing \,\!}$

قوانین هویت (همراه با قوانین جابجایی) می گویند که، درست مثل 0 و 1 برای جمع و ضرب، ∅ و U عناصر هویت برای اجتماع و اشتراک‌اند.

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

پنج قانون یادشده - جابجایی، شرکت پذیری، پخش پذیری، هویت و متمم – تمام جبر مجموعه‌ها را در بر می‌گیرد، به این معنا که هر گزاره معتبر در جبر مجموعه‌ها می‌تواند از آن‌ها استنتاج شود.

توجه داشته باشید که اگر قوانین مکمل به قانون ${\displaystyle (A^{C})^{C}=A}$ تقلیل داده شود، این دقیقاً همان جبر منطق خطی است.

اصل دوگانگی

هر جفت از خواص مطرح شده در بالا را می‌توان با جایگزینی ∪ به جای ∩ و برعکس و همچنین ∅ به جای U و برعکس، به یکدیگر تبدیل نمود.

اینها مثال‌هایی از یکی از ویژگی‌های بسیار مهم و قدرتمند جبر مجموعه‌ها یعنی، اصل دوگانگی است، که ادعا می‌کند که برای هر عبارت درست در مورد مجموعه ها، عبارت دوگان توسط تبادل اجتماع‌ها و اشتراک‌ها و همچنین تبادل U و ∅ به دست می‌آید که این عبارت نیز درست است. اگر دوگان یک عبارت با خود عبارت برابر باشد، عبارت را خود-دوگان می گوییم.

چند قانون دیگر برای اجتماع و اشتراک

گزاره زیر، شش قانون مهم دیگر از جبر مجموعه‌ها -شامل اجتماع‌ها و اشتراک ها- را بیان می‌کند. گزاره 3: هر زیر مجموعه‌ای از مجموعه ی جهانی U، مانند A و B، خواص زیر را دارا می‌باشند:

قوانین همانی:

• ${\displaystyle A\cup A=A\,\!}$
• ${\displaystyle A\cap A=A\,\!}$

قوانین غلبه:

• ${\displaystyle A\cup U=U\,\!}$
• ${\displaystyle A\cap \varnothing =\varnothing \,\!}$

قوانین جذب:

• ${\displaystyle A\cup (A\cap B)=A\,\!}$
• ${\displaystyle A\cap (A\cup B)=A\,\!}$

همانطور که در بالا اشاره شد، هر یک از قوانین مندرج در گزاره 3 را می‌توان از پنج قانون بنیادی استنتاج کرد. به عنوان مثال، یک اثبات برای قانون همانی اجتماع در زیر بیان شده‌است.

اثبات:

${\displaystyle A\cup A\,\!}$	${\displaystyle =(A\cup A)\cap U\,\!}$	طبق قانون هویت اشتراک
	${\displaystyle =(A\cup A)\cap (A\cup A^{C})\,\!}$	طبق قانون متمم اجتماع
	${\displaystyle =A\cup (A\cap A^{C})\,\!}$	طبق قانون پخش‌پذیری اجتماع بر روی اشتراک
	${\displaystyle =A\cup \varnothing \,\!}$	طبق قانون متمم اشتراک
	${\displaystyle =A\,\!}$	طبق قانون هویت اجتماع

اثبات زیر نشان می‌دهد که دوگان اثبات فوق، اثبات "دوگان قانون همانی برای اجتماع"، یعنی "قانون همانی برای اشتراک" است.

اثبات:

${\displaystyle A\cap A\,\!}$	${\displaystyle =(A\cap A)\cup \varnothing }$	طبق قانون هویت اجتماع
	${\displaystyle =(A\cap A)\cup (A\cap A^{C})\,\!}$	طبق قانون متمم اشتراک
	${\displaystyle =A\cap (A\cup A^{C})\,\!}$	طبق قانون پخش‌پذیری اشتراک بر روی اجتماع
	${\displaystyle =A\cap U\,\!}$	طبق قانون متمم اجتماع
	${\displaystyle =A\,\!}$	طبق قانون هویت اشتراک

اشتراک دو مجموعه را می‌توان با عملگر "تفاضل دو مجموعه" بیان کرد: ${\displaystyle A\cap B\,\!=A\smallsetminus (A\smallsetminus B)}$

چند قانون دیگر برای متمم

گزاره ی زیر چند قانون مهم تر در باب متمم‌ها را بیان می‌کند:

گزاره ی 4 : فرض کنید A و B، زیرمجموعه‌هایی از مجموعه ی جهانی U باشند:

قانون دمرگان:یکی از قوانین مهم که به افتخار کاشف آن نامگذاری شده.

• ${\displaystyle (A\cup B)^{C}=A^{C}\cap B^{C}\,\!}$
• ${\displaystyle (A\cap B)^{C}=A^{C}\cup B^{C}\,\!}$

مکمل دوتایی یا قانون همانی:

• ${\displaystyle {(A^{C})}^{C}=A\,\!}$

قوانین متمم برای مجموعه ی جهانی و مجموعه ی تهی:

• ${\displaystyle \varnothing ^{C}=U}$
• ${\displaystyle U^{C}=\varnothing }$

توجه کنید که مکمل دوتایی، خود-دوگان است.

گزاره ی بعدی، که آن هم خود-دوگان است، بیان می‌کند که متمم یک مجموعه تنها مجموعه‌ای است که قوانین متمم برایش صادق است. به عبارت دیگر، متمم توسط قوانین متمم مشخص می‌شود.

گزاره ی 5 : فرض کنید A و B، زیرمجموعه‌هایی از مجموعه ی جهانی U باشند:

همتایی متمم:

• اگر ${\displaystyle A\cup B=U\,\!}$ و ${\displaystyle A\cap B=\varnothing \,\!}$، آنگاه ${\displaystyle B=A^{C}\,\!}$

جبر شمول

گزاره ی زیر بیان می‌کند که شمول دارای خاصیت ترتیب است:

گزاره ی 6 : B ، A و C سه مجموعه هستند:

بازتابی:

• ${\displaystyle A\subseteq A\,\!}$

پادتقارنی:

• ${\displaystyle A\subseteq B\,\!}$ و ${\displaystyle B\subseteq A\,\!}$ اگر و تنها اگر ${\displaystyle A=B\,\!}$

تراگذری:

• اگر ${\displaystyle A\subseteq B\,\!}$ و ${\displaystyle B\subseteq C\,\!}$، آنگاه ${\displaystyle A\subseteq C\,\!}$

گزاره زیر می گوید که برای هر مجموعه S، مجموعه توانی S، یک توری محدود است، و از این رو همراه با قوانین توزیع و متمم فوق، نشان داده می‌شود که یک جبر بولی است.

گزاره ی 7: اگر B ، A و C سه زیرمجموعه از S باشند:

وجود کوچکترین عضو و بزرگترین عضو:

• ${\displaystyle \varnothing \subseteq A\subseteq S\,\!}$

وجود سوپریمم:

• ${\displaystyle A\subseteq A\cup B\,\!}$
• اگر ${\displaystyle A\subseteq C\,\!}$ و ${\displaystyle B\subseteq C\,\!}$، آنگاه ${\displaystyle A\cup B\subseteq C\,\!}$

وجود اینفیمم:

• ${\displaystyle A\cap B\subseteq A\,\!}$
• اگر ${\displaystyle C\subseteq A\,\!}$ و ${\displaystyle C\subseteq B\,\!}$، آنگاه ${\displaystyle C\subseteq A\cap B\,\!}$

گزاره ی زیر بیان می‌کند که عبارت ${\displaystyle A\subseteq B\,\!}$ معادل عبارت‌های دیگر از جمله اشتراک، اجتماع و مکمل است.

گزاره ی 8 : برای هر دو مجموعه ی A و B عبارت‌های زیر همگی معادل اند:

• ${\displaystyle A\subseteq B\,\!}$
• ${\displaystyle A\cap B=A\,\!}$
• ${\displaystyle A\cup B=B\,\!}$
• ${\displaystyle A\smallsetminus B=\varnothing }$
• ${\displaystyle B^{C}\subseteq A^{C}}$

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

جبر متمم

گزاره ی زیر شامل چند خاصیت پیرامون اصل متمم است.

گزاره ی 9 : برای هر مجموعه ی جهانی U و زیرمجموعه‌های B ، A و C از این مجموعه داریم:

• ${\displaystyle C\setminus (A\cap B)=(C\setminus A)\cup (C\setminus B)\,\!}$
• ${\displaystyle C\setminus (A\cup B)=(C\setminus A)\cap (C\setminus B)\,\!}$
• ${\displaystyle C\setminus (B\setminus A)=(A\cap C)\cup (C\setminus B)\,\!}$
• ${\displaystyle (B\setminus A)\cap C=(B\cap C)\setminus A=B\cap (C\setminus A)\,\!}$
• ${\displaystyle (B\setminus A)\cup C=(B\cup C)\setminus (A\setminus C)\,\!}$
• ${\displaystyle A\setminus A=\varnothing \,\!}$
• ${\displaystyle \varnothing \setminus A=\varnothing \,\!}$
• ${\displaystyle A\setminus \varnothing =A\,\!}$
• ${\displaystyle B\setminus A=A^{C}\cap B\,\!}$
• ${\displaystyle (B\setminus A)^{C}=A\cup B^{C}\,\!}$
• ${\displaystyle U\setminus A=A^{C}\,\!}$
• ${\displaystyle A\setminus U=\varnothing \,\!}$

منابع

• Enderton, H. B. Elements of Set Theory, 2nd edition, ACADEMIC Press, Inc., 1977.

• کتاب درسی جبر و احتمال، سال سوم نظام جدید (رشته ریاضی،فیزیک).