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

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.

share|cite|improve this question
I tried reformatting your question in what I thought you meant, does it look correct? Sorry if it isn't. – yunone Jul 20 '11 at 1:02
Yea, that looks better. Thanks. – Ryan Warnick Jul 20 '11 at 1:04
Can you think of an injective map $\mathbf{R} \to \mathbf{R}^2$? – Dylan Moreland Jul 20 '11 at 1:18
You're on the right track! You should be explicit about what you mean by "the matching $X_i$ in $X^n$," because there are lots of potential matching $X_i$. – Adam Saltz Jul 20 '11 at 1:19
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. – André Nicolas Jul 20 '11 at 1:20

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}$.

share|cite|improve this answer

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.

share|cite|improve this answer

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.