This post has been replaced by the post A slow introduction to category theory.
Tag Archives: identity
Presenting binary operations
This is the first of a set of notes I am writing to help me develop my thoughts about how particular topics in my book Abstracting algebra should be organized. This article describes my plan for the book in some detail. The present post has some thoughts about presenting binary operations.
Before binary operations are introduced
Traditionally, an abstract algebra book assumes that the student is familiar with high school algebra and will then proceed with an observation that such operations as $+$ and $\times$ can be thought of as functions of two variables that take a number to another number. So the first abstract idea is typically the concept of binary operation, although in another post I will consider whether that really should be the first abstract concept.
The Abstracting Algebra book will have a chapter that presents concrete examples of algebraic operations and expressions on numbers as in elementary school and as in high school algebra. This section of the post outlines what should be presented there. Each subsection needs to be expanded with lots of examples.
In elementary school
In elementary school you see expressions such as
 $3+4$
 $3\times 4$
 $34$
The student invariably thinks of these expressions as commands to calculate the value given by the expression.
They will also see expressions such as
\[\begin{equation}
\begin{array}[b]{r}
23\\
355\\
+ 96\\
\hline
\end{array}
\end{equation}\]
which they will take as a command to calculate the sum of the whole list:
\[\begin{equation}
\begin{array}[b]{r}
23\\
355\\
+ 96\\
\hline
474
\end{array}
\end{equation}\]
That uses the fact that addition is associative, and the format suggests using the standard school algorithm for adding up lists. You don’t usually see the same format with more than two numbers for multiplication, even though it is associative as well. In some elementary schools in recent years students are learning other ways of doing arithmetic and in particular are encouraged to figure out short cuts for problems that allow them. But the context is always “do it”, not “this represents a number”.
Algebra
In algebra you start using letters for numbers. In algebra, “$a\times b$” and “$a+b$” are expressions in the symbolic language of math, which means they are like noun phrases in English such as “My friend” and “The car I bought last week and immediately totaled” in that both are used semantically as names of objects. English and the symbolic language are both languages, but the symbolic language is not a natural language, nor is it a formal language.
Example
In beginning algebra, we say “$3+5=8$”, which is a (true) statement.
Basic facts about this equation:
The expressions “$3+5$” and “$8$”
 are not the same expression
 but in the standard semantics of algebra they have the same meaning
 and therefore the equation communicates information that neither “$3+5$” nor “$8$” communicate.
Another example is “$3+5=6+2$”.
Facts like this example need to be communicated explicitly before binary operations are introduced formally. The students in a college abstract algebra class probably know the meaning of an equation operationally (subconsciously) but they have never seen it made explicit. See Algebra is a difficult foreign language.
Note
The equation “$3+5=6+2$” is an expression just as much as “$3+5$” and “$6+2$” are. It denotes an object of type “equation”, which is a mathematical object in the same way as numbers are. Most mathematicians do not talk this way, but they should.
Binary operations
Early examples
Consciousnessexpanding examples should appear early and often after binary operations are introduced.
Common operations
 The GCD is a binary operation on the natural numbers. This disturbs some students because it is not written in infix form. It is associative. The GCD can be defined conceptually, but for computation purposes needs (Euclid’s) algorithm. This gives you an early example of conceptual definitions and algorithms.
 The maximum function is another example of this sort. This is a good place to point out that a binary operation with the “same” definition cen be defined on different sets. The max function on the natural numbers does not have quite the same conceptual definition as the max on the integers.
Extensional definitions
In order to emphasize the arbitrariness of definitions, some random operations on a small finite sets should be given by a multiplication table, on sets of numbers and sets represented by letters of the alphabet. This will elicit the common reaction, “What operation is it?” Hidden behind this question is the fact that you are giving an extensional definition instead of a formula — an algorithm or a combination of familiar operations.
Properties
The associative and commutative properties should be introduced early just for consciousnessraising. Subtraction is not associative or commutative. Rock paper scissors is commutative but not associative. Groups of symmetries are associative but not commutative.
Binary operation as function
The first definition of binary operation should be as a function. For example, “$+$” is a function that takes pairs of numbers to numbers. In other words, $+:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is a function.
We then abstract from that example and others like it from specific operations to arbitrary functions $\Delta:S\times S\to S$ for arbitrary sets $S$.
This is abstraction twice.
 First we replace the example operations by an arbitrary operation. such as multiplication, subtraction, GCD and MAX on $\mathbb{Z}$, or something complicated such as \[(x,y)\mapsto 3(xy1)^2(x^2+xy^3)^3\].

