The Open Logic Text — accessible offline edition

Functions — Source and provenance

Functions

Source and provenance

These are all 7 files in the frozen Functions source boundary, shown line by line and copied byte-for-byte for download. The reading views bind all 414 formula occurrences to their exact source locations.

content/sets-functions-relations/functions/composition.tex

67 lines; SHA-256 091c7ab9e4d0517b2a62f4ecf10e4eb75f0f83e31e1bbd9c365c4b751b981fee. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  3. % Section: composition
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{fun}{cmp}
  10. \olsection{Composition of Functions}
  12. \begin{explain}
  13. \oliflabeldef{sfr:fun:inv:sec}{We saw in \olref[inv]{sec} that the
  14. inverse~$f^{-1}$ of !!a{bijection}~$f$ is itself a function. Another
  15. operation on functions is composition: w}{W}e can define a new
  16. function by composing two functions, $f$ and~$g$, i.e., by first
  17. applying $f$ and then~$g$. Of course, this is only possible if the
  18. ranges and domains match, i.e., the range of~$f$ must be a subset of
  19. the domain of~$g$. \oliflabeldef{sfr:rel:ops:sec}{This operation on
  20. functions is the analogue of the operation of relative product on
  21. relations from \olref[rel][ops]{sec}.}{}
  23. A diagram might help to explain the idea of composition. In
  24. \olref{fig:composition}, we depict two functions $f \colon A \to B$
  25. and $g \colon B \to C$ and their composition~$(\comp{f}{g})$. The
  26. function $(\comp{f}{g}) \colon A \to C$ pairs each !!{element} of~$A$
  27. with !!a{element} of~$C$. We specify which !!{element} of~$C$
  28. !!a{element} of $A$ is paired with as follows: given an input $x \in
  29. A$, first apply the function $f$ to~$x$, which will output some $f(x)
  30. = y \in B$, then apply the function $g$ to~$y$, which will output some
  31. $g(f(x)) = g(y) = z \in C$.
  32. \begin{figure}
  33. \olasset[2\olphotowidth]{assets/diagrams/composition.tikz}
  34. \caption{The composition $g \circ f$ of two functions $f$ and~$g$.}
  35. \ollabel{fig:composition}
  36. \end{figure}
  37. \end{explain}
  39. \begin{defn}[Composition]
  40. Let $f\colon A \to B$ and $g\colon B \to C$ be functions. The
  41. \emph{composition} of $f$ with~$g$ is $\comp{f}{g} \colon A \to C$,
  42. where $(\comp{f}{g})(x) = g(f(x))$.
  43. \end{defn}
  45. \begin{ex}
  46. Consider the functions $f(x) = x + 1$, and $g(x) = 2x$. Since
  47. $(\comp{f}{g})(x) = g(f(x))$, for each input~$x$ you must first take
  48. its successor, then multiply the result by two. So their composition
  49. is given by $(\comp{f}{g})(x) = 2(x+1)$.
  50. \end{ex}
  52. \begin{prob}
  53. Show that if $f \colon A \to B$ and $g \colon B \to C$ are both
  54. !!{injective}, then $\comp{f}{g}\colon A \to C$ is !!{injective}.
  55. \end{prob}
  57. \begin{prob}
  58. Show that if $f \colon A \to B$ and $g \colon B \to C$ are both
  59. !!{surjective}, then $\comp{f}{g}\colon A \to C$ is !!{surjective}.
  60. \end{prob}
  62. \begin{prob}
  63. Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that the graph
  64. of $\comp{f}{g}$ is $R_f \mid R_g$.
  65. \end{prob}
  67. \end{document}

content/sets-functions-relations/functions/function-basics.tex

