הבדלים בין גרסאות בדף "תרגול 14 תשעח"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(יצירת דף עם התוכן "=== תרגיל === הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}|</math> ==== פתרון ==== נגדיר פונקציה <math>f:P(\mathbb...")
 
שורה 1: שורה 1:
 +
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]].
 +
 +
=עוצמות=
 +
 +
'''הגדרה.''' יהיו <math>A,B</math> שתי קבוצות. אזי:
 +
*אם קיימת <math>f:A\to B </math> חח"ע ועל אז אומרים של-<math>A</math> ול-<math>B</math> '''יש אותה עוצמה'''. סימון <math>|A|=|B|</math>.
 +
*אם קיימת <math>f:A\to B </math> חח"ע אז אומרים כי העוצמה של <math>A</math> קטנה או שווה לזו של <math>B</math>. סימון <math>|A|\leq|B|</math>.
 +
* אם <math>|A|\leq|B|</math> וגם <math>|A|\not=|B|</math> אזי אומרים כי העוצמה של <math>A</math> קטנה ממש מהעוצמה של <math>B</math>. סימון <math>|A|<|B|</math>.
 +
 +
הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת <math>f:A\to B </math> על אזי <math>|B|\leq |A|</math>.
 +
 
=== תרגיל ===
 
=== תרגיל ===
−
הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\emptyset\}|</math>
+
הוכיחו כי <math>|P(\mathbb{N})|=|P(\mathbb{N})-\{\varnothing\}|</math>.
  
 
==== פתרון ====
 
==== פתרון ====
−
נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\emptyset\} </math> ע"י <math>\{n\}\mapsto \{n+1\},\emptyset \mapsto \{1\}</math> וכל B שאינה נקודון ואינה קבוצה ריקה נשלחת לעצמה.
+
נגדיר פונקציה <math>f:P(\mathbb{N})\to P(\mathbb{N})-\{\varnothing\} </math> ע"י <math>\{n\}\mapsto \{n+1\},\varnothing \mapsto \{1\}</math> וכל <math>B</math> שאינה נקודון ואינה הקבוצה הריקה נשלח לעצמה.
  
 
===תרגיל ===
 
===תרגיל ===
−
הוכיחו כי <math>|A\times A| = |A^{\{1,2\}}|</math>
+
הוכיחו כי <math>|A\times A| = |A^{\{1,2\}}|</math>.
  
 
פתרון: הפונקציה  <math>F:A^{\{1,2\}}\to A\times A</math> המוגדרת <math>f\mapsto (f(1),f(2))</math> הפיכה.
 
פתרון: הפונקציה  <math>F:A^{\{1,2\}}\to A\times A</math> המוגדרת <math>f\mapsto (f(1),f(2))</math> הפיכה.
  
−
===משפט (קנטור- שרדר-ברנשטיין)===
+
===משפט (קנטור-שרדר-ברנשטיין)===
  
−
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math>
+
אם <math>|B|\leq|A|</math> וגם <math>|A|\leq|B|</math> אז <math>|B|=|A|</math>.
 +
 
 +
בהמשך נקצר לק.ש.ב.
  
 
===תרגיל===
 
===תרגיל===
−
הוכיחו: <math>|\mathbb{Q}\cap [0,1]|=\aleph_0</math>
+
הוכיחו: <math>|\mathbb{Q}\cap [0,1]|=\aleph_0</math>.
  
 
====פתרון====
 
====פתרון====
−
לפי ק.ש.ב. כי מוכל ברציונאליים ומכיל <math>\aleph_0</math> שברים מהצורה <math>\frac{1}{n}</math>.
+
לפי ק.ש.ב. כי הקבוצה מוכלת ברציונליים ומכילה <math>\aleph_0</math> שברים מהצורה <math>\frac{1}{n}</math>.
−
 
+
  
 
===תרגיל===  
 
===תרגיל===  
  
−
הוכח כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</math> כאשר <math>a<b</math> ממשיים.
+
הוכיחו כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה <math>[a,b],(a,b),[a,b),(a,b]</math> כאשר <math>a<b</math> ממשיים.
  
 
====פתרון====
 
====פתרון====
שורה 29: שורה 41:
 
נראה שכולם שווי עוצמה לקטע <math>(0,1)</math>.
 
נראה שכולם שווי עוצמה לקטע <math>(0,1)</math>.
  
−
ראשית נגדיר <math>f:(0,1)\rightarrow (a,b)</math> ע"י <math>f(x)=a+(b-a)x</math> חח"ע ועל. השאר עם ק.ש.ב.
+
ראשית נגדיר <math>f:(0,1)\rightarrow (a,b)</math> ע"י <math>f(x)=a+(b-a)x</math> חח"ע ועל. השאר עם ק.ש.ב.
−
 
+
−
ט: הקטע <math>(\frac{-\pi}{2},\frac{\pi}{2})</math>  בעל עוצמה שווה ל <math>\mathbb{R}</math>.
+
  
−
ה: הפונקציה <math>tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R}</math> הפיכה בתחום הזה ולכן חח"ע ועל.
+
טענה: הקטע <math>(\frac{-\pi}{2},\frac{\pi}{2})</math> בעל עוצמה שווה ל-<math>\mathbb{R}</math>.
  
 +
הוכחת הטענה: הפונקציה <math>\tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R}</math> הפיכה בתחום הזה ולכן חח"ע ועל.
  
 
===תרגיל ===
 
===תרגיל ===
−
תהא A קבוצה. הוכח כי <math>|A|\leq |P(A)|</math>
+
תהא <math>A</math> קבוצה. הוכיחו כי <math>|A|\leq |P(A)|</math>.
  
