משתמש:יחס הזהב/טיוטה4

שאלה 1

נתון:
1. $x\in A$
2. $(A\triangle B)\cap C=\emptyset$.
צ"ל: $x\in B\leftarrow x\in C$

הוכחה:

יהי $x$ שרירותי. נתון $x\in A$ ונניח $x\in C$.

נתון $(A\triangle B)\cap C=\emptyset$. אז מהגדרת הפרש סימטרי $(A\cup B\setminus A\cap B)\cap C=\emptyset$, כלומר: $x\notin (A\cup B\setminus A\cap B)\cap C$. אבל מהנחה $x\in C$ אז מהגדרת חיתוך $x\notin (A\cup B\setminus A\cap B)$.

מהגדרת הפרש $x\notin A\cup B$ או $x\in A\cup B)$ וגם $(x\in A\cap B$. אבל נתון $x\in A$ אז מהגדרת העצמי $x\in A\cup B$. לכן $x\in A\cup B$ וגם $x\in A\cap B$. מהגדרת חיתוך $x\in A$ וגם $x\in B$. מש"ל.

שאלה 2

צ"ל:
${\mathcal {P}}(A\setminus B)\subseteq ({\mathcal {P}}(A)\setminus {\mathcal {P}}(B))\ \cup \ \left\{\emptyset \right\}$

הוכחה:

יהי $x$ שרירותי. נניח $x\in {\displaystyle {\mathcal {P}}(A\setminus B)}$, אז מהגדרת קבוצת חזקה $x\subseteq A\setminus B$. נפצל למקרים:

• $x\neq \emptyset$:
  מהגדרת הכלה לכל $y\in x$ מתקיים $y\in A\setminus B$. אז מהגדרת הפרש $y\in A$ וגם $y\notin B$. אז מהגדרת הכלה $x\subseteq A$ וגם $x\not \subseteq B$. אז מהגדרת קבוצת חזקה $x\in {\mathcal {P}}(A)$ וגם $x\notin {\mathcal {P}}(B)$. אז מהגדרת הפרש $x\in {\mathcal {P}}(A)\setminus {\mathcal {P}}(B)$. אז מהגדרת העצמי $x\in ({\mathcal {P}}(A)\setminus {\mathcal {P}}(B))\ \cup \ \left\{\emptyset \right\}$. מש"ל.

• $x=\emptyset$:
  אגף שמאל: הנחנו $x\in {\displaystyle {\mathcal {P}}(A\setminus B)}$ וגם $x=\emptyset$ אז $\emptyset \in {\mathcal {P}}(A\setminus B)$.
  אגף ימין: $({\mathcal {P}}(A)\setminus {\mathcal {P}}(B))\ \cup \ \left\{\emptyset \right\}$. ברור ש-$\emptyset \in \left\{\emptyset \right\}$ אז מהגדרת האיחוד $\emptyset \in ({\mathcal {P}}(A)\setminus {\mathcal {P}}(B))\ \cup \ \left\{\emptyset \right\}$. מש"ל.

שאלה 3

נתון:

1. $\{A_{i}\}_{i\in I}$ קבוצה של קבוצות.
2. $I\neq \emptyset$.
3. תהי $B$ קבוצה.

צ"ל: $B\setminus \bigcap _{i\in I}A_{i}=\bigcup _{i\in I}(B\setminus A_{i})$ הוכחה:

$\Rightarrow$: יהי $x$ שרירותי. נניח $x\in B\setminus \bigcap _{i\in I}A_{i}$. לפי הגדרת הפרש $x\in B$ וגם $x\notin \bigcap _{i\in I}A_{i}$. אז לפי הגדרת חיתוך אונארי $\exists A_{i}\in A:x\notin A_{i}$. לכן, ומכך ש-$x\in B$, אז קיים $A_{i}$ כך ש-$x\in B\setminus A_{i}$ ומהגדרת איחוד אונארי $x\in \bigcup _{i\in I}(B\setminus A_{i})$. הראנו שלכל$x\in B\setminus \bigcap _{i\in I}A_{i}$ מתקיים $x\in \bigcup _{i\in I}(B\setminus A_{i})$. אז מהגדרת הכלה: $B\setminus \bigcap _{i\in I}A_{i}\subseteq \bigcup _{i\in I}(B\setminus A_{i})$.

$\Leftarrow$: יהי $x$ שרירותי. נניח $x\in \bigcup _{i\in I}(B\setminus A_{i})$. אז לפי הגדרת הפרש $x\in B$ וגם $x\notin \bigcup _{i\in I}A_{i}$. אז מהגדרת איחוד אונארי $\forall A_{i}\in A:x\notin A_{i}$. נפצל למקרים:

• $A=\emptyset$: אז מהגדרת חיתוך אונארי $\bigcap _{i\in I}A_{i}=\emptyset$ אז מהגדרת הפרש $B\setminus \bigcap _{i\in I}A_{i}=B$ ומהנחה ש-$x\in B$ נובע $x\in B\setminus \bigcap _{i\in I}A_{i}$.
• $A\neq \emptyset$: הראנו קודם ש-$\forall A_{i}\in A:x\notin A_{i}$ והנחנו $A\neq \emptyset$ אזי, $\exists A_{i}\in A:x\notin A_{i}$, אז מהגדרת חיתוך אונארי $x\notin \bigcap _{i\in I}A_{i}$. הנחנו $x\in B$ אז מהגדרת הפרש $x\in B\setminus \bigcap _{i\in I}A_{i}$.

הראנו הכלה דו־כיוונית ולכן $B\setminus \bigcap _{i\in I}A_{i}=\bigcup _{i\in I}(B\setminus A_{i})$. מש"ל.

שאלה 4

צ"ל:

$\bigcup {\mathcal {F}}\subseteq B\Leftarrow {\mathcal {F}}\subseteq {\mathcal {P}}(B)$

הוכחה:

נניח ${\mathcal {F}}\subseteq {\mathcal {P}}(B)$. מהגדרת הכלה $\forall x\in {\mathcal {F}}:x\in {\mathcal {P}}(B)$ אז $x\in {\mathcal {P}}(B)\Leftarrow x\in {\mathcal {F}}$.

מהגדרת קבוצת חזקה $\forall x\in {\mathcal {P}}(B):x\subseteq B$ אז $x\subseteq B\Leftarrow x\in {\mathcal {P}}(B)$.

לפיכך $x\subseteq B\Leftarrow x\in {\mathcal {P}}(B)\Leftarrow x\in {\mathcal {F}}$.

מהגדרת הכלה $\forall y\in x:y\in B$ אז $y\in B\Leftarrow y\in x$.

יהי $y$ שרירותי. נניח $y\in \bigcup {\mathcal {F}}$.

מהגדרת איחוד אונארי $\bigcup {\mathcal {F}}=\{y\mid \exists x\in {\mathcal {F}}:y\in x\}$. אז מכך ש-$y\in \bigcup {\mathcal {F}}$ נובע $y\in x$. אבל הראנו ש-$y\in B\Leftarrow y\in x$, אזי $y\in B$. מש"ל.

שאלה 5

נתון:

1. ${\mathcal {F}}$ ו-${\mathcal {G}}$ קבוצות לא ריקות של קבוצות.

צ"ל: $\bigcup ({\mathcal {F}}\ \cup \ {\mathcal {G}})=\bigcup {\mathcal {F}}\cup \ \bigcup {\mathcal {G}}$

הוכחה:

$\Rightarrow$: יהי $x$ שרירותי. נניח $x\in \bigcup ({\mathcal {F}}\ \cup \ {\mathcal {G}})$. אז מהגדרת איחוד אונארי $\exists y\in ({\mathcal {F}}\cup {\mathcal {G}}):x\in y$. מהגדרת איחוד $y\in {\mathcal {F}}$ או $y\in {\mathcal {G}}$. נפצל למקרים:

• $y\in {\mathcal {F}}$: הראנו $x\in y$ אז לפי הגדרת איחוד אונארי $x\in \bigcup {\mathcal {F}}$. אז מהגדרת איחוד $x\in \bigcup {\mathcal {F}}\cup \ \bigcup {\mathcal {G}}$.
• $y\in {\mathcal {G}}$: הראנו $x\in y$ אז לפי הגדרת איחוד אונארי $x\in \bigcup {\mathcal {G}}$. אז מהגדרת איחוד $x\in \bigcup {\mathcal {F}}\cup \ \bigcup {\mathcal {G}}$.

$\Leftarrow$: יהי $x$ שרירותי. נניח $x\in \bigcup {\mathcal {F}}\cup \ \bigcup {\mathcal {G}}$. מהגדרת איחוד $x\in \bigcup {\mathcal {F}}$ או $x\in \bigcup {\mathcal {G}}$. נפצל למקרים:

• $x\in \bigcup {\mathcal {F}}$: אז מהגדרת איחוד אונארי $\exists y\in {\mathcal {F}}:x\in y$. אז מהגדרת איחוד $y\in {\mathcal {F}}\cup {\mathcal {G}}$ והראנו $x\in y$ אזי מהגדרת איחוד אונארי $x\in \bigcup ({\mathcal {F}}\ \cup \ {\mathcal {G}})$.
• $x\in \bigcup {\mathcal {G}}$ אז מהגדרת איחוד אונארי $\exists y\in {\mathcal {G}}:x\in y$. אז מהגדרת איחוד $y\in {\mathcal {F}}\cup {\mathcal {G}}$ והראנו $x\in y$ אזי מהגדרת איחוד אונארי $x\in \bigcup ({\mathcal {F}}\ \cup \ {\mathcal {G}})$.

הראנו הכלה דו-כיוונית ולכן הקבוצות שוות.

שאלה 6

צ"ל: $\exists !X:A\vartriangle X=A$

הוכחה:

נראה שקיים $X$ עבורו הטענה מתקיימת.

נניח $X=\emptyset$.

$\Leftarrow$: יהי $x$ שרירותי. נניח $x\in A\vartriangle X$. מהגדרת הפרש סימטרי $x\in A\setminus X\cup X\setminus A$. מהגדרת הפרש $x\in A)$ וגם $(x\notin X$ או $x\in X)$ וגם $(x\notin A$. הנחנו $X=\emptyset$ אז מהגדרת הקבוצה הריקה $!\exists x\in X$ ולכן בהכרח $x\in A)$ וגם $(x\notin X$. אז מהגדרת "וגם" $x\in A$.

$\Rightarrow$: יהי $x$ שרירותי. נניח $x\in A$. הנחנו $X=\emptyset$, אז מהגדרת הפרש $x\in A\setminus X$ וגם $x\notin X\setminus A$. מהגדרת איחוד $x\in A\setminus X\cup X\setminus A$. מהגדרת הפרש סימטרי $x\in A\vartriangle X$.

הראנו הכלה דו-כיוונית ולכן עבור $X=\emptyset$ מתקיים $A\vartriangle X=A$. כלומר הראנו שקיים $X$ המקיים את הטענה. נותר להראות שלא קיים עוד $X$ כזה.

נניח בשלילה ש-$\exists X:(A\vartriangle X=A)\land (X\neq \emptyset )$. נפצל למקרים:

• $A\cap X=\emptyset$: הנחנו $X\neq \emptyset$ אז מהגדרת הקבוצה הריקה $\exists y:y\in X$. אז מהגדרת האיחוד $y\in A\cup X$. הנחנו $A\cap X=\emptyset$ אז $A$ זרה ל-$X$ ולכן $\neg \exists z:z\in X\land z\in A$ או באופן שקול $\forall z:z\notin X\lor z\notin A$. אז מכך ש-$y\in X$ נובע $y\notin A$. מהגדרת האיחוד $y\in A\cup X$ והנחנו $A\cap X=\emptyset$ אז מהגדרת הפרש $y\in A\cup X\setminus A\cap X$ אז מהגדרת הפרש סימטרי $y\in A\vartriangle X$. אבל הראנו ש-$y\notin A$. אזי $A\vartriangle X\neq A$ וזאת בסתירה להנחה.
  
• $A\cap X\neq \emptyset$: אז מהנחה $\exists x:x\in A\cap X$. מהגדרת חיתוך $x\in A$ וגם $x\in X$ אז מהגדרת איחוד $x\in A\cup B$. אז מהגדרת הפרש $x\notin A\cup X\setminus X\cap A$ אז מהגדרת הפרש סימטרי $x\notin A\vartriangle X$. אבל הראנו ש-$x\in A$. אזי $A\vartriangle X\neq A$ וזאת בסתירה להנחה.

אזי $\neg \exists X\neq \emptyset :A\vartriangle X=A$ לכן $X=\emptyset$ הוא היחיד המקיים את $A\vartriangle X=A$. מש"ל.

שאלה 7

נתון:

1. תהי $A$ קבוצה ו-${\mathcal {F}}$ קבוצה של קבוצות.

2. $A\in {\mathcal {F}}\Leftarrow \bigcup {\mathcal {F}}=A$

צ"ל:

$\exists !x:x\in A$

הוכחה:

נניח בשלילה $\neg \exists x:x\in A\$ אז משלילת כמתים $\forall x:x\notin A\$ אז מהגדרת קבוצה ריקה $A=\emptyset$.

נניח $A\in {\mathcal {F}}\Leftarrow \bigcup {\mathcal {F}}=A$ מההנחה ש-$A=\emptyset$ נובע $\bigcup {\mathcal {F}}=\emptyset$. אז מהגדרת איחוד אונארי $\lnot \exists x:\exists y\in {\mathcal {F}}:x\in y$ אזי $y=\emptyset$ ולכן ${\mathcal {F}}=\emptyset$.

מהגדרת קבוצה ריקה $\emptyset \notin {\mathcal {F}}$. וזו בסתירה להנחה - לפיכך קיים $x\in A$. נניח בשלילה שקיים $y\in A$ כך ש-$x\neq y$.

נסמן קבוצה $B=A\setminus \{x,y\}$. עבור הקבוצה ${\mathcal {F}}=\{\{x\},\{y\},B\}$ מתקיים לפי הגדרת איחוד אונארי $\bigcup {\mathcal {F}}=\{x\}\cup \{y\}\cup B\$.

מההנחה $\bigcup {\mathcal {F}}=A$ אז $A=\{x\}\cup \{y\}\cup B\$. אבל $A\notin {\mathcal {F}}$ וזו בסתירה להנחה - לפיכך $x=y$.

הראנו שקיים $x\in A$ ולכל $y\in A:y=x$ ולכן הוכחנו קיום יחידות. מש"ל.

שאלה 8 סעיף א'

צ"ל: $A\times (B\setminus C)=(A\times B)\setminus (A\times C)$

הוכחה:

יהי $<x,y>$ זוג סדור שרירותי.

$\Rightarrow$: נניח $<x,y>\in A\times (B\setminus C)$. אז מהגדרת קבוצת חזקה $x\in A$ וגם $y\in B\setminus C$. אז מהגדרת הפרש $y\in B$ וגם $y\notin C$. אז מהגדרת מכפלה קרטזית $<x,y>\in A\times B$ וגם $<x,y>\notin A\times C$ אז מהגדרת הפרש $<x,y>\in (A\times B)\setminus (A\times C)$.

$\Leftarrow$: $<x,y>\in (A\times B)\setminus (A\times C)$ אז מהגדרת הפרש $<x,y>\in (A\times B)$ וגם $<x,y>\notin (A\times C)$. אז מהגדרת מכפלה קרטזית $x\in A)$ וגם $(y\in B$ וגם $x\notin A)$ או $(y\notin C$ אבל הראנו ש-$x\in A$ אז בהכרח $y\notin C$. אז מהגדרת הפרש $y\in B\setminus C$. אז מהגדרת מכפלה קרטזית $<x,y>\in A\times (B\setminus C)$.

הראנו הכלה דו-כיוונית ולכן הקבוצות שוות.

שאלה 8 סעיף ב'

צ"ל: $(A\cap C=\emptyset )\lor (B\cap D=\emptyset )\Leftarrow (A\times B)\cap (C\times D)=\emptyset$

נוכיח על דרך הקונטרה פוזיטיב: $\neg ((A\times B)\cap (C\times D)=\emptyset )\Leftarrow \neg ((A\cap C=\emptyset )\lor (B\cap D=\emptyset ))$. נפשט לפי זהויות לוגיות:

• רישא:$\neg ((A\cap C=\emptyset )\lor (B\cap D=\emptyset ))\equiv \ \neg (A\cap C=\emptyset )\land \neg (B\cap D=\emptyset )\equiv \ (A\cap C\neq \emptyset )\land (B\cap D\neq \emptyset )$
• סיפא: $\neg ((A\times B)\cap (C\times D)=\emptyset )\equiv (A\times B)\cap (C\times D)\neq \emptyset$

אזי, נוכיח $(A\times B)\cap (C\times D)\neq \emptyset \Leftarrow (A\cap C\neq \emptyset )\land (B\cap D\neq \emptyset )$

הוכחה:

נניח$(A\cap C\neq \emptyset )\land (B\cap D\neq \emptyset )$ אז מהגדרת חיתוך$\exists x:x\in A\land x\in C$ וגם $\exists y:y\in B\land y\in D$.

אז לפי הגדרת מכפלה קרטזית קיים זוג סדור $<x,y>$ כך ש-$<x,y>\in A\times B$ וגם $<x,y>\in C\times D$.

אז לפי הגדרת חיתוך $<x,y>\in (A\times B)\cap (C\times D)$ ולכן $(A\times B)\cap (C\times D)\neq \emptyset$. מש"ל.

שאלה 8 סעיף ג'

צ"ל: ${\mathcal {P}}(A\times B)={\mathcal {P}}(A)\times {\mathcal {P}}(B)$

דוגמה נגדית:

$A=\{0\}$

$B=\{0\}$

${\mathcal {P}}(A)=\{\emptyset ,\{0\}\}$

${\mathcal {P}}(B)=\{\emptyset ,\{0\}\}$

$A\times B=\{<0,0>\}$

${\mathcal {P}}(A\times B)=\{\emptyset ,<0,0>\}$

${\mathcal {P}}(A)\times {\mathcal {P}}(B)=\{<\emptyset ,\emptyset >\ ,<\emptyset ,\{0\}>,<\{0\},\{0\}>,<\{0\},\emptyset >\}$