140 lines; SHA-256 f01a58d84a175f42d8c233ef0e7d41c23d406b54e8f11475c14514b64eca3dc7. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  3. % Section: basics
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{fun}{bas}
  10. \olsection{Basics}
  12. \begin{explain}
  13. A \emph{function} is a map which sends each !!{element} of a given set
  14. to a specific !!{element} in some (other) given set. For instance, the
  15. operation of adding~$1$ defines a function: each number~$n$ is mapped
  16. to a unique number~$n+1$.
  18. More generally, functions may take pairs, triples, etc., as inputs and
  19. return some kind of output. Many functions are familiar to us from
  20. basic arithmetic. For instance, addition and multiplication are
  21. functions. They take in two numbers and return a third.
  23. In this mathematical, abstract sense, a function is a \emph{black
  24. box}: what matters is only what output is paired with what input, not
  25. the method for calculating the output.
  26. \end{explain}
  28. \begin{defn}[Function]
  29. A \emph{function} $f \colon A \to B$ is a mapping of each !!{element}
  30. of~$A$ to an !!{element} of~$B$.
  32. We call $A$ the \emph{domain} of~$f$ and $B$ the \emph{codomain}
  33. of~$f$. The !!{element}s of~$A$ are called inputs or \emph{arguments}
  34. of~$f$, and the !!{element} of~$B$ that is paired with an argument~$x$
  35. by~$f$ is called the \emph{value of~$f$} for argument~$x$,
  36. written~$f(x)$.
  38. The \emph{range} $\ran{f}$ of~$f$ is the subset of the codomain
  39. consisting of the values of~$f$ for some argument; $\ran{f} =
  40. \Setabs{f(x)}{x \in A}$.
  41. \end{defn}
  43. The diagram in \olref{fig:function} may help to think about functions. The ellipse
  44. on the left represents the function's \emph{domain}; the ellipse on
  45. the right represents the function's \emph{codomain}; and an arrow
  46. points from an \emph{argument} in the domain to the corresponding
  47. \emph{value} in the codomain.
  49. \begin{figure}
  50. \olasset{assets/diagrams/function.tikz}
  51. \caption{A function is a mapping of each !!{element} of one set to
  52. !!a{element} of another. An arrow points from an argument in the
  53. domain to the corresponding value in the codomain.}
  54. \ollabel{fig:function}
  55. \end{figure}
  57. \begin{ex}
  58. Multiplication takes pairs of natural numbers as inputs and maps them
  59. to natural numbers as outputs, so goes from $\Nat \times \Nat$ (the
  60. domain) to $\Nat$ (the codomain). As it turns out, the range is also
  61. $\Nat$, since every $n \in \Nat$ is $n \times 1$.
  62. \end{ex}
  64. \begin{ex}
  65. Multiplication is a function because it pairs each input---each pair
  66. of natural numbers---with a single output: $\times \colon \Nat^2 \to
  67. \Nat$. By contrast, mapping a natural number~$n$ to a real~$x$ such
  68. that $x^2 = n$ is not functional, since each positive integer~$n$ has two
  69. square roots: $\sqrt{n}$ and~$-\sqrt{n}$. We can make it functional by
  70. only returning the positive square root: $\sqrt{\phantom{X}} \colon
  71. \Nat \to \Real$.
  72. \end{ex}
  74. \begin{ex}
  75. The relation that pairs each student in a class with their final grade
  76. is a function---no student can get two different final grades in the
  77. same class. The relation that pairs each student in a class with their
  78. parents is not a function: students can have zero, or two, or more
  79. parents.
  80. \end{ex}
  82. \begin{explain}
  83. We can define functions by specifying in some precise way what the
  84. value of the function is for every possible argument. Different ways of
  85. doing this are by giving a formula, describing a method for computing
  86. the value, or listing the values for each argument. However functions
  87. are defined, we must make sure that for each argument we specify one,
  88. and only one, value.
  89. \end{explain}
  92. \begin{ex}
  93. Let $f \colon \Nat \to \Nat$ be defined such that $f(x) = x+1$. This
  94. is a definition that specifies $f$ as a function which takes in
  95. natural numbers and outputs natural numbers. It tells us that, given a
  96. natural number~$x$, $f$ will output its successor~$x+1$.
  97. In this case, the codomain $\Nat$ is not the range of~$f$, since the
  98. natural number~$0$ is not the successor of any natural number. The
  99. range of~$f$ is the set of all positive integers, $\Int^{+}$.
  100. \end{ex}
  102. \begin{ex}\ollabel{examplefunext}
  103. Let $g \colon \Nat \to \Nat$ be defined such that $g(x) = x+2-1$. This
  104. tells us that $g$ is a function which takes in natural numbers and
  105. outputs natural numbers. Given a natural number~$n$, $g$ will output
  106. the predecessor of the successor of the successor of~$x$, i.e.,
  107. $x+1$.
  108. \end{ex}
  110. \begin{explain}
  111. We just considered two functions, $f$ and $g$, with different
  112. \emph{definitions}. However, these are the \emph{same function}. After
  113. all, for any natural number~$n$, we have that $f(n) = n+1 = n+2-1 =
  114. g(n)$. Otherwise put: our definitions for $f$ and~$g$ specify the
  115. same mapping by means of different equations. Implicitly, then, we are
  116. relying upon a principle of extensionality for functions,
  117. \[
  118. \text{if }\forall x\, f(x) = g(x)\text{, then }f = g
  119. \]
  120. provided that $f$ and~$g$ share the same domain and codomain.
  121. \end{explain}
  123. \begin{ex}
  124. We can also define functions by cases. For instance, we could define
  125. $h \colon \Nat \to \Nat$ by
  126. \[
  127. h(x) =
  128. \begin{cases}
  129. \frac{x}{2} & \text{if $x$ is even} \\
  130. \frac{x+1}{2} & \text{if $x$ is odd.}
  131. \end{cases}
  132. \]
  133. Since every natural number is either even or odd, the output of this
  134. function will always be a natural number. Just remember that if you
  135. define a function by cases, every possible input must fall into
  136. exactly one case. In some cases, this will require a proof that the
  137. cases are exhaustive and exclusive.
  138. \end{ex}
  140. \end{document}

