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

6 - קבוצות בנות מנייה

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • הגדרות
  • דרכי הוכחה שקבוצה היא ב"מ
  • הבחנה בין סימונים דומים
  • מתכון להוכחה שהקבוצה B אינה בת מנייה בעזרת לכסון

6 - קבוצות בנות מנייה

02340129

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

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

קבוצות בנות מנייה

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

uni-folder.vercel.app

הגדרות

הגדרה 1

יהיו A,BA,BA,B קבוצות. נסמן ∣A∣≤∣B∣|A|\leq |B|∣A∣≤∣B∣ אם קיימת f:A→Bf:A\to Bf:A→B חח"ע.

הגדרה 2 (קבוצה בת מנייה)

קבוצה AAA נקראת בת-מנייה, אם ∣A∣≤ℵ0|A|\leq \aleph_{0}∣A∣≤ℵ0​, כאשר ℵ0=∣N∣\aleph_{0}=|\mathbb{N}|ℵ0​=∣N∣.

דוגמה

בנות מנייה - Z,{1,2,3},Q,N\mathbb{Z},\left\{ 1,2,3 \right\},\mathbb{Q},\mathbb{N}Z,{1,2,3},Q,N. כל קבוצה סופית היא בת מניה.
לא בנות מנייה - R,(0,1),P(N)\mathbb{R},(0,1),P(\mathbb{N})R,(0,1),P(N).

הגדרה 3 (איחוד בן מנייה)

⋃i∈BAi\bigcup_{i \in B}A_{i}i∈B⋃​Ai​

יקרא בן מנייה אם BBB היא קבוצה בת מנייה.

משפט (מההרצאה)

איחוד בן מנייה של קבוצות בנות מניה הוא קבוצה בן מנייה.

תרגיל

תהא {A1,…,An}\left\{ A_{1},\dots,A_{n} \right\}{A1​,…,An​} קבוצה סופית של קבוצות בנות-מנייה.
הוכיחו כי המכפלה הקרטזית A1×A2×⋯×AnA_{1}\times A_{2}\times \dots \times A_{n}A1​×A2​×⋯×An​ קבוצה בת מנייה.

רעיון ההוכחה:

  1. נוכיח שאם A,BA,BA,B בנות מנייה, אזי A×BA\times BA×B בת מניה.
  2. נכליל את הטענה באינדוקציה.

הוכחה:
יהיו A,BA,BA,B קבוצות ב"מ. לאור כך, ניתן לרשום A={a0,a1,… }A=\left\{ a_{0},a_{1},\dots \right\}A={a0​,a1​,…}.
נניח ש-AAA אינסופית, ההוכחה במקרה ש-AAA סופית - זהה.

A×B={(a,b)∣a∈A∧b∈B}={(ai,b)∣i∈N,b∈B}A\times B=\left\{ (a,b)|a \in A \land b \in B\right\}=\left\{ (a_{i},b)| i \in \mathbb{N},b \in B \right\}A×B={(a,b)∣a∈A∧b∈B}={(ai​,b)∣i∈N,b∈B} ={(a0,b)∣b∈B}∪{(a1,b)∣b∈B}∪…=\left\{ (a_{0},b)|b \in B \right\} \cup \left\{ (a_{1},b)|b \in B \right\} \cup \dots={(a0​,b)∣b∈B}∪{(a1​,b)∣b∈B}∪… =⋃i∈N{(ai,b)∣b∈B}=⋃i∈N({ai}×B)= \bigcup_{i \in \mathbb{N}}\left\{ (a_{i},b)|b \in B \right\} = \bigcup_{i \in \mathbb{N}}(\left\{ a_{i} \right\}\times B)=i∈N⋃​{(ai​,b)∣b∈B}=i∈N⋃​({ai​}×B)

נוכיח כי לכל i∈Ni \in \mathbb{N}i∈N, {ai}×B\left\{ a_{i} \right\}\times B{ai​}×B ב"מ. יהי i∈Ni \in \mathbb{N}i∈N. נגדיר f:{ai}→B×Bf:\left\{ a_{i} \right\}\to B\times Bf:{ai​}→B×B באופן הבא:

∀b∈B:  f((ai,b))=b\forall b \in B:\; f((a_{i},b))=b∀b∈B:f((ai​,b))=b

