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$.


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$.


2 Answers 2


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$.


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$.)


This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .