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

תהי $f : A \to A$ פונקציה. תהי $B \subseteq A$ ונגדיר $B_1 := B$, ולכל $n \in \mathbb{N}$ נגדיר $B_{n+1} := f^{-1}[B_n]$. [תזכורת: $x \in A$ נקראת נקודת שבת של $f$ אם $f(x) = x$.] א. הוכיחו כי אם לכל $B \subseteq A$ מתקיים $\bigcap_{n \in \mathbb{N}} B_n$ הוא ריק, אזי ל-$f$ אין נקודות שבת. ב. אם ל-$f$ אין נקודות שבת. האם לכל $B \subseteq A$ מתקיים $\bigcap_{n \in \mathbb{N}} B_n$ הוא ריק?

רמז: עבור א': נניח בשלילה $f(x) = x$. קחו $B = \{x\}$ והראו ש-$x \in B_n$ לכל $n$ (באינדוקציה). עבור ב': נסו $f$ ללא נקודות שבת אבל $B = A$, וחשבו האם $\bigcap B_n$ יכול להיות לא ריק.

פתרון: **א.** נניח בשלילה שקיים $x \in A$ עם $f(x) = x$. ניקח $B = \{x\}$. $B_1 = \{x\}$. $B_2 = f^{-1}[\{x\}] \ni x$ (כי $f(x) = x$). באינדוקציה: $x \in B_n$ לכל $n$ (כי $x \in B_n \Rightarrow f(x) = x \in B_n \Rightarrow x \in f^{-1}[B_n] = B_{n+1}$). לכן $x \in \bigcap_{n \in \mathbb{N}} B_n \neq \emptyset$ — **סתירה** לנתון. $\blacksquare$ **ב. לא בהכרח.** דוגמה נגדית: $A = \{1, 2\}$, $f(1) = 2$, $f(2) = 1$ (ללא נקודות שבת). ניקח $B = A = \{1,2\}$. $B_1 = \{1,2\}$. $B_2 = f^{-1}[\{1,2\}] = \{1,2\}$. באותו אופן $B_n = \{1,2\}$ לכל $n$. $\bigcap B_n = \{1,2\} \neq \emptyset$. $\blacksquare$