חזור לתיקייה: תרגול

סדנה על במ לפני מועד א'

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • הוכחת ב"מ
  • לכסון

סדנה על במ לפני מועד א'

02340129

מבוא לתורת הקבוצות ואוטומטים למדמח

רשימות תרגול לקריאה בשבת

סדנה על במ לפני מועד א'

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

הוכחת ב"מ

​סדנה במ למתקא תר 1.png
מה נוכל להגיד על כל קבוצה A∈XA \in XA∈X?
תהי A⊆NA \subseteq \mathbb{N}A⊆N 2-סגורה לחיבור ויהי a∈Aa \in Aa∈A, אזי:

a,a+2,a+4,⋯∈Aa,a+2,a+4,\dots \in Aa,a+2,a+4,⋯∈A

כלומר, לכל b∈Nb \in \mathbb{N}b∈N המקיים b≥ab\geq ab≥a וגם b≡a(mod  2)b\equiv a(mod\; 2)b≡a(mod2) אז b∈Ab \in Ab∈A.

מסקנה

לכל A1,A2⊆NA_{1},A_{2}\subseteq \mathbb{N}A1​,A2​⊆N שהן 2-סגורות לחיבור המקיימות A1≠A2A_{1}\neq A_{2}A1​=A2​, השוני הוא באיבר הזוגי הקטן ביותר בהן(אם קיים) או השוני הוא באיבר האי זוגי הקטן ביותר בהן(אם קיים).

נגדיר f:X→N×Nf:X\to \mathbb{N}\times \mathbb{N}f:X→N×N באופן הבא:
נגדיר:

k=max⁡{min⁡{x∈A∣x≡0(mod  2)}∪{−1}}ℓ=max⁡{min⁡{x∈A∣x≡1(mod  2)}∪{−1}}k=\max\left\{ \min\left\{ x \in A|x\equiv 0(mod\; 2) \right\} \cup \left\{ -1 \right\} \right\} \qquad \ell=\max\left\{ \min\left\{ x \in A|x\equiv 1(mod\; 2) \right\} \cup \left\{ -1 \right\} \right\}k=max{min{x∈A∣x≡0(mod2)}∪{−1}}ℓ=max{min{x∈A∣x≡1(mod2)}∪{−1}} f(A)=(k+1,ℓ+1)f(A)=\left(k+1,\ell+1\right)f(A)=(k+1,ℓ+1)
הערה

זה כמו במלון של הילברט, בו נכניס את האורח החדש לחדר 0.

נוכיח כי fff היא פונקציה.

  • קיום: תהי A∈XA \in XA∈X, יהיו k,ℓk,\ellk,ℓ האיבר האי-זוגי הקטן ביותר ב-AAA והזוגי הקטן ביותר ב-AAA בהתאמה או −1-1−1 בשניהם אם אין כאלו. אזי לכל k,ℓk,\ellk,ℓ יתקיים כי k+1,ℓ+1∈Nk+1,\ell+1 \in \mathbb{N}k+1,ℓ+1∈N ולכן f(A)∈N×Nf(A)\in \mathbb{N}\times \mathbb{N}f(A)∈N×N.
  • יחידות: k,ℓk,\ellk,ℓ הינם איברים יחידים שכן הקבוצות אינן משתנות, ולכן, f(A)f(A)f(A) תמיד יהיה אותו האיבר.

לכן fff פונקציה. כעת נוכיח כי היא חח"ע.
יהיו A1,A2∈XA_{1},A_{2} \in XA1​,A2​∈X כך ש-A1≠A2A_{1}\neq A_{2}A1​=A2​.
מהמסקנה, A1A_{1}A1​ שונה מ-A2A_{2}A2​ לפי האיבר הזוגי הקטן ביותר או האיבר האי-זוגי הקטן ביותר. נחלק למקרים:

  1. האיבר הזוגי הקטן ביותר שונה בשתי הקבוצות: נסמן ב-k1∈A1k_{1} \in A_{1}k1​∈A1​ את האיבר הזוגי הקטן ביותר ב-A1A_{1}A1​ או k1=−1k_{1}=-1k1​=−1 אם לא קיים כזה. בהתאמה, נגדיר גם את k2∈A2k_{2}\in A_{2}k2​∈A2​. מכיוון שהאיבר הזוגי הקטן ביותר שונה בין שתי הקבוצות k1≠k2k_{1}\neq k_{2}k1​=k2​ ולכן, f(A1)=(k1,∗)≠(k2,∗)=f(A2)f(A_{1})=(k_{1},*)\neq(k_{2},*)=f(A_{2})f(A1​)=(k1​,∗)=(k2​,∗)=f(A2​).
  2. האיבר האי-זוגי הקטן ביותר שונה בשתי הקבוצות: נסמן ב-ℓ1∈A1\ell_{1}\in A_{1}ℓ1​∈A1​ את האיבר האי-זוגי הקטן ביותר ב-A1A_{1}A1​ או-ℓ1=−1\ell_{1}=-1ℓ1​=−1 אם לא קיים כזה. בהתאמה נגדיר גם את ℓ2∈A2\ell_{2}\in A_{2}ℓ2​∈A2​. מכיוון שהאיבר האי-זוגי הקטן ביותר שונה בין שתי הקבוצות, ℓ1≠ℓ2\ell_{1}\neq \ell_{2}ℓ1​=ℓ2​ ולכן: f(A1)=(∗,ℓ1)≠(∗,ℓ2)=f(A2)f(A_{1})=(*,\ell_{1})\neq(*,\ell_{2})=f(A_{2})f(A1​)=(∗,ℓ1​)=(∗,ℓ2​)=f(A2​).
הערה

