# Cardinality of sets of functions with well-ordered domain and codomain

I would like to determine the cardinality of the sets specified bellow. Nevertheless, I don't know how to approach or how to start such a proof. Any help will be appreciated.

If $X$ and $Y$ are well-ordered sets, then determine the cardinality of:

1. $\{f : f$ is a function from $X$ to $Y\}$
2. $\{f : f$ is an order-preserving function from $X$ to $Y\}$
3. $\{f : f$ is a surjective and order-preserving function from $X$ to $Y\}$
-
Are you allowed to assume the axiom of choice? – Asaf Karagila Mar 5 '11 at 9:15
@Asaf: Yes, I am. – 4math Mar 5 '11 at 9:19
Oh, any hints yet? I suppose this problem is somewhat complicated. – 4math Mar 5 '11 at 17:44

1. The cardinality of the set of functions from $X$ to $Y$ is the definition of the cardinal $Y^X$.
2. The number of order-preserving functions from $X$ to $Y$, given that well-orders of each set have been fixed, depends on the nature of those orders. For example, there are no such orders in the case that the order type of $X$ is longer than the order type of $Y$. If $X$ and $Y$ are finite, then there is some interesting combinatorics involved to give the right answer. For example, if both are finite of the same size, there is only one order-preserving function. If $Y$ is one bigger, then there are $Y$ many (you can put the hole anywhere). And so on. If $Y$ is infinite, of size at least $X$, then you get $Y^X$ again, since you can code any function into the omitted part, by leaving gaps of a certain length.
In (2), if $X,Y$ are finite then we get $\binom{Y}{X}$. – Yuval Filmus Mar 6 '11 at 2:21
The images of the function form a subset of size $|X|$ of $Y$. Moreover, given the subset, the function itself is defined uniquely by the requirement that the function be order-preserving. – Yuval Filmus Mar 6 '11 at 4:16
@4math, I interpret "order-preserving" to mean $x\leq y\iff \phi(x)\leq\pi(y)$, and I believe that this is what most people mean by that terminology (this is likely the same as what you mean by strict order-preserving). If you intend the property that $x\leq y\to \phi(x)\leq\phi(y)$, then you have merely a weak order homomorphism, and there will of course be more maps. – JDH Mar 6 '11 at 19:32