3.5 Functions[1YR]
The definition of function can be obtained from set theory in this way.
[1Y6] Given two sets \(A,B\), a function \(f:A→ B\) is a triple
(where \(A\) is said domain and \(B\) codomain) and \(F\) is a relation \(F⊆ A× B\) such that
i.e. it enjoys the properties of being functional and total (defined in 46).
Being the element \(y\) unique, we can write \(y=f(x)\) to say that \(y\) is the only element in relation \(xFy\) with \(x\).
[16G] Given nonempty sets \(I,A\), a sequence with indexes in \(I\) and taking values in \(A\) is a function \(a:I→ A\); this though is usually written by the notation \(( a_ n )_{ n ∈ I}\) . To denote the codomain, the notation \( ( a_ n )_{ n ∈ I}⊆ A\) is also employed. In this text, in most cases, we will have that \(I=ℕ\), and in this case we will simply write \((a_{n})\).
In practice, the definition of function is always written as \(f:A→ B\); for this reason the graph is defined as
[08X]Let \(A\) be a non-empty set, let \(f:A→\{ 0,1\} \) and \(g:A→\{ 1\} \) both given by \(f(x)=g(x)=1\) for each \(x∈ A\).
Let \(F,G\) respectively be the graphs: note that \(F=G\) (!) Will we say that \(f=g\) or not? We choose “not”, otherwise the concept of ”surjective” would not make sense.
For this reason in the definition we decided that the function is the triple ”domain”, ”codomain”, ”relation”.
- E75
[1WQ]Show that the composition of two injective functions is an injective function.
- E75
[1WR]Show that the composition of two surjective functions is a surjective function.
- E75
[1WS]Let \(f:ℕ→ℕ\) be an assigned function and \(I\) its image, prove that \(A⊆ ℕ\) exists such that \(f|_{A}\) is injective and \(f(A)=I\). (Hint it may be useful to know that the usual order of \(ℕ\) is a well-order cf 103 and 146).
Hidden solution: [UNACCESSIBLE UUID ’1WT’]
Note: The result is true for any function \(f:A→ B\), but the proof requires the axiom of choice.
- E75
[08Y](Proposed on 2022-12) Let \(I,J⊆ ℝ\) and let \(f:I→ J\) be given by \(f(x)=\sin (x)\). By choosing \(I=ℝ\) or \(I=[0,𝜋/2]\) or \(I=[-𝜋/2,𝜋/2]\), and choosing \(J=ℝ\) or \(J=[-1,1]\), say for which choices \(f\) is surjective, and for which it is injective.
(This exercise is to make you ponder about the difference between ”formula” and ”function.”.)
- E75
[1X3] Let \(A,B⊆ ℝ\) and let \(f:A→ B\) be defined by the formula \(f(x)=x^ 2\); tell if, for the following choices of \(A,B\), the function \(f\) is injective and/or surjective.
\(A=ℝ,B=ℝ\)
\(A=ℝ,B=[0,∞)\)
\(A=[0,∞),B=ℝ\)
\(A=[0,∞),B=[0,∞)\)
If the function is bijective, what is its inverse commonly called?
(This exercise is to make you ponder about the difference between ”formula” and ”function.”
- E75
[1X4]Given \(f,g:ℕ → ℕ\) defined by \(f(n)=n^ 2-1\) and \(g(n)=(n+1)^ 2\), write explicitly \(f◦ g\) and \(g◦ f\), say if they coincide or are different functions.
- E75
[1X5]Find an example of \(f,g:ℕ → ℕ\) such that \(f◦ g≡ g◦ f\), but neither \(f\) nor \(g\) are bijective.
- E75
[1X6]Let \(f:ℝ→ℝ\) be bijective, and \(F⊆ ℝ^ 2\) its graph; let \(f^{-1}\) be the inverse of \(f\) and let \(G\) be its graph; show that \(G\) is the symmetric of \(F\) with respect to the bisector of the first and third quadrants.
- E75
[091] Let \(D,C\) be non-empty sets and \(f:D→ C\) a function. Let \(I\) a non-empty family of indexes, \(B_ i⊆ C\) for \(i∈ I\). Given \(B⊆ C\) remember that the counterimage of \(B\) is
\[ f^{-1}(B){\stackrel{.}{=}}\{ x∈ D, f(x) ∈ B\} ~ ~ , \]Given \(B⊆ C\) we write \(B^ c=\{ x∈ C,x∉ B\} \) to denote the complement. Show these counterimage properties.
\begin{align} f^{-1}\bigl(⋃_{i∈ I} B_ i \bigr) & = ⋃_{i∈ I} f^{-1}\bigl(B_ i \bigr)\\ f^{-1}\bigl(⋂_{i∈ I} B_ i \bigr) & = ⋂_{i∈ I} f^{-1}\bigl(B_ i \bigr)\\ f^{-1}\bigl( B^ c \bigr) & = f^{-1}\bigl(B \bigr)^ c~ ~ . \end{align}- E75
[092] Let \(D,C\) be non-empty sets and \(f:D→ C\) a function. Let \(I\) be a non-empty family of indexes, \(A_ i⊆ D\), for \(i∈ I\). Given \(A⊆ D\) remember that the image of \(A\) is the subset \(f(A)\) of \(D\) given by
\[ f(A){\stackrel{.}{=}}\{ f(x), x ∈ A\} ~ ~ . \]Show these image properties.
\begin{eqnarray} f\bigl(⋃_{i∈ I} A_ i \bigr) & =& ⋃_{i∈ I} f\bigl(A_ i \bigr) \nonumber \\ f\bigl(⋂_{i∈ I} A_ i \bigr) & ⊆ & ⋂_{i∈ I} f\bigl(A_ i \bigr) \nonumber ~ ~ . \end{eqnarray}Show that the function is injective if and only if
\begin{equation} f\bigl( A_ 1∩ A_ 2 \bigr) = f\bigl(A_ 1 \bigr) ∩ f\bigl(A_ 2 \bigr) \end{equation}79is an equality for every choice of \(A_ 1,A_ 2⊆ D\).
- E75
[250]Let \(D,C\) be non-empty sets and \(f:D\to C\) a function. Given \(U\subseteq C\) show that
\[ f(f^{-1}(U)) \subseteq U~ ; \]if \(f\) is surjective show that they are equal; find an example where they are different.
- E75
[251]Let \(D,C\) be non-empty sets and \(f:D→ C\) a function. Given \(A⊆ D\) show that
\[ f^{-1}(f(A)) ⊇ A~ ; \]if \(f\) is injective show that they are equal; find an example where they are different.
- E75
[2BX]Let \(A,B\) be non-empty sets.
Suppose that \(f:A→ B\) is an injective function: there exists a surjective function \(g:B→ A\) such that \(g◦ f=\text{Id}_ A\) (the identity function). (Such \(g\) is a left inverse of \(g\)).
Suppose that \(g:B→ A\) is a surjective function: there exists a injective function \(f:A→ B\) such that \(g◦ f=\text{Id}_ A\). (Such \(f\) is a right inverse of \(g\)).
The proof of the second statement requires the Axiom of Choice (see 2).
Vice versa.
If \(f:A→ B\) has a left inverse then it is an injective function.
If \(g:B→ A\) has a right inverse, then it is a surjective function.
Hidden solution: [UNACCESSIBLE UUID ’2BY’]
- E75
[093] Let \(A\) be a set and let \(g:A→ A\) be injective. We define the relation \(x∼ y\) which is true when an \(n≥ 0\) exists such that \(x=g^ n (y)\) or \(x= g^ n(y)\); where
\[ g^ n=\overbrace{g◦ \cdots ◦ g}^ n \]is the \(n\)-th iterate of the composition. (We decide that \(g^ 0\) is identity). Show that \(x∼ y\) is an equivalence relation. Study equivalence classes. Let \(U=⋂_{n=1}^∞ g^ n(A)\) be the intersection of repeated images. Show that each class is entirely contained in \(U\) or is external to it.
Hidden solution: [UNACCESSIBLE UUID ’094’]
- E75
[095] Show that there is a function \(f:ℝ→ℝ\) such that \(f(f(x))=-x\). Is there a continuous function for which \(f(f(x))=-x\)? (Hint: show that for every such \(f\) you have \(f^{-1}(\{ 0\} )=\{ 0\} \)). Hidden solution: [UNACCESSIBLE UUID ’096’]
- E75
[097]Show that there exists a function \(f:[0,1]→[0,1]\) such that \(f(f(x))=\sin (x)\). Is there a continuous function? Hidden solution: [UNACCESSIBLE UUID ’098’]
- E75
[01P] (Solved on 2022-11-15) Let \(D,C\) be non-empty sets. A partial function from \(D\) in \(C\) is a function \(𝜑:B→ C\) where \(B⊆ D\). (The definition of ”function” is in 73).
It can be convenient to think of the partial function as a relation \(Φ⊆ D× C\) such that, if \((x,a),(x,b)∈ Φ\) then \(a=b\) (see 46). The two notions are equivalent in this sense: given \(Φ\) we build the domain of \(𝜑\), which we will call \(B\), with the projection of \(Φ\) on the first factor i.e. \(B=\{ x∈ D : ∃ c∈ C, (x,c)∈Φ\} \), and we define \(𝜑(x)=c\) as the only element \(c∈ C\) such that \((x,c)∈Φ\); vice versa \(Φ\) is the graph of \(𝜑\).
Partial functions, seen as relations \(Φ\), are of course sorted by inclusion; equivalently \(𝜑≤ 𝜓\) if \(𝜑:B→ C\) and \(𝜓:E→ C\) and \(B⊆ E⊆ D\) and \(𝜑=𝜓_{|B}\).
Let now \(U\) be a chain, i.e. family of partial functions that is totally ordered according to the order previously given; seeing each partial function as a relation, let \(Ψ\) be the union of all relations in \(U\); show that \(Ψ\) is the graph of a partial function \(𝜓:E→ C\), whose domain \(E\) is the union of all the domains of the functions in \(U\), and whose image \(I\) is the union of all images of functions in \(U\)
If moreover all functions in \(U\) are injective, show that \(𝜓\) is injective.
Hidden solution: [UNACCESSIBLE UUID ’01Q’]
[UNACCESSIBLE UUID ’09B’] [UNACCESSIBLE UUID ’09C’] [UNACCESSIBLE UUID ’09D’]