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

2 - קבוצת החזקה, שיטות להוכחת טענות אם-אז

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

2 - קבוצת החזקה, שיטות להוכחת טענות אם-אז

02340129

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

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

קבוצת החזקה, שיטות להוכחת טענות אם-אז

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

uni-folder.vercel.app

קבוצת חזקה

הגדרה 1

תהא AAA קבוצה.
קבוצת החזקה של AAA היא קבוצת תתי הקבוצות של AAA.

P(A)={S∣S⊆A}P(A)=\{ S|S \subseteq A \}P(A)={S∣S⊆A}
דוגמה

A={1,∅}  ⟹  P(A)={∅,{1},{∅},A}A=\{ 1,\emptyset \} \implies P(A)=\{ \emptyset,\{ 1 \},\{ \emptyset \},A \}A={1,∅}⟹P(A)={∅,{1},{∅},A} B={1}  ⟹  P(B)={B,∅}B=\{ 1 \}\implies P( B)=\{ B,\emptyset \}B={1}⟹P(B)={B,∅} ∅  ⟹  P(∅)={∅}\emptyset \implies P(\emptyset)=\{ \emptyset \}∅⟹P(∅)={∅}
הערה

אם AAA היא קבוצה עם nnn איברים, אז ב-P(A)P(A)P(A) יש 2n2^n2n איברים.

משפט (תכונות קבוצת החזקה)

  1. כל איבר בקבוצת החזקה הוא בעצמו קבוצה.
  2. לכל קבוצה A, תמיד A,∅A,\emptysetA,∅ שייכים ל-P(A)P(A)P(A).
תרגיל

הוכיחו כי לכל 222 קבוצות A,BA,BA,B מתקיים:
אם P(A∪B)=P(A)∪P(B)P(A \cup B)=P(A)\cup P(B)P(A∪B)=P(A)∪P(B) אז A⊆BA \subseteq BA⊆B או B⊆AB \subseteq AB⊆A.

הוכחה:

הערה (דרך הפתרון)

נוכיח טענה שקולה: אם לא קורה B אז לא A (הנוגד הלוגי)

יהיו A,BA,BA,B קבוצות ונניח כי A⊈BA \not \subseteq BA⊆B וגם כי B⊈AB \not \subseteq AB⊆A. ונרצה להוכיח כי P(A∪B)≠P(A)∪P(B)P(A \cup B)\neq P(A)\cup P(B)P(A∪B)=P(A)∪P(B).
אם A⊈BA \not \subseteq BA⊆B, על פי הגדרת ההכלה, קיים a∈Aa \in Aa∈A כך ש-a∉Ba \not \in Ba∈B.
אם B⊈AB \not \subseteq AB⊆A, על פי הגדרת ההכלה, קיים b∈Bb \in Bb∈B כך ש-b∉Ab \not\in Ab∈A.
לכל a∈Aa \in Aa∈A, על פי הגדרת האיחוד, a∈A∪Ba \in A \cup Ba∈A∪B.
לכל b∈Bb \in Bb∈B, על פי הגדרת האיחוד, b∈A∪Bb \in A \cup Bb∈A∪B.
ולכן, על פי הגדרת ההכלה:

{a,b}⊆A∪B\{ a,b \}\subseteq A \cup B{a,b}⊆A∪B

ולכן, על פי הגדרת קבוצת החזקה, מתקיים:

{a,b}∈P(A∪B)\{ a,b \} \in P(A \cup B){a,b}∈P(A∪B)

נראה כי {a,b}∉P(A)∪P(B)\{ a,b \}\not\in P(A)\cup P(B){a,b}∈P(A)∪P(B).
נניח בשלילה ש-{a,b}∈P(A)∪P(B)\{ a,b \}\in P(A)\cup P(B){a,b}∈P(A)∪P(B).
מהגדרת האיחוד אנו יודעים כי {a,b}∈P(A)\{ a,b \}\in P(A){a,b}∈P(A) או ש-{a,b}∈P(B)\{ a,b \}\in P(B){a,b}∈P(B).
ולכן, מהגדרת קבוצת החזקה, {a,b}⊆A\{ a,b \}\subseteq A{a,b}⊆A או ש-{a,b}⊆B\{ a,b \}\subseteq B{a,b}⊆B.
⇐ מהגדרת ההכלה, b∈Ab \in Ab∈A או a∈Ba \in Ba∈B. מה שעומד בסתירה לתנאים ההתחלתיים שלנו.
לכן, הטענה מתקיימת ולכן, גם הנוגד הלוגי שלה מתקיים ולכן אם P(A∪B)=P(A)∪P(B)P(A \cup B)=P(A)\cup P(B)P(A∪B)=P(A)∪P(B) אז A⊆BA \subseteq BA⊆B או B⊆AB \subseteq AB⊆A
‎∎

