- Thread starter
- #1

- Mar 10, 2012

- 835

- Thread starter caffeinemachine
- Start date

- Thread starter
- #1

- Mar 10, 2012

- 835

- Admin
- #2

- Mar 5, 2012

- 9,591

Erm... suppose we pick X={1,2} and Y={1}, then there is no injection...?

- Moderator
- #3

- Feb 7, 2012

- 2,799

Let $\mathcal{F}$ be the set of bijective maps of the form $f(f)\to R(f)$ with domain $D(f)\subseteq X$ and range $R(f)\subseteq Y$, made into a partially ordered set by the relation $f\prec g\; \Longleftrightarrow\; \{D(f)\subset D(g) \text{ and } g(x) = f(x)\; \forall x\in D(f)\}$. Show that $\mathcal{F}$ satisfies the conditions for Zorn's Lemma, and then check that a maximal element is either an injection from $X$ to $Y$ or the inverse of an injection from $Y$ to $X$.

- Jun 26, 2012

- 45

- Jan 26, 2012

- 644

Yes there is.. from Y to XErm... suppose we pick X={1,2} and Y={1}, then there is no injection...?

- Moderator
- #6

- Feb 7, 2012

- 2,799

- Thread starter
- #7

- Mar 10, 2012

- 835

I think there is a trivial injection from $Y$ to $X$. Take $f:Y\to X$ as $f(1)=1$.Erm... suppose we pick X={1,2} and Y={1}, then there is no injection...?

- Thread starter
- #8

- Mar 10, 2012

- 835

I started out this way myself but I could not complete the proof. May be I am missing something simple. Here's my proof:Let $\mathcal{F}$ be the set of bijective maps of the form $f: D(f)\to R(f)$ with domain $D(f)\subseteq X$ and range $R(f)\subseteq Y$, made into a partially ordered set by the relation $f\prec g\; \Longleftrightarrow\; \{D(f)\subset D(g) \text{ and } g(x) = f(x)\; \forall x\in D(f)\}$. Show that $\mathcal{F}$ satisfies the conditions for Zorn's Lemma, and then check that a maximal element is either an injection from $X$ to $Y$ or the inverse of an injection from $Y$ to $X$.

Let $\mathcal C$ be the collection of all ordered triples $(A,B,f)$ such that $A\subseteq X, B\subseteq Y$ and that $f$ is an injection from $A$ to $B$. We order $\mathcal C$ in the folloewing way. Let $(A_1,B_1,f_1)$ and $(A_2,B_2,f_2)$ be two elements of $\mathcal C$. Then we write $(A_1,B_1,f_1)\leq(A_2,B_2,f_2)$ if $A_1\subseteq A_2$, $B_1\subseteq B_2$ and the restriction of $f_2$ to $A_1$ is same as $f_1$. Now let $C=\{(A_\alpha,B_\alpha,f_\alpha)\}_{\alpha\in J}$ be any chain in $\mathcal C$, where $J$ is an index set. Define $A=\bigcup_{\alpha\in J}A_\alpha$ and $B=\bigcup_{\alpha\in J}B_\alpha$. Consider a function $f:A\to B$ defined as $f(a)=f_\alpha(a)$ if $a\in A_\alpha$.

Now by Zorn's Lemma, $\mathcal C$ has a maximal element.

Say the maximal element is $(A_0,B_0,f_0)$. If $A_0=X$ then we are done. So assume $A_0\neq X$. Now if $B_0\neq Y$ then we can easily find an element in $\mathcal C$ which is greater than $(A_0,B_0,f_0)$ and we would run into a contradiction. Thus $B_0=Y$. From here its not easy to see that $f_0^{-1}:Y\to X$ is an injection and the proof is complete.

Last edited by a moderator:

- Moderator
- #9

- Feb 7, 2012

- 2,799

I think you need to define $\mathcal C$ from the start to consist of triples $(A,B,f)$ such that $A\subseteq X$, $B\subseteq Y$ and that $f$ is an injection from $A$$\vdots$

Now by Zorn's Lemma, $\mathcal C$ has a maximal element.

Say the maximal element is $(A_0,B_0,f_0)$. If $A_0=X$ then we are done. So assume $A_0\neq X$. Now if $B_0\neq Y$ then we can easily find an element in $\mathcal C$ which is greater than $(A_0,B_0,f_0)$ and we would run into a contradiction. Thus $B_0=Y$. From here its not easy to see that $f_0^{-1}:Y\to X$ is an injection and the proof is complete.

- Thread starter
- #10

- Mar 10, 2012

- 835

I guess including the "onto" clause will simplify the proof a bit. I have not checked the details though.I think you need to define $\mathcal C$ from the start to consist of triples $(A,B,f)$ such that $A\subseteq X$, $B\subseteq Y$ and that $f$ is an injection from $A$onto$B$. (You will need to check that this surjective property is preserved by upper bounds of chains.) Then if $(A_0,B_0,f_0)$ satisfies $B_0=Y$, that means that $f_0$ is a bijection from $A_0$ onto $Y$, and so $f_0^{-1}$ is a bijection from $Y$ onto $A_0\subseteq X$.

I think my proof is correct too. Isn't it?

Also, can you give some details of your proof in which you don't require triples but only pairs which seems to be considerably simpler than mine.

- Moderator
- #11

- Feb 7, 2012

- 2,799

Your proof is fine – I was just tying up the loose ends where you said that you could not complete the proof.I guess including the "onto" clause will simplify the proof a bit. I have not checked the details though.

I think my proof is correct too. Isn't it?

Also, can you give some details of your proof in which you don't require triples but only pairs which seems to be considerably simpler than mine.

I don't see what you mean by using pairs rather than triples. My proof used the triples $(f,D(f),R(f))$, just like yours. And the only reason that my proof "seems to be considerably simpler" is that I left out all the details for you to fill in, which you have done.

- Thread starter
- #12

- Mar 10, 2012

- 835

Oh. Now I see. Actually this problem is there in Simmon's 'Introduction to Topology and Modern Analysis' in which the author has given a hint which just uses pairs and not triples and I still don't know how to do it on those lines.Your proof is fine – I was just tying up the loose ends where you said that you could not complete the proof.

I don't see what you mean by using pairs rather than triples. My proof used the triples $(f,D(f),R(f))$, just like yours. And the only reason that my proof "seems to be considerably simpler" is that I left out all the details for you to fill in, which you have done.

Anyway, thanks for taking part in this challenge thread. Your posts are invaluable.