Cardinalities of any two sets are comparable.

[caffeinemachine]

Let $X$ and $Y$ be any two sets. Show by using Zorn's Lemma (or anything equivalent to it) that there is an injection of one into the other.

 

[I like Serena]

Let $X$ and $Y$ be any two sets. Show by using Zorn's Lemma (or anything equivalent to it) that there is an injection of one into the other.

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

 

[Opalg]

Let $X$ and $Y$ be any two sets. Show by using Zorn's Lemma (or anything equivalent to it) that there is an injection of one into the other.

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

 

[ModusPonens]

I think the idea is to start with one of them, say, X and use the axiom of choice to remove elements of Y one by one, for each element of X. If you remove them all and use all the elements of X, it's a bijection. If you only remove part of Y with all the elements of X, the choice function is an injection. Finaly, if you remove all the elements of Y, but don't use all X, the inverse of that choice function is an injection of Y into X.

 

[Nono713]

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

Yes there is.. from Y to X ;)

 

[Opalg]

Just to point out that ModusPonens's suggestion and mine are essentially the same. In both cases, the idea is to pair off elements of $X$ with elements of $Y$ until you run out of further choices (in one space or the other). As usual in such proofs, you can make the argument rigorous by using either Zorn or Choice, according to taste.

 

[caffeinemachine]

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

I think there is a trivial injection from $Y$ to $X$. Take $f:Y\to X$ as $f(1)=1$.

 

[caffeinemachine]

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

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

Claim 1: $f$ is well defined.
Proof: Let $a\in A$ be such that $a\in A_\alpha$ and $a\in A_\beta$. We need to show that $f_\alpha(a)=f_\beta(a)$. Since $C$ is a chian, WLOG assume that $A_\alpha\subseteq A_\beta$. Then the restriction of $f_\beta$ to $A_\alpha$ is same as $f_\alpha$. Thus $f_\beta(a)=f_\alpha(a)$ and the claim is settled.

Claim 2: $(A,B,f)$ is in $\mathcal C$.
Proof: Clearly $A\subseteq X$ and $B\subseteq Y$. We just need to show that $f$ is an injection. Let $f(p)=f(q)$ for some $p,q\in A$. Say $p\in A_\gamma$ and $q\in A_\delta$. WLOG assume that $A_\gamma\subseteq A_\delta$. Then $f(p)=f_\delta(p)=f_\delta(q)\Rightarrow p=q$ by the injectivity of $f_\delta$.

Claim 3: $(A,B,f)$ is an upper bound of $C$.
Proof: Let $(A_\alpha,B_\alpha,f_\alpha)$ be any element of $C$. Clearly $A_\alpha\subseteq A$ and $B_\alpha\subseteq B$. We need to show that the restriction of $f$ to $A_\alpha$ is same as $f_\alpha$. But this is evident by the definition of $f$ and hecne the claim is settled.

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.

 

[Opalg]

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

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

 

[caffeinemachine]

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

 

[Opalg]

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.

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.

 

[caffeinemachine]

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.

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.

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