content/sets-functions-relations/functions/function-kinds.tex

118 lines; SHA-256 6dfe2a70579f8e3521d8e2286e2360dd58a19fbeda9718b62342105388ab4f93. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  3. % Section: kinds
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{fun}{kin}
  10. \olsection{Kinds of Functions}
  12. \begin{explain}
  13. It will be useful to introduce a kind of taxonomy for some of the
  14. kinds of functions which we encounter most frequently.
  16. To start, we might want to consider functions which have the property
  17. that every member of the codomain is a value of the function. Such
  18. functions are called !!{surjective}, and can be pictured as in
  19. \olref{fig:surjective}.
  21. \begin{figure}
  22. \olasset{assets/diagrams/surjective.tikz}
  23. \caption{!!^a{surjective} function has every !!{element} of the
  24. codomain as a value.}
  25. \ollabel{fig:surjective}
  26. \end{figure}
  27. \end{explain}
  29. \begin{defn}[!!^{surjective} function]
  30. A function $f \colon A \rightarrow B$ is \emph{!!{surjective}} iff $B$
  31. is also the range of~$f$, i.e., for every $y \in B$ there is at least
  32. one $x \in A$ such that~$f(x) = y$, or in symbols:
  33. \[
  34. (\forall y \in B)(\exists x \in A)f(x) = y.
  35. \]
  36. We call such a function !!a{surjection} from $A$ to $B$.
  37. \end{defn}
  39. \begin{explain}
  40. If you want to show that $f$ is !!a{surjection}, then you need to show
  41. that every object in $f$'s codomain is the value of $f(x)$ for some
  42. input $x$.
  44. Note that any function \emph{induces} !!a{surjection}. After all,
  45. given a function $f \colon A \to B$, let $f' \colon A \to \ran{f}$ be
  46. defined by $f'(x) = f(x)$. Since $\ran{f}$ is \emph{defined} as
  47. $\Setabs{f(x) \in B}{x \in A}$, this function $f'$ is guaranteed to be
  48. !!a{surjection}
  49. \end{explain}
  51. \begin{explain}
  52. Now, any function maps each possible input to a unique output. But
  53. there are also functions which never map different inputs to the same
  54. outputs. Such functions are called !!{injective}, and can be pictured
  55. as in \olref{fig:injective}.
  56. \begin{figure}
  57. \olasset{assets/diagrams/injective.tikz}
  58. \caption{!!^a{injective} function never maps two different
  59. arguments to the same value.}
  60. \ollabel{fig:injective}
  61. \end{figure}
  62. \end{explain}
  64. \begin{defn}[!!^{injective} function]
  65. A function $f \colon A \rightarrow B$ is \emph{!!{injective}} iff for
  66. each $y \in B$ there is at most one $x \in A$ such that~$f(x) = y$. We
  67. call such a function !!a{injection} from $A$ to~$B$.
  68. \end{defn}
  70. \begin{explain}
  71. If you want to show that $f$ is !!a{injection}, you need to show that
  72. for any !!{element}s $x$ and $y$ of $f$'s domain, if $f(x)=f(y)$, then
  73. $x=y$.
  74. \end{explain}
  76. \begin{ex}
  77. The constant function $f\colon \Nat \to \Nat$ given by $f(x) = 1$ is
  78. neither !!{injective}, nor !!{surjective}.
  80. The identity function $f\colon \Nat \to \Nat$ given by $f(x) = x$ is
  81. both !!{injective} and !!{surjective}.
  83. The successor function $f \colon \Nat \to \Nat$ given by $f(x) = x+1$
  84. is !!{injective} but not !!{surjective}.
  86. The function $f \colon \Nat \to \Nat$ defined by:
  87. \[
  88. f(x) =
  89. \begin{cases}
  90. \frac{x}{2} & \text{if $x$ is even} \\
  91. \frac{x+1}{2} & \text{if $x$ is odd.}
  92. \end{cases}
  93. \]
  94. is !!{surjective}, but not !!{injective}.
  95. \end{ex}
  97. \begin{explain}
  98. Often enough, we want to consider functions which are both
  99. !!{injective} and !!{surjective}. We call such functions
  100. !!{bijective}. They look like the function pictured in
  101. \olref{fig:bijective}. !!^{bijection}s are also sometimes called
  102. \emph{one-to-one correspondences}, since they uniquely pair elements
  103. of the codomain with elements of the domain.
  104. \begin{figure}
  105. \olasset{assets/diagrams/bijective.tikz}
  106. \caption{!!^a{bijective} function uniquely pairs the elements of the
  107. codomain with those of the domain.}
  108. \ollabel{fig:bijective}
  109. \end{figure}
  110. \end{explain}
  112. \begin{defn}[!!^{bijection}]
  113. A function $f \colon A \to B$ is \emph{!!{bijective}} iff it is both
  114. !!{surjective} and !!{injective}. We call such a function
  115. !!a{bijection} from $A$ to~$B$ (or between $A$ and~$B$).
  116. \end{defn}
  118. \end{document}

content/sets-functions-relations/functions/functions-relations.tex

103 lines; SHA-256 0205f7168e0679f513e7c95ea7124ce364bce36f9e04f06d519e90f6a5480a5c. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  3. % Section: functions-relations
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  8. \begin{document}
  10. \olfileid{sfr}{fun}{rel}
  12. \olsection{Functions as Relations}
  14. \begin{explain}
  15. A function which maps !!{element}s of~$A$ to !!{element}s of~$B$
  16. obviously defines a relation between $A$ and~$B$, namely the relation
  17. which holds between $x$ and $y$ iff $f(x) = y$. In fact, we might
  18. even---if we are interested in reducing the building blocks of
  19. mathematics for instance---\emph{identify} the function~$f$ with this
  20. relation, i.e., with a set of pairs. This then raises the question:
  21. which relations define functions in this way?
  22. \end{explain}
  24. \begin{defn}[Graph of a function] Let $f\colon A \to B$ be a function.
  25. The \emph{graph} of~$f$ is the relation $R_f \subseteq A \times B$
  26. defined by
  27. \[
  28. R_f = \Setabs{\tuple{x,y}}{f(x) = y}.
  29. \]
  30. \end{defn}
  32. \begin{explain}
  33. The graph of a function is uniquely determined, by extensionality.
  34. Moreover, extensionality (on sets) will immediately vindicate the
  35. implicit principle of extensionality for functions,
  36. whereby if $f$ and~$g$ share a domain and codomain then they are
  37. identical if they agree on all values.
  39. Similarly, if a relation is ``functional'', then it is the graph of a function.
  40. \end{explain}
  42. \begin{prop}\ollabel{prop:graph-function}
  43. Let $R \subseteq A \times B$ be such that:
  44. \begin{enumerate}
  45. \item If $Rxy$ and $Rxz$ then $y = z$; and
  46. \item for every $x \in A$ there is some $y \in B$ such that $\tuple{x,
  47. y} \in R$.
  48. \end{enumerate}
  49. Then $R$ is the graph of the function $f\colon A \to B$ defined by
  50. $f(x) = y$ iff $Rxy$.
  51. \end{prop}
  53. \begin{proof}
  54. Suppose there is a $y$ such that $Rxy$. If there were another $z \neq
  55. y$ such that $Rxz$, the condition on~$R$ would be violated. Hence, if
  56. there is a $y$ such that $Rxy$, this $y$ is unique, and so $f$ is
  57. well-defined. Obviously, $R_f = R$.
  58. \end{proof}
  60. \begin{explain}
  61. Every function $f\colon A \to B$ has a graph, i.e., a relation on $A
  62. \times B$ defined by $f(x) = y$. On the other hand, every relation~$R
  63. \subseteq A \times B$ with the properties given in
  64. \olref{prop:graph-function} is the graph of a function~$f \colon A \to
  65. B$. Because of this close connection between functions and their
  66. graphs, we can think of a function simply as its graph. In other
  67. words, functions can be identified with certain relations, i.e., with
  68. certain sets of tuples. \oliflabeldef{sfr:rel:ref:sec}{Note, though,
  69. that the spirit of this ``identification'' is as in
  70. \olref[sfr][rel][ref]{sec}: it is not a claim about the metaphysics of
  71. functions, but an observation that it is convenient to \emph{treat}
  72. functions as certain sets. One reason that this is so convenient, is
  73. that w}{W}e can now consider performing similar operations on
  74. functions as we performed on relations (see
  75. \olref[sfr][rel][ops]{sec}). In particular:
  76. \end{explain}
  78. \begin{defn}\ollabel{defn:funimage}
  79. Let $f \colon A \to B$ be a function with $C\subseteq A$.
  81. The \emph{restriction} of~$f$ to~$C$ is the
  82. function~$\funrestrictionto{f}{C}\colon C \to B$ defined by
  83. $(\funrestrictionto{f}{C})(x) = f(x)$ for all $x \in C$. In other
  84. words, $\funrestrictionto{f}{C} = \Setabs{\tuple{x, y} \in R_f}{x \in
  85. C}$.
  87. The \emph{application} of~$f$ to~$C$ is $\funimage{f}{C} =
  88. \Setabs{f(x)}{x \in C}$. We also call this the \emph{image} of~$C$
  89. under~$f$.
  90. \end{defn}
  92. \begin{explain}
  93. It follows from these definitions that $\ran{f} =
  94. \funimage{f}{\dom{f}}$, for any function~$f$.
  95. \oliflabeldef{sfr:rel:ops:sec}{These notions are exactly as one would
  96. expect, given the definitions in \olref[sfr][rel][ops]{sec} and our
  97. identification of functions with relations. But two other
  98. operations---inverses and relative products---require a little more
  99. detail. We will provide that in \olref[inv]{sec} and
  100. \olref[cmp]{sec}.}{}
  101. \end{explain}
  103. \end{document}