Then we replace sets of numbers by arbitrary sets. An example would be the random multiplication on the set $\{1,2,5\}$ given by the table
\[
\begin{array}{cccc}
\Delta& 1&2&5\\
\hline
1&2&2&1\\
2&5&2&1\\
5&2&1&5
\end{array}
\]
This defines a function $\Delta:\{1,2,5\}\times\{1,2,5\}\to\{1,2,5\}$ for which for example $\Delta(2,1)=5$, or $2\Delta 1=5$. This example uses numbers as elements of the set and is good for eliciting the “What operation is it?” question.  I will use examples where the elements are letters of the alphabet, as well. That sort of example makes the students think the letters are variables they can substitute for, another confusion to be banished by the wise professor who know the right thing to say to make it clear. (Don’t ask me; I taught algebra for 35 years and I still don’t know the right thing to say.)
It is important to define prefix notation and infix notation right away and to use both of them in examples.
Other representations of binary operations.
The main way of representing binary operations in Abstracting Algebra will be as trees, which I will cover in later posts. Those posts will be much more interesting than this one.
Binary operations in high school and college algebra
 Some binops are represented in infix notation: “$a+b$”, “$ab$”, and “$a\times b$”.
 “$a\times b$” is usually written “$ab$” for letters and with the “$\times$” symbol for numbers.
 Some binops have idiosyncratic representation: “$a^b$”, “${a}\choose{b}$”.
 A lot of binops such as GCD and MAX are given as functions of two variables (prefix notation) and their status as binary operations usually goes unmentioned. (That is not necessarily wrong.)
 The symbol “$(a,b)$” is used to denote the GCD (a binop) and is also used to denote a point in the plane or an open interval, both of which are not strictly binops. They are binary operations in a multisorted algebra (a concept I expect to introduce later in the book.)
 Some apparent binops are in infix notation but have flaws: In “$a/b$”, the second entry can’t be $0$, and the expression when $a$ and $b$ are integers is often treated as having good forms ($3/4$) and bad forms ($6/8$).
Trees
The chaotic nature of algebraic notation I just described is a stumbling block, but not the primary reason high school algebra is a stumbling block for many students. The big reason it is hard is that the notation requires students to create and hold complicated abstract structures in their head.
Example
This example is a teaser for future posts on using trees to represent binary operations. The tree below shows much more of the structure of a calculation of the area of a rectangle surmounted by a semicircle than the expression
\[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\]
does.
The tree explicitly embodies the thought process that leads to the formula:
 You need to add the area of the rectangle and the area of the semicircle.
 The area of the rectangle is width times height.
 The area of the semicircle is $\frac{1}{2}(\pi r^2)$.
 In this case, $r=\frac{1}{2}w$.
Any mathematician will extract the same abstract structure from the formula\[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\] This is difficult for students beginning algebra.
References
 Abstracting algebra. An outline of the proposed book.
 Abstraction in abstractmath.org.
 Algebra is a difficult foreign language. G&G post.
 Formal language in Wikipedia.
 Monads for high school III. G&G post.
 Monads in Wikipedia
 Natural language in Wikipedia.
 Noun phrases in Wikipedia.
 Symbolic language of math in abstractmath.org.
 Visible Algebra I.G&G post.
 Visible algebra I supplement. G&G post.
 Visible Algebra II. G&G post.
This work is licensed under a Creative Commons AttributionShareAlike 2.5 License.
The definition of “function”
This is the new version of the abstractmath article on the definition of function. I had to adapt the formatting and some of it looks weird, but legible. It is prettier on abstractmath.org.
I expect to announce new revisions of other abmath articles on this blog, with links, but not to publish them here. This article brings out a new point of view about defining functions that I wanted to call attention to, so I am publishing it here, as well.
FUNCTIONS: SPECIFICATION AND DEFINITION
It is essential that you understand many of the images, metaphors and terminology that mathematicians use when they think and talk about functions. For many purposes, the precise mathematical definition of "function" does not play much of a role when you are trying to understand particular kinds of functions. But there is one point of view about functions that has resulted in fundamental progress in math:
A function is a mathematical object.
To deal with functions in that way you need a precise definition of "function". That is what this article gives you.
 The article starts by giving a specification of "function".
 After that, we get into the technicalities of the definitions of the general concept of function.
 Things get complicated because there are several inequivalent definitions of "function" in common use.
