Tag Archives: evaluate

abstracting algebra, category theory, exposition, language of math, math, Mathematica, representations, understanding math

The only axiom of algebra

Leave a comment

This is one of a series of posts I am writing to help me develop my thoughts about how particular topics in my book Abstracting Algebra (“AbAl“) should be organized. This post concerns the relation between substitution and evaluation that essentially constitutes the definition of algebra. The Mathematica code for the diagrams is in Subs Eval.nb.

Substitution and evaluation

This post depends heavily on your understanding of the ideas in the post Presenting binary operations as trees.

Notation for evaluation

I have been denoting evaluation of an expression represented as a tree like this:



In standard algebra notation this would be written:\[(6-4)-1=2-1=1\]

Comments

This treatment of evaluation is intended to give you an intuition about evaluation that is divorced from the usual one-dimensional (well, nearly) notation of standard algebra. So it is sloppy. It omits fine points that will have to be included in AbAl.

  • The evaluation goes from bottom up until it reaches a single value.
  • If you reach an expression with an empty box, evaluation stops. Thus $(6-3)-a$ evaluates only to $3-a$.
  • $(6-a)-1$ doesn’t evaluate further at all, although you can use properties peculiar to “minus” to change it to $5-a$.
  • I used the boxed “1” to show that the value is represented as a trivial tree, not a number. That’s so it can be substituted into another tree.

Notation for substitution

I will use a configuration like this

to indicate the data needed to substitute the lower tree into the upper one at the variable (blank box). The result of the substitution is the tree

In standard algebra one would say, “Substitute $3\times 4$ for $a$ in the expression $a+5$.” Note that in doing this you have to name the variable.

Example

“If you substitute $12$ for $a$ in $a+5$ you get $12+5$”:

results in

Example

“If you substitute $3\times 4$ for $a$ in $a+b$ you get $3\times4+b$”:

results in

Comments

Like evaluation, this treatment of substitution omits details that will have to be included in AbAl.

  • You can also substitute on the right side.
  • Substitution in standard algebraic notation often requires sudden syntactic changes because the standard notation is essentially two-dimensional. Example: “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”.
  • The allowed renaming of free variables except when there is a clash causes students much trouble. This has to be illustrated and contrasted with the “binop is tree” treatment which is context-free. Example: The variable $b$ in the expression $(3\times 4)+b$ by itself could be changed to $a$ or $c$, but in the sentence “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”, the $b$ is bound. It is going to be difficult to decide how much of this needs explaining.

The axiom

The Axiom for Algebra says that the operations of substitution and evaluation commute: if you apply them in either order, you get the same resulting tree. That says that for the current example, this diagram commutes:

The Only Axiom for Algebra

In standard algebra notation, this becomes:

  • Substitute, then evaluate: If $a=3\times 4$, then $a+5=3\times 4+5=12+5$.
  • Evaluate, then substitute: If $a=3\times 4$, then $a=12$, so $a+5=12+5$.

Well, how underwhelming. In ordinary algebra notation my so-called Only Axiom amounts to a mere rewording. But that’s the point:


The Only Axiom of Algebra is what makes algebraic manipulation work.

Miscellaneous comments

  • In functional notation, the Only Axiom says precisely that $\text{eval}∘\text{subst}=\text{subst}∘(\text{eval},\text{id})$.
  • The Only Axiom has a symmetric form: $\text{eval}∘\text{subst}=\text{subst}∘(\text{id},\text{eval})$ for the right branch.
  • You may expostulate: “What about associativity and commutativity. They are axioms of algebra.” But they are axioms of particular parts of algebra. That’s why I include examples using operations such as subtraction. The Only Axiom is the (ahem) only one that applies to all algebraic expressions.
  • You may further expostulate: Using monads requires the unitary or oneidentity axiom. Here that means that a binary operation $\Delta$ can be applied to one element $a$, and the result is $a$. My post Monads for high school III. shows how it is used for associative operations. The unitary axiom is necessary for representing arbitrary binary operations as a monad, which is a useful way to give a theoretical treatment of algebra. I don’t know if anyone has investigated monads-without-the-unitary-axiom. It sounds icky.
  • The Only Axiom applies to things such as single valued functions, which are unary operations, and ternary and higher operations. They also apply to algebraic expressions involving many different operations of different arities. In that sense, my presentation of the Only Axiom only gives a special case.
  • In the case of unary operations, evaluation is what we usually call evaluation. If you think about sets the way I do (as a special kind of category), evaluation is the same as composition. See “Rethinking Set Theory”, by Tom Leinster, American Mathematical Monthly, May, 2014.
  • Calculus functions such as sine and the exponential are unary operations. But not all of calculus is algebra, because substitution in the differential and integral operators is context-sensitive.