הפונקציה חח"ע כי אם (ai,b1)≠(ai,b2)(a_{i},b_{1})\neq(a_{i},b_{2})(ai​,b1​)=(ai​,b2​) אז b1≠b2b_{1}\neq b_{2}b1​=b2​ מהגדרת זוג סדור ולכן f((ai,b1))≠f((ai,b2))f((a_{i},b_{1}))\neq f((a_{i},b_{2}))f((ai​,b1​))=f((ai​,b2​)) ו-fff חח"ע.
הפונקציה fff מקיימת קיום ויחידות כי כל איבר (ai,b)(a_{i},b)(ai​,b) נשלח ל-bbb שקיים ויחד.
הראנו כי קיימת פונקציה חח"ע מ-{ai}×B\left\{ a_{i} \right\}\times B{ai​}×B לקבוצה ב"מ, ולכן, לפי משפט, {ai}×B\left\{ a_{i} \right\}\times B{ai​}×B ב"מ.
הצגנו את A×BA\times BA×B כאיחוד ב"N של קבוצות ב"מ ולכן A×BA\times BA×B ב"מ.
כעת, נוכיח שלכל n∈Nn \in \mathbb{N}n∈N, אילו A1,…,AnA_{1},\dots,A_{n}A1​,…,An​ ב"מ ⇐ A1,…,AnA_{1},\dots,A_{n}A1​,…,An​ ב"מ.
בסיס: n=1n=1n=1 - המכפלה הקרטזית היא A1A_{1}A1​ והיא ב"מ מהגדרה.
צעד: נניח כי A1×⋯×AnA_{1}\times\dots \times A_{n}A1​×⋯×An​ ב"מ ל-nnn טבעי כלשהו, ונראה ש-A1×⋯×An+1A_{1}\times\dots \times A_{n+1}A1​×⋯×An+1​ ב"מ.
נסמן A=A1×⋯×AnA=A_{1}\times\dots \times A_{n}A=A1​×⋯×An​ ו-B=An+1B=A_{n+1}B=An+1​. אנו יודעים כי AAA היא ב"מ מהנחת האינודקציה ו-BBB ב"מ מהנתון.
לכן, לאור מה שהוכחנו הנ"ל, A×BA\times BA×B ב"מ.
∎

הערה

מכפלה קרטזית סופית היא מספר סופי של קבוצות שמוכפלות - הקבוצות הן לאו דווקא סופיות.

