I was given the following problem worded exactly:

"Let $X,Y \neq \emptyset$ and suppose that every element of $F(X,Y)$ is injective. Show that $|X|=1.$"

and the set $F(X,Y) := \{f\ | f:X \to Y \} $

I can't prove this statement holds, in fact I think it is false. I came up with the following argument:

Suppose that every element of $F(X,Y)$ is injective, and modifying the definition above we get the set $$F(X,Y) := \{f\ | f:X \to Y \ \wedge f(x_1)=f(x_2)\ \supset \ \ x_1=x_2\} $$

Take set $X=\{x_1,x_2,\dots,x_n\}$ and set $Y=\{y_1,y_2,\dots,y_m\}$ $n\le m$

and we can construct a counterexample where $f_1$ is injective and maps $x_i\to y_i$ for all $i=1,...,n$.

Or similarly lets say $f_2$ is injective and maps $x_i\to y_{2i}$ for all $i=1,...,n$ where $y_{2i}\le m$.

This would mean $|X|\neq1$.

However I can see that if $|X|=1$ and $Y$ was nonempty then necessarily $f:X \to Y$ would be injective.

Can you help explain if I'm wrong, how I am wrong and what the proof would be that shows the statement above holds? Thanks.

  • $\begingroup$ I think you're mixing up "every function from $X$ to $Y$ is injective" and "there exists a function $f: X \to Y$ that's injective." $\endgroup$ – pjs36 Feb 6 '17 at 1:54
  • $\begingroup$ @pjs36 That was the wording I was given the problem in. It says evey element of the set $F(X,Y)$ which are functions. $\endgroup$ – Red Feb 6 '17 at 1:57
  • $\begingroup$ The hypothesis is that there does NOT exist a non-injective $f:X\to Y.$ $\endgroup$ – DanielWainfleet Feb 6 '17 at 2:14

Your error is that the existence of some injective functions $f\colon X \to Y$ doesn't disprove the claim that "if all functions $f \colon X \to Y$ are injective then $|X| = 1$." Indeed, by assuming $|X| \le |Y|$, there are injective functions from $X$ to $Y$, yet the claim is still true.

Instead of using contradiction, to prove that

$$\text{If every function in $F(X, Y)$ is injective, then $|X| = 1$}$$ it's much easier to prove the contrapositive:

$$\text{If $|X| > 1$, then there exists some function $f \in F(X, Y)$ that's not injective}$$

(we're assuming $X, Y$ are nonempty, so the negation of $|X| = 1$, that is $|X| \neq 1$, amounts to $|X| > 1$).

I think you'll have a much easier time believing this is true, and even proving it. Just pick some generic sets $X, Y$ with $|X| > 1$ and see if you can find a way to build a function that isn't injective. Before long you'll have some ideas about how to prove it for general $X, Y$.

  • 2
    $\begingroup$ Nice explanation! I might remark that one doesn't need contradiction to prove the original implication. Indeed, if every function $X \to Y$ is injective and $X, Y$ are nonempty, then the constant function $f_{y} \colon X \to Y$ which sends every $x \in X$ to some fixed $y \in Y$ is injective. $\endgroup$ – Alex Wertheim Feb 6 '17 at 2:37
  • $\begingroup$ @AlexWertheim Thank you, and your alternative is very slick, it definitely didn't occur to me! $\endgroup$ – pjs36 Feb 6 '17 at 2:42
  • $\begingroup$ @AlexWertheim Can you please explain how the statement about the constant function proves the statement? Because I don't understand intuitively why that would allow us to exclude other injective functions from $F$ where the $|X| \neq1$... even a hint would be helpful thanks!! $\endgroup$ – Red Feb 7 '17 at 7:03
  • 1
    $\begingroup$ @Red: for any $x, x' \in X$, $f_{y}(x) = f_{y}(x') = y$. Since every function from $X$ to $Y$ is injective by hypothesis, $f_{y}$ must be injective, so $f_{y}(x) = f_{y}(x')$ implies $x = x'$. Since $x, x'$ were arbitrary elements of $X$, this shows that all elements of $X$ must be equal, i.e. $X$ has one element. $\endgroup$ – Alex Wertheim Feb 7 '17 at 17:16

If $a,b\in X$ with $a\ne b$ then for any $c\in Y$ the function $X\times \{c\}$ is not injective.

Note: You might call $X\times \{c\}$ the graph of a function. In set theory, a function IS its graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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