Specification of "function"
A function $f$ is a mathematical object which determines and is completely determined by the following data:
(DOM) $f$ has a domain, which is a set. The domain may be denoted by $\text{dom} f$.
(COD) $f$ has a codomain, which is also a set and may be denoted by $\text{cod} f$.
(VAL) For each element $a$ of the domain of $f$, $f$ has a value at $a$, denoted by $f(a)$.
(FP) The value of $f$ at $a$ is completely determined by $a$ and $f$.
(VIC) The value of $f$ at $a$ must be an element of the codomain of $f$.
 The operation of finding $f(a)$ given $f$ and $a$ is called evaluation.
 "FP" means functional property.
 "VIC" means "value in codomain".
Examples
The examples of functions chapter contains many examples. The two I give here provide immediate examples.
A finite function
Let $F$ be the function defined on the set $\left\{1,\,2,3,6 \right\}$ as follows: $F(1)=3,\,\,\,F(2)=3,\,\,\,F(3)=2,\,\,\,F(6)=1$. This is the function called "Finite'' in the chapter on examples of functions.
 The definition of $F$ says "$F$ is defined on the set $\left\{1,\,2,\,3,\,6 \right\}$". That phrase means that the domain is that set.
 The value of $F$ at each element of the domain is given explicitly. The value at 3, for example, is 2, because the definition says that $F(2) = 3$. No other reason needs to be given. Mathematical definitions can be arbitrary.
 The codomain of $F$ is not specified, but must include the set $\{1,2,3\}$. The codomain of a function is often not specified when it is not important — which is most of the time in freshman calculus (for example).
A realvalued function
Let $G$ be the realvalued function defined by the formula $G(x)={{x}^{2}}+2x+5$.
 The definition of $G$ gives the value at each element of the domain by a formula. The value at $3$, for example, is $G(3)=3^2+2\cdot3+5=20$.
 The definition of $G$ does not specify the domain. The convention in the case of functions defined on the real numbers by a formula is to take the domain to be all real numbers at which the formula is defined. In this case, that is every real number, so the domain is $\mathbb{R}$.
 The definition does not specify the codomain, either. However, must include all real numbers greater than or equal to 4. (Why?)
What the specification means
 The specification guarantees that a function satisfies all five of the properties listed.
 The specification does not define a mathematical structure in the way mathematical structures have been defined in the past: In particular, it does not require a function to be one or more sets with structure.

Even so, it is useful to have the specification, because:
Many mathematical definitions
introduce extraneous technical elements
which clutter up your thinking
about the object they define.I will say more about this when I give the various definitions that are in use.
History
Until late in the nineteenth century, functions were usually thought of as defined by formulas (including infinite series). Problems arose in the theory of harmonic analysis which made mathematicians require a more general notion of function. They came up with the concept of function as a set of ordered pairs with the functional property (discussed below), and that understanding revolutionized our understanding of math.
This discussion is an oversimplification of the history of mathematics, which many people have written thick books about. A book relevant to these ideas is Plato's Ghost, by Jeremy Gray.
In particular, this definition, along with the use of set theory, enabled abstract math (ahem) to become a common tool for understanding math and proving theorems. It is conceivable that some of you may wish it hadn't. Well, tough.
The more modern definition of function given here (which builds on the older definition) came into use beginning in the 1950's. The strict version became necessary in algebraic topology and is widely used in many fields today.
The concept of function as a formula never disappeared entirely, but was studied mostly by logicians who generalized it to the study of functionasalgorithm. Of course, the study of algorithms is one of the central topics of modern computing science, so the notion of functionasformula (updated to functionasalgorithm) has achieved a new importance in recent years.
To state both the old abstract definition and the modern one, we need a preliminary idea.
The functional property
A set $P$ of ordered pairs has the functional property if two pairs in $P$ with the same first coordinate have to have the same second coordinate (which means they are the same pair). In other words, if $(x,a)$ and $(x,b)$ are both in $P$, then $a=b$.
How to think about the functional property
The point of the functional property is that for any pair in the set of ordered pairs, the first coordinate determines what the second one is. That's why you can write "$G(x)$'' for any $x $ in the domain of $G$ and not be ambiguous.
Examples
 The set $\{(1,2), (2,4), (3,2), (5,8)\}$ has the functional property, since no two different pairs have the same first coordinate. Note that there are two different pairs with the same second coordinate. This is irrelevant to the functional property.
 The set $\{(1,2), (2,4), (3,2), (2,8)\}$ does not have the functional property. There are two different pairs with first coordinate 2.
 The empty set $\emptyset$ has the function property vacuously.
