'''פתרון.'''
תהי 1. ''' f על אמ"מ g חח"ע שאינה '''בכיוון אחד- נתון ש f על (קל למצוא כאלה). אזי נניח <math>\exists y\in Y\forall x\in X:f^{-1}(B)=g(B)=g(A)=f^{-1}(xA)\neq y</math>. לכן נפעיל את f על שני הצדדים ונקבל (בגלל ש f על) <math>g(Y)B=f(f^{-1}(YB))=f(f^{-1}(Y/\{y\}A))=gA(Y/\{y\})</math> בסתירה לחח"ע של g.
בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי <math>\exists y\in Y\forall x\in X:f(x)\neq y</math> לכן <math>g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\}=g(Y/\{y\})</math> בסתירה לחח"ע של g.
*לכן '''ייתכן ו-f חח"ע אך g אינה כזו'''.
2. ''' f חח"ע אמ"מ g על '''
בכיוון אחד- נתון f חח"ע. אזי <math>g(f(A))=f^{-1}(f(A))=A</math> ולכן g על ( עבור A המקור שלה יהיה <math>f(A)</math> )
בכיוון השני- נתון g על. נניח בשלילה ש f אינה חח"ע אזי קיימים <math>x,y \in X</math> שונים כך ש <math>f(x)=f(y)</math>. נביט בנקודון <math>A=\{x\}</math> כיוון ש g כלקיימת <math>B\in P(Y)</math>
כך ש <math>f^{-1}(B)=g(B)=A</math> לכן <math>B\subseteq f(f^{-1}(B)) = f(A)= \{f(x)\} </math> כיוון ש B אינה ריקה נקבל ש <math>B=\{f(x)\} </math>
לכן <math> \{x\}=A=g(B)=f^{-1}(B)=f^{-1}(\{f(x)\})\supseteq \{x,y\}</math>. ולכן <math>x=y</math>. סתירה.
תהי f כך ש-g חח"ע. כפי שראינו לעיל, מכאן ניתן ישר להסיק ש-f הינה על. כי שאר הגרירות אינן מוכרחות:
* '''ייתכן ו-f חח"ע אך g אינה כזו''' (ניקח f חח"ע שאינה על אזי g אינה חח"ע לפי 1)
נוכיח שאם f על אזי * '''יתכן ו-g חח"ע; נניח בשלילה שg אך f אינה כזו'''. (ניקח g חח"ע, שאינה על אזי קיימות שתי קבוצות <math>B\neq C \in P(Y)</math> כך ש <math>g(B)=g(C)</math>. בלי הגבלת הכלליות, נניח שקיים איבר <math>c\in C</math> כך ש <math>c\notin B</math>. מכיוון ש-f על, קיים איבר a כך ש <math>f(a אינה חח"ע לפי 2)=c</math>, לכן <math>a\in g(B)</math>, ואז קיים <math>b\in B</math> כך ש<math>f(a)=b</math> ולכן b=c בסתירה.
* '''ייתכן ו-f על אך g אינה כזו ''' (ניקח f על שאינה חח"ע אזי g אינה על לפי 2)
*אם כן, הוכחנו ש-'''f ייתכן ו-g על אם"ם אך f אינה כזו ''' (ניקח g על שאינה חח"ע.'''אזי f אינה על לפי 1)
אתם מוזמנים לתת דוגמאות למסקנות לעיל
למשל:
יהיו <math>X=\mathbb{Z}, Y=\{0\}</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן <math>g(\{\})\neq g(\{0\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.
*לכן '''יתכן ו-g חח"ע אך f אינה כזו'''.
נניח וg על ונניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>a,b \in X</math> שונים כך ש <math>f(x)=f(y)</math>. נביט בנקודון <math>A=\{x\}</math> נניח וקיימת <math>B\in P(Y)</math> כך ש <math>g(B)=A</math>, לכן <math>f(x)\in B</math>. אבל אז בעצם גם <math>f(y)\in B</math> ולכן <math>y\in g(B)=A</math> בסתירה. לכן f חח"ע.
נניח f חח"ע, הוכחנו כבר שבהכרח <math>f^{-1}(f(A))=A</math> לכל A תת קבוצה של X. נובע ש <math>g(f(A))=A</math> ולכן g הינה על.
*סה"כ, הוכחנו ש'''f חח"ע אם"ם g הינה על'''.
ניקח f פונקציה חח"ע שאינה על, לכן g היא על.
*לכן '''ייתכן ו-g הינה על אך f אינה על'''
באופן דומה ניקח f על שאינה חח"ע, לכן g אינה על.
*לכן '''ייתכן ו-f הינה על אך g אינה על'''