content/sets-functions-relations/functions/functions.tex

26 lines; SHA-256 ce481e97a8f301c749d1461326b4ee3d0792b4adc15a1fceb7c6ed3b58ceca54. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  4. \documentclass[../../../include/open-logic-chapter]{subfiles}
  6. \begin{document}
  8. \olchapter{sfr}{fun}{Functions}
  10. \olimport{function-basics}
  12. \olimport{function-kinds}
  14. \olimport{functions-relations}
  16. \olimport{inverses}
  18. \olimport{composition}
  20. %\olimport{isomorphic-functions}
  22. \olimport{partial-functions}
  24. \OLEndChapterHook
  26. \end{document}

content/sets-functions-relations/functions/inverses.tex

177 lines; SHA-256 93a84a2705e1ed3c92a7f5206c4308420bebbbbcb43824c1eb50e05f83777c4b. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  3. % Section: inverses
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  7. \begin{document}
  9. \olfileid{sfr}{fun}{inv}
  10. \olsection{Inverses of Functions}
  12. \begin{explain}
  13. We think of functions as maps. An obvious question to ask about
  14. functions, then, is whether the mapping can be ``reversed.'' For
  15. instance, the successor function $f(x) = x + 1$ can be reversed, in
  16. the sense that the function $g(y) = y - 1$ ``undoes'' what $f$ does.
  18. But we must be careful. Although the definition of~$g$ defines a
  19. function $\Int \to \Int$, it does not define a \emph{function} $\Nat
  20. \to \Nat$, since $g(0) \notin \Nat$. So even in simple cases, it is
  21. not quite obvious whether a function can be reversed; it may depend on
  22. the domain and codomain.
  24. This is made more precise by the notion of an inverse of a function.
  25. \end{explain}
  27. \begin{defn}
  28. A function $g \colon B \to A$ is an \emph{inverse} of a function $f
  29. \colon A \to B$ if $f(g(y)) = y$ and $g(f(x)) = x$ for all $x \in A$
  30. and $y \in B$.
  31. \end{defn}
  33. If $f$ has an inverse~$g$, we often write $f^{-1}$ instead of~$g$.
  35. \begin{explain}
  36. Now we will determine when functions have inverses. A good candidate
  37. for an inverse of $f\colon A \to B$ is $g\colon B \to A$ ``defined
  38. by''
  39. \[
  40. g(y) = \text{``the'' $x$ such that $f(x) = y$.}
  41. \]
  42. But the scare quotes around ``defined by'' (and ``the'') suggest that
  43. this is not a definition. At least, it will not always work, with
  44. complete generality. For, in order for this definition to specify a
  45. function, there has to be one and only one~$x$ such that $f(x) =
  46. y$---the output of~$g$ has to be uniquely specified. Moreover, it has
  47. to be specified for every $y \in B$. If there are $x_1$ and $x_2 \in
  48. A$ with $x_1 \neq x_2$ but $f(x_1) = f(x_2)$, then $g(y)$ would not be
  49. uniquely specified for $y = f(x_1) = f(x_2)$. And if there is no~$x$
  50. at all such that $f(x) = y$, then $g(y)$ is not specified at all. In
  51. other words, for $g$ to be defined, $f$~must be both !!{injective} and
  52. !!{surjective}.
  54. Let's go slowly. We'll divide the question into two: Given a
  55. function~$f\colon A \to B$, when is there a function $g\colon B \to A$
  56. so that $g(f(x)) = x$? Such a $g$ ``undoes'' what $f$ does, and is
  57. called a \emph{left inverse} of~$f$. Secondly, when is there a
  58. function $h\colon B \to A$ so that $f(h(y)) = y$? Such an $h$ is
  59. called a \emph{right inverse} of~$f$---$f$ ``undoes'' what $h$~does.
  60. \end{explain}
  62. \begin{prop}
  63. If $f\colon A \to B$ is !!{injective}, then there is a \emph{left
  64. inverse}~$g\colon B \to A$ of~$f$ so that $g(f(x)) = x$ for all $x
  65. \in A$.
  66. \end{prop}
  68. \begin{proof}
  69. Suppose that $f\colon A \to B$ is !!{injective}. Consider a $y \in B$.
  70. If $y \in \ran{f}$, there is an $x \in A$ so that $f(x) = y$. Because
  71. $f$ is !!{injective}, there is only one such~$x \in A$. Then we can
  72. define: $g(y) = x$, i.e., $g(y)$ is ``the'' $x \in A$ such that $f(x)
  73. = y$. If $y \notin \ran{f}$, we can map it to any~$a \in A$. So, we
  74. can pick an $a \in A$ and define $g\colon B \to A$ by:
  75. \[
  76. g(y) = \begin{cases}
  77. x & \text{if $f(x) = y$}\\
  78. a & \text{if $y \notin \ran{f}$.}
  79. \end{cases}
  80. \]
  81. It is defined for all $y \in B$, since for each such $y \in \ran{f}$
  82. there is exactly one $x \in A$ such that $f(x) = y$. By definition, if
  83. $y = f(x)$, then $g(y) = x$, i.e., $g(f(x)) = x$.
  84. \end{proof}
  86. \begin{prob}
  87. Show that if $f\colon A \to B$ has a left inverse~$g$, then $f$~is
  88. !!{injective}.
  89. \end{prob}
  91. \begin{prop}
  92. If $f\colon A \to B$ is !!{surjective}, then there is a
  93. \emph{right inverse}~$h\colon B \to A$ of~$f$ so that $f(h(y)) =
  94. y$ for all~$y \in B$.
  95. \end{prop}
  97. \begin{proof}
  98. Suppose that $f\colon A \to B$ is !!{surjective}. Consider a $y \in
  99. B$. Since $f$~is !!{surjective}, there is an $x_y \in A$ with $f(x_y)
  100. = y$. Then we can define: $h(y) = x_y$, i.e., for each $y \in B$ we
  101. choose some $x \in A$ so that $f(x) = y$; since $f$~is !!{surjective}
  102. there is always at least one to choose from.\footnote{Since $f$ is
  103. !!{surjective}, for every~$y \in B$ the set $\Setabs{x}{f(x) = y}$ is
  104. nonempty. Our definition of~$h$ requires that we choose a single $x$
  105. from each of these sets. That this is always possible is actually not
  106. obvious---the possibility of making these choices is simply assumed as an axiom.
  107. In other words, this proposition assumes the so-called Axiom of
  108. Choice, an issue we will \oliflabeldef{sth:choice::chap}{revisit in \olref[sth][choice][]{chap}}{gloss over}.
  109. However, in many specific cases, e.g., when $A = \Nat$ or is finite, or when $f$ is !!{bijective},
  110. the Axiom of Choice is not required. (In the particular case when $f$ is !!{bijective}, for each $y \in B$ the set
  111. $\Setabs{x}{f(x) = y}$ has exactly one !!{element}, so that there is no choice to make.)}
  112. By definition, if $x = h(y)$,
  113. then $f(x) = y$, i.e., for any $y \in B$, $f(h(y)) = y$.
  114. \end{proof}
  116. \begin{prob}
  117. Show that if $f\colon A \to B$ has a right inverse~$h$, then $f$~is
  118. !!{surjective}.
  119. \end{prob}
  121. \begin{explain}
  122. By combining the ideas in the previous proof, we now get that every
  123. !!{bijection} has an inverse, i.e., there is a single function
  124. which is both a left and right inverse of~$f$.
  125. \end{explain}
  127. \begin{prop}\ollabel{prop:bijection-inverse}
  128. If $f\colon A \to B$ is !!{bijective}, there is a
  129. function~$f^{-1}\colon B \to A$ so that for all $x \in A$,
  130. $f^{-1}(f(x)) = x$ and for all $y \in B$, $f(f^{-1}(y)) = y$.
  131. \end{prop}
  133. \begin{proof}
  134. Exercise.
  135. \end{proof}
  137. \begin{prob}
  138. Prove \olref[sfr][fun][inv]{prop:bijection-inverse}. You have to
  139. define~$f^{-1}$, show that it is a function, and show that it is an
  140. inverse of~$f$, i.e., $f^{-1}(f(x)) = x$ and $f(f^{-1}(y)) = y$ for
  141. all $x \in A$ and $y \in B$.
  142. \end{prob}
  144. \begin{explain}
  145. There is a slightly more general way to extract inverses. We saw in
  146. \olref[kin]{sec} that every function $f$ induces !!a{surjection} $f'
  147. \colon A \to \ran{f}$ by letting $f'(x) = f(x)$ for all $x \in A$.
  148. Clearly, if $f$~is !!{injective}, then $f'$~is !!{bijective}, so that
  149. it has a unique inverse by \olref{prop:bijection-inverse}. By a very
  150. minor abuse of notation, we sometimes call the inverse of $f'$ simply
  151. ``the inverse of~$f$.''
  152. \end{explain}
  154. \begin{prop}\ollabel{prop:left-right}%
  155. Show that if $f\colon A \to B$ has a left inverse~$g$ and a right
  156. inverse~$h$, then $h = g$.
  157. \end{prop}
  159. \begin{proof}
  160. Exercise.
  161. \end{proof}
  163. \begin{prob}
  164. Prove \olref[sfr][fun][inv]{prop:left-right}.
  165. \end{prob}
  167. \begin{prop}\ollabel{prop:inverse-unique}
  168. Every function~$f$ has at most one inverse.
  169. \end{prop}
  171. \begin{proof}
  172. Suppose $g$ and $h$ are both inverses of~$f$. Then in particular
  173. $g$~is a left inverse of~$f$ and $h$~is a right inverse. By
  174. \olref{prop:left-right}, $g = h$.
  175. \end{proof}
  177. \end{document}