דרכי הוכחה שקבוצה היא ב"מ

  1. מראים פונקציה f:A→Nf:A\to \mathbb{N}f:A→N חח"ע. (ישירות מהגדרה)
  2. מראים f:A→Bf:A\to Bf:A→B חח"ע כש-BBB ב"מ.
  3. מראים f:N→Af:\mathbb{N}\to Af:N→A על (ואז לפי משפט יש g:A→Ng:A\to \mathbb{N}g:A→N חח"ע)
  4. משתמשים במשפט איחוד ב"מ של קבוצות ב"מ הוא קבוצה ב"מ.
  5. משתמשים במשפט שהוכחנו עכשיו: מכפלה קרטזית סופית של קבוצות ב"מ היא קבוצה ב"מ.
תרגיל

הוכיחו כי הקבוצה הבאה ב"מ.

C=⋃i∈N+{0,1}iC=\bigcup_{i \in \mathbb{N}^+}\left\{ 0,1 \right\}^iC=i∈N+⋃​{0,1}i

רעיון: נוכיח כי לכל i∈Ni \in \mathbb{N}i∈N הקבוצה {0,1}i\left\{ 0,1 \right\}^i{0,1}i ב"מ, ואז מהמשפט שאיחוד ב"מ של קבוצות ב"מ הוא קבוצה ב"מ נקבל ש-CCC ב"מ.

הוכחה:
יהי i∈N+i \in \mathbb{N}^+i∈N+. {0,1}i\left\{ 0,1 \right\}^i{0,1}i היא מכפלה קרטזית סופית של {0,1}\left\{ 0,1 \right\}{0,1} שהיא ב"מ, ולכן, מהמשפט שהוכחנו {0,1}i\left\{ 0,1 \right\}^i{0,1}i ב"מ.
∎

הבחנה בין סימונים דומים

  • קבוצה בחזקת קבוצה - ABA^BAB - קבוצת הפונקציות מ-BBB ל-AAA.
  • יחס בחזקת מספר - RiR^iRi כאשר i∈Zi \in \mathbb{Z}i∈Z - Ri=R∘R∘…R^i=R \circ R \circ \dotsRi=R∘R∘…
  • קבוצה בחזקת מספר - AiA^iAi עבור i∈Ni \in \mathbb{N}i∈N: Ai=A×⋯×AA^i=A\times\dots \times AAi=A×⋯×A.

מתכון להוכחה שהקבוצה BBB אינה בת מנייה בעזרת לכסון

  1. נניח בשלילה כי BBB היא בת מנייה ⇐ מההגדרה, קיימת פונקציה חח"ע מ-BBB ל-N\mathbb{N}N.
  2. לפי משפט, קיימת פונקציה h:N→Bh:\mathbb{N}\to Bh:N→B על.
  3. נראה שקיים x∈Bx \in Bx∈B כך שלכל n∈Nn \in \mathbb{N}n∈N מתקיים h(n)≠xh(n)\neq xh(n)=x.

[תוכן]

  1. הראנו שקיים x∈Bx \in Bx∈B שאינו בתמונה של hhh - סתירה לכך ש-hhh על.
  2. לכן, BBB אינה בת מנייה.
הערה

גם בלי תוכן נקבל נקודות.

הערה (להערה)

עדיף שיהיה תוכן

תרגיל (כנראה יופיע במבחן או בבחן אמצע)

תהא B={0,1}NB=\left\{ 0,1 \right\}^\mathbb{N}B={0,1}N(כלומר, BBB היא קבוצת הפונקציות מ-N\mathbb{N}N ל-{0,1}\left\{ 0,1 \right\}{0,1}).
הראו בעזרת לכסון ש-BBB אינה ב"מ.

הוכחה:
נניח בשלילה כי BBB בת מנייה ⇐ מההגדרה, קיימת פונקציה חח"ע מ-BBB ל-N\mathbb{N}N. ⇐ לפי משפט, קיימת h:N→Bh:\mathbb{N}\to Bh:N→B על.
נראה כי קיימת g∈Bg \in Bg∈B כך שלכל n∈Nn \in \mathbb{N}n∈N מתקיים h(n)≠gh(n)\neq gh(n)=g. נסמן לכל n∈Nn \in \mathbb{N}n∈N: h(n)=fnh(n)=f_{n}h(n)=fn​.

הערה (ענן המחשבות של אביב צנזור)

012…h(0)=f0010…h(1)=f1000…f2111⋮g110\begin{array}{c|c} & 0 & 1& 2 & \dots \\ \hline h(0)=f_{0}&0&1&0&\dots \\ \hline h(1)=f_{1}&0&0&0&\dots \\ \hline f_{2} & 1&1&1\\ \vdots \\ g & 1&1&0 \end{array}h(0)=f0​h(1)=f1​f2​⋮g​00011​11011​20010​………​

נבחר לכל איבר ב-ggg קלט במקום המתאים ב-hhh ואז נשים בו אחד שהוא בטוח שונה ממנו - כדי ש-ggg יהיה בטוח שונה בתא אחד מכל שורה.
נניח, בתא הראשון נבחר 1 שכן ב-f0f_{0}f0​ במקום ה-000 יש 000.

נגדיר g:N→{0,1}g:\mathbb{N}\to \left\{ 0,1 \right\}g:N→{0,1} באופן הבא:

∀n∈N:  g(n)=1−fn(n)={1fn(n)≠10fn(n)=1\forall n \in \mathbb{N}:\; g(n)=1-f_{n}(n)=\begin{cases} 1 & f_{n}(n)\neq1 \\ 0 & f_{n}(n)=1 \end{cases}∀n∈N:g(n)=1−fn​(n)={10​fn​(n)=1fn​(n)=1​

לכל n∈Nn \in \mathbb{N}n∈N, fnf_{n}fn​ היא פונקציה מ-N\mathbb{N}N ל-{0,1}\left\{ 0,1 \right\}{0,1} ולכן ggg מקיימת קיום ויחידות ושולחת לאיבר ב-{0,1}\left\{ 0,1 \right\}{0,1} מכיוון ש-1−0=11-0=11−0=1 ו-1−1=01-1=01−1=0. בנוסף, על פי הגדרת BBB מתקיים g∈Bg \in Bg∈B.
לכל n∈Nn \in \mathbb{N}n∈N, מתקיים כי g(n)=1−fn(n)≠fn(n)g(n)=1-f_{n}(n)\neq f_{n}(n)g(n)=1−fn​(n)=fn​(n). לכן, משוויון פונקציות fn≠gf_{n}\neq gfn​=g כנדרש.
הראנו כי g∈Bg \in Bg∈B כך ש-ggg אינה בתמונה של -hhh, בסתירה לכך ש-hhh על. לכן, BBB אינה ב"מ.
∎