4

While I was studying from my Set Theory book, I can across with a theorem that says: let $f:A\to B$ be a function. We'll say that $f$ is reduced from left if for every $g,h$ from set $X$ to $A$ if $f\circ g= f\circ h$ so $g=h$. Also from the right side - We'll say that $f$ is reduced from right if for every $g,h$ from set $B$ to $X$ if $g \circ f= h \circ f$ so $g=h$. I didn't quite got it and I would like to see some examples of functions that shows those two condition.

TTaJTa4
  • 198
  • These are injective and surjective functions respectively. – user113988 Dec 29 '17 at 11:14
  • You wrote the definition of reduced from right identical to that of reduced from left. I changed the 'reduced from right' definition so that they are different again and so that Ittay's answer becomes correct. The small price to pay is that G Sassateli's comment no longer makes sense – Vincent Dec 29 '17 at 11:22

2 Answers2

2

The standard terminology for left reduced is monomorphism (or mono) and for right reduced is epimorphism (or epi). These are the terms used in any category. For sets and functions, a function is a monomorphism iff it is injective, and is an epimorphism iff it is surjective. These are standard results which are quite straightforward to prove, giving a complete characterisation in terms of injectivity and surjectivity.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • 2
    Is this supposed to answer the question? – Jean-Claude Arbaut Dec 29 '17 at 11:21
  • 2
    I think it does answer the question under assumption that the original poster is already familiar with the notions of injective and surjective. If that is indeed the case they can easily construct examples of left and right reduced functions by looking at injective and surjective ones. If the OP has never heard about injective and surjective functions before, perhaps a second answer is needed... – Vincent Dec 29 '17 at 11:24
  • @Jean-ClaudeArbaut yes, it was meant to answer the question. It enables OP to search for the relevant terms which can be found in countless sources, while giving the correct categorical setting and commenting on the highly non-standard use of terminology. – Ittay Weiss Dec 29 '17 at 11:33
  • @GaurangTandon in the context of your question, morphism is another word for function. When you encounter category theory you’ll learn that morphism is an abstract concept that need not be a function. In the general context a morphism can be thought of as an edge in a graph, albeit the graph has a bit of extra structure. – Ittay Weiss Dec 29 '17 at 11:36
  • Yes @Jean-ClaudeArbaut OP now knows exactly what to look for to find as many examples as he/she pleases, as well as furher details and proofs. We can agree to that. – Ittay Weiss Dec 29 '17 at 11:50
2

Okay, I will take the plunge and provide the answer at a lower level.

Recall a function $f $ is called injective or one to one if it never maps two different elements of $A $ to the same element of $B $, i.e. when the following holds:

$$(\forall x,y\in A)(f (x)=f (y) \implies x=y)$$

A function is called surjective or onto if every element of $B $ is the image of some element of $A $, that is:

$$(\forall x\in B)(\exists y\in A) f (y)=x $$

Theorem 1: $f:A\to B $ is reduced from left if and only if $f $ is injective.

Proof: "If" part: Assume $f $ is injective, and suppose $f\circ g=f\circ h $. Let $x \in X $. Because $(f\circ g)(x)=(f\circ h)(x)$, we have $f (g (x))=f (h (x)) $. Using injectivity, it follows that $g (x)=h (x) $. As this is valid for every $x\in X $, it follows that $g=h $.

"Only if" part: Assume $f:A\to B $ is reduced from left. Let $x,y\in A $ such that $f (x)=f (y) $. As $X $, take any nonempty set, and define $f,g $ to be constant maps: $f (z)=x, g (z)=y $ for all $z\in X $. Now, for every $z\in X $ we have $(f\circ g)(z)=f (g (z))=f (x)=f (y)=f (h (z))=(f\circ h)(z) $, thus $f\circ g=f\circ h $. Because $f $ is reduced from left, we have $g=h $. Now, as we took $X $ to be nonempty, pick any $z\in X $, and we have $x=g (z)=h (z)=y $.

Theorem 2: $f:A\to B $ is reduced from right if and only if $f $ is surjective.

Proof: "If" part: Assume $f $ is surjective. Let $g,h:B\to X $ such that $g\circ f=h\circ f $. Take $x\in B $. As $f $ is surjective, there exists $y\in A $ such that $f (y)=x $. Now, we have $g (x)=g (f (y))=(g\circ f)(y)=(h \circ f)(y)=h (f (y))=h (x) $. As this is valid for every $x\in B $, it follows that $g=h $.

"Only if" part: Suppose that $f $ is not surjective, i.e. that there is $x\in B $ such that $f (y)\ne x $ for all $y\in A $. As $X $, take a 2-element set $\{a,b\} $ and define $g (z)=a $ and $h (z)=\begin {cases}a & z\ne x \\ b & z=x \end {cases} $, for all $z\in B $. Now, note $g\ne h $ because $g (x)=a $ and $h (x)=b $. However, $g\circ f=h\circ f $ because $(g\circ f)(y)=g (f (y))=a=h (f (y))=(h\circ f)(y) $ for all $y\in A $ because $f (y) $ is never equal to $x $. It follows that $f $ is not reduced from right.