Example: graph of a function defined by a formula
In calculus books, a picture like this one (of part of $y=x^2+2x+5$) is called a graph. Here I use the word "graph" to denote the set of ordered pairs \[\left\{ (x,{{x}^{2}}+2x+5)\,\mathsf{}\,x\in \mathbb{R } \right\}\] which is a mathematical object rather than some ink on a page or pixels on a screen.
The graph of any function studied in beginning calculus has the functional property. For example, the set of ordered pairs above has the functional property because if $x$ is any real number, the formula ${{x}^{2}}+2x+5$ defines a specific real number.
 if $x = 0$, then ${{x}^{2}}+2x+5=5$, so the pair $(0, 5)$ is an element of the graph of $G$. Each time you plug in $0$ in the formula you get 5.
 if $x = 1$, then ${{x}^{2}}+2x+5=8$.
 if $x = 2$, then ${{x}^{2}}+2x+5=5$.
You can measure where the point $\{2,5\}$ is on the (picture of) the graph and see that it is on the blue curve as it should be. No other pair whose first coordinate is $2$ is in the graph of $G$, only $(2, 5)$. That is because when you plug $2$ into the formula ${{x}^{2}}+2x+5$, you get $5$ and nothing else. Of course, $(0, 5)$ is in the graph, but that does not contradict the functional property. $(0, 5)$ and $(2, 5)$ have the same second coordinate, but that is OK.
Modern mathematical definition of function
A function $f$ is a mathematical structure consisting of the following objects:
 A set called the domain of $f$, denoted by $\text{dom} f$.
 A set called the codomain of $f$, denoted by $\text{cod} f$.
 A set of ordered pairs called the graph of $ f$, with the following properties:
 $\text{dom} f$ is the set of all first coordinates of pairs in the graph of $f$.
 Every second coordinate of a pair in the graph of $f$ is in $\text{cod} f$ (but $\text{cod} f$ may contain other elements).
 The graph of $f$ has the functional property.
Using arrow notation, this implies that $f:A\to B$.
Remark
The main difference between the specification of function given previously and this definition is that the definition replaces the statement "$f$ has a value at $a$" by introducing a set of ordered pairs (the graph) with the functional property.
 This set of ordered pairs is extra structure introduced by the definition mainly in order to make the definition a classical setswithstructure, which makes the graph, which should be a concept derived from the concept of function, into an apparently necessary part of the function.
 That suggests incorrectly that the graph is more of a primary intuition that other intuitions such as function as relocator, function as transformer, and other points of view discussed in the article Intuitions and metaphors for functions.
Examples
 Let $F$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$ and define $A = \{1, 2, 3, 5\}$ and $B = \{2, 4, 8\}$. Then $F:A\to B$ is a function. In speaking, we would usually say, "$F$ is a function from $A$ to $B$."
 Let $G$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$ (same as above), and define $A = \{1, 2, 3, 5\}$ and $C = \{2, 4, 8, 9, 11, \pi, 3/2\}$. Then $G:A\to C$ is a (admittedly ridiculous) function. Note that all the second coordinates of the graph are in $C$, along with a bunch of miscellaneous suspicious characters that are not second coordinates of pairs in the graph.
 Let $H$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$. Then $H:A\to \mathbb{R}$ is a function, since $2$, $4$ and $8$ are all real numbers.
 Let $D = \{1, 2, 5\}$ and $E = \{1, 2, 3, 4, 5\}$. Then there is no function $D\to A$ and no function $E\to A$ with graph $\{(1,2), (2,4), (3,2), (5,8)\}$. Neither $D$ nor $E$ has exactly the same elements as the first coordinates of the graph.
Identity and inclusion
Suppose we have two sets A and B with $A\subseteq B$.
 The identity function on A is the function ${{\operatorname{id}}_{A}}:A\to A$ defined by ${{\operatorname{id}}_{A}}(x)=x$ for all $x\in A$. (Many authors call it ${{1}_{A}}$).
 When $A\subseteq B$, the inclusion function from $A$ to $B$ is the function $i:A\to B$ defined by $i(x)=x$ for all $x\in A$. Note that there is a different function for each pair of sets $A$ and $B$ for which $A\subseteq B$. Some authors call it ${{i}_{A,\,B}}$ or $\text{in}{{\text{c}}_{A,\,B}}$.
