שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 2022 - יחס סדר

תזכורת: עבור קבוצה $A$, יחס $R \subseteq A \times A$ נקרא סדר חלקי אם הוא רפלקסיבי, אנטי-סימטרי, וטרנזיטיבי. איבר $a \in A$ הוא מקסימלי (ביחס $R$) אם מתקיים: $\forall x \in A.\, aRx \to x = a$. נסמן ב-$X$ את קבוצת יחסי הסדר החלקי מעל $\mathbb{N}$ בהם יש **בדיוק** שני איברים מקסימליים. מה העוצמה של $X$? הוכיחו! הקלה: במהלך ההוכחה אתם אמורים להגדיר פונקציה/פונקציות עם תכונות מסוימות. אין צורך להוכיח שהפונקציות האלה אכן מקיימות תכונות אלה, אלא רק לציין את התכונות עליהן אתם מסתמכים. כמו כן אין צורך להוכיח שפונקציות מוגדרות היטב.

רמז: הראו $|X| \le \aleph$ כי $X \subseteq P(\mathbb{N} \times \mathbb{N})$, ו-$|X| \ge \aleph$ ע"י בניית חח"ע מ-$P(\mathbb{N}'')$ ל-$X$ שמחלקת תת-קבוצות בין שני מקסימלים 0 ו-1.

פתרון: נוכיח ש $|X| = \aleph$. ראשית, $X \subseteq P(\mathbb{N} \times \mathbb{N})$, לכן $|X| \le |P(\mathbb{N} \times \mathbb{N})| = 2^{\aleph_0} = \aleph$. לכיוון השני, נגדיר ראשית $\mathbb{N}'' = \mathbb{N} \setminus \{0, 1\}$, ונגדיר $F \in P(\mathbb{N}'') \to X$ חח"ע באופן הבא: $$F = \lambda A \in P(\mathbb{N}'').\, I_{\mathbb{N}} \cup \{\langle a, 0 \rangle \mid a \in A\} \cup \{\langle a, 1 \rangle \mid a \notin A\}$$ בבירור $\mathbb{N}''$ היא קבוצה בת מניה ולכן $|X| \ge |P(\mathbb{N}'')| = 2^{\aleph_0} = \aleph$. מקש"ב נסיק ש $|X| = \aleph$. **רעיון הפתרון:** בהינתן $A$ תת קבוצה של $\mathbb{N}''$ אנו "קורדנו" אותה בתור איבר של $X$ באופן הבא: דאגנו שיהיו בדיוק שני איברים מקסימליים ב-$F(A)$ והם 0 ו-1. איברי $A$ "נמצאים מתחת" ל-0 בעוד שאר האיברים נמצאים מתחת ל-1. $\blacksquare$