תכונות של פונקציות

חד-חד-ערכיות (אינייקציה)

פונקציה $f : A \to B$ נקראת חד-חד-ערכית (חח”ע) אם לכל $a_{1}, a_{2} \in A$ :

a_{1} \neq = a_{2} ⟹ f (a_{1}) \neq = f (a_{2})

שקילות: $f (a_{1}) = f (a_{2}) ⟹ a_{1} = a_{2}$ .

פירוש: $f$ “לא מזהה” שני איברים שונים — לכל ערך יש לכל היותר מקור אחד.

פונקציה $f : A \to B$ נקראת על אם לכל $b \in B$ קיים $a \in A$ עם $f (a) = b$ .

פירוש: כל ערך ב- $B$ מושג על ידי $f$ — אין איברים “בלתי מושגים” ב- $B$ .

פונקציה שהיא גם חח”ע וגם על נקראת חיח”ע (חד-חד-ערכית ועל) או ביקציה. לכל ביקציה קיימת פונקציה הפוכה $f^{- 1} : B \to A$ .

הרכבת חח”ע עם חח”ע היא חח”ע: אם $f : A \to B$ , $g : B \to C$ חח”ע, אז $g \circ f : A \to C$ חח”ע.
הרכבת על עם על היא על.
הרכבת ביקציות היא ביקציה.

שתי קבוצות שוות עוצמה (סימון: $∣ A ∣ = ∣ B ∣$ ) אם קיימת ביקציה $f : A \to B$ .

נכתוב $∣ A ∣ \leq ∣ B ∣$ אם קיימת חח”ע $f : A \to B$ (או על מ- $B$ ל- $A$ ).