Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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\}$
share|cite|improve this question
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.

  3. A surjective order-preserving map is an isomorphism, and for well-orders, this is unique if it exists at all, so the answer is either 0 or 1, depending on whether the orders are isomorphic or not.

share|cite|improve this answer
In (2), if $X,Y$ are finite then we get $\binom{Y}{X}$. – Yuval Filmus Mar 6 '11 at 2:21
@Yuval Filmus: How do you prove that? – 4math Mar 6 '11 at 3:49
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
Between to finite sets of the same size, every constant function is order-preserving. Therefore, how is that there can only be one order-preserving function in that case? On the other hand, what would happen if in 2. we replace "order-preserving" for "strict order-preserving" or "order-reversing" – 4math Mar 6 '11 at 5:44
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.