אם k1=k2k_{1}=k_{2}k1​=k2​ וגם ℓ1=ℓ2\ell_{1}=\ell_{2}ℓ1​=ℓ2​ אז A1=A2A_{1}=A_{2}A1​=A2​ לפי המסקנה ממקודם.

לכן, ע"פ הגדרה, ∣A∣≤ℵ0|A|\leq \aleph_{0}∣A∣≤ℵ0​ ולכן, ע"פ הגדרה, AAA ב"מ.
∎

​סדנה דמקה לפני מועד א שאלה 2.png
הוכחה:

הערה (ענן המחשבות)

אם ggg שכנה של fff, אזי ggg יכולה לא להסכים עם fff לפי כל i∈Ni \in \mathbb{N}i∈N. כאשר לכל iii יש ℵ0\aleph_{0}ℵ0​ אפשרויות.
זה אומר כי נוכל לבנות איחוד בן מניה של קבוצות בנות מניה.

נגדיר Xi={g:N→N∣g(i)≠f(i),f שכנה של g}X_{i}=\left\{ g:\mathbb{N}\to \mathbb{N}|g(i)\neq f(i),f\R{\text{ שכנה של }}g \right\}Xi​={g:N→N∣g(i)=f(i),f שכנה של g} עבור כל i∈Ni \in \mathbb{N}i∈N. נשים לב כי X=⋃i∈NXiX=\bigcup_{i \in \mathbb{N}}X_{i}X=⋃i∈N​Xi​. זהו איחוד בן מנייה. כעת, נותר רק להוכיח כי לכל i∈Ni \in \mathbb{N}i∈N הקבוצה XiX_{i}Xi​ היא ב"מ.
יהי i∈Ni \in \mathbb{N}i∈N. נגדיר h:Xi→Nh:X_{i}\to \mathbb{N}h:Xi​→N באופן הבא:

h(g)=g(i)h(g)=g(i)h(g)=g(i)

נוכיח כי זוהי פונקציה:

  • קיום: מכיוון ש-i∈Ni \in \mathbb{N}i∈N ו-g:N→Ng:\mathbb{N}\to \mathbb{N}g:N→N, הפונקציה ggg מוגדרת ב-iii ולכן, g(i)g(i)g(i) קיים.
  • יחידות: ggg היא פונקציה ולכן מקיימת יחידות, לכן, g(i)g(i)g(i) הוא יחיד.

כעת, נוכיח כי hhh חח"ע.
יהיו g1,g2∈Xig_{1},g_{2} \in X_{i}g1​,g2​∈Xi​ כך ש-g1≠g2g_{1}\neq g_{2}g1​=g2​. אזי, מכיוון ש-g1,g2g_{1},g_{2}g1​,g2​ שכנות של fff, לכל i≠k∈Ni\neq k \in \mathbb{N}i=k∈N מתקיים g1(k)=f(k)=g2(k)g_{1}(k)=f(k)=g_{2}(k)g1​(k)=f(k)=g2​(k). לכן, g1(i)≠g2(i)g_{1}(i)\neq g_{2}(i)g1​(i)=g2​(i).
לכן, h(g1)=g1(i)≠g2(i)=h(g2)h(g_{1})=g_{1}(i)\neq g_{2}(i)=h(g_{2})h(g1​)=g1​(i)=g2​(i)=h(g2​).
לכן, קיימת פונקציה מ-XiX_{i}Xi​ ל-N\mathbb{N}N שהיא חח"ע ולכן ∣Xi∣≤ℵ0|X_{i}|\leq \aleph_{0}∣Xi​∣≤ℵ0​. לכן, לפי הגדרה, XiX_{i}Xi​ ב"מ.
לכן, X=⋃i∈NXiX=\bigcup_{i \in \mathbb{N}}X_{i}X=⋃i∈N​Xi​ הוא איחוד ב"מ של קבוצות ב"מ ולכן, לפי משפט, הוא ב"מ.
∎

לכסון

​סדנת דמקה לפני מועד א' תר 3.png

הוכחה: (ב)
נניח בשלילה כי AAA ב"מ. אזי, לפי הגדרה, קיימת פונק' חח"ע מ-AAA ל-N\mathbb{N}N ולכן, לפי משפט, קיימת f:N→Af:\mathbb{N}\to Af:N→A על.
לכל n∈Nn \in \mathbb{N}n∈N נסמן f(n)=Rnf(n)=R_{n}f(n)=Rn​. נגדיר יחס חדש - RRR כך:

R=Id∪{(i,i+1)∣i∈N∧(i,i+1)∉Ri}R=Id \cup \left\{ (i,i+1)|i \in \mathbb{N}\land (i,i+1)\not\in R_{i} \right\}R=Id∪{(i,i+1)∣i∈N∧(i,i+1)∈Ri​}

מכיוון ש-IdIdId היא רפלקסיבית, לכל a∈Na \in \mathbb{N}a∈N מתקיים (a,a)∈Id(a,a)\in Id(a,a)∈Id ולכן, ע"פ הגדרת האיחוד, (a,a)∈R(a,a)\in R(a,a)∈R ולכן, RRR רפלקסיבי ולכן, ע"פ הגדרת AAA נקבל כי R∈AR \in AR∈A.
לכל i∈Ni \in \mathbb{N}i∈N, נקבל כי קיים (i,i+1)(i,i+1)(i,i+1) שנמצא או ב-RRR או ב-RiR_{i}Ri​ אך לא בשניהם ע"פ הגדרת RRR. לכן, R≠RiR\neq R_{i}R=Ri​ לכל iii ולכן R≠f(n)R\neq f(n)R=f(n) לכל n∈Nn \in \mathbb{N}n∈N.
זוהי סתירה לכף ש-fff על AAA ולכן, AAA אינה ב"מ.
∎