# Elementary Set Theory Question

I am working on the following question.

Let $X$ be a nonempty set and consider a map $f:X\to Y$. Prove that the following are equivalent:

(a) $f$ is injective;

(b) there exists $g:Y\to X$ such that $g∘f=1_{X}$ where $1_{X}:X\to X$ is the identity map;

(c) for any set $Z$ and any maps $h_{1},h_{2}:Z\to X$, the equation $f∘h_{1}=f∘h_{2}$ implies that $h_{1}=h_{2}$.

(*I would like to add here that the "$1$" from each "$1_{X}$" is supposed to be written with the Math Blackboard font - I'm not sure how to do that*)

My issue at the moment arises from being unable to understand (some of) the notation and ideas. I will attempt to describe in my own terms what I believe to understand. I apologize for the terribly imprecise language. You will see why I am not ready to prove anything yet.

(a) That the function $f$ is injective means that it never maps distinct elements of its domain to the same element of its codomain. So every element from the set $X$ maps to a unique element in the set $Y$. And vice versa. A function of the form $f(x)=ax+c$ would be injective (and also a bijection) while a function of the form $f(x)=ax^{2}+bx+c$ would not be (assuming no restrictions on the domain).

(b) This part states that there exists a function $g$ that maps the set $Y$ to the set $X$. The rest I am not sure of. The composite function $g∘f$ equals the identity map $1_{X}$. Does the identity map simply map X back onto X? For instance if $X=\left \{ 1,2 \right \}$, does $1_{X}$ map $1 \to 1$ and $2 \to 2$? So this part would mean, informally, that if you take an element from $Y$, replace it with its corresponding element from $X$, and then map it back to the same element from $X$, you get the identity map. Essentially each element from $Y$ maps to one element from $X$ and you can go back and forth between the sets.

(c) Now the final part. There is a set $Z$ and two maps $h_{1}$, and $h_{2}$, both of which map the set $Z$ to the set $X$. Furthermore (and I dont know if this notation is acceptable),

$$f:(h_{1}:Z \to X) \to Y=f:(h_{2}:Z \to X) \to Y.$$

I'm not seeing why this shows that $f$ is injective.

I apologize again for this clutter. This is my first real exposure to set theory for my first year Calculus course and our textbook (Stewart) does not cover this. Writing this out has actually helped me to get a better grasp of what I am trying to prove, though I doubt it looks that way. Any help would be appreciated.

• If $X$ is a set, the identity $1_X$ on $X$ is just the function $x \mapsto x$ that maps any element to itself. So $g \circ f = 1_X$ is just a concise way of writing $\forall x \in X, \ g(f(x)) = x$. – Joel Cohen Mar 1 '12 at 1:19
• Thank you very much. Is it alright if I ask a related question right here in the comments? If so, what does $f:X \to X \setminus\left \{ x_{0} \right \}$ mean? – Ralph_Glasser Mar 1 '12 at 1:30
• There's some subtlety required in $(b)$. The function $g$ need not be 1-1. However, if $g$'s domain is restricted to $f[X]$, then $g$ is 1-1 and the inverse of $f$. – Patrick Mar 1 '12 at 1:31
• $X\setminus A$ is the set of all things that are members of $X$ but not of $A$, so $X\setminus\{x_0\}$ is simply the set of all members of $X$ except $x_0$. To say that $f:X\to X\setminus\{x_0\}$ is to say that $f$ is a function whose domain is $X$ and whose range is a subset of $X\setminus\{x_0\}$; in other words, $f$ maps $X$ into $X$, but without ever ‘hitting’ $x_0$. – Brian M. Scott Mar 1 '12 at 1:56
• "So every element from the set $X$ is mapped to a unique element in the set $Y$. And vice versa." Unfortunately, this is not an accurate paraphrase of an injective function. For any function, every element in the domain is mapped to a unique element of the codomain; this is one of the defining properties of being a function. And "vice versa" would mean "every element of $Y$ is mapped to a unique element of $X$" (false, the function goes from $X$ to $Y$), or perhaps "every element of $Y$ comes from a unique element of $X$" (which is also incorrect, if $f$ is not onto as well). – Arturo Magidin Mar 1 '12 at 4:44

To show that three statements are equivalent one needs to assume the first, show that the second follow; assume the second and show that the third follow; and lastly assume the third and show that the first follow. (Of course one can mix the order up, or show equivalence of pairs instead - very much of the order depends on the formulation of the problem).

1. If so suppose that $f:X\to Y$ is injective. Let $x_0\in X$ be a fixed element (since $X$ is non-empty we have such element) we can define $g:Y\to X$ as $$g(y)=\begin{cases} f^{-1}(x) & y\in Rng(f)\\ x_0 &\text{otherwise}\end{cases}$$

This is indeed a good definition since $f$ is injective $f^{-1}$ defined on its range. Now consider $g\circ f:X\to X$, it takes $x$ to $g(f(x))$ however $f(x)\in Rng(f)$ so $g(f(x))=f^{-1}(f(x))=x$ as wanted.

2. Suppose that $f:X\to Y$ is such that $g$ exists as wanted. Let $h_1,h_2$ be maps as specified, and $f\circ h_1=f\circ h_2$. Consider $g\circ (f\circ h_i):Z\to X$ since $\circ$ is associative this is the same as $(g\circ f)\circ h_i$, but by our assumption this is the same as $h_i$. So we have that $h_1=h_2$ as wanted.

3. Lastly, suppose the third condition, and assume by contradiction that $f$ is not injective. It means that for some $a,b\in X$ we have $f(a)=f(b)$ while $a\neq b$. Define $Z=\{0,1\}$ and $h_1(n)=a$ for all $n\in Z$ while $h_2(n)=b$ for all $n\in Z$. Now we have that $f\circ h_1=f\circ h_2$ but $h_1$ is clearly not equal $h_2$ - contradiction as wanted.

The main trick is indeed in the last implication $(3)\Rightarrow (1)$ but you need to exploit the fact that the assumption is on any space $Z$, and so we are free to generate counterexamples if we want to.

• Thank you very much. Unfortunately I am not familiar with $Rng(f)$ – Ralph_Glasser Mar 1 '12 at 7:05
• @Ralph: the range of $f$ is sometimes called the image of $f$. It is the set $\{f(x)\mid x\in X\}$. – Asaf Karagila Mar 1 '12 at 8:41

(a) For the moment, forget prettymuch everything that you've ever learned from the calculus sequence (or high school algebra, etc). $X$ and $Y$ are sets. That's all that we know. Sure, they could be sets of numbers. They could also be the set of your great-grandmother's cake recipies or the set of cars registered in Massachusetts between January 3, 1982 and September 28, 1994. They're just sets.

So, if $f:X\rightarrow Y$, then what it means for $f$ to be injective is that for all $x_1,x_2\in X$ if $f(x_1)=f(x_2)$, then $x_1=x_2$.

(b) Yes, given a set $X$, the identity function $1_X:X\rightarrow X$ is defined by $1_X(x)=x$ for all $x\in X$.

(c) No, I'm not sure what you mean by your notation. The condition says that for all functions $h_1:Z\rightarrow X$ and $h_2:Z\rightarrow X$, $f\circ h_1=f\circ h_2$ implies $h_1=h_2$.

Now, here are some hints. We'll show that (a) implies (b), (b) implies (c), and (c) implies (a).

For (a)$\Rightarrow$(b), assume that $f$ is injective. So, for all $x_1,x_2\in X$, if $f(x_1)=f(x_2)$, then $x_1=x_2$. We now want to show that (b) holds. So, we need to find a function $g:Y\rightarrow X$ such that $g\circ f=1_X$--ie $g(f(x))=x$ for all $x\in X$.

So, pick some $y\in Y$. If $y=f(x)$--ie if $y$ is in the image of $f$--then what element of $X$ should we pick for $g(y)$? What if $y$ isn't in the image of $f$ (ie $y\not=f(x)$ for any $x\in X$)? Remember, we want to pick $g$ such that $g(f(x))=x$ for all $x\in X$.

For (b)$\Rightarrow$(c), we now assume that there exists a function $g:Y\rightarrow X$ such that $g\circ f = 1_X$. Choose two arbitrary functions $h_1,h_2:Z\rightarrow X$ such that $f\circ h_1=f\circ h_2$. We need to show that $h_1=h_2$ (ie $h_1(x)=h_2(x)$ for all $x\in X$).

Hmmmm, so take a look at the equation $f\circ h_1=f\circ h_2$. Is there something that we can do to both sides that will allow us to conclude that $h_1=h_2$? As a further hint, function composition is associative.

For (c)$\Rightarrow$(a), suppose that for any set $Z$ and for any two functions $h_1,h_2:Z\rightarrow X$, whenever $f\circ h_1=f\circ h_2$, then $h_1=h_2$.

We now want to show that $f$ is injective. So, suppose that $f(x_1)=f(x_2)$ for some $x_1,x_2\in X$. We need to show that $x_1=x_2$. You know, I'll bet we can get away with picking $Z=X$...can you think of a pair of functions $h_1$ and $h_2$ from $X$ to $X$ such that $f\circ h_1=f\circ h_2$ and that also have $h_1(x_1)=x_1$ and $h_2(x_1)=x_2$? If so, then we can conclude that $x_1=x_2$ (why?).