Math-Wiki - תרומות המשתמש [he]

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 4

2023-08-21T20:19:28Z

רועי91: /* הרכבת פונקציות */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

==פונקציות==
'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו A,B קבוצות וR יחס בינהן. אזי:
*התחום של R הינו <math>dom(R)=\{a\in A|\exists b\in B:(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}</math>
*התמונה של R הינה <math>im(R)=\{b\in B|\exists a\in A:(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \}</math>

'''הערה''': ישירות מהגדרה מתקיים כי <math>dom(R)\subseteq A, Im(R)\subseteq B</math>

'''דוגמא:'''
*אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A (כי כל שני איברים ניתן להשוות)
*<math>R=\{(1,a),(2,b),(3,a),(a,1)\}</math> אזי התחום הוא <math>dom(R)=\{a,1,2,3\}</math> והתמונה הינה <math>im(R)=\{1,a,b\}</math>

'''הגדרה:'''
*יחס R מ-A ל-B נקרא '''על''' אם <math>\forall b\in B \exists a\in A:(a,b)\in R</math> כלומר <math>im(R)=B</math>
*יחס R מ-A ל-B נקרא '''שלם''' אם <math>\forall a\in A \exists b\in B:(a,b)\in R</math> כלומר <math>dom(R)=A</math>
*יחס R נקרא '''חד ערכי''' אם <math>[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)</math> כלומר אין איבר שנשלח ל-2 מקומות שונים
*יחס R נקרא '''חד-חד ערכי''' אם <math>[(x,b)\in R] \and [(y,b) \in R] \rightarrow (x=y)</math> כלומר איברים שונים נשלחים למקומות שונים (כלומר, היחס ההופכי הינו חד ערכי)

'''הגדרה:'''

יחס חד ערכי ושלם נקרא '''פונקציה'''; נסמן במקרה זה <math>(a,b)\in R\leftrightarrow b=R(a)</math>.
ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>.
(A נקרא תחום (הגדרה) של הפונקציה. ו B נקרא הטווח של הפונקציה)

נחזור על הגדרת חח"ע עבור פונקציה:

<math>f</math> חח"ע אמ"מ <math>f(x_1)=f(x_2)\Rightarrow x_1=x_2</math> אמ"מ <math>x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)</math>

'''הגדרה:'''

תהא A קבוצה. '''פונקציית הזהות''' היא פונקציה <math>f:A \to A</math> המקיימת <math>\forall a\in A: f(a)=a</math>. נהוג לסמנה: <math>id_A</math> פונקציית הזהות היא חח"ע ועל.

===דוגמאות:===
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> (אינה חח"ע ואינה על)
*<math>f:\mathbb{N}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> ( חח"ע ואינה על)
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p</math>. זו פונקציית הזהות.
*<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> ( חח"ע ו על)
* <math>f:\mathbb{R}\to\mathbb{R}</math> המוגדרת ע"י הכלל <math>f(x)=\sin(x)</math>.
*<math>f:\mathbb{R}\to\mathbb{R}</math> המוגדרת ע"י הכלל <math>f(x)=x^{3}</math>
* <math>f:\mathbb{C}\to\mathbb{C}</math> המוגדרת ע"י הכלל <math>f(x)=x^{2}</math>
*<math>f:\mathbb{N}\rightarrow\mathbb{N}</math> כאשר <math>f(x)=x-1</math> ( לא מוגדר כי <math>f(1)=?</math>)
*<math>f:\mathbb{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
*<math>f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3</math> כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
*<math>D:\mathbb{R}\rightarrow\mathbb{R}</math> פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
* תהא <math>A</math> קבוצה ו <math>B\subseteq A</math> תת קבוצה. הפונקציה
<math>
\chi_B=
\begin{cases} 1 & \text{ if } x\in B \\ 0 & \text{ otherwise } \end{cases}
</math>
פונקצית האינדקטור. במקרה של דריכלה <math>D=\chi_{\mathbb{Q}}</math>
* תהא <math>f:A\to B</math> אזי <math>g:A\to Im(f) </math> המוגדרת <math>g(a)=f(a)</math> היא על (במילים: פשוט חושבים על הטווח של f להיות התמונה של g)
* תהא <math>A\subseteq B</math> אזי הפונקציה <math>i : A\to B </math> המוגדרת <math>i(a)=a</math> נקראת פונקציה ההכלה (במקרה ש <math>A=B</math> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.

====תרגיל (בשיעוריי הבית)====
יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע

=====הוכחה=====
נסמן <math>f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\} </math> . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B

נניח <math>f </math> חח"ע אזי <math>|\{f(a_1),\dots f(a_n)\}|=n</math>
כיוון ש <math>\{f(a_1),\dots f(a_n)\}\subseteq B </math> ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן <math>f </math> על.

נניח <math>f </math> על. נניח בשלילה ש <math>f </math> אינה חח"ע אזי <math>|\{f(a_1),\dots f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום)
ואז <math>f </math> אינה על -סתירה.

הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.

למשל פונקצית הערך השלם <math>f:\mathbb{R} \to \mathbb{Z} </math> המוגדרת <math>f(x) =\lfloor{x}\rfloor</math> היא על ואינה חח"ע

==== תרגיל====
קבעו האם הפונקציות הבאות חח"ע/על
* <math>f:\mathbb{R}\to \mathbb{R}</math> המוגדרת <math>f(x)=\lfloor x \rfloor</math>
* <math>f:\mathbb{N}\times \mathbb{N}\to \mathbb{Z}</math> המוגדרת <math>f(n,m)=n-m</math>
*תהא A קבוצה, הפונקציה <math>f:A\to P(P(A))</math> המוגדרת <math>f(x)=\{B\subseteq A \mid x\in B\}</math>

==== תרגיל====
מצאו פונקציה <math>f:\mathbb{N}\to \mathbb{N}</math> על שאינה חח"ע.

==== תרגיל ====
תהא A קבוצה ו <math>f:A\to \mathbb{N}</math> פונקציה. נגדיר יחס R על A ע"י <math>aRa'\iff f(a)\leq f(a')</math>. הוכיחו כי R יחס סדר על A אמ"מ <math>f</math> חח"ע.

==== תרגיל ====
א. תהא A קבוצה לא ריקה. מצאו פונקציה <math>F:A^A\to A</math> שהיא על.

ב. תהא <math>A</math> קבוצה. מצאו פונקציה <math>F:A\to A^A</math> שהיא חח"ע.

ג. למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?

==== תרגיל ====
תהיינה <math>f,g:\mathbb{N}\rightarrow \mathbb{N}</math> פונקציות כך ש-<math>f(n)=g(3n-1)</math>.

הוכיחו שאם <math>f</math> על, אז <math>g</math> לא חח"ע.

==הרכבת פונקציות==

'''הגדרה:'''
יהיו <math>f:A\to B, g:B\to C </math> שתי פונקציות אז '''ההרכבה של <math>g</math> על <math>f</math>''' היא פונקציה <math>g \circ f:A\to C </math> המוגדרת על ידי הכלל <math>g \circ f(a)=g(f(a)) </math>

תכונות:
# הרכבה היא קיבוצית. כלומר <math>f_3 \circ (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 </math>
# הרכבה '''אינה''' (בהכרח) חילופית כלומר לא מתקיים בהכרח כי <math>f_2 \circ f_1 = f_2 \circ f_1 </math>. למשל <math>f(x) =x^2 , g(x) = x+1</math> אזי <math>f(g(2))=f(3)=9, g(f(2))=g(4)=5</math> ולכן <math>f\circ g \neq g \circ f</math>

==== תרגיל ====
תהא <math>g:\mathbb{N}\to \mathbb{N}</math> פונקציה. נגדיר <math>F:\mathbb{N}^{\mathbb{N}}\to \mathbb{N}^{\mathbb{N}}</math> ע"י <math>F(f)=g\circ f</math>. הוכיחו כי F חח"ע אמ"מ g חח"ע.

=====פתרון=====
<math>\Leftarrow</math>: נתון: F חח"ע. נניח <math>g(n)=g(m)</math>, לכן עבור הפונקציות הקבועות <math>f\equiv n,f'\equiv m</math> נקבל <math>\forall k:g\circ f(k)=g((n)=g(m)=g\circ f'(k)</math> ולכן <math>F(f)=g\circ f=g\circ f'=F(f')</math>, ומחח"ע של F נקבל <math>f=f'</math> ולכן <math>n=m</math>.

<math>\Rightarrow</math>: נתון <math>g</math> חח"ע. תהיינה <math>f\neq f'\in \mathbb{N}^{\mathbb{N}}</math>, לכן יש <math>n\in \mathbb {N}</math> כך ש- <math>f(n)\neq f'(n)</math>, ולכן זה מתקיים גם אחרי ההרכבה, ולכן <math>F(f)\neq F(f')</math>.

====תרגיל====
*נניח <math>g \circ f</math> חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
*נניח <math>g \circ f</math> על. הוכח/הפרך: g על, f על

=====פתרון=====

נניח <math>g \circ f</math> חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>f(x)=f(y)</math> אבל <math>x\neq y</math>. אבל, <math>g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y)</math> בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.

לגבי g ניתן דוגמא נגדית: <math>f(x)=e^x ,g(y)=y^2</math> ההרכבה היא <math>h(x)=e^{2x}</math>

נניח <math>g \circ f</math> על. נסמן <math>g \circ f : A\rightarrow B</math> אזי לכל איבר <math>b\in B</math> קיים איבר <math>a\in A</math> כך ש <math>g(f(a))=b</math>. לכן עבור g לכל b קיים <math>f(a)</math> שנותן את b תחת g ולכן g על.

דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם
<math>f(n)=n+1</math>;
<math>\forall n\not=0 g(n)=n-1 , g(0)=0</math>
ההרכבה היא הזהות

(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <math>f(n)=2n</math>, והפונקציה g מוגדרת כ <math>g(2n)=n</math> ו <math>g(2n+1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

==פונקציות הפיכות==
'''הערה:''' לכל פונקציה <math>f</math> מתקיים <math>f\circ id =f</math> וגם <math>id \circ f =f</math>

'''הגדרה:''' תהי <math>f</math> פונקציה <math>f:A\rightarrow B</math>. פונקציה <math>g:B\rightarrow A</math> תיקרא '''הפונקציה ההופכית ל-<math>f</math>''' אם <math>f\circ g = id_B</math> וגם <math>g\circ f = id_A</math>. במקרה זה נסמן את <math>g</math> על ידי <math>f^{-1}</math>, ונאמר שהפונקציה <math>f</math> היא '''הפיכה'''.

הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

====משפט====

הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.

=====הוכחה=====

אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.

אם f חח"ע ועל, אז נגדיר <math>g:B\to A</math> ע"י: עבור <math>a\in A </math> קיים (כי f על) יחיד (כי f חח"ע)
<math>b\in B</math> כך ש <math>f(a)=b</math> . נגדיר <math>g(b):=a</math>. תרגיל: בדקו ש g ההופכית של f.

יחידות: נניח g,h הופכיות של f אזי <math>h= h\circ I_B=h\circ f \circ g=I_A \circ g=g</math>.

דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, <math>\exists a\in A:g(a)\neq h(a)</math>. אבל <math>f(g(a))=f(h(a))</math> וזו סתירה לחח"ע של f.

====משפט====
יהיו <math>f_1,\dots f_k:A\to A</math> הפיכות/חח"ע/על. הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על

=====הוכחה=====

חח"ע: נניח <math>(f_k \circ \dots \circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2)</math> אזי מח"ע של <math>f_k</math>
נקבל כי <math>(f_{k-1} \circ \dots \circ f_1)(x_1) =(f_{k-1} \circ \dots \circ f_1)(x_2)</math> באופן דומה נמשיך (או באינדוקציה) ונקבל <math>x_1=x_2</math>

על: יהא <math>y\in A</math> כיוון ש <math>f_k</math> על קיים <math>a_k\in A</math> כך ש <math>f_k(a_k)= y</math>
באותו אופן קיים <math>a_{k-1}</math> כך ש <math>f_{k-1}(a_{k-1}=a_k</math> נמשיך באופן דומה (או באינקודציה)
ונקבל <math>(f_k \circ \dots \circ f_1)(a_1)=(f_k \circ \dots \circ f_2)(a_2)=\dots f_k\circ f_{k-1} (a_{k-1}) = f_k(a_k)=y</math>

הפיכות: נובע מחח"ע+על

====מסקנות====

* אם <math>f,g</math> הפיכות אז <math>g\circ f</math> הפיכה.

* אם <math>g\circ f</math> הפיכה אז <math>f</math> חח"ע, <math>g</math> על (והן לאו דוקא הפיכות).

==== דוגמאות ====
1. <math>f:\mathbb{R} \to \mathbb{R}</math> המוגדרת:
# <math>f(x)=x+1</math> הפיכה וההופכית היא <math>f^{-1}(x) = x-1 </math>
# <math>f(x)=x^3</math> הפיכה וההופכית היא <math>f^{-1}(x) = x^{1/3} </math>
# <math>f(x)=\sin (x)</math> אינה הפיכה כי איננה חח"ע למשל <math>\sin(0) =\sin(2\pi k)</math>

2 תהא <math>A</math> קבוצה <math>f:P(A)\to P(A)</math> המוגדרת:
# <math>f(B)= B^c</math> הפיכה וההופכית היא <math>f^{-1}(B) = B^c </math>
# תהא <math>C\subseteq A</math> תת קבוצה <math>f(B)= B \triangle C</math> הפיכה וההופכית היא <math>f^{-1}(B) = B \triangle C </math>

3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :
<math>
f(B)=
\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}
</math>

תקיים כי<math>f(C)=f(A) </math> ואם <math>C\neq A</math> אזי הפונקציה אינה חח"ע ובפרט אינה הפיכה

4. תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתירגול על יחסי שקילות)
להגדיר <math>f:\{R \; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f(R)=A/R</math> והיא תהיה חח"ע ועל כי ראינו את הפונקציה ההופכית לה

5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.

====תרגיל====
הוכח כי אם <math>g\circ f \circ g =id</math> אז <math>f </math> הפיכה

הוכחה:

הרכבה של פונקציה חח"ע <math>(g\circ f) \circ g =id</math> גורר שהשמאלית <math>g</math> חח"ע

הרכבה של פונקציה על <math>g\circ (f \circ g) =id</math> גורר שהימנית <math>g</math> על

ביחד נקבל ש <math>g</math> חח"ע ועל כלומר הפיכה. נכפול ב <math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של הפיכות.

88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 1

2023-07-22T14:35:23Z

רועי91: /* תרגיל */

'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''

==קישורים==
מידע רב חופף בין הקורס שלנו לקורס תורת הקבוצות, ניתן להעזר לכן ב[http://he.wikipedia.org/wiki/%D7%95%D7%99%D7%A7%D7%99%D7%A4%D7%93%D7%99%D7%94:%D7%9E%D7%99%D7%96%D7%9E%D7%99_%D7%95%D7%99%D7%A7%D7%99%D7%A4%D7%93%D7%99%D7%94/%D7%A7%D7%95%D7%A8%D7%A1%D7%99%D7%9D/%D7%AA%D7%95%D7%A8%D7%AA_%D7%94%D7%A7%D7%91%D7%95%D7%A6%D7%95%D7%AA/%D7%AA%D7%95%D7%9B%D7%9F_%D7%94%D7%A7%D7%95%D7%A8%D7%A1 קורס תורת הקבוצות בויקיפדיה]

==קבוצות==
ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים". ההגדרה הזו מובילה לסתירות לוגיות כגון "פרדוקס ראסל". נביט בקבוצה הבאה:
*X=אוסף כל הקבוצות שאינן שייכות לעצמן

אם X שייכת לקבוצה הזו, אזי היא אינה שייכת לקבוצה. אולם, אם היא אינה שייכת לקבוצה אזי היא כן שייכת לקבוצה.

סתירה אינה מקובלת במחוזות המתמטיקאים, ולכן הגדירו את "תורת הקבוצות האקסיומטית" העוקפת בעייה זו. ניתן לקרוא יותר על נושא זה בקישור לעיל, עבורנו מספיקה ההגדרה האינטואיטיבית.

אם כן, נחזור להגדרתנו הנאיבית; '''קבוצה''' הינה אוסף של איברים שונים. בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות:

<math>\{1,horse,3\}</math>, <math>\{1,2,3\}</math> ו<math>\{1,\{2,3\},\{\}\}</math>

איבר ה'''שייך''' לקבוצה אנו מסמנים בסימן <math>\in</math>. למשל <math>1\in\{1,2,3\}</math>, ואילו <math>4\notin\{1,2,3\}</math>. שימו לב שגם <math>1\notin\{\{1,2,3\}\}</math> שכן האיבר היחיד בקבוצה זו הינה הקבוצה <math>\{1,2,3\}</math>.

*אומרים שקבוצה A '''מוכלת''' בקבוצה B (מסומן <math>A \subseteq B</math>) אם כל האיברים בA הם גם איברים בB. בשפה מדויקת, A מוכלת בB אם מתקיים <math>\forall a\in A: a\in B</math>.

:דוגמא:
<math>\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}</math>
כאשר
::<math>\mathbb{N}=\{1,2,3,\dots\}</math> המספרים הטבעיים
::<math>\mathbb{Z}=\{\dots,-2,-1,0,1,2,3,\dots\}</math> המספרים השלמים
::<math>\mathbb{Q}=\{\frac{m}{n} : m,n\in \mathbb{Z},n\neq 0\}</math> המספרים הרציונאלים (שברים)
::<math>\mathbb{R}</math> המספרים הממשיים ("כל המספרים" על הישר)
::<math>\mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\}</math> המספרים המרוכבים

==== תרגיל (חשוב!)====
מצאו קבוצות A,B כך ש:
*<math>A\in B, A\subseteq B</math>
*<math>A\in B, A\not\subseteq B</math>
*<math>A\not\in B, A\subseteq B</math>
*<math>A\not\in B, A\not\subseteq B</math>

====תרגיל (חשוב)====
נתון <math>A=\{\phi\}</math> ונתון <math>B=\{\phi,\{\phi\}\}</math>. סמן את הביטויים הנכונים:
#<math>\phi\subseteq B</math> (כן)
#<math>\phi\in \phi</math> (לא)
#<math>\phi \subseteq \phi</math> (כן)
#<math>A\subseteq B</math> (כן)
#<math>A\in B</math> (כן)
#<math>A\cup B = B</math> (כן)
#<math>A\cap B=\phi</math> (לא)

====תרגיל====
נתונות <math>A=\{2m+1:m\in\mathbb{Z}\}</math>, ו <math>B=\{2m+3:m\in\mathbb{Z}\}</math>. הוכח שA=B.

פתרון
נוכיח הכלה דו כיוונית. נניח <math>x\in A</math> לכן קיים מספר שלם m כך ש <math>x=2m+1</math>. קל לראות שמתקיים <math>x=2(m-1)+3</math> אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים <math>x\in B</math> כמו שרצינו.

ההכלה בכיוון ההפוך דומה.

====תרגיל ====
הוכיחו כי <math>\{n^2\mid n\in \mathbb{N}\}=\{n\in \mathbb{N}\mid \sqrt{n}\in \mathbb{N}\}</math>
==== תרגיל ====
הוכיחו כי <math>\left\{ 8x+6y\,\mid x,y\in\mathbb{Z}\right\} =\left\{ n\in\mathbb{Z}\,\mid\exists k\in\mathbb{Z}:\,n=2k\right\}</math>

=== פעולות על קבוצות ===
*'''חיתוך''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן <math>A\cap B</math>). מתקיים ש<math>a \in A\cap B \iff (a\in A \and a\in B)</math>.

*'''איחוד''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן <math>A\cup B</math>). מתקיים ש<math>a \in A\cup B \iff (a\in A \or a\in B)</math>.

*קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה '''הכלה דו כיוונית''': A=B אם ורק אם <math>(A\subseteq B) \and (B \subseteq A) </math>.

*A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש <math>x\in A \setminus B \iff (x\in A) \and (x\notin B)</math>.

*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\Delta B</math>). מתקיים ש <math>x\in A\Delta B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A)) \iff x\in (A\cup B) \smallsetminus (A\cap B)</math>

דוגמא:

יהיו <math>A=\{1,2,\{1\}\},B=\{1,\{2\}\},C=\{2,\{1,2\}\}</math> קבוצות.

אזי:

<math>A\cup B =\{1,2 ,\{1\},\{2\}\} </math>

<math>(A\cup B)\cap C =\{2\} </math>

<math> B \cap C = \emptyset</math>

<math>C \smallsetminus A =\{\{1,2\}\}</math>

<math> B \Delta C = B \cup C</math>

<math> A \Delta C = \{1,\{1\},\{1,2\}\}</math>

תכונות האיחוד והחיתוך (דומה לכפל וחיבור)
*אסוציאטיביות: <math>(A\cap B)\cap C = A\cap (B\cap C)</math> (וכנ"ל לגבי איחוד)
*חילוף: <math>A\cap B = B\cap A</math> (וכנ"ל לגבי איחוד)
*דיסטריביוטיביות: <math>A\cap (B\cup C) = (A\cap B) \cup (A\cap C)</math>, וגם <math>A\cup (B\cap C) = (A\cup B) \cap (A\cup C)</math>

===תרגיל===
הוכח כי <math>(A\cap B)\cup C = (A\cup C)\cap (B\cup C)</math>. במילים: האיברים שהם (גם בA וגם בB) או בC הם בדיוק האיברים ב(A או C) וגם ב(B או C)

====פתרון====
נראה שקילות בין התנאים של איבר להיות באחת הקבוצות.

<math>x\in (A\cap B)\cup C \iff [x\in (A\cap B)] \or [x\in C] \iff [x\in A \and x\in B] \or [x\in C]</math>

כעת, מתוך הטאוטולוגיה <math>(p\and q)\or r \iff (p\or r)\and(q\or r)</math> קל להשיג את השקילות למה שצריך.
(הערה: ניתן להשתכנע בקלות בטאוטולוגיה באופן הבא: אם r=1 אזי נשאר עם הטאוטולוגיה
<math>1\iff 1</math> אם r=0 אזי נשאר עם הטאוטולוגיה
<math>(p\land q)\iff (p)\land (q)</math>)

===תרגיל===
הוכח כי:
א. הקבוצה הריקה <math>\phi=\{\}</math> מוכלת בכל קבוצה A

ב. <math>\phi \cap A = \phi </math>

ג. <math>\phi \cup A = A </math>

====פתרון====
א. יש להוכיח את הפסוק הבא: <math>\forall a\in\phi : a\in A</math>. אבל מכיוון שאין איברים בקבוצה הריקה, המשפט הזה נכון '''באופן ריק'''. זכרו ששקר גורר כל דבר, לכן האטום "איבר a שייך לקבוצה הריקה" גורר כל דבר.
הערה: שימו לב שעל מנת להוכיח שקבוצה A אינה מוכלת בקבוצה B, יש להראות כי '''קיים''' איבר בA שאינו שייך לB. אם היינו משתמשים בפסוק "כל האיברים בA אינם בB" היינו מקבלים שהקבוצה הריקה לא מוכלת בכל קבוצה, וגם אינה מוכלת בכל קבוצה.

ב. <math>\phi \cap A = \{x:x\in \phi \and x\in A\}\subseteq \{x:x\in \phi \}=\phi </math>

ג. <math>\phi \cup A = \{x:x\in \phi \or x\in A\}= \{x:x\in A \}=A </math>

====תרגיל====
הוכח כי <math>A\cap (B/C)=(A\cap B) / (A\cap C)</math>

פתרו:

דרך גרירות לוגיות:

<math>x\in A\cap (B/C)\iff (x\in A) \and [(x\in B) \and (x\notin C)]\iff [(x\in A) \and (x\in B) \and (x\notin C)] \or [(x\in A) \and (x\in B) \and (x\notin A)] </math>

בצד הימני הוספנו סתירה בעזרת הקשר "או" ולכן נשארנו עם ביטוי שקול. כעת נשתמש בחוק הפילוג של הלוגיקה:

<math>\iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff [(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)] </math>

וזה בדיוק מה שרצינו.

דרך הכלה דו כיוונית:

(<math>\subseteq</math>) נניח <math>x\in A\cap(B\backslash C)</math> אזי

<math>x\in A \land x\in B \land x\not\in C \Leftarrow</math>
<math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math>
<math>x\in (A\cap B) \backslash (A\cap C)</math>

(<math>\supseteq</math>) נניח <math>x\in (A\cap B) \backslash (A\cap C)</math> אזי

<math>x\in A\cap B \land x\not\in A\cap C \Leftarrow</math>
<math>x\in A \land x\in B \land x\not\in C \Leftarrow </math>
(כי אם <math>x\in C</math> אזי <math>x\in A\cap C</math> סתירה)
<math>x\in A\cap(B\backslash C)\Leftarrow </math>

===הכללה לאיחודים וחיתוכים כל שהם===
'''מוטיבציה:''' הגדרנו את החיתוך והאיחוד עבור שתי קבוצות. לעיתים נרצה לחתוך או לאחד יותר קבוצות, לדוגמא נרצה לדבר על חיתוכן של 17 הקבוצות <math>A_1,A_2,\ldots,A_{17}</math>. מכיוון שחיתוך ואיחוד הן פעולות אסוציטיביות, ניתן לרשום <math>A_1\cap A_2\cap \ldots\cap A_{17}</math>, וזה ביטוי חד משמעי. אך צורת רישום זו היא ארוכה, ולכן אנו מסמנים את החיתוך הזה בקיצור הבא: <math>\bigcap _{i=1} ^{17} A_i</math>. לעיתים נרצה לחתוך או לאחד אוסף אינסופי של קבוצות, ולכך באה ההכללה הבאה:

'''הגדרה:'''
יהיו <math>\{A_i\}_{i\in I}</math> אוסף קבוצות כאשר <math>I</math> הוא קבוצת אינדקסים אזי נגדיר את האיחוד והחיתוך של אוסף הקבוצות כך:

<math>\bigcup _{i\in I} A_i := \{x| \exist i\in I :x\in A_i \} </math>

<math>\bigcap _{i\in I} A_i := \{x| \forall i\in I :x\in A_i \} </math>. כאן יש להניח שקבוצת האינדקסים <math>I</math> לא ריקה.

דוגמא:

נגדיר <math>\forall n\in \mathbb{N} \; A_n:=[n,n+1]</math> אזי

<math>\bigcup _{i\in \mathbb{N}} A_i = [ 1,\infty ) </math>

<math>\bigcap _{i\in \mathbb{N}} A_i = \phi </math>

==== תרגיל ====
לכל n>1 טבעי נגדיר <math>A_n</math> להיות קבוצת כל הראשוניים המחלקים את n.

חשבו את
*<math>A_{12}\cap A_{10}</math>
*<math>\cup_{n=2}^{15} A_n</math>
*<math>\cap_{n=2}^5 A_{6n}</math>
*<math>\bigcup _{i=2}^\infty A_i</math>
*<math>\bigcup _{i=1}^\infty A_{2^i}</math>

==== תרגיל (הכללת פילוג)====
יהיו <math>\{A_i\}_{i\in I}</math> אוסף קבוצות, B קבוצה. הוכיחו כי
<math>(\bigcup _{i\in I} A_i)\cap B= \bigcup _{i\in I} (A_i\cap B) </math>

פתרון:

יהא <math>x\in (\bigcup _{i\in I} A_i)\cap B</math> אזי <math>x\in B</math> וגם <math>x\in (\bigcup _{i\in I} A_i)</math>
לכן <math>x\in B</math> וגם <math>\exist i\in I :x\in A_i</math> ולכן <math>x\in A_i\cap B</math> ומכאן ש <math>x\in \bigcup _{i\in I} (A_i\cap B)</math>

בכיוון שני: יהא <math>x\in \bigcup _{i\in I} (A_i\cap B)</math> ולכן <math>\exist i\in I :x\in A_i\cap B</math> לכן <math>x\in B</math>
וגם <math>x\in A_i</math> לכן <math>x\in B</math> וגם <math>x\in (\bigcup _{i\in I} A_i)</math> ולכן <math>x\in (\bigcup _{i\in I} A_i)\cap B</math>

==== משלים ====

'''הגדרה''': תהי קבוצה U, ונביט בתת קבוצה שלה A. ניתן להגדיר את ה'''משלים''' של A כאוסף האיברים בU שאינם בA (כלומר ההפרש <math>U\setminus A</math>), מסומן <math>A^c</math>. לא ניתן לדבר על משלים אוניברסאלי ללא U מכיוון שאין קבוצה המכילה את כל הדברים בעולם (אחרת נגיע לסתירות כמו פרדוקס ראסל).

תכונות בסיסיות:
* <math>A\cup A^c = U</math>
* <math>\emptyset^c = U</math>
* <math>U^c = \emptyset</math>
* <math>(A^c)^c = A</math>

על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):
*<math>(A\cap B)^c = A^c \cup B^c</math>
*<math>(A\cup B)^c = A^c \cap B^c</math>
הערה: באופן כללי מתקיים
* <math>(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c </math>
* <math>(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c </math>

===תרגיל===

הוכיחו כי <math>A \triangle B = A^c \triangle B^c</math>.

פתרון:

נשתמש בהצגת ההפרש הסימטרי כאיחוד ההפרשים:

<math>x\in A \triangle B \iff (x\in A \land x\notin B)\lor (x\in B \land x\notin A) \iff</math>

<math>(x\notin A^c \land x\in B^c)\lor (x\notin B^c \land x\in A^c)</math> ומחילופיות "וגם" ו"או":

<math>(x\notin B^c \land x\in A^c)\lor (x\notin A^c \land x\in B^c) \iff</math>
<math>(x\in A^c \land x\notin B^c)\lor (x\in B^c \land x\notin A^c) \iff x\in A^c \triangle B^c</math>

===== תרגיל =====
יהיו A,B ת"ק של U אזי <math>A\subseteq B \iff B^c \subseteq A^c</math>

פתרון: בכיוון אחד- יהא <math>x\in A</math> אזי <math>x\notin A^c</math> לכן לפי נתון <math>x\notin B^c</math> לכן <math>x\in B</math>.

בכיוון שני: יהא <math>x\in B^c</math> אזי <math>x\notin B</math> לכן לפי נתון <math>x\notin A</math> לכן <math>x\in A^c</math>.

===== תרגיל =====

נגדיר <math>\forall n\in \mathbb{N}\cup \{0\} \; A_n:=(n,n+1) \cup (-n-1,-n)</math> אזי

א. <math>\bigcup _{n\in \mathbb{N}} A_n = \mathbb{R}\smallsetminus \mathbb{Z} </math>

ב. <math>\bigcap _{n\in \mathbb{N}} A_n = \varnothing </math>

ג. נגדיר <math>B_n=\mathbb{R}\smallsetminus A_n</math>. חשבו את <math>\bigcap_{n\in \mathbb{N}} B_n</math>

הוכחה:

א. ע"י הכלה דו כיוונית.

ב. מספיק להראות <math>A_1\cap A_2=\phi</math>.

ג. נתייחס ל-<math>\mathbb{R}</math> כקבוצה האוניברסלית לדיוננו. לפי דה-מורגן נקבל:<math>\bigcap_{n\in \mathbb{N}} B_n=\bigcap_{n\in \mathbb{N}} A_n^c=(\bigcup_{n\in \mathbb{N}} A_n)^c=(\mathbb{Z}^c)^c=\mathbb{Z}</math>.

=== קבוצת החזקה ===
'''הגדרה''': תהי קבוצה A. נגדיר את '''קבוצת החזקה''' של A בתור אוסף כל תתי הקבוצות של A. מסומן <math>P(A)=\{X:X\subseteq A\}</math>

דוגמא:

<math>A=\{1,2\}</math> אזי <math>P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}</math>.

האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?

====תרגיל====
הוכיחו או הפריכו:

א. לכל A,B מתקיים: <math>P(A)\cap P(B)=P(A\cap B)</math>

ב. לכל A,B מתקיים: <math>P(A)\cup P(B)=P(A\cup B)</math>

ג. קיימת A כך ש <math>A\cap P(A)\neq \emptyset</math>

ד. קיימת A סופית כך ש <math>A\cap P(A)=P(A)</math>. לגבי אינסופית תראו בבעתיד.

פתרון:

א. הוכחה: <math>X\in P(A)\cap P(B) \iff X\subseteq A\land X\subseteq B\iff</math>

<math>X\subseteq A\cap B\iff X\in P(A\cap B)</math>

ב. הפרכה: ניקח <math>A=\{1\},B=\{2\}</math>. אז <math>\{1,2\} \in P(A\cup B)</math>, אבל לא ל-<math>P(A)\cup P(B)</math>.

למעשה הוכיחו כי <math>P(A)\cup P(B)=P(A\cup B)</math> אם ורק אם <math>A\subseteq B</math> או <math>B\subseteq A</math>.

ג. ייתכן, למשל <math>A=\{\emptyset\}</math>

ד. לא, כי אז <math>P(A)\subseteq A</math> שלא ייתכן משיקולי עוצמה (בקבוצה סופית: ב <math>P(A)</math> יש יותר איברים מ Aׂׂ)

==== תרגיל ====
הוכיחו כי אם <math>P(A)\cup P(B)=P(A\cup B)</math> אז <math>A\subseteq B</math> או <math>B\subseteq A</math>

==== תרגיל ====
תהא <math>A\subseteq U</math>. הוכיחו כי <math>P(A^c)\setminus\{\emptyset\}\subseteq P(A)^c</math>

===תרגיל ממבחן===
יהיו A,B,C קבוצות. הוכיחו/הפריכו:

א. אם <math>A \not\subseteq B \cap C</math> אזי <math>(A/B)\cap(A/C)\neq \phi</math>

ב. אם <math>A\subseteq B</math> אזי <math>A\cup(B/A)=B</math>

ג. אם <math>A\cap B=\phi</math> אזי <math>P(A)\cap P(B) = \{\phi\}</math>

====פתרון====
א. '''הפרכה''': <math>A=\{1,2\},B=\{1\},C=\{2\}</math>. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל <math>(A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi</math>

ב. נתון שלכל <math>a\in A</math> מתקיים <math>a \in B</math>. אזי <math>x\in [A\cup(B/A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff [(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)] </math>

כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון <math>(x\in A)\rightarrow (x\in B)</math> ניתן להסיק בקלות ש<math>(x\in A)\or (x\in B) \iff (x\in B)</math> כפי שרצינו.

דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית <math>U:=B</math> ואז צריך להוכיח כי
<math>A\cup A^c =U</math> וזה אכן נכון!

ג. נניח בשלילה ש<math>P(A)\cap P(B)\neq \{\phi\}</math>. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה <math>\phi \not=C</math> השייכת לחיתוך <math>P(A)\cap P(B)</math>. קבוצות החזקה הן אוסף תתי הקבוצות, ולכן <math>C\subseteq A \and C\subseteq B</math>. מכיוון שC אינה ריקה קיים בה איבר <math>\exists c\in C</math> וקל מאד לראות ש<math>(c\in A)\and (c\in B) </math> ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.