שיטות להוכחת טענה מהצורה "אם AAA אז BBB"

  1. ישיר: מניחים כי AAA מתקיים ומוכיחים כי BBB מתקיים לאור זאת.
  2. היפוך: מוכיחים את הנוגד הלוגי של הטענה("אם לא BBB אז לא AAA").
  3. שלילה: מניחים כי AAA נכון, מניחים בשלילה כי BBB לא נכון ומגיעים לסתירה.
  4. אינדוקציה: ניתן להשתמש רק למספרים טבעיים.
  5. באופן ריק:
    אפשרות 1. מוכיחים כי AAA אף פעם לא נכון.
    אפשרות 2. מוכיחים כי BBB תמיד נכון.

איך כותבים דוגמה נגדית

  1. בוחרים ערכים לכל המשתנים בבעיה.
  2. מוכיחים שהדוגמה מקיימת את נתוני הבעיה.
  3. מוכיחים שהדוגמה לא מקיימת את מסקנת הטענה.
תרגיל

הוכיחו או הפריכו כי אם A∖B⊆CA \setminus B \subseteq CA∖B⊆C אזי P(A)∖P(B)⊆P(C)P(A)\setminus P(B)\subseteq P(C)P(A)∖P(B)⊆P(C).

הוכחה:
הטענה אינה נכונה. נראה דוגמה נגדית:
נגדיר A={1,2},B={2},C={1}A=\{ 1,2 \},B=\{ 2 \},C=\{ 1 \}A={1,2},B={2},C={1} .
מתקיים כי A∖B={1}⊆CA \setminus B=\{ 1 \}\subseteq CA∖B={1}⊆C.

P(A)={∅,{1},{2},{1,2}}P(A)=\{ \emptyset,\{ 1 \},\{ 2 \},\{ 1,2 \} \}P(A)={∅,{1},{2},{1,2}} P(B)={∅,{2}}P(B)=\{ \emptyset,\{ 2 \} \}P(B)={∅,{2}} P(A)∖P(B)={{1},{1,2}}P(A)\setminus P(B)=\{ \{ 1 \},\{ 1,2 \} \}P(A)∖P(B)={{1},{1,2}} P(C)={∅,{1}}P(C)=\{ \emptyset,\{ 1 \}\}P(C)={∅,{1}}

מתקיים {1,2}∈P(A)∖P(B)\{ 1,2 \}\in P(A)\setminus P(B){1,2}∈P(A)∖P(B) אבל {1,2}∉P(C)\{ 1,2 \}\not\in P(C){1,2}∈P(C).
לכן, מהגדרת הכלה, P(A)∖P(B)⊈P(C)P(A)\setminus P(B) \not \subseteq P(C)P(A)∖P(B)⊆P(C) כנדרש.
‎∎

הגדרה 2

אם FFF היא קבוצה של קבוצות, נגדיר:

⋃F:=⋃A∈FA:={a∣∃A∈F: a∈A}\bigcup F:= \bigcup_{A \in F}A:=\{ a| \exists A \in F:\ a \in A \}⋃F:=A∈F⋃​A:={a∣∃A∈F: a∈A} ⋂F:=⋂A∈FA:={a∣∀A∈F: a∈A}\bigcap F:=\bigcap_{A \in F}A:=\{ a| \forall A \in F:\ a \in A \}⋂F:=A∈F⋂​A:={a∣∀A∈F: a∈A}
דוגמה

F={{1,2},{2,3},{2,4}}F=\{ \{ 1,2 \},\{ 2,3 \},\{ 2,4 \} \}F={{1,2},{2,3},{2,4}} ⋃F={1,2}∪{2,3}∪{2,4}={1,2,3,4}\bigcup F=\{ 1,2 \}\cup \{ 2,3 \}\cup \{ 2,4 \}=\{ 1,2,3,4 \}⋃F={1,2}∪{2,3}∪{2,4}={1,2,3,4} ⋂F={1,2}∩{2,3}∩{2,4}={2}\bigcap F=\{ 1,2 \}\cap \{ 2,3 \}\cap\{ 2,4 \}=\{ 2 \}⋂F={1,2}∩{2,3}∩{2,4}={2}
הערה

מאוד כדאי לעבוד עם ההגדרה הנ"ל כאשר עובדים עם משהו מופשט.

משפט (מקרה פרטי של ההגדרה ממקודם)

אם F={An∣n∈N}F=\{ A_{n}|n \in \mathbb{N} \}F={An​∣n∈N} כאשר לכל n∈Nn \in \mathbb{N}n∈N, AnA_{n}An​ קבוצה, אז נהוג לכתוב את ⋃F\bigcup F⋃F כך:

⋃n=0∞An=⋃An:={x∣∃n∈N: x∈An}\bigcup_{n=0}^{\infty}A_{n}=\bigcup A_{n}:=\{ x|\exists n \in \mathbb{N}:\ x \in A_{n} \}n=0⋃∞​An​=⋃An​:={x∣∃n∈N: x∈An​}
תרגיל