The identity function and an inclusion function for the same set $A$ have exactly the same graph, namely $\left\{ (a,a)a\in A \right\}$. More about this below.
Other definitions of function
Original abstract definition of function
Definition
 A function $f$ is a set of ordered pairs with the functional property.
 If $f$ is a function according to this definition, the domain of $f$ is the set of first coordinates of all the pairs in $f$.
 If $x\in \text{dom} f$, then we define the value of $f$ at $x$, denoted by $f(x)$, to be the second coordinate of the only ordered pair in $f$ whose first coordinate is $x$.
Remarks
 This definition is still widely used in mathematical writing.
 Many authors do not tell you which definition they are using.
 For many purposes (including freshman calculus for the most part) it does not matter which definition is used.
 In some branches of math, the modern definition adds great clarity to many complicated situations; using the older definition can even make it difficult to describe some important constructions.
Possible confusion
Some confusion can result because of the presence of these two different definitions.
 For example, since the identity function ${{\operatorname{id}}_{A}}:A\to A$ and the inclusion function ${{i}_{A,\,B}}:A\to B$ have the same graph, users of the older definition are required in theory to say they are the same function.
 Also it requires you to say that the graph of a function is the same thing as the function.
 In my observation, this does not make a problem in practice, unless there is a very picky person in the room.
 It also appears to me that the modern definition is (quite rightly) winning.
Multivalued function
Some older mathematical papers in complex function theory do not tell you that their functions are multivalued. There was a time when complex function theory was such a Big Deal in research mathematics that the phrase "function theory" meant complex function theory and all the cognoscenti knew that their functions were multivalued.
The phrase multivalued function refers to an object that is like a function $f:S\to T$ except that for $s\in S$, $f(s)$ may denote more than one value.
Examples
 Multivalued functions arose in considering complex functions. In common practice, the symbol $\sqrt{4}$ denoted $2$, although $2$ is also a square root of $4$. But in complex function theory, the square root function takes on both the values $2$ and $2$. This is discussed in detail in Wikipedia.
 The antiderivative is an example of a multivalued operator. For any constant $C$, $\frac{x^3}{3}+C$ is an antiderivative of $x^2$.
A multivalued function $f:S\to T$ can be modeled as a function with domain $S$ and codomain the set of all subsets of $T$. The two meanings are equivalent in a strong sense (naturally equivalent}). Even so, it seems to me that they represent two different ways of thinking about multivalued functions. ("The value may be any of these things…" as opposed to "The value is this whole set of things.")
The phrases "multivalued function" and "partial function" upset some picky types who say things like, "But a multivalued function is not a function!". A stepmother is not a mother, either. See the Handbook article on radial category.
Partial function
A partial function $f:S\to T$ is just like a function except that its input may be defined on only a subset of $S$. For example, the function $f(x)=\frac{1}{x}$ is a partial function from the real numbers to the real numbers.
This models the behavior of computer programs (algorithms): if you consider a program with one input and one output as a function, it may not be defined on some inputs because for them it runs forever (or gives an error message).
In some texts in computing science and mathematical logic, a function is by convention a partial function, and this fact may not be mentioned explicitly, especially in research papers.
New approaches to functions
All the definitions of function given here produce mathematical structures, using the traditional way to define mathematical objects in terms of sets. Such definitions have disadvantages.
Mathematicians have many ways to think about functions. That a function is a set of ordered pairs with a certain property (functional) and possibly some ancillary ideas (domain, codomain, and others) is not the way we usually think about them$\ldots$Except when we need to reduce the thing we are studying to its absolutely most abstract form to make sure our proofs are correct. That most abstract form is what I have called the rigorous view or the dry bones and it is when that reasoning is needed that the setswithstructure approach has succeeded.
Our practice of abstraction has led us to new approaches to talking about functions. The most important one currently is category theory. Roughly, a category is a bunch of objects together with some arrows going between them that can be composed head to tail. Functions between sets are examples of this: the sets are the objects and the functions the arrows.
This abstracts the idea of function in a way that brings out common ideas in various branches of math. Research papers in many branches of mathematics now routinely use the language of category theory. Categories now appear in some undergraduate math courses, meaning that Someone needs to write a chapter on category theory for abstractmath.org.
Besides category theory, computing scientists have come up with other abstract ways of dealing with functions, for example type theory. It has not come as far along as category theory, but has shown recent signs of major progress.
Both category theory and type theory define math objects in terms of their effect on and relationship with other math objects. This makes it possible to do abstract math entirely without using setswithstructure as a means of defining concepts.