Let $R$ be a relation from $A$ to $B$. Prove that there exists a subset $f^*$ of $R$ such that $f^*$ is a function from $A$ into $B$. 
Let $R$ be a relation from $A$ to $B$ and suppose the domain of $R$ is $A$.
Then there exists a subset $f^*$ of $R$ such that $f^*$ is a function
from $A$ into $B$.


Proof:

Zorn's Lemma:
Let $X$ be a non-empty partially ordered set in which every totally ordered
subset has an upper bound. Then $X$ contains at least one maximal element.

$R \subset A \times B$.
Let $P$ be partially ordered by set inclusion and $P \subset R$ such that
$f \in P$ is a function from a subset of $A$ into $B$.
Let $T$ be a totally ordered subset of $P$.
$T = \{f_i: A_i \rightarrow B; \:\:i \in I\}$
This implies:
$f = \cup f_i: \cup A_i \rightarrow B$ and $f \subset R$.
$f$ is an upper bound of $T$ and Zorn's lemma gives that $P$ has a maximal element
$f^*: A^* \rightarrow B$.

I am not sure how finish it from here and prove that $A^* = A$.
 A: In this case it's much easier to directly apply the axiom of choice. Using the fact that $A$ is the domain of $R$, we know that the set $\{b \in B \mid a R b\}$ is nonempty for every $a \in A$. So by the axiom of choice we can choose an element $b_a \in \{b \in B \mid a R b\}$ for each $a$. Then, we define $f(a) = b_a$. Now $f$ is clearly a function, so we need to show that $f$ is contained in $R$.
So suppose $f(x) = y$. We want to show that $x R y$. But we defined $f$ so that we always have $y \in \{b \in B \mid x R b\}$, or in other words, so that $x R y$. Thus, $f$ is contained in $R$.
A: You're not using Zorn's lemma correctly. You don't want $P$ to be a subset of $R$, but rather of the power set of $R$. Namely, you want $f\in P$ to satisfy $f\subseteq R$. 
Other than that, you're almost done. You need to appeal to maximality of $f^*$, if $A^*\neq A$ then you can extend $f^*$ by another ordered pair, which contradicts the maximality.
(Also, you haven't argued why $\bigcup T$ is a function in $P$, but I'll give you the benefit of the doubt that you've already proven that the union of a chain of functions is a function, and its domain and range equal to the union of domains and ranges, so $\bigcup T$ is in fact an element of $P$.)
