There is no need to use the axiom of choice here. Suppose $X$ is an infinite well-orderable set. We argue that there is a well-ordered set $(Y,<)$ with $Y$ of strictly larger cardinality than $X$.
For this, consider the set $A$ of all binary relations $R\subseteq X\times X$ such that $R$ is a well-ordering of a subset of $X$. Let's call $X_R$ this unique subset.
We introduce an equivalence relation on $A$ by setting that $R_1\sim R_2$ iff $(X_{R_1},R_1)$ and $(X_{R_2},R_2)$ are order isomorphic. Let $Y$ be the set of equivalence classes.
We can well-order $Y$ by saying that $[R_1]<[R_2]$ iff there is an order isomorphism from $(X_{R_1},R_1)$ to a proper initial segment of $(X_{R_2},R_2)$. One easily verifies that $<$ is well-defined. This means that if $R_1\sim R_3$ and $R_2\sim R_4$, then $(X_{R_1},R_1)$ is isomorphic to a proper initial segment of $(X_{R_2},R_2)$ iff $(X_{R_3},R_3)$ is isomorphic to a proper initial segment of $(X_{R_4},R_4)$. One also verifies easily that $<$ is a well-ordering.
Finally, $Y$ has size strictly larger than $X$. To see this, note first that $X$ injects naturally into $Y$, namely, given a well-ordering $\prec$ of $X$ and any two initial segments $X_1$ and $X_2$ of $X$ under $\prec$, with $X_1$ a proper initial segment of $X_2$, $[\prec\upharpoonright X_1]<[\prec\upharpoonright X_2]$. But each point of $X$ determines an initial segment of $X$.
Now, if there were an injection $f$ of $Y$ into $X$, then the range $Z$ of $f$ would be well-orderable in a way isomorphic to $(Y,<)$ by using $f$ to copy the well-ordering $<$ of $Y$: Simply set $f(a) R f(b)$ iff $a<b$ for any classes $a,b\in Y$. We then have a copy of $(Y,<)$ as a proper initial segment of $(Y,<)$ (again, looking at initial segments of $(Z,R)$), contradicting that $<$ is a well-ordering.
The above may seem complicated but it is simple: All it is saying is that a well-ordering is less than another if it is an initial segment, and this is a "well-ordering of well-orderings". (And we have to use equivalence classes because different well-orderings may actually be isomorphic.)
When $X$ is a countably infinite set, the resulting set $Y$ is well-ordered and uncountable, but any initial segment of $Y$ corresponds to a well-ordering of $X$, so it is countable. If you want a set $B$ as required, simply set $B=Y\cup\{*\}$ where $*$ is some point not in $Y$, ordered by simply making $*$ larger than all the elements of $Y$. Then $\{a\in B\mid a<*\}$ is uncountable, but $\{c\in B\mid c<d\}$ is countable for any $d\in Y$, i.e., for any $d\in B$ with $d\ne *$.
Once you are familiar with the construction of ordinals, the above can be streamlined a bit: Rather than using an equivalence class, we simply use the ordinal isomorphic to any representative of the class. The argument above gives us that the collection of countable ordinals is actually a set, and its union is an (in fact, the first) uncountable ordinal. As a matter of fact, there is not even the need to take a union. The set of countable ordinals is already an uncountable ordinal.
(The argument above shows that given any well-ordered set there is a larger well-ordered set. A similar argument gives that if we have a family of well-orders, we can paste them together to get a well-ordering larger than all the ones in the family.)
Suppose $ (\Bbb Z_+,\le)$ and $(\Bbb Z_-,\le)$ are order isomorphic.
Then $\exists f:\Bbb{Z}_+ \to \Bbb{Z}_-$ such that
$f$ is binjective.
$f$ preserve order i.e $a\le b$ implies $f(a) \le f(b) $
Since $|\Bbb{Z}_+|=\aleph_0=| \Bbb{Z}_-|$ , hence there is a bijection between $\Bbb{Z}_+ $ and $\Bbb{Z}_-$.
Claim: No bijection $f: \Bbb{Z}_+ \to \Bbb{Z}_-$ is not order preserving.
Proof: Assume the contrary.
Let $f(1) =u$
Then $\forall x\in \Bbb{Z}_+ \space , 1\le x$ implies $u=f(1) \le f(x) $
i.e $u\le y\space , \forall y\in \Bbb{Z}_-$ implies $u$ is the least element which is a contradiction because $\Bbb{Z}_-$ in it's usual ordering has no least element (given any $u\in \Bbb{Z}_- $ , $u-1<u$ ).
Note: Order isomorphism between two poset maps least element to least element.
Conclusion: $(\Bbb{Z}_+, \le) $ and $( \Bbb{Z}_-, \le) $ is not order isomorphic.
Best Answer
Use the fact that for any infinite ordinal $\alpha$, $|\alpha|=|\alpha+1|$ (but of course $\alpha$ is not isomorphic to $\alpha+1$ as a well-ordered set).
To prove this, find a bijection between $\alpha$ and $\alpha+1$ by applying the logic of "Hilbert's hotel": Map $0$ to $\alpha,$ then map $1$ to $0$, $2$ to $1,$ $3$ to $2,$ and so on. Then map everything $\ge \omega$ to itself.