References

Preceding posts in this series
Remarks concerning these posts
  • Each of the posts in this series discusses how I will present a small part of AbAl.
  • The wording of some parts of the posts may look like a first draft, and such wording may indeed appear in the text.
  • In many places I will talk about how I should present the topic, since I am not certain about it.

Other references

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.


Send to Kindle
abstracting algebra, category theory, exposition, language of math, math, Mathematica, representations, understanding math

Presenting binops as trees

Leave a comment

Binary operations as trees

This is one of a series of posts I am writing to help me develop my thoughts about how particular topics in my book Abstracting Algebra (“AbAl“) should be organized. In some parts, I present various options that I have not decided between.

This post concerns the presen­ta­tion of binary operations as trees. The Mathematica code for the diagrams is in Substitution in algebra.nb

Binary operations as functions

A binary operation or binop $\Delta$ is a function of two variables whose value at $(a,b)$ is traditionally denoted by $a\Delta b$. Most commonly, the function is restricted to having inputs and outputs in the same set. In other words, a binary operation is a function $\Delta:S\times S\to S$ defined on some set $S$. $S$ is the underlying set of the operation. For now, this will be the definition, although binops may be generalized to multiple sets later in the book.

In AbAl:

  • Binops will be defined as functions in the way just described.
  • Algebraic expressions will be represented
    as trees, which exhibit more clearly the structure of the expressions that is encoded in algebraic notation.
  • They will also be represented using the usual infix expressions such as “$3\times 5$” and “$3-5$”,

Fine points

The definition of a binop as a function has termi­no­logical consequences. The correct point of view concerning a function is that it determines its domain and its codomain. In particular:


A binary operation determines its underlying set.

Thus if we talk about an arbitrary binop $\Delta$, we don’t have to give a name to its underlying set. We can just say “the underlying set of $\Delta$” or “$U(\Delta)$”.

Examples

“$+$” is not one binary operation.

  • $+:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is a binary operation.
  • $+:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ is another binary operation.

Mathematicians commonly refer to these particular binops as “addition on the integers” and “addition on the reals”.

Remark

You almost never see this attitude in textbooks on algebra. It is required by both category theory and type theory, two Waves flooding into math. Category theory is a middle-aged Wave and type theory, in the version of homo­topy type theory, is a brand new baby Wave. Both Waves have changed and will change our under­standing of math in deep ways.

Trees

An arbitrary binop $\Delta$ can be represented as a binary tree in this way:

generic binop

This tree represents the expression that in standard algebraic notation is “$a\Delta b$”.

In more detail, the tree is an ordered rooted binary tree. The “ordered” part means that the leaves (nodes with no descendants) are in a specific left to right order. In AbAl, I will define trees in some detail, with lots of pictures.

The root shows the operation and the two leaves show elements of the underlying set. I follow the custom in computing science to put the root at the top.

Metaphors should not dictate your life by being taken literally.

Remark

The Wikipedia treatment of trees is scat­tered over many articles and they almost always describe things mostly in words, not pictures. Describing math objects in words when you could use pictures is against my religion. Describing is not the same as defining, which usually requires words.

Some concrete examples:



    
    

3trees

These are represen­ta­tions of the expressions “$3+5$”, “$3\times5$”, and “$3-5$”.

Just as “$5+3$” is a different expression from “$3+5$”, the left tree in 3trees above is a different expression from this one:



    

switch

They have the same value, but they are distinct as expressions — otherwise, how could you state the commutative law?

Fine points

I regard an expression as an abstract math object that can have many repre­sentations. For example “$3+5$” and the left tree in 3trees are two different represen­ta­tions of the same (abstract) expression. This deviates from the usual idea that “expression” refers to a typographical construction.

In previous posts, when the operation is not commutative, I have sometimes labeled the legs like this:


I have thought about using this notation consistently in AbAl, but I suspect it would be awkward in places.

Evaluation and substitution


The two basic operations on algebraic expressions
are evaluation and substitution.

They and the Only Axiom of Algebra, which I will discuss in a later post, are all that is needed to express the true nature of algebra.

Evaluation

  • If you evaluate $3+5$ you get $8$.
  • If you evaluate $3\times 5$ you get $15$.
  • If you evaluate $3-5$ you get $-2$.

I will show evaluation on trees like this:




Evaluation with trace

A more elaborate version, valuation with trace, would look like this. This allows you to keep track of where the valuations come from.




You could also keep track of the operation used at each node. An interactive illustration of this is in the post Visible algebra I supplement. That illustration requires CDF Player to be installed on your computer. You can get it free from the Mathematica website.

Variables