תהא {An∣n∈N}\{ A_{n}|n \in \mathbb{N} \}{An​∣n∈N} קבוצה של קבוצות ותהא BBB קבוצה.

  1. הוכיחו או הפריכו כי אם קיים i∈Ni \in \mathbb{N}i∈N כך ש-Ai⊆BA_{i}\subseteq BAi​⊆B אז ⋃n∈NAn⊆B\bigcup_{n \in \mathbb{N}}A_{n}\subseteq B⋃n∈N​An​⊆B.
  2. הוכיחו או הפריכו כי אם לכל i∈Ni \in \mathbb{N}i∈N מתקיים Ai⊆BA_{i}\subseteq BAi​⊆B אז: P(⋃n∈NAn)⊆P(B)P(\bigcup_{n \in \mathbb{N}}A_{n}) \subseteq P(B)P(⋃n∈N​An​)⊆P(B)

הוכחה: 1️⃣
הטענה אינה נכונה. נראה דוגמה נגדית:
נגדיר A0={1},A1={2}A_{0}=\{ 1 \},A_{1}=\{ 2 \}A0​={1},A1​={2}
לכל n∈Nn \in \mathbb{N}n∈N כך ש-n>1n>1n>1 נגדיר An=∅A_{n}=\emptysetAn​=∅.
נגדיר B={1}B=\{ 1 \}B={1}.
עבור i=0∈Ni=0 \in \mathbb{N}i=0∈N מתקיים Ai⊆BA_{i}\subseteq BAi​⊆B אבל:

⋃n∈NAn={1,2}⊈{1}=B\bigcup_{n \in \mathbb{N}}A_{n}=\{ 1,2 \} \not\subseteq \{ 1 \}=Bn∈N⋃​An​={1,2}⊆{1}=B

‎∎

הוכחה: 2️⃣

הערה

תחילה נוכיח כי ⋃n∈NAn⊆B\bigcup_{n \in \mathbb{N}}A_{n}\subseteq B⋃n∈N​An​⊆B.
אחרי זה נוכיח כי אם x⊆yx \subseteq yx⊆y אזי P(x)⊆P(y)P(x)\subseteq P(y)P(x)⊆P(y).

יהי x∈Anx \in A_{n}x∈An​. על פי הגדרת איחוד כללי:

x∈⋃n∈NAn  ⟹  ∃n∈N: x∈Anx \in \bigcup_{n \in \mathbb{N}}A_{n} \implies \exists n \in \mathbb{N}:\ x \in A_{n}x∈n∈N⋃​An​⟹∃n∈N: x∈An​

לכל i∈Ni \in \mathbb{N}i∈N A⊆BA \subseteq BA⊆B, בפרט עבור i=ni=ni=n ולכן, בעזרת הגדרת ההכלה:

  ⟹  ∃n∈N: x∈B\implies \exists n \in \mathbb{N}:\ x \in B⟹∃n∈N: x∈B

מכיוון ש-BBB אינו תלוי ב-nnn אזי:

x∈Bx \in Bx∈B

ולכן, מהגדרת ההכלה:

⋃n∈NAn⊆B\bigcup_{n \in \mathbb{N}}A_{n} \subseteq Bn∈N⋃​An​⊆B

נוכיח טענת עזר:

טענה

אם x⊆yx \subseteq yx⊆y אזי P(x)⊆P(y)P(x)\subseteq P(y)P(x)⊆P(y).

הוכחה:
יהיו x,yx,yx,y קבוצות כך ש-x⊆yx \subseteq yx⊆y.
יהי z∈P(x)z \in P(x)z∈P(x).
על פי הגדרת קבוצת חזקה:

z∈P(x)  ⟹  z⊆xz \in P(x) \implies z \subseteq xz∈P(x)⟹z⊆x

על פי הגדרת ההכלה:

∀w∈z:w∈x  ⟹  x⊆y∀w∈z:w∈y\forall w \in z: w \in x \underset{x \subseteq y}{\implies} \forall w \in z: w \in y∀w∈z:w∈xx⊆y⟹​∀w∈z:w∈y

בעזרת הגדרת ההכלה נדע כי:

z⊆yz \subseteq yz⊆y

ולכן, לאור הגדרת קבוצת חזקה:

z∈P(y)z \in P(y)z∈P(y)

ולכן, בעזרת הגדרת ההכלה נדע כי:

P(x)⊆P(y)P(x) \subseteq P(y)P(x)⊆P(y)

‎טענת העזר ∎

בעזרת טענת העזר נדע כי:

x=⋃n∈NAny=Bx=\bigcup_{n \in N}A_{n}\quad y=Bx=n∈N⋃​An​y=B

נקבל ישירות כי:

P(⋃n∈NAn)⊆P(B)P(\bigcup_{n \in \mathbb{N}}A_{n}) \subseteq P(B)P(n∈N⋃​An​)⊆P(B)

‎∎