שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 2024

קורס: מתמטיקה בדידה

אוניברסיטה: אוניברסיטת תל אביב

שנה: 2024

סמסטר: א

נושאים: פונקציות, עוצמות

רמת קושי: בינוני-קשה

תהי $G$ פונקציה $G \in (\mathbb{R} \to \mathbb{R}) \to (\mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R} \times \mathbb{R}))$. הוכיחו ש-$G$ אינה על $\mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R} \times \mathbb{R})$. **רמז:** השתמשו בחשבון עוצמות.

רמז: השוו את עוצמת התחום של $G$ לעוצמת הטווח. חשבו כמה פונקציות מסוג $\mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R} \times \mathbb{R})$ קיימות, לעומת כמה פונקציות מסוג $(\mathbb{R} \to \mathbb{R}) \to (\mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R} \times \mathbb{R}))$ קיימות, ובדקו אם מספר האיברים בתחום קטן ממספר האיברים בטווח.

פתרון: כדי להוכיח ש-$G$ אינה **על**, נראה שעוצמת התחום של $G$ קטנה בהחלט מעוצמת הטווח. **חישוב עוצמת הטווח:** הטווח של $G$ הוא הקבוצה $\mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R} \times \mathbb{R})$, כלומר כל הפונקציות מ-$\mathcal{P}(\mathbb{R})$ ל-$\mathcal{P}(\mathbb{R} \times \mathbb{R})$. נסמן $|\mathbb{R}| = \mathfrak{c} = 2^{\aleph_0}$. אזי: $$|\mathcal{P}(\mathbb{R})| = 2^{\mathfrak{c}}, \quad |\mathcal{P}(\mathbb{R} \times \mathbb{R})| = 2^{\mathfrak{c}}$$ עוצמת קבוצת הפונקציות מ-$\mathcal{P}(\mathbb{R})$ ל-$\mathcal{P}(\mathbb{R} \times \mathbb{R})$ היא: $$|\mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R} \times \mathbb{R})| = |\mathcal{P}(\mathbb{R} \times \mathbb{R})|^{|\mathcal{P}(\mathbb{R})|} = (2^{\mathfrak{c}})^{2^{\mathfrak{c}}} = 2^{\mathfrak{c} \cdot 2^{\mathfrak{c}}} = 2^{2^{\mathfrak{c}}}$$ **חישוב עוצמת התחום:** התחום של $G$ הוא $\mathbb{R} \to \mathbb{R}$, כלומר כל הפונקציות מ-$\mathbb{R}$ ל-$\mathbb{R}$. עוצמתו היא: $$|\mathbb{R} \to \mathbb{R}| = |\mathbb{R}|^{|\mathbb{R}|} = \mathfrak{c}^{\mathfrak{c}} = (2^{\aleph_0})^{2^{\aleph_0}} = 2^{\aleph_0 \cdot 2^{\aleph_0}} = 2^{2^{\aleph_0}} = 2^{\mathfrak{c}}$$ לכן עוצמת התחום של $G$ היא $2^{\mathfrak{c}}$. **השוואה:** עוצמת התחום של $G$ היא $2^{\mathfrak{c}}$, ועוצמת הטווח (קבוצת הפונקציות מ-$\mathcal{P}(\mathbb{R})$ ל-$\mathcal{P}(\mathbb{R}\times\mathbb{R})$) היא $2^{2^{\mathfrak{c}}}$. לפי משפט קנטור, לכל קבוצה $A$ מתקיים $|A| < 2^{|A|}$, ולכן: $$2^{\mathfrak{c}} < 2^{2^{\mathfrak{c}}}$$ מכיוון שעוצמת התחום של $G$ קטנה בהחלט מעוצמת הטווח שלה, פונקציה $G$ אינה יכולה להיות **על** — שכן פונקציה על מחייבת שלכל איבר בטווח יש לפחות פריימייג' אחד, ולכן עוצמת התחום חייבת להיות לפחות כגדולה מעוצמת הטווח. $\blacksquare$

תהי

G

פונקציה

G \in (R \to R) \to (P (R) \to P (R \times R))

. הוכיחו ש-

G

אינה על

P (R) \to P (R \times R)

.

רמז: השתמשו בחשבון עוצמות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א'2024סמסטר א

★★★★★

פונקציותעוצמות

השוו את עוצמת התחום של

G

לעוצמת הטווח. חשבו כמה פונקציות מסוג

P (R) \to P (R \times R)

קיימות, לעומת כמה פונקציות מסוג

(R \to R) \to (P (R) \to P (R \times R))

קיימות, ובדקו אם מספר האיברים בתחום קטן ממספר האיברים בטווח.

כדי להוכיח ש-

G

אינה על, נראה שעוצמת התחום של

G

קטנה בהחלט מעוצמת הטווח.

חישוב עוצמת הטווח:

הטווח של

G

הוא הקבוצה

P (R) \to P (R \times R)

, כלומר כל הפונקציות מ-

P (R)

ל-

P (R \times R)

.

נסמן

∣ R ∣ = c = 2^{ℵ_{0}}

. אזי:

∣ P (R) ∣ = 2^{c}, ∣ P (R \times R) ∣ = 2^{c}

עוצמת קבוצת הפונקציות מ-

P (R)

ל-

P (R \times R)

היא:

∣ P (R) \to P (R \times R) ∣ = ∣ P (R \times R) ∣^{∣ P (R) ∣} = (2^{c})^{2^{c}} = 2^{c \cdot 2^{c}} = 2^{2^{c}}

חישוב עוצמת התחום:

התחום של

G

הוא

R \to R

, כלומר כל הפונקציות מ-

R

ל-

R

. עוצמתו היא:

∣ R \to R ∣ = ∣ R ∣^{∣ R ∣} = c^{c} = (2^{ℵ_{0}})^{2^{ℵ_{0}}} = 2^{ℵ_{0} \cdot 2^{ℵ_{0}}} = 2^{2^{ℵ_{0}}} = 2^{c}

לכן עוצמת התחום של

G

היא

2^{c}

.

השוואה:

עוצמת התחום של

G

היא

2^{c}

, ועוצמת הטווח (קבוצת הפונקציות מ-

P (R)

ל-

P (R \times R)

) היא

2^{2^{c}}

.

לפי משפט קנטור, לכל קבוצה

A

מתקיים

∣ A ∣ < 2^{∣ A ∣}

, ולכן:

2^{c} < 2^{2^{c}}

מכיוון שעוצמת התחום של

G

קטנה בהחלט מעוצמת הטווח שלה, פונקציה

G

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

■

שאלת מבחן במתמטיקה בדידה - אוניברסיטת תל אביב 2024 - פונקציות