5
$\begingroup$

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\}$
  • 0
    Oh, any hints yet? I suppose this problem is somewhat complicated.2011-03-05

1 Answers 1

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

  • 0
    @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.2011-03-06