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

נגדיר את היחס $R \subseteq \mathcal{P}(\mathbb{N}) \times \mathcal{P}(\mathbb{N})$ באופן הבא: $$R = \{\langle A, B \rangle \in \mathcal{P}(\mathbb{N}) \mid A \cap \mathbb{N}_{even} = B \cap \mathbb{N}_{even}\}$$ $R$ הוא יחס שקילות. נסמן: $$A = \{B \cup \{6\} \mid B \in \mathcal{P}(\mathbb{N}_{odd})\}$$ ידוע כי $[\{5,6\}]_R = A$. הוכיחו באמצעות לכסון ש-$[\{5,6\}]_R$ אינה בת מנייה.

רמז: השתמשו בלכסון ישירות על $A = \{B \cup \{6\} \mid B \in \mathcal{P}(\mathbb{N}_{odd})\}$. נניח בשלילה שקיימת פונקציה על מ-$\mathbb{N}$ ל-$A$, ובנו באמצעות לכסון איבר ב-$A$ שלא נמצא בטווח.

פתרון: **הוכחה בלכסון:** נניח בשלילה ש-$[\{5,6\}]_R = A$ בת מנייה. אז קיימת פונקציה על $h: \mathbb{N} \to A$. לכל $n \in \mathbb{N}$, $h(n) \in A$, כלומר $h(n) = B_n \cup \{6\}$ עבור $B_n \in \mathcal{P}(\mathbb{N}_{odd})$ כלשהי. נרשום את האיברים האי-זוגיים בסדר עולה: $\mathbb{N}_{odd} = \{1, 3, 5, 7, 9, \ldots\}$. נסמן את האיבר ה-$n$-י (החל מ-$0$) ברשימה זו כ-$o_n$, כלומר $o_n = 2n+1$. נגדיר קבוצה חדשה באמצעות לכסון: $$D = \{o_n \in \mathbb{N}_{odd} \mid o_n \notin B_n\}$$ $D \subseteq \mathbb{N}_{odd}$, לכן $D \in \mathcal{P}(\mathbb{N}_{odd})$, ולכן $D \cup \{6\} \in A$. נראה ש-$D \cup \{6\} \neq h(n)$ לכל $n \in \mathbb{N}$: עבור כל $n$: $h(n) = B_n \cup \{6\}$. - אם $o_n \in B_n$, אז $o_n \notin D$ (מהגדרת $D$), לכן $D \neq B_n$. - אם $o_n \notin B_n$, אז $o_n \in D$ (מהגדרת $D$), לכן $D \neq B_n$. בכל מקרה $D \neq B_n$, לכן $D \cup \{6\} \neq B_n \cup \{6\} = h(n)$. מצאנו $D \cup \{6\} \in A$ שאינו בטווח $h$, בסתירה לכך ש-$h$ על. לכן $[\{5,6\}]_R$ אינה בת מנייה. $\blacksquare$