−
פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> היא חח"ע.
+
פתרון: נגדיר את הפונקציה <math>f:A|\to P(A)</math> ע"י <math>a \mapsto \{a\}</math> והיא חח"ע.
  
−
תהא A קבוצה. הוכח כי <math>|A|\neq |P(A)|</math>
+
תהא <math>A</math> קבוצה. הוכיחו כי <math>|A|\neq |P(A)|</math>.
  
−
פתרון: נניח בשלילה כי <math>|A|= |P(A)|</math> אזי קיימת <math>f: A\to P(A)</math> הפיכה, בפרט על. נגדיר <math>X=\{a\in A: a\notin f(a)\}</math>. זוהי תת קבוצה של A ולכן, מכיוון ש f על, קיים <math>x\in A</math> כך ש <math>f(x)=X</math>. האם <math>x\in X</math>? אם לא, לפי הגדרת X נקבל כי <math>x\notin f(x)=x</math> סתירה. אם כן אז <math>x\in X=f(x)</math> אבל לפי הגדרת X מתקיים <math>x\notin f(x)</math> סתירה. משל/
+
פתרון: נניח בשלילה כי <math>|A|= |P(A)|</math> אזי קיימת <math>f: A\to P(A)</math> הפיכה, בפרט על. נגדיר <math>X=\{a\in A: a\notin f(a)\}</math>. זוהי תת קבוצה של <math>A</math> ולכן, מכיוון ש-<math>f</math> על, קיים <math>x\in A</math> כך ש-<math>f(x)=X</math>. האם <math>x\in X</math>? אם לא, לפי הגדרת <math>X</math> נקבל כי <math>x\notin f(x)=X</math>, סתירה. אם כן אז <math>x\in X=f(x)</math> אבל לפי הגדרת <math>X</math> מתקיים <math>x\notin f(x)</math> סתירה. מש"ל.

גרסה מ־22:39, 20 בינואר 2018

חזרה לדף מערכי התרגול.

עוצמות

הגדרה. יהיו A,B שתי קבוצות. אזי:

  • אם קיימת f:A\to B חח"ע ועל אז אומרים של-A ול-B יש אותה עוצמה. סימון |A|=|B|.
  • אם קיימת f:A\to B חח"ע אז אומרים כי העוצמה של A קטנה או שווה לזו של B. סימון |A|\leq|B|.
  • אם |A|\leq|B| וגם |A|\not=|B| אזי אומרים כי העוצמה של A קטנה ממש מהעוצמה של B. סימון |A|<|B|.

הערה: בעזרת אקסיומת הבחירה מוכיחים כי אם קיימת f:A\to B על אזי |B|\leq |A|.

תרגיל

הוכיחו כי |P(\mathbb{N})|=|P(\mathbb{N})-\{\varnothing\}|.

פתרון

נגדיר פונקציה f:P(\mathbb{N})\to P(\mathbb{N})-\{\varnothing\} ע"י \{n\}\mapsto \{n+1\},\varnothing \mapsto \{1\} וכל B שאינה נקודון ואינה הקבוצה הריקה נשלח לעצמה.

תרגיל

הוכיחו כי |A\times A| = |A^{\{1,2\}}|.

פתרון: הפונקציה F:A^{\{1,2\}}\to A\times A המוגדרת f\mapsto (f(1),f(2)) הפיכה.

משפט (קנטור-שרדר-ברנשטיין)

אם |B|\leq|A| וגם |A|\leq|B| אז |B|=|A|.

בהמשך נקצר לק.ש.ב.

תרגיל

הוכיחו: |\mathbb{Q}\cap [0,1]|=\aleph_0.

פתרון

לפי ק.ש.ב. כי הקבוצה מוכלת ברציונליים ומכילה \aleph_0 שברים מהצורה \frac{1}{n}.

תרגיל

הוכיחו כי עוצמת כל הקבוצות הבאות שווה - כל קטעים מהצורה [a,b],(a,b),[a,b),(a,b] כאשר a<b ממשיים.

פתרון

נראה שכולם שווי עוצמה לקטע (0,1).

ראשית נגדיר f:(0,1)\rightarrow (a,b) ע"י f(x)=a+(b-a)x חח"ע ועל. השאר עם ק.ש.ב.

טענה: הקטע (\frac{-\pi}{2},\frac{\pi}{2}) בעל עוצמה שווה ל-\mathbb{R}.

הוכחת הטענה: הפונקציה \tan:(\frac{-\pi}{2},\frac{\pi}{2})\to \mathbb{R} הפיכה בתחום הזה ולכן חח"ע ועל.

תרגיל

תהא A קבוצה. הוכיחו כי |A|\leq |P(A)|.

פתרון: נגדיר את הפונקציה f:A|\to P(A) ע"י a \mapsto \{a\} והיא חח"ע.

תהא A קבוצה. הוכיחו כי |A|\neq |P(A)|.

פתרון: נניח בשלילה כי |A|= |P(A)| אזי קיימת f: A\to P(A) הפיכה, בפרט על. נגדיר X=\{a\in A: a\notin f(a)\}. זוהי תת קבוצה של A ולכן, מכיוון ש-f על, קיים x\in A כך ש-f(x)=X. האם x\in X? אם לא, לפי הגדרת X נקבל כי x\notin f(x)=X, סתירה. אם כן אז x\in X=f(x) אבל לפי הגדרת X מתקיים x\notin f(x) סתירה. מש"ל.

מקור: https://math-wiki.com/index.php?title=תרגול_14_תשעח&oldid=74569