Using Zorn’s lemma to show a function maps part of a set one to one onto another set Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of Using Zorn’s lemma to show a function maps part of a set one to one onto another set without wasting too much if your time.

The question is published on by Tutorial Guruji team.

Let $A$ and $B$ be any two sets. Let $X$ be the collection of functions that map a subset of $A$ one to one onto a subset of $B$. Define a partial order on $X$ and use Zorn’s lemma to show that there is a function that maps $A$ into $B$ or maps part of $A$ one to one onto $B$.

Let $X$ be the set defined in the question statement. We order $X$ by $f leq g$ iff $f subset g$. $(X,leq)$ is a Poset since the elements of $X$ are functions, which are sets of ordered pairs. Now, let $Y subset Z$ be a chain. Let $f = bigcup Y$. $f$ is a (partial) function from $A$ to $B$ that is 1-1, hence in $X$, also it is an upper bound for $Y$. Now applying Zorn’s lemma let $F$ be a maximal element in $X$. $F$ is a 1-1 partial function from $A$ to $B$, which implies that dom$(f)=A$ or $f$ is onto.

This proof is by no means complete, I am having a really hard time with this one, if anyone can show me how they would prove it I would really appreciate it


Usually I prefer to give hints, but in this case I think that a full exposition of most of the details is probably more useful in the long run; there is still one bit that I’ll leave for you to try.

Let $X$ be the set of injective functions whose domains are subsets of $A$ and whose ranges are subsets of $B$. This means that if $fin X$, then $operatorname{dom}fsubseteq A$, $operatorname{ran}fsubseteq B$, and (by the definition of function) $f={langle a,f(a)rangle:ainoperatorname{dom}f}$. Thus, $fsubseteq Atimes B$. Since the elements of $X$ are sets, the subset relation $subseteq$ partially orders them, and $langle X,subseteqrangle$ is a partial order.

It might be a good idea to stop here for a moment and see just what it means to say that $fsubseteq g$ for functions $f,gin X$. For notational convenience let $A_f=operatorname{dom}f$ and $A_g=operatorname{dom}g$, and suppose that $ain A_f$. Then $langle a,f(a)ranglein fsubseteq g$, so $langle a,f(a)ranglein g$, so $ain A_g$. Thus, $A_fsubseteq A_g$: everything in the domain of $f$ is also in the domain of $g$. Since $ain A_g$, we also know that $langle a,g(a)ranglein g$. But $g$ is a function, so if both $langle a,f(a)rangle$ and $langle a,g(a)rangle$ belong to $g$, then $f(a)=g(a)$. In other words, $g$ agrees with $f$ on the set $A_f$: for every $ain A_f$, $g(a)=f(a)$. In technical terms, $gupharpoonright A_f=f$, where $gupharpoonright A_f$ is the restriction of $g$ to the set $A_f$. (You may use a different notation for the restriction, e.g., $g|_{A_f}$.)

Now suppose that $Y$ is a chain in $X$. In other words, $Y$ is a family of partial functions from $A$ to $B$ with the property that if $g,hin Y$, then $gsubseteq h$ or $hsubseteq g$. Let $f=bigcup Y$; we want to show that $fin X$. Each $gin Y$ is a subset of $Atimes B$, so at least we know that $fsubseteq Atimes B$. The next step is to show that $f$ is a function. In other words, we must show that if $langle a,brangle,langle a,b’ranglein f$, then $b=b’$.

If $langle a,branglein f$, there must be some $gin Y$ such that $langle a,branglein g$. Similarly, if $langle a,b’ranglein f$, there must be some $hin Y$ such that $langle a,b’ranglein h$. $Y$ is a chain, so either $gsubseteq h$ or $hsubseteq g$; without loss of generality assume that $gsubseteq h$. But then $langle a,branglein h$ and $langle a,b’ranglein h$, and $h$ is a function, so $b=b’$, as desired. Thus, $f$ is a function from some subset of $A$ to subset of $B$, and it only remains to show that $f$ is injective.

The argument is very similar to the proof that $f$ is a function. Suppose that $langle a,brangle,langle a’,branglein f$; we want to show that $a=a’$. See if you can adapt the argument of the preceding paragraph to do so.

Proofs using Zorn’s lemma typically break into three parts. The first part is finding the right partial order; that was done for us here. The second part is showing that each chain in that partial order has an upper bound. Very often there’s an obvious candidate for the upper bound; when the partial order is inclusion, it’s very likely to be the union of the chain, as here, and in that case it’s clear that it’s an upper bound — if it’s in the partial order. Proving that it’s in the partial order typically requires showing that it satisfies certain conditions, each of which involves only finitely many objects. (Here we had to deal with only two objects at a time.) Because we have a chain, we can find a single element of the chain that deals with all of those objects at once and use that to show that the union of the chain deals with them in the same way. The third part is showing that a maximal element of the partial order does what we want it to do.

Now we know that $fin X$, and since $f=bigcup Y$, it’s clear that $gsubseteq f$ for each $gin Y$, i.e., that $f$ is an upper bound for $Y$ in the partial order $langle X,lerangle$. $Y$ was an arbitrary chain in $langle X,lerangle$, so we’ve shown that every chain in $langle X,lerangle$ has an upper bound in $X$. We can therefore apply Zorn’s lemma to conclude that $X$ has a maximal element $f$. What do we know about $f$?

First, $fin X$, so $f$ is an injective function whose domain is some set $A_fsubseteq A$. Let $B_f=operatorname{ran}f$; we know that $B_fsubseteq B$, and we know that $f$ is a bijection from $A_f$ to $B_f$. Finally, we know that $f$ is maximal in $langle X,lerangle$, meaning that if $gin X$, and $fle g$, then $f=g$.

Now we’ve reached the third part of the argument: we want to show that either $A_f=A$, or $B_f=B$. This is where we’ll use the fact that $f$ is maximal in $langle X,lerangle$, and we’ll do so in a very typical way: we’ll show that if $A_fne A$ and $B_fne B$, then $f$ cannot be maximal after all.

Suppose, then, that $A_fne A$ and $B_fne B$, and let $a_0in Asetminus A_f$ and $b_0in Bsetminus B_f$. Let $g=fcuplangle a_0,b_0rangle$. Clearly $fsubsetneqq gsubseteq Atimes B$. I claim that $gin X$; since $fle g$ but $fne g$, this will contradict the maximality of $f$, and the contradiction will show that it’s impossible to have both $A_fne A$ and $B_fne B$. Thus, we’ll be able to conclude that either $A_f=A$ or $B_f=B$, as desired. (Of course it’s possible that both are true: that’s not an exclusive either-or.)

First we have to check that $g$ is a function. Suppose that $langle a,brangle,langle a’,branglein g$. If $langle a,brangle,langle a’,branglein f$, then $a=a’$ because we already know that $f$ is a function. The only other possibility is that one of the ordered pairs, say $langle a,brangle$, is in $f$, and the other is $langle a_0,brangle$, but that’s impossible: $a_0notin A_f$, so the only element of $g$ with first coordinate $a_0$ is $langle a_0,b_0rangle$, and since $b_0notin B_f$, we know that $b_0ne b$. Thus, $g$ is a function, and all that remains is to verify that it’s injective.

Since $f$ is injective, $g$ could fail to be injective only if there were some $ain A_f$ such that $g(a)=g(a_0)$. But $g(a)in B_f$, while $g(a_0)=b_0notin B_f$, so this can’t happen, and we’re done.

We are here to answer your question about Using Zorn’s lemma to show a function maps part of a set one to one onto another set - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji