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

תהי

X

קבוצה כלשהי. הוכיחו כי

∣ P (X)^{2} ∣ = ∣ X \to {0, 1, 2, 3} ∣

באמצעות פונקציית זיווג.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמבחן סמסטר ב מועד ב · 2024 · סמסטר ב

★★★★★

קבוצותפונקציותעוצמותפונקציית זיווג

זוג תתי-קבוצות

(A, B)

של

X

שקול לפונקציה

X \to {0, 1} \times {0, 1}

. זהו בעצם

{0, 1, 2, 3}

הוכחה: נגדיר

φ : P (X)^{2} \to (X \to {0, 1, 2, 3})

כך:

לכל

(A, B) \in P (X)^{2}

φ (A, B) = λ x \in X . ⎩ ⎨ ⎧ 0123 x \in / A וגם x \in / B x \in A וגם x \in / B x \in / A וגם x \in B x \in A וגם x \in B

כלומר

φ (A, B) (x) = 2 \cdot 1_{B} (x) + 1_{A} (x)

φ

מוגדרת היטב: לכל

x \in X

, בדיוק אחד מארבעת המקרים מתקיים, והפלט ב-

{0, 1, 2, 3}

.

חח"ע: נניח

φ (A_{1}, B_{1}) = φ (A_{2}, B_{2})

. לכל

x \in X

הערכים שווים. אם

x \in A_{1}

אז

φ (A_{1}, B_{1}) (x) \in {1, 3}

, ולכן

φ (A_{2}, B_{2}) (x) \in {1, 3}

, כלומר

x \in A_{2}

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

A_{1} = A_{2}

. בדומה

B_{1} = B_{2}

.

על: תהי

f : X \to {0, 1, 2, 3}

. נגדיר

A = {x \in X : f (x) \in {1, 3}}

ו-

B = {x \in X : f (x) \in {2, 3}}

. אז

A, B \subseteq X

ו-

φ (A, B) = f

.

לכן

φ

פונקציית זיווג, ו-

∣ P (X)^{2} ∣ = ∣ X \to {0, 1, 2, 3} ∣

■

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