content/sets-functions-relations/functions/partial-functions.tex

75 lines; SHA-256 2a1e79725a70fde443cc3c19c325a2c422c49e7ccd095c965f8c50fd5cc6b10b. Open the preserved source file.

  1. % Part: sets-functions-relations
  2. % Chapter: functions
  3. % Section: partial-functions
  5. \documentclass[../../../include/open-logic-section]{subfiles}
  8. \begin{document}
  10. \olfileid{sfr}{fun}{par}
  12. \olsection{Partial Functions}
  14. \begin{explain}
  15. It is sometimes useful to relax the definition of function so that it
  16. is not required that the output of the function is defined for all
  17. possible inputs. Such mappings are called \emph{partial functions}.
  18. \end{explain}
  20. \begin{defn}
  21. A \emph{partial function} $f \colon A \pto B$ is a mapping which
  22. assigns to every !!{element} of~$A$ at most one !!{element} of~$B$.
  23. If $f$ assigns an element of~$B$ to $x \in A$, we say $f(x)$ is
  24. \emph{defined}, and otherwise \emph{undefined}. If $f(x)$ is defined,
  25. we write $f(x) \fdefined$, otherwise $f(x) \fundefined$. The
  26. \emph{domain} of a partial function~$f$ is the subset of~$A$ where it
  27. is defined, i.e., $\dom{f} = \Setabs{x \in A}{f(x) \fdefined}$.
  28. \end{defn}
  30. \begin{ex}
  31. Every function $f\colon A \to B$ is also a partial function. Partial
  32. functions that are defined everywhere on~$A$---i.e., what we so far
  33. have simply called a function---are also called \emph{total}
  34. functions.
  35. \end{ex}
  37. \begin{ex}
  38. The partial function $f \colon \Real \pto \Real$ given by $f(x) = 1/x$
  39. is undefined for $x = 0$, and defined everywhere else.
  40. \end{ex}
  42. \begin{prob}
  43. Given $f\colon A \pto B$, define the partial function $g\colon B \pto
  44. A$ by: for any $y \in B$, if there is a unique $x \in A$ such that
  45. $f(x) = y$, then $g(y) = x$; otherwise $g(y) \fundefined$. Show that
  46. if $f$ is injective, then $g(f(x)) = x$ for all $x \in \dom{f}$, and
  47. $f(g(y)) = y$ for all $y \in \ran{f}$.
  48. \end{prob}
  50. \begin{defn}[Graph of a partial function]
  51. Let $f\colon A \pto B$ be a partial function. The \emph{graph} of~$f$
  52. is the relation $R_f \subseteq A \times B$ defined by
  53. \[
  54. R_f = \Setabs{\tuple{x,y}}{f(x) = y}.
  55. \]
  56. \end{defn}
  58. \begin{prop}
  59. Suppose $R \subseteq A \times B$ has the property that whenever $Rxy$
  60. and $Rxy'$ then $y = y'$. Then $R$ is the graph of the partial
  61. function $f\colon A \pto B$ defined by: if there is a $y$ such that
  62. $Rxy$, then $f(x) = y$, otherwise $f(x) \fundefined$. If $R$ is also
  63. \emph{serial}, i.e., for each $x \in A$ there is a $y \in B$ such that
  64. $Rxy$, then $f$ is total.
  65. \end{prop}
  67. \begin{proof}
  68. Suppose there is a $y$ such that $Rxy$. If there were another $y'
  69. \neq y$ such that $Rxy'$, the condition on $R$ would be
  70. violated. Hence, if there is a $y$ such that $Rxy$, that $y$ is
  71. unique, and so $f$ is well-defined. Obviously, $R_f = R$ and $f$ is
  72. total if~$R$ is serial.
  73. \end{proof}
  75. \end{document}