In the tree above, the $a$ and $b$ are variables, just as they are in the equivalent expression $a\Delta b$. Algebra beginners have a hard time understanding variables.

  • You can’t evaluate an expression until you substitute numbers for the letters, which produces an instance of expression. (“Instance” is the preferable name for this, but I often refer to such a thing as an “example”.)
  • If a variable is repeated you have to substitute the same value for each occurrence. So $a\Delta b$ is a different expression from $a\Delta a$: $2+3$ is an instance of $a+b$ but it is not an instance of $a+a$. But $a\Delta a$ and $b\Delta b$ are the same expression: any instance of one is an instance of the other.
  • Substitute $a\Delta b$ for $a$ in $a\Delta b$ and you get $(a\Delta b)\Delta b$. You may have committed variable clash. You might have meant $(a\Delta b)\Delta c$. (Somebody please tell me a good link that describes variable clash.)
  • Later, you will deal with multiplication tables for algebraic structures. There the elements are denoted by letters of the alphabet. They can’t be substituted for.

Empty boxes

A straightforward way to denote variables would be to use empty boxes:

The idea is that a number (element of the underlying set) can be inserted in each box. If $3$ (left) and $5$ (right) are placed in the boxes, evaluation would place the value of $3\Delta5$ in the root. Each empty box represents a separate variable.

Empty boxes could also be used in the standard algebraic notation: $\Delta$ or $+$ or $-$.
I have seen that notation in texts explaining variables, but I don’t know a reference. I expect to use this notation with trees in AbAl.

To achieve the effect of one variable in two different places, as in

we can cause it to repeat, as below, where “$\text{id}$” denotes the identity function on the underlying set:

To evaluate at a number (member of the underlying set) you insert a number into the only empty box

which evaluates to

which of course evaluates to $3\Delta3$.

This way of treating repeated variables exhibits the nature of repeated variables explicitly and naturally, putting the values automatically in the correct places. This process, like everything in this section, comes from monad theory. It also reminds me of linear logic in that it shows that if you want to use a value more than once you have to copy it.

Substitution

Given two binary trees



      

you could attach the root of the first one to one of the leaves of the second one, in two different ways, to get these trees:



      


2trees

which in standard algebra notation would be written $(a-b)-c)$ and $a-(b-c)$ respectively. Note that this tree



would be represented in algebra as $(a-b)-b$.

In general, substituting a tree for an input (variable or empty box) consists of replacing the empty box by the whole tree, identifying the root of the new tree with the empty box. In graph theorem, “substitution” may be called “grafting”, which is a good metaphor.

You can evaluate the left tree in 2trees at particular numbers to evaluate it in two stages:



Of course, evaluating the right one at the same values would give you a different answer, since subtraction is not associative. Here is another example:


Binary trees in general

By repeated substitution, you can create general binary trees built up of individual trees of this form:

In AbAl I will give examples of such things and their counterparts in algebraic notation. This will include binary trees involving more than one binop, as well. I showed an example in the previous post, which example I repeat here:

It represents the precise unsimplified expression

\[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\]

Some of the operations in that tree are associative and commutative, which is why the expression can be simplified. The collection of all (finite) binary trees built out of a single binop with no assumption that it satisfies laws (associative, commutative and so on) is the free algebra on that binary operation. It is the mother of all binary operations, so it plays the same role for an arbitrary binop that the set of lists plays for associative operations, as described in Monads for High School III: Algebras. All this will be covered in later chapters of AbAl.

References

Preceding posts in this series

Other references

 

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.


Send to Kindle
abstractmath.org, exposition, language of math, math, understanding math

The Mathematical Definition of Function

Leave a comment

Introduction

This post is a completely rewritten version of the abstractmath article on the definition of function. Like every part of abstractmath, the chapter on functions is designed to get you started thinking about functions. It is no way complete. Wikipedia has much more complete coverage of mathematical functions, but be aware that the coverage is scattered over many articles.

The concept of function in mathematics is as important as any mathematical idea. The mathematician’s concept of function includes the kinds of functions you studied in calculus but is much more abstract and general. If you are new to abstract math you need to know:

  • The precise meaning of the word “function” and other concepts associated with functions. That’s what this section is about.
  • Notation and terminology for functions. (That will be a separate section of abstractmath.org which I will post soon.)
  • The many different kinds of functions there are. (See Examples of Functions in abmath).
  • The many ways mathematicians think about functions. The abmath article Images and Metaphors for Functions is a stub for this.

I will use two running examples throughout this discussion:

  • {F} is 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 a function defined on a finite set by explicitly naming each value.
  • {G} is the real-valued function defined by the formula {G(x)={{x}^{2}}+2x+5}.

Specification of function

We start by giving a specification of “function”. (See the abstractmath article on specification.) After that, we get into the technicalities of the definitions of the general concept of function.

