Show that if $f$ and $g$ are surjective, then $f\cup g$ is surjective.

calculusfunctions

In the text of 'Introduction to Mathematical structures and Proofs', by Larry Garstein; there are below sub-problems as part of Q. 14 in Ex.#3.3, as shown here. Have taken a few questions below:

(d) Show that if $f$ and $g$ are surjective, then $f\cup g$ is surjective.
(e) Show that if $f\cup g$ is injective, then $f$ and $g$ are injective.
(h) Give an example of functions where $f$ and $g$ are injective, but $f\cup g$ is not injective.

I present here my attempt using three approaches:
(i) logic based approach that uses set-representation for domain & range,
(ii) calculus based approach by taking example of functions representing $f,g, f\cup g$.

(d) Show that if $f$ and $g$ are surjective, then $f\cup g$ is surjective.

(i) Both $f,g$ have their co-domain = range; that means that if consider the union of set of members in range (whether finite, or infinite) will have at least one member of the combined domain (set formed by union of domain sets of both $f,g$) that is pre-image of that.
Also, being union of sets, the common elements of the two sets (combined set of domain, or combined set of range) are repeated only once.

(ii) Let there be a polynomial $p_f$ that represents function $f$, & similarly $p_g$. Each polynomial denotes a mapping. Being surjective for any polynomial function means that two criteria are satisfied, as below :
(a) The function is unbounded from above & below, i.e.
$$
\lim_{x\to +\infty} f(x) = +\infty, \text{ and } \lim_{x\to -\infty} f(x) = -\infty
$$
(b) Then, it is an added requirement that the polynomial is an odd order one. For an even order polynomial, for any $y\in \mathbb{R}$, there is $M > 0$ such that
$$
x > M \Rightarrow f(x) > y, \text{ and } x < -M \Rightarrow f(x) < y
$$
Hence, by intermediate value theorem, there is $x_0 \in [-M,M]$ such that $f(x_0) = y$.

So, the union of two surjective functions too is.

(e) Show that if $f\cup g$ is injective, then $f$ and $g$ are injective.

(i) If $f\cup g$ is injective, then there is an underlying assumption: having common elements eliminated from the set of domain, & range of union of the functions $f,g$. Also, each element in the domain of set $f\cup g$ maps to a unique element in the range.

On separating out the respective members of domains of $f,g$ with duplication of common elements, get the two functions still injective.

(ii) For being an injective function, the polynomial representing the function should be monotonic. This can be checked by verifying that the first derivative is not infinity anywhere.

Stuck on this part.

(h) Give an example of functions where $f$ and $g$ are injective, but $f\cup g$ is not injective.

Need help as am unable to think such example. Particularly, am not clear how it is possible theoretically.

Best Answer

For part $d$ and $e$, the task is to prove a general statement and we shouldn't assume structures such as we can we are dealing with real numbers, continuous functions, or polynomials.

$f:A \to B$, $g: C \to D$.

From the assumption, $f \cup g: A \cup C \to B \cup D$.

For part $d$:

If $f$ and $g$ are surjections. Take an element from $y \in B \cup D$. If $y \in B$, we can find a preimage in $A$, hence we can find a preimage in $A \cup C$. If $y \in D$, then we can find a preimage in $C$ and we can find a preimage in $A \cup C$.

Hence $f \cup g$ is a surjection.

For part $e$:

If $f \cup g$ is an injection, let's verify that $f$ is an injection. Suppose it is not, then we can find $x,y \in A$, $x \ne y$ such that $f(x)=f(y)$. That is we have found $x,y \in A \cup C$, $x \ne y$ such that $f(x)=f(y)$, violating the injectivity of $f \cup g$.

For part $h$:

Just let $B=D=\{1\}$, $A=\{1\}$, $C=\{2\}$.

Motivation

When I go hiking, I want to be able to retrace my steps and get back to my starting point.

When I go to a store, I want to be able to return home.

When I swim out from the shore, I want to be able to get back to the shore.

Going somewhere and then coming back to where one started is important in life.

And it is important in mathematics.

And it is important in functional programming.

Domain, Codomain, and Inverse

If a function maps a set of elements (the domain) to a set of values (the codomain) then it is often useful to have another function that can take the elements in the codomain and send them back to their original domain values. The latter is called the inverse function.

In order for a function to have an inverse function, it must possess two important properties, which I explain now.

The Injective Property

Let the domain be the set of days of the week. In Haskell one can create the set using a data type definition such as this:

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

Let the codomain be the set of breakfasts. One can create this set using a data type definition such as this:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

Now I create a function that maps each element of the domain to a value in the codomain.

Here is one such function. The first line is the function signature and the following lines is the function definition:

f  ::  Day  ->  Breakfast
f  Monday       =  Eggs
f  Tuesday      =  Cereal
f  Wednesday    =  Toast
f  Thursday     =  Oatmeal
f  Friday       =  Pastry
f  Saturday     =  Ham
f  Sunday       =  Grits

An important thing to observe about the function is that no two elements in the domain map to the same codomain value. This function is called an injective function.

[Definition] An injective function is one such that no two elements in the domain map to the same value in the codomain.

Contrast with the following function, where two elements from the domain -- Monday and Tuesday -- both map to the same codomain value -- Eggs.

g  ::  Day  ->  Breakfast
g  Monday       =  Eggs
g  Tuesday      =  Eggs
g  Wednesday    =  Toast
g  Thursday     =  Oatmeal
g  Friday       =  Pastry
g  Saturday     =  Ham
g Sunday        =  Grits

The function is not injective.

Can you see a problem with creating an inverse function for g :: Day -> Breakfast?

Specifically, what would an inverse function do with Eggs? Map it to Monday? Or map it to Tuesday? That is a problem.

[Important] If a function does not have the injective property then it cannot have an inverse function.

In other words, I can't find my way back home.

The Surjective Property

There is a second property that a function must possess in order for it to have an inverse function. I explain that next.

Did you notice in the codomain that there are 8 values:

data Breakfast = Eggs | Cereal | Toast | Oatmeal | Pastry | Ham | Grits | Sausage

So there are more values in the codomain than in the domain.

In function f :: Day -> Breakfast there is no domain element that mapped to the codomain value Sausage.

So what would an inverse function do with Sausage? Map it to Monday? Tuesday? What?

The function is not surjective.

[Definition] A surjective function is one such that for each element in the codomain there is at least one element in the domain that maps to it.

[Important] If a function does not have the surjective property, then it does not have an inverse function.

[Important] In order for a function to have an inverse function, it must be both injective and surjective.

Injective + Surjective = Bijective

One final piece of terminology: a function that is both injective and surjective is said to be bijective. So, in order for a function to have an inverse function, it must be bijective.

Recap

If you want to be able to come back home after your function has taken you somewhere, then design your function to possess the properties of injectivity and surjectivity.

[Math] Give the formula for a function with natural domain $(\infty ,0]\cup [10,\infty)$ and with range $(-\infty, -1]$

We will change the problem a bit, to natural domain $(-\infty,-5]\cup [5,\infty)$. If we solve that problem we can shift to get what we want. We are doing this because symmetry is nice.

And although I have nothing really against $5$, but $1$ is a nicer number. So we will deal with natural domain $(-\infty,-1]\cup [1,\infty)$. You can do the suitable scaling.

So we want to run into trouble in $(-1,1)$. The following sounds good: $$\sqrt{1-\frac{1}{x^2}}.$$

But the range is $[0,\infty)$. That part is easy to fix: switch sign, and subtract $1$.