1
$\begingroup$

Let $m, n$ be positive integers. Let $X$ be a non-empty set.

a. If $m$ is the less than or equal to n, find an injective map $f: X^m \rightarrow X^n$

b. Find a bijective map $g: X^m \times X^n \rightarrow X^{m+n}$.

I'm just looking for information on what exactly the question is asking. I figured for A the question is asking for a map from an element $X_i$ in $X^m$ onto the matching $X_i$ in $X^n$, since the question is only asking for injectivity and doesn't require the map to span $X^n$. I'm sorry if my formatting is confusing.

  • 0
    I will answer (a). Let $k$ be a certain element of $X$, fixed from now on. Map any $m$-tuple $(x_1,\cdots,x_m)$ in $X^m$ to the $n$-tuple $(x_1,\dots,x_m,k,\dots,k)$ where there are $n-m$ $k$'s. It is easy to show that this mapping is injective. Do this for $X$ your favourite set, $m=3$, $n=5$ to make sure you understand. Your proof, though based on the right intuition, was too vague.2011-07-20

2 Answers 2

3

Remember that $X^m$ contains all m-tuples over $X$, thus every $x \in X^m$ looks like this: $(x_1,\ldots,x_m)$ with $x_i \in X$.

Now, an injective map from $X^m$ to $X^n$ with $m \leq n$ should come to your attention, as every element of $X^n$ is a tuple of size equal or larger to $m$. Thus, we can given an element $(x_1,\ldots,x_m) \in X^m$ construct an element in $X^n$ by `appending' $n-m$ arbitrary elements of $X$ to it. As you will see it will suffice to just pick a single element $y \in X$.

More formal we get the following function $f: X^m \rightarrow X^n: (x_1,\ldots,x_m) \mapsto (x_1,\ldots,x_m,\ldots,x_n)$ where $\forall m < i \leq n: x_i = y$. (In my math classes we usually called functions like these an embedding from one set to the other)

The same idea works for (b), only here we will `append' $(y_1,\ldots,y_n) \in X^n$ to $(x_1,\ldots,x_m) \in X^m$ to construct a new tuple $(x_1,\ldots,x_m,y_1,\ldots,y_n)$, which is an element of $X^{m+n}$.

0

For part a, think like this. What does a generic element of $X^m$ look like? What is the "obvious" way to stick it inside of $X^n$? This will guide you to the answer. [edited: $X^n$ replaces $X_n$.]

For part b, notice that $X^m\times X^n$ is an ordered pair containing an $m$-tuple of elements of $X$ followed an $n$-tuple of elements of $X$. How can you get this into $X^{m+n}$? Follow your instincts and it will come out right.