Specification: A function {f} is a mathematical object which determines and is completely determined bythe following data:

  • {f} has a domain, which is a set. The domain may be denoted by {\text{dom }f}.
  • {f} has a codomain, which is also a set and may be denoted by {\text{cod }f}.
  • For each element {a} of the domain of {f}, {f} has a value at {a}, denoted by {f(a)}.
  • The value of {f} at {a} is completely determined by {a} and {f} .
  • 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.

Examples

  • The definition above of the finite function {F} specifies that the domain is the set {\left\{1,\,2,\,3,\,6 \right\}}. 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}. The codomain of {F} is not specified, but must include the set {\{1,2,3\}}.
  • The definition of {G} above 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 does not specify the domain or the codomain. 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 codomain must include all real numbers greater than or equal to 4. (Why?)

Comment: The formula above that defines the function G in fact defines a function of complex numbers (even quaternions).

Definition of function

In the nineteenth century, mathematicians realized that it was necessary for some purposes (particularly harmonic analysis) to give a mathematical definition of the concept of function. A stricter version of this definition turned out to be necessary in algebraic topology and other fields, and that is the one I give here.

To state this definition we need a preliminary idea.

The functional property

A set R of ordered pairs has the functional property if two pairs in R with the same first coordinate have to have the same second coordinate (which means they are the same pair).

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. It is true that two of them have the same second coordinate, but that is irrelevant.
  • 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 graphs of functions in beginning calculus have the functional property.
  • The empty set {\emptyset} has the functional property .

Example: Graph of a function defined by a formula

The graph of the function {G} given above has the functional property. The graph is the set

\displaystyle \left\{ (x,{{x}^{2}}+2x+5)\,\mathsf{|}\,x\in {\mathbb R} \right\}.

If you repeatedly plug in one real number over and over, you get out the same real number every time. Example:

  • if {x = 0}, then {{{x}^{2}}+2x+5=5}.  You get 5 every time you plug in 0.
  • if {x = 1}, then {{{x}^{2}}+2x+5=8}.
  • if {x =-2}, then {{{x}^{2}}+2x+5=5}.

This set has the functional property because if {x} is any real number, the formula {{{x}^{2}}+2x+5} defines a specific real number. (This description of the graph implicitly assumes that {\text{dom } G={\mathbb R}}.)  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} every time. 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.

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.

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\rightarrow B}.

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\rightarrow B} is a function.
  • 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\rightarrow 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\rightarrow {\mathbb R}} is a function.

According to the definition of function, {F}, {G} and {H} are three different functions.

Identity and inclusion

Suppose we have two sets A and B with {A\subseteq B}.

  • The identity function on A is the function {{{\text{id}}_{A}}:A\rightarrow A} defined by {{{\text{id}}_{A}}(x)=x} for all{x\in A}. (Many authors call it {{{1}_{A}}}).
  • The inclusion function from A to B is the function {i:A\rightarrow 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}}}.

Remark 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\}}.

Graphs and functions

  • If {f} is a function, the domain of {f} is the set of first coordinates of all the pairs in {f}.
  • If {x\in \text{dom } f}, then {f(x)} is the second coordinate of the only ordered pair in {f} whose first coordinate is {x}.

Examples

The set {\{(1,2), (2,4), (3,2), (5,8)\}} has the functional property, so it is the graph of a function. Call the function {H}. Then its domain is {\{1,2,3,5\}} and {H(1) = 2} and {H(2) = 4}. {H(4)} is not defined because there is no ordered pair in H beginning with {4} (hence {4} is not in {\text{dom } H}.)

I showed above that the graph of the function {G}, ordinarily described as “the function {G(x)={{x}^{2}}+2x+5}”, has the functional property. The specification of function requires that we say what the domain is and what the value is at each point. These two facts are determined by the graph.

Other definitions of function

Because of the examples above, many authors define a function as a graph with the functional property. Now, the graph of a function {G} may be denoted by {\Gamma(G)}.  This is an older, less strict definition of function that doesn’t work correctly with the concepts of algebraic topology, category theory, and some other branches of mathematics.

For this less strict definition of function, {G=\Gamma(G)}, which causes a clash of our mental images of “graph” and “function”. In every important way except the less-strict definition, they ARE different!

A definition is a device for making the meaning of math technical terms precise. When a mathematician think of “function” they think of many aspects of functions, such as a map of one shape into another, a graph in the real plane, a computational process, a renaming, and so on. One of the ways of thinking of a function is to think about its graph. That happens to be the best way to define the concept of function.  (It is the less strict definition and it is a necessary concept in the modern definition given here.)

The occurrence of the graph in either definition doesn’t make thinking of a function in terms of its graph the most important way of visualizing  it. I don’t think it is even in the top three.

Send to Kindle