Notes - Set Theory HT25, Functions
Flashcards
@Define a function $f$ formally.
A function $f$ is a binary relation with the property that for all $x$, there is at most one $y$ such that $\langle x, y \rangle \in f$.
@Define the restriction of $f$ to a set $a \subseteq \text{dom}(f)$.
\[f|_a := f \cap (a \times \text{ran}(f)) = \\{\langle x, y\rangle \in f : x \in a\\}\]
@Define the image of $a \subseteq \text{dom}(f)$ under $f$.
\[f[a] := \text{ran}(f|_a) = \\{ y : \exists x \in a . f(x) = y \\}\]
@Prove that given sets $X$ and $Y$, there is a set $Y^X$ whose elements are precisely the functions from $X$ to $Y$.
Note that any $f : X \to Y$ is an element of $\mathcal P(X \times Y)$, so by Comprehension it suffices to see that the property of a set $f \subseteq X \times Y$ being a function $X \to Y$ is expressible in $\mathcal L$, as follows:
\[\phi(f) := \forall x \in X (\exists y \in Y . f(x) = y \land \forall y' (f(x) = y' \implies y' = y))\]What is $Y^\emptyset$?
\[\\{\emptyset\\}\]
@example~