Here's a question that bugs me. Consider the set $P$ of non-empty subsets of $\mathbb{N}$, and for $A,B\in P$ define $A{\bf \leq}B$ if $A=B$ or if there exists a 1-1 mapping $f:A\rightarrow B$ which is not onto. The question is, is $\leq$ a partial ordering?
So, if I understand it correctly, we are to check the following:
a) $A\leq A$.
b) $A\leq B$ and $B\leq A$ implies $A=B$.
c) $A\leq B$ and $B\leq C$ implies $A\leq C$.
For c), we have a 1-1 function $f: A \rightarrow B$ and a 1-1 function $g:B\rightarrow C$. So if we consider the composition $gof$ we obtain a 1-1 function from $A$ to $B$.
For a), there is no trouble: I thought about using the identity function but this is onto. We can just use $A=A$ to have $A\leq A$.
For b), I don't quite know how to do it. It would be simple if $f$ was allowed to be onto...
Thanks in advance for any reply!
Hints:
Let $A,B$ be any two distinct infinite subsets of $\mathbb{N}$.
Write $A = \{a_1,a_2,a_3,...\}$, and $B= \{b_1,b_2,b_3,...\}$.
Construct an explicit injection from $A$ to $B$ which is not onto, and an explicit injection from $B$ to $A$ which is not onto.
Conclude that anti-symmetry fails.
Note:
If $P$ was the set of finite subsets of $\mathbb{N}$, then anti-symmetry would hold.
To see that, suppose $A,B$ are finite subsets of $\mathbb{N}$ such that $A\le B$, $B\le A$, but $A\ne B$.
Then there must be an injection $f:A \to B$ which is not onto, and an injection $g:B \to A$ which is not onto.
But then $g\circ f$ would be an injection from $A$ to $A$ which is not onto, contradiction, since any injective map from a finite set to itself is a bijection.