Representations of functions III

Introduction to this post

I am writing a new abstractmath chapter called Representations of Functions. It will replace some of the material in the chapter Functions: Images, Metaphors and Representations. This post is a draft of the sections on representations of finite functions.

The diagrams in this post were created using the Mathematica Notebook Constructions for cographs and endographs of finite functions.nb.
You can access this notebook if you have Mathematica, which can be bought, but is available for free for faculty and students at many universities, or with Mathematica CDF Player, which is free for anyone and runs on Windows, Mac and Linux.

Like everything in abstractmath.org, the notebooks are covered by a Creative Commons ShareAlike 3.0 License.

Graphs of finite functions

When a function is continuous, its graph shows up as a curve in the plane or as a curve or surface in 3D space. When a function is defined on a set without any notion of continuity (for example a finite set), the graph is just a set of ordered pairs and does not tell you much.

A finite function $f:S\to T$ may be represented in these ways:

• Its graph $\{(s,f(s))|s\in S\}$. This is graph as a mathematical object, not as a drawing or as a directed graph — see graph (two meanings)).
• A table, rule or two-line notation. (All three of these are based on the same idea, but differ in presentation and are used in different mathematical specialties.)
• By using labels with arrows between them, arranged in one of two ways:
• A cograph, in which the domain and the codomain are listed separately.
• An endograph, in which the elements of the domain and the codomain are all listed together without repetition.

All these techniques can also be used to show finite portions of infinite discrete functions, but that possibility will not be discussed here.

Introductory Example

Let $\text{f}:\{a,b,c,d,e\}\to\{a,b,c,d\}$ be the function defined by requiring that $f(a)=c$, $f(b)=a$, $f(c)=c$, $f(d)=b$, and $f(e)=d$.

Graph

The graph of $f$ is the set
$(a,c),(b,a),(c,c),(d,b),(e,d)$
As with any set, the order in which the pairs are listed is irrelevant. Also, the letters $a$, $b$, $c$, $d$ and $e$ are merely letters. They are not variables.

Table

$\text{f}$ is given by this table:

This sort of table is the format used in databases. For example, a table in a database might show the department each employee of a company works in:

Rule

The rule determined by the finite function $f$ has the form

$(a\mapsto b,b\mapsto a,c\mapsto c,d\mapsto b,e\mapsto d)$

Rules are built in to Mathematica and are useful in many situations. In particular, the endographs in this article are created using rules. In Mathematica, however, rules are written like this:

$(a\to b,b\to a,c\to c,d\to b,e\to d)$

This is inconsistent with the usual math usage (see barred arrow notation) but on the other hand is easier to enter in Mathematica.

In fact, Mathematica uses very short arrows in their notation for rules, shorter than the ones used for the arrow notation for functions. Those extra short arrows don’t seems to exist in TeX.

Two-line notation

Two-line notation is a kind of horizontal table.

$\begin{pmatrix} a&b&c&d&e\\c&a&c&b&d\end{pmatrix}$

The three notations table, rule and two-line do the same thing: If $n$ is in the domain, $f(n)$ is shown adjacent to $n$ — to its right for the table and the rule and below it for the two-line.

Note that in contrast to the table, rule and two-line notation, in a cograph each element of the codomain is shown only once, even if the function is not injective.

Cograph

To make the cograph of a finite function, you list the domain and codomain in separate parallel rows or columns (even if the domain and codomain are the same set), and draw an arrow from each $n$ in the domain to $f(n)$ in the codomain.

This is the cograph for $\text{f}$, represented in columns

and in rows (note that $c$ occurs only once in the codomain)

Pretty ugly, but the cograph for finite functions does have its uses, as for example in the Wikipedia article composition of functions.

In both the two-line notation and in cographs displayed vertically, the function goes down from the domain to the codomain. I guess functions obey the law of gravity.

Rearrange the cograph

There is no expectation that in the cograph $f(n)$ will be adjacent to $n$. But in most cases you can rearrange both the domain and the codomain so that some of the structure of the function is made clearer; for example:

The domain and codomain of a finite function can be rearranged in any way you want because finite functions are not continuous functions. This means that the locations of points $x_1$ and $x_2$ have nothing to do with the locations of $f(x_1)$ and $f(x_2)$: The domain and codomain are discrete.

Endograph

The endograph of a function $f:S\to T$ contains one node labeled $s$ for each $s\in S\cup T$, and an arrow from $s$ to $s’$ if $f(s)=s’$. Below is the endograph for $\text{f}$.

The endograph shows you immediately that $\text{f}$ is not a permutation. You can also see that with whatever letter you start with, you will end up at $c$ and continue looping at $c$ forever. You could have figured this out from the cograph (especially the rearranged cograph above), but it is not immediately obvious in the cograph the way it in the endograph.

There are more examples of endographs below and in the blog post
A tiny step towards killing string-based math. Calculus-type functions can also be shown using endographs and cographs: See Mapping Diagrams from A(lgebra) B(asics) to C(alculus) and D(ifferential) E(quation)s, by Martin Flashman, and my blog posts Endographs and cographs of real functions and Demos for graph and cograph of calculus functions.

Example: A permutation

Suppose $p$ is the permutation of the set $\{0,1,2,3,4,5,6,7,8,9\}$given in two-line form by
$\begin{pmatrix} 0&1&2&3&4&5&6&7&8&9\\0&2&1&4&5&3&7&8&9&6\end{pmatrix}$

Endograph

Again, the endograph shows the structure of the function much more clearly than the cograph does.

The endograph consists of four separate parts (called components) not connected with each other. Each part shows that repeated application of the function runs around a kind of loop; such a thing is called a cycle. Every permutation of a finite set consists of disjoint cycles as in this example.

Disjoint cycle notation

Any permutation of a finite set can be represented in disjoint cycle notation: The function $p$ is represented by:

$(0)(1,2)(3,4,5)(6,7,8,9)$

Given the disjoint cycle notation, the function can be determined as follows: For a given entry $n$, $p(n)$ is the next entry in the notation, if there is a next entry (instead of a parenthesis). If there is not a next entry, $p(n)$ is the first entry in the cycle that $n$ is in. For example, $p(7)=8$ because $8$ is the next entry after $7$, but $p(5)=3$ because the next symbol after $5$ is a parenthesis and $3$ is the first entry in the same cycle.

The disjoint cycle notation is not unique for a given permutation. All the following notations determine the same function $p$:

$(0)(1,2)(4,5,3)(6,7,8,9)$
$(0)(1,2)(8,9,6,7)(3,4,5)$
$(1,2)(3,4,5)(0)(6,7,8,9)$
$(2,1)(5,3,4)(9,6,7,8)$
$(5,3,4)(1,2)(6,7,8,9)$

Cycles such as $(0)$ that contain only one element are usually omitted in this notation.

Example: A tree

Below is the endograph of a function $t:\{0,1,2,3,4,5,6,7,8,9\}\to\{0,1,2,3,4,5,6,7,8,9\}$

This endograph is a tree. The graph of a function $f$ is a tree if the domain has a particular element $r$ called the root with the properties that

• $f(r)=r$, and
• starting at any element of the domain, repreatedly applying $f$ eventually produces $r$.

In the case of $t$, the root is $4$. Note that $t(4)=4$, $t(t(7))=4$, $t(t(t(9)))=4$, $t(1)=4$, and so on.

The endograph

shown here is also a tree.

See the Wikipedia article on trees for the usual definition of tree as a special kind of graph. For reading this article, the definition given in the previous paragraph is sufficient.

The general form of a finite function

This is the endograph of a function $t$ on a $17$-element set:

It has two components. The upper one contains one $2$-cycle, and no matter where you start in that component, when you apply $t$ over and over you wind up flipping back and forth in the $2$-cycle forever. The lower component has a $3$-cycle with a similar property.

This illustrates a general fact about finite functions:

• The endograph of any finite function contains one or more components $C_1$ through $C_k$.
• Each component $C_k$ contains exactly one $n_k$ cycle, for some integer $n_k\geq 1$, to which are attached zero or more trees.
• Each tree in $C_k$ is attached in such a way that its root is on the unique cycle contained in $C_k$.

In the example above, the top component has three trees attached to it, two to $3$ and one to $4$. (This tree does not illustrate the fact that an element of one of the cycles does not have to have any trees attached to it).

You can check your understanding of finite functions by thinking about the following two theorems:

• A permutation is a finite function with the property that its cycles have no trees attached to them.
• A tree is a finite function that has exactly one component whose cycle is a $1$-cycle.

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

Send to Kindle

Representations of functions II

Introduction to this post

I am writing a new abstractmath chapter called Representations of Functions. It will replace some of the material in the chapter Functions: Images, Metaphors and Representations.

This post includes a draft of the introduction to the entire new chapter (immediately below) and of the sections on graphs of continuous functions of one variable with values in the plane and in 3-space. Later posts will concern multivariable continuous functions and finite discrete functions.

Introduction to the new Chapter

Functions can be represented visually in many different ways. There is a sharp difference between representing continuous functions and representing discrete functions.

For a continuous function $f$, $f(x)$ and $f(x’)$ tend to be close together when $x$ and $x’$ are close together. That means you can represent the values at an infinite number of points by exhibiting them for a bunch of close-together points. Your brain will automatically interpret the points nearby that are not represented.

Nothing like this works for discrete functions. Many different arrangements of the inputs and outputs can be made. Different arrangements may be useful for representing different properties of the function.

Illustrations

The illustrations were created using these Mathematica Notebooks:

These notebooks contain many more examples of the ways functions can be represented than are given in this article. The notebooks also contain some manipulable diagrams which may help you understand the diagrams. In addition, all the 3D diagrams can be rotated using the cursor to get different viewpoints. You can access these tools if you have Mathematica, which is available for free for faculty and students at many universities, or with Mathematica CDF Player, which runs on Windows, Mac and Linux.

Like everything in abstractmath.org, the notebooks are covered by a Creative Commons ShareAlike 3.0 License.

Functions from a subset of $\mathbb{R}$ to $\mathbb{R}\times\mathbb{R}$

Suppose $F:\mathbb{R}\to\mathbb{R}\times\mathbb{R}$. That means you put in one number and get out a pair of numbers.

The unit circle

An example is the unit circle, which is the graph of the function $t\mapsto(\cos t,\sin t)$. That has this parametric plot:

Because $\cos^2 t+\sin^2 t=1$, every real number $t$ produces a point on the unit circle. Four point are shown. For example,$(\cos\pi,\,\sin\pi)=(-1,0)$ and
$(\cos(5\pi/3),\,\sin(5\pi/3))=(\frac{1}{2},\frac{\sqrt3}{2})\approx(.5,.866)$

$t$ as time

In graphing functions $f:\mathbb{R}\to\mathbb{R}$, the plot is in two dimensions and consists of the points $(x,f(x))$: the input and the output. The parametric plot shown above for $t\mapsto(\cos^2 t+\sin^2)$ shows only the output points $(\cos t,\sin t)$; $t$ is not plotted on the graph at all. So the graph is in the plane instead of in three-dimensional space.

An alternative is to use time as the third dimension: If you start at some number $t$ on the real line and continually increase it, the value $f(t)$ moves around the circle counterclockwise, repeating every $2\pi$ times. If you decrease $t$, the value moves clockwise. The animated gif circlemovie.gif shows how the location of a point on the circle moves around the circle as $t$ changes from $0$ to $2\pi$. Every point is traversed an infinite number of times as $t$ runs through all the real numbers.

The unit circle with $t$ made explicit

Since we have access to three dimensions, we can show the input $t$ explicitly by using a three-dimensional graph, shown below. The blue circle is the function $t\mapsto(\cos t,\sin t,0)$ and the gold helix is the function $t\mapsto(\cos t,\sin t,.2t)$.

The introduction of $t$ as the value in the vertical direction changes the circle into a helix. The animated .gif covermovie.gif shows both the travel of a point on the circle and the corresponding point on the helix.

As $t$ changes, the circle is drawn over and over with a period of $2\pi$. Every point on the circle is traversed an infinite number of times as $t$ runs through all the real numbers. But each point on the helix is traversed exactly once. For a given value of $t$, the point on the helix is always directly above or below the point on the circle.

The helix is called the universal covering space of the circle, and the set of points on the helix over (and under) a particular point $p$ on the circle is called the fiber over $p$. The universal cover of a space is a big deal in topology.

Figure-8 graph

This is the parametric graph of the function $t\mapsto(\cos t,\sin 2t)$.

Notice that it crosses itself at the origin, when $t$ is any odd multiple of $\frac{\pi}{2}$.

Below is the universal cover of the Figure-8 graph. As you can see, the different instances of crossing at $(0,0)$ are separated. The animated.gif Fig8movie shows the paths taken as $t$ changes on the figure 8 graph and on its universal cover

Functions from a subset of $\mathbb{R}$ to $\mathbb{R}\times\mathbb{R}\times\mathbb{R}$

The graph of a function from a subset of $\mathbb{R}$ to $\mathbb{R}\times\mathbb{R}\times\mathbb{R}$ can also be drawn as a parametric graph in three-dimensional space, giving a three-dimensional curve. The trick that I used in the previous section of showing the input parameter so that you can see the universal cover won’t work in this case because it would require four dimensions.

Universal covers

The gold curves in the figures for the universal covers of the circle and the figure 8 are examples of functions from $\mathbb{R}$ to $\mathbb{R}\times\mathbb{R}\times\mathbb{R}$.

The seven-pointed crown

Here are views from three different angles of the graph of the function $t\mapsto(\cos t, \sin t, \sin 7t)$:

The animated gif crownmovie.gif represents the parameter $t$ in time.

Another curve in space

Below are two views of the curve defined by $t\mapsto({-4t^2+53t)/18,t,.4(-t^2+1-10t)}$.

The following plots the $x$-curve $-4t^2+53t)/18$ gold in the $yz$ plane and the $z$ curve $.4(-t^2+1-10t)$ in the $xy$ plane. The first and third views are arranged so that you see the curve just behind one of those two planes.

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

Send to Kindle

Representations of functions I

Introduction to this post

I am writing a new abstractmath chapter called Representations of Functions. It will replace some of the material in the chapter Functions: Images, Metaphors and Representations.

This post includes a draft of the introduction to the new chapter (immediately below) and of the section Graphs of continous functions of one variable. Later posts will concern multivariable continuous functions, probably in two or three sections, and finite discrete functions.

Introduction to the new abstractmath chapter on representations of functions

Functions can be represented visually in many different ways. There is a sharp difference between representing continuous functions and representing discrete functions.

For a continuous function $f$, $f(x)$ and $f(x’)$ tend to be close together when $x$ and $x’$ are close together. That means you can represent the values at an infinite number of points by exhibiting them for a bunch of close-together points. Your brain will automatically interpret the points nearby that are not represented.

Nothing like this works for discrete functions. As you will see in the section on discrete functions, many different arrangements of the inputs and outputs can be made. In fact, different arrangements may be useful for representing different properties of the function.

Illustrations

The illustrations were created using these Mathematica Notebooks:

These notebooks contain many more examples of the ways functions can be represented than are given in this article. The notebooks also contain some manipulable diagrams which may help you understand the diagrams. In addition, all the 3D diagrams can be rotated using the cursor to get different viewpoints. You can access these tools if you have Mathematica, which is available for free for faculty and students at many universities, or with Mathematica CDF Player, which runs on Windows, Mac and Linux.

Like everything in abstractmath.org, the notebooks are covered by a Creative Commons ShareAlike 3.0 License.

Graphs of continous functions of one variable

The most familiar representations of continuous functions are graphs of functions with one real variable. Students usually first see these in secondary school. Such representations are part of the subject called Analytic Geometry. This section gives examples of such functions.

There are other ways to represent continuous functions, in particular the cograph and the endograph. These will be the subject of a separate post.

The graph of a function $f:S\to T$ is the set of ordered pairs $\{(x,f(x))\,|\,x\in S\}$. (More about this definition here.)

In this section, I consider continuous functions for which $S$ and $T$ are both subsets of the real numbers. The mathematical graph of such a function are shown by plotting the ordered pairs $(x,f(x))$ as points in the two-dimensional $xy$-plane. Because the function is continuous, when $x$ and $x’$ are close to each other, $f(x)$ and $f(x’)$ tend to be close to each other. That means that the points that have been plotted cause your brain to merge together into a nice curve that allows you to visualize how $f$ behaves.

Example

This is a representation of the graph of the curve $g(x):=2-x^2$ for approximately the interval $(-2,2)$. The blue curve represents the graph.

The brown right-angled line in the upper left side, for example, shows how the value of independent variable $x$ at $(0.5)$ is plotted on the horizontal axis, and the value of $g(0.5)$, which is $1.75$, is plotted on the vertical axis. So the blue graph contains the point $(0.5,g(0.5))=(0.5,1.75)$. The animated gif upparmovie.gif shows a moving version of how the curve is plotted.

Fine points

• The mathematical definition of the graph is that it is the set $\{(x,2-x^2)\,|\,x\in\mathbb{R}\}$. The blue curve is not, of course, the mathematical graph, it represents the mathematical graph.
• The blue curve consists of a large but finite collection of pixels on your screen, which are close enough together to appear to form a continuous curve which approximates the mathematical graph of the function.
• Notice that I called the example the “representation of the graph” instead of just “graph”. That maintains the distinction between the mathematical ordered pairs $(x,g(x))$ and the pixels you see on the screen. But in fact mathe­maticians and students nearly always refer to the blue line of pixels as the graph. That is like pointing to a picture of your grandmother and saying “this is my grandmother”. There is nothing wrong with saying things that way. But it is worth understanding that two different ideas are being merged.

Discontinuous functions

A discontinuous function which is continuous except for a small finite number of breaks can also be represented with a graph.

Example

Below is the function $f:\mathbb{R}\to\mathbb{R}$ defined by
f(x):=\left\{ \begin{align} 2-x^2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(x\gt0) \\ 1-x^2\,\,\,\,\,\,(-1\lt x\lt 0) \\ 2-x^2\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(x\lt-1) \end{align}\right.

Example

The Dirichlet function is defined by
$F(x):= \begin{cases} 1 & \text{if }x\text{ is rational}\\ \frac{1}{2} & \text{if }x\text{ is irrational}\\ \end{cases}$  for all real $x$.

The abmath article Examples of functions spells out in detail what happens when you try to draw this function.

Graphs can fool you

The graph of a continuous function cannot usually show the whole graph, unless it is defined only on a finite interval. This can lead you to jump to conclusions.

Example

For example, you can’t tell from the the graph of the function $y=2-x^2$ whether it has a local minimum (because the graph does not show all of the function), although you can tell by using calculus on the formula that it does not have one. The graph looks like it might have a vertical asymptotes, but it doesn’t, again as you can tell from the formula.

Discovering facts about a function
by looking at its graph
is useful but dangerous.

Example

Below is the graph of the function
$f(x)=.0002{{\left( \frac{{{x}^{3}}-10}{3{{e}^{-x}}+1} \right)}^{6}}$

If you didn’t know the formula for the function (but know it is continuous), you could still see that it has a local maximum somewhere to the right of $x=1$. It looks like it has one or more zeroes around $x=-1$ and $x=2$. And it looks like it has an asymptote somewhere to the right of $x=2.5$.

If you do know the formula, you can find out many things about the function that you can’t depend on the graph to see.

• You can see immediately that $f$ has a zero at $x=\sqrt[3]{10}$, which is about $2.15$.
• If you notice that the denominator is positive for all $x$, you can figure out that
• $\sqrt[3]{10}$ is the only root.
• $f(x)\geq0$ for all $x$.
• $f$ has an asymptote as $x\to-\infty$ (use L’Hôpital).
• Numerical analysis (I used Mathematica) shows that $f'(x)$ has two zeros, at $\sqrt[3]{10}$ and at about $x=1.1648$. $f”(1.1648)$ is about $-10.67$ , which strongly suggests that $f$ has a local max near $1.1648$, consistent with the graph.
• Since $f$ is defined for every real number, it can’t have a vertical asymptote anywhere. The graph looks like it becomes vertical somewhere to the right of $x=2.4$, but that is simply an illustration of the unbelievably fast growth of any exponential function.
• The section on Zooming and Chunking gives other details.

Acknowledgments

Sue VanHattum.

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

Send to Kindle

Recent revisions to abstractmath.org

For the last six months or so I have been systematically going through the abstractmath.org files, editing them for consistency, updating them, and in some cases making major revisions.

In the past I have usually posted revised articles here on Gyre&Gimble, but WordPress makes it difficult to simply paste the HTML into the WP editor, because the editor modifies the HTML and does things such as recognizing line breaks and extra spaces which an HTML interpreters is supposed to ignore.

Here are two lists of articles that I have revised, with links.

Other recent changes

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

Send to Kindle

Proofs using diagrams

Introduction

This post gives a proof of an easy theorem in category theory using the graph-based logic approach of Graph based logic and sketches, (GBLS) by Atish Bagchi and me.

Formal logic is typically defined in terms of formulas and terms, defined recursively as strings of characters, together with rules of inference. GBLS proposes a new approach to logic where diagrams are used instead of strings of characters. The exposition here spells out the proof in more detail than GBLS does and uses various experimental ways of drawing diagrams using Mathematica.

To follow this proof, you need to be familiar with basic category theory. Most special definitions that are needed are defined in this post where they are first used. Section 1 of GBLS also gives the definitions you need with more context.

The theorem

The Theorem to be proved (it is Theorem 8.3.1 of GBLS) says that, in any category, if the triangles in the diagram below commute, then the outside square commutes. This is easy using the associative law: If $xf=h$ and $kx=g$, then $kh=k(xf)=(kx)f=gf$.

Subject Diagram

So what?

This theorem is not interesting. The point of this post is to present a new approach to proving such theorems, using diagrams instead of strings. The reason that exhibiting the dig
rammatic proof is interesting is that many different kinds of categories have a FL cattheory, including these:

Essentially algebraic string-based logic is described in detail in Partial Horn logic and cartesian categories, by E. Palmgren and Steven Vickers.

Commercial

My concept of form in A generalization of the concept of sketch generalizes sketches to all the categories that can be defined as models of FL cattheories. So the method of proof using diagrams can be applied to theorems about the objects defined by forms.

Concepts needed for the graph-based proof

To prove the theorem, I will make use of $\mathbf{ThCat}$, the FL cattheory for categories.

• An FL category is a category with all finite limits.
• GLBS uses the word cattheory for what Category theory for computing science and Toposes, triples and theories call the theory of a sketch.
• In many books and articles, and in nLab, a “sketch” is what we call the cattheory (or the theory) of a sketch. For us, the sketch is a generating collection of objects, arrows, diagrams, cones and cocones for the cattheory. The category of models of the sketch and the cattheory are equivalent.
• $\mathbf{ThCat}$ is a category with finite limits freely generated by certain designated objects, arrows, commutative diagrams and limit cones, listed below.
• A model of $\mathbf{ThCat}$ in $\mathbf{Set}$ (the category of sets, whichever one you like) is an FL functor $\mathfrak{C}:\mathbf{ThCat}\to\mathbf{Set}.$
• Such a model $\mathfrak{C}$ is a small category, and every small category is such a model. If this statement worries you, read Section 3.4 of GBLS.
• Natural transformations between models are FL-preserving functors that preserve the structure on the nose.
• The category of models of $\mathbf{ThCat}$ in $\mathbf{Set}$ is equivalent to the category of small categories and morphisms, which, unlike the category of models, includes functors that don’t preserve things on the nose.
• $\mathbf{ThCat}$ is an example of the theory of an FL sketch. Chapter 4 of GBLS describes this idea in detail. The theory has the same models as the sketch.
• The sketch generating $\mathbf{ThCat}$ is defined in detail in section 7.2 of GBLS.

Some objects and arrows of $\mathbf{ThCat}$

I will make use of the following objects and arrows that occur in $\mathbf{ThCat}.$ A formal thing is a construction in $\mathbf{ThCat}$ that becomes an actual thing in a model. So for example a model $\mathfrak{C}$ of $\mathbf{ThCat}$ in $\mathbf{Set}$ is an actual (small) category, and $\mathfrak{C}(\mathsf{ar_2})$ is the set of all composable pairs of arrows in the category $\mathfrak{C}$.

• $\mathsf{ob}$, the formal set of objects.
• $\mathsf{ar}$, the formal set of arrows.
• $\mathsf{ar}_2$, the formal set of composable pairs of arrows.
• $\mathsf{ar}_3$, the formal set of composable triples of arrows.
• $\mathsf{unit} : \mathsf{ob}\to \mathsf{ar}$ that formally picks out the identity arrow of an object.
• $\mathsf{dom},\mathsf{cod} : \mathsf{ar}\to \mathsf{ob}$ that formally pick out the domain and codomain of an arrow.
• $\mathsf{comp} : \mathsf{ar}_2\to \mathsf{ar}$ that picks out the composite of a composable pair.
• $\mathsf{lfac}, \mathsf{rfac} :\mathsf{ar}_2\to \mathsf{ar}$ that pick out the left and right factors in a composable pair.
• $\mathsf{lfac}, \mathsf{mfac},\mathsf{rfac} :\mathsf{ar}_3 \to\mathsf{ar}$ that pick out the left, middle and right factors in a composable triple of arrows.
• $\mathsf{lass}, \mathsf{rass} : \mathsf{ar}_3 \to \mathsf{ar}_2$: $\mathsf{lass}$ formally takes $\langle{h,g,f}\rangle$ to $\langle{hg,f}\rangle$ and $\mathsf{rass}$ takes it to $\langle{h,gf}\rangle$.

$\mathsf{ob}$, $\mathsf{ar}$, $\mathsf{unit}$, $\mathsf{dom}$, $\mathsf{cod}$ and $\mathsf{comp}$ are given primitives and the others are defined as limits of finite diagrams composed of those objects. This is spelled out in Chapter 7.2 of GBLS. The definition of $\mathbf{ThCat}$ also requires certain diagrams to be commutative. They are all provided in GBLS; the one enforcing associativity is shown later in this post.

Color coding

I will use color coding to separate syntax from semantics.

• Syntax consists of constructions in $\mathbf{ThCat}.$ The description will always be a commutative diagram in black, with annotations as explained later.
• The limit of the description will be an object in $\mathbf{ThCat}$ (the form) whose value in a model $\mathfrak{C}$ will be shown in green, because being an element of the value of a model makes it semantics.
• When a limit cone is defined, the projections (which are arrows in $\mathbf{ThCat}$) will be shown in blue.

Descriptions

In graph-based logic, a type of construction that can be made in a category has a description, which (in the case of our Theorem) is a finite diagram in $\mathbf{ThCat}$. The value of the limit of the description in a model $\mathfrak{C}$ is the set of all instances of that type of construction in $\mathfrak{C}$.

The Subject Diagram

• This diagram is the subject matter of the Theorem. It is not assumed to be commutative.
• As in most diagrams in category theory texts, the labels in this diagram are variables, so the diagram is implicitly universally quantified. The Subject Diagram is a generic diagram of its shape.
• “Any diagram of its shape” includes diagrams in which some of the nodes may represent the same object. An extreme example is the graph in which every node is an object $\mathsf{E}$ and every arrow is its identity arrow. The diagram below is nevertheless an example of the Subject Diagram:
• Shapes of diagrams are defined properly in Section 2.3 of
GBLS and in Section 4.1 of Category Theory for Computing Science.

The description of the Subject Diagram

Diagram SDD below shows the Subject Diagram as the limit of its description. The description is the black diagram.

Diagram SDD

Definition of $\mathsf{ar}_2$

The object $\mathsf{ar}_2$ of composable pairs of arrows is defined as a pullback:

In the usual categorical notation this would be shown as

This makes use of the fact that the unnamed blue arrow is induced by the other two projection arrows. In the rest of the post, projection arrows that are induced are normally omitted.

An enrichment of the description

Because $\mathsf{ar}_2$ is defined as a pullback, we can enrich the description of Diagram SDD by adjoining two pullbacks as shown below. This is Diagram 8.10 in GBLS. The enriched diagram has the same limit as the description of Diagram SDD.

Enriched Diagram SDD

Note that the projections from the limit to the two occurrences of $\mathsf{ar}_2$ induce all the other projections. This follows by diagram chasing; remember that the description must be a commutative diagram.

Make the triangles commute

To make the triangles commute, we add two comp arrows to the enriched diagram as shown below. These two arrows are not induced by the description; they are therefore additions to the description — they describe a more restrictive (green) diagram with commutative triangles and so are shown in black.

Diagram TC: The triangles commute

The left comp makes $xf=h$ and the right comp makes $kx=g$.

The outside square commutes

Now we enrich Diagram TC with four objects, <comp,id>, <id,comp> and three comp arrows as shown in bolder black. These objects and arrows already exist in $\mathbf{ThCat}$ and therefore do not change the limit, which must be the same as the limit of Diagram TC.

The outside square commutes

The diagram in bold black is exactly the commutative diagram that requires associativity for these particular objects and arrows, which immediately implies that $gf=kh$, as the Theorem requires.

By the definitions of $\mathsf{ar_2}$ and $\mathsf{ar_3}$, the part of the description in bold black induces the rest of the diagram. Omitting the rest of the diagram would make $\mathsf{ar_2}$ and $\mathsf{ar_3}$ modules in the sense of GBLS, Chapter 7.4. Modules would be vital to deal with proofs more complicated than the one given here.

References

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

Send to Kindle

Improving abstractmath.org

This post discusses some ideas I have for improving abstractmath.org.

Handbook of mathematical discourse

The Handbook was kind of a false start on abmath, and is the source of much of the material in abmath. It still contains some material not in abmath, parti­cularly the citations.

By citations I mean lexicographical citations: examples of the usage from texts and scholarly articles.

I published the Handbook of mathe­ma­tical discourse in 2003. The first link below takes you to an article that describes what the Handbook does in some detail. Briefly, the Handbook surveys the use of language in math (and some other things) with an emphasis on the problems it causes students. Its collection of citations of usage could some day could be the start of an academic survey of mathematical language. But don’t expect me to do it.

Links

The Handbook exists as a book and as two different web versions. I lost the TeX source of the Handbook a few years after I published the book, so none of the different web versions are perfect. Version 2 below is probably the most useful.

1. Handbook of mathe­ma­tical discourse. Description.
2. Handbook of mathe­ma­tical discourse. Hypertext version without pictures but with active internal links. Some links don’t work, but they won’t be repaired because I have lost the TeX input files.
3. Handbook of mathe­ma­tical discourse. Paperback.
4. Handbook of mathematical discourse. PDF version of the printed book, including illustrations and citations but without hyperlinks.
5. Citations for the paperback version of the Handbook. (The hypertext version and the PDF version include the citations.)

Abmath

Soon after the Handbook was published, I started work on abstractmath.org, which I abbreviate as abmath. It is intended specifically for people beginning to study abstract math, which means roughly post-calculus. I hope their teachers will read it, too. I had noticed when I was teaching that many students hit a big bump when faced with abstraction, and many of them never recovered. They would typically move into another field, often far away from STEM stuff.

Links

These abmath articles give more detail about the purpose of this website and the thinking behind the way it is presented:

Presentation of abmath

Informal

Abmath is written for students of abstract math and other beginners to tell them about the obstacles they may meet up with in learning abstract math. It is not a scholarly work and is not written in the style of a scholarly work. There is more detail about its style in my rant in Attitude.

Scholarly works should not be written in the style of a scholarly work, either.

To do:

Every time I revise an article I find myself rewriting overly formal parts. Fifty years of writing research papers has taken its toll. I must say that I am not giving this informalization stuff very high priority, but I will continue doing it.

No citations

One major difference concerns the citations in the Handbook. I collected these in the late nineties by spending many hours at Jstor and looking through physical books. When I started abmath I decided that the website would be informal and aimed at students, and would contain few or no citations, simply because of the time it took to find them.

Boxouts and small screens

The Handbook had both sidebars on every page of the paper version containing a reference index to words on that page, and also on many pages boxouts with comments. It was written in TeX. I had great difficulty using TeX to control the placement of both the sidebars and especially the boxouts. Also, you couldn’t use TeX to let the text expand or contract as needed by the width of the user’s screen.

Abmath uses boxouts but not sidebars. I wrote Abmath using HTML, which allows it to be presented on large or small screens and to have extensive hyperlinks.
HTML also makes boxouts easy.

The arrival of tablets and i-pods has made it desirable to allow an abmath page to be made quite narrow while still readable. This makes boxouts hard to deal with. Also I have gotten into the habit of posting revisions to articles on Gyre&Gimble, whose editor converts boxouts into inline boxes. That can probably be avoided.

To do:

I have to decide whether to turn all boxouts into inline small-print paragraphs the was you see them in this article. That would make the situation easier for people reading small screens. But in-line small-print paragraphs are harder to associate to the location you want them to refer, in contrast to boxouts.

Abmath 2.0

For the first few years, I used Microsoft Word with MathType, but was plagued with problems described in the link below. Then I switched to writing directly in HTML. The articles of abmath labeled “abstractmath.org 2.0” are written in this new way. This makes the articles much, much easier to update. Unfortunately, Word produces HTML that is extraordinarily complicated, so transforming them into abmath 2.0 form takes a lot of effort.

Illustrations

Abmath does not have enough illustrations and diagrams. Gyre&Gimble has many posts with static illustrations, some of them innovative. It also has some posts with interactive demos created with Mathematica. These demos require the reader to download the CDF Player, which is free. Unfortunately, it is available only for Windows, Mac and Linux, which precludes using them on many small devices.

To do:

• Create new illustrations where they might be useful, and mine Gyre&Gimble and other sources.
• There are many animated GIFs out there in the math cloud. I expect many of them are licensed under Creative Commons so that I can use them.
• I expect to experiment with converting some of the interactive CFD diagrams that are in Gyre&Gimble into animated GIFs or AVIs, which as far as I know will run on most machines. This will be a considerable improvement over static diagrams, but it is not as good as interactive diagrams, where you can have several sliders controlling different variables, move them back and forth, and so on. Look at Inverse image revisited. and “quintic with three parameters” in Demos for graph and cograph of calculus functions.

Abmath content

Language

Abmath includes most of the ideas about language in the Handbook (rewritten and expanded) and adds a lot of new material.

Links

1. The languages of math. Article in abmath. Has links to the other articles about language.
2. Syntactic and semantic thinkers. Gyre&Gimble post.
3. Syntax trees in mathematicians’ brains. Gyre&Gimble post.
4. A visualization of a computation in tree form.Gyre&Gimble post.
5. Visible algebra I. Gyre&Gimble post.
6. Algebra is a difficult foreign language. Gyre&Gimble post.
7. Presenting binops as trees. Gyre&Gimble post.
8. Moths to the flame of meaning. How linguistics students also have trouble with syntax.
9. Varieties of mathematical prose, by Atish Bagchi and Charles Wells.

To do:

The language articles would greatly benefit from more illustrations. In parti­cular:

• G&G contains several articles about using syntax trees (items 3, 4, 5 and 7 above) to understand algebraic expressions. A syntax tree makes the meaning of an algebraic expression much more transparent than the usual one-dimensional way of writing it.
• Several items in the abmath article More about the language of math, for example the entries on parenthetic assertions and postconditions could benefit from a diagrammatic representation of the relation between phrases in a sentence and semantics (or how the phrases are spoken).
• The articles on Names and Alphabets could benefit from providing spoken pronunciations of many words. But what am I going to do about my southern accent?
• The boxed example of change in context as you read a proof in More about the language of math could be animated as you click through the proof. *Sigh* The prospect of animating that example makes me tired just thinking about it. That is not how grasshoppers read proofs anyway.

Understanding and doing math

Abmath discusses how we understand math and strategies for doing math in some detail. This part is based on my own observations during 35 years of teaching, as well as extensive reading of the math ed literature. The math ed literature is usually credited in footnotes.

Math objects and math structures

Understanding how to think about mathematical objects is, I believe, one of the most difficult hurdles newbies have to overcome in learning abstract math. This is one area that the math ed community has focused on in depth.

The first two links below are take you to the two places in abmath that discuss this problem. The first article has links to some of the math ed literature.

To do: Everything is a math object

An important point about math objects that needs to be brought out more is that everything in math is a math object. Obviously math structures are math objects. But the symbol “$\leq$” in the statement “$35\leq45$” denotes a math object, too. And a proof is a math object: A proof written on a blackboard during a lecture does not look like it is an instance of a rigorously defined math object, but most mathe­maticians, including me, believe that in principle such proofs can be transformed into a proof in a formal logical system. Formal logics, such as first order logic, are certainly math objects with precise mathematical definitions. Definitions, math expressions and theorems are math objects, too. This will be spelled out in a later post.

To do: Bring in modern ideas about math structure

Classically, math structures have been presented as sets with structure, with the structure being described in terms of subsets and functions. My chapter on math structures only waves a hand at this. This is a decidedly out-of-date way of doing it, now that we have category theory and type theory. I expect to post about this in order to clarify my thinking about how to introduce categorical and type-theoretical ideas without writing a whole book about it.

Particular math structures

Abmath includes discussions
of the problems students have with certain parti­cular types of structures. These sections talk mostly about how to think about these structure and some parti­cular misunder­standings students have at the most basic levels.

These articles are certainly not proper intro­ductions to the structures. Abmath in general is like that: It tells students about some aspects of math that are known to cause them trouble when they begin studying abstract math. And that is all it does.

To do:

• I expect to write similar articles about groups, spaces and categories.
• The idea about groups is to mention a few things that cause trouble at the very beginning, such as cosets, quotients and homomorphisms (which are all obviously related to each other), and perhaps other stumbling blocks.
• With categories the idea is to stomp on misconceptions such as that the arrows have to be functions and to emphasize the role of categories in allowing us to define math structures in terms of their relations with other objects instead of in terms with sets.
• I am going to have more trouble with spaces. Perhaps I will show how you can look at the $\epsilon$-$\delta$ definition of continuous functions on the reals and “discover” that they imply that inverse images of open sets are open, thus paving the way for the family-of-subsets definition of a topoogy.
• I am not ruling out other particular structures.

Proofs

This chapter covers several aspects of proofs that cause trouble for students, the logical aspects and also the way proofs are written.

It specifically does not make use of any particular symbolic language for logic and proofs. Some math students are not good at learning languages, and I didn’t see any point in introducing a specific language just to do rudimentary discussions about proofs and logic. The second link below discusses linguistic ability in connection with algebra.

I taught logic notation as part of various courses to computer engineering students and was surprised to discover how difficult some students found using (for example) $p+q$ in one course and $p\vee q$ in another. Other students breezed through different notations with total insouciance.

To do:

Much of the chapter on proofs is badly written. When I get around to upgrading it to abmath 2.0 I intend to do a thorough rewrite, which I hope will inspire ideas about how to conceptually improve it.

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

Send to Kindle

Inverse image demo revisited

This post is an update of the post Demonstrating the inverse image of a function.

To manipulate the demos in this post, you must have Wolfram CDF Player installed on your computer. It is available free from the Wolfram website. CDF Player works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome.

The code for the demos, with some explanatory remarks, is in the file InverseImage.nb on my ,Mathematica website. That website also includes some other examples as .cdf files.

If the diagrams don’t appear, or appear but show pink diagrams, or if the formulas in the text are too high or too low, refresh the screen.

• The vertical red interval has the horizontal green interval(s) as inverse image.
• You can move the sliders back and forth to move to different points on the curve. The sliders control the vertical red interval. $a$ is the lower point of the vertical red line and $b$ is the upper point.
• As you move the sliders back and forth you will see the inverse image breaking up into a disjoint union in intervals, merging into a single interval, or disappearing entirely.
• The arrow at the upper right makes it run automatically.
• If you are using Mathematica, you can enter values into the boxes, but if you are using CDF Player, you can only change the number using the slider or the plus and minus incrementers.

This is the graph of $y=x^2-1$.

The graph of $-.5 + .5 x + .2 x^2 – .19 x^3 – .015 x^4 + .01 x^5$

The graph of the rational function $0.5 x+\frac{1.5 \left(x^4-1\right)}{x^4+1}$

The graph of a straight line whose slope can be changed. You can design demos of other functions with variable parameters.

The graph of the sine function. The other demos were coded using the Mathematica Reduce function to get the inverse image. This one had to be done in an ad hoc way as explained in the InverseImage.nb file.

Send to Kindle

Writing math for the web

Abstractmath

I built my website abstractmath.org during the years 2002 through 2006. After that I made sporadic changes, but medical operations and then teaching courses as an adjunct for a couple of years kept me from making much progress until 2010.

This post is an explanation of the tools I used for abstractmath, what went right and what went wrong, and my plans for redoing the website.

Methodology

My previous experience in publishing math was entirely with TeX. When I began work on abstractmath, I wanted to produce html files, primarily because they refloated the text when the window width changed. I was thinking of small screens and people wanting to look at several windows at once.

In those days, there was no method of starting with a LaTeX input file and producing an html file that preserved all the math and all the formatting. I have over the years spent many hours trying out various systems that claimed to do it and not found one that did not require major massaging to get the look I wanted. Most of them can cannot implement all LaTeX commands, or even most of the LaTeX formatting commands. (I have not looked at any of these since 2011.)

In contrast, systems such as PDFTeX turn even very complicated (in formatting and in math) LaTeX files into nearly perfect PDF files. Unfortunately, PDF files are a major impediment to having several windows open at once.

Word and MathType

My solution was to write abstractmath articles using Microsoft Word with MathType, which provides a plugin for Word.

The MathType interface was a very useful expansion of the Equation Editor in Word, and it produced little .gif files that were automatically inserted into the text. MathType also provided a command to create an html file. This file was produced with the usual “_files” folder that contained all the illustrations I had included as well as all the .gif files that MathType created. The html file contained code that put each .gif file in the right place in the typeset text.

That combination worked well. Using Word allowed me tight control over formatting and allowed floating textboxes, which I used freely. They very nicely moved around when you changed the width of the window.

I had used textboxes in my book A Handbook of Mathematical Discourse for apt quotations, additional comments, and (very clever if I say so myself) page indexes. The Handbook is available in several ways:

• Amazon. The citations are not included.
• The Handbook in paper form. A pdf file showing the book as it appears on paper (all the illos, textboxes and page indexes, no hyperlinks), plus all the citations. (This paragraph was modified on 2013-05-02).
• A version with hyperlinks, This includes the citations but omits the boxes and the illustrations, and it has hyperlinks to the citations. The page indexes are replaced by internal hyperlinks.
• The citations.

That book was written in TeX with much massaging using AWK commands. Boxes are much easier to do in Word than they are in TeX, and the html files produced by MathType preserved them quite well. The abmath article on definitions shows boxes used both for side comments and for quotations.

There were some problems with using MathType and Word together. In particular, a longish article would have dozens or hundreds of .gif files, which greatly slowed down uploading via ftp. I now have WebDrive (thanks to CWRU) and that may make it quicker.

Rot sets in

Without my doing anything at all, the articles on abstractmath began deteriorating. This had several main causes.

• Html was revised over time. Currently it is HTML5.0.
• Browsers changed way they rendered the html. And they had always differed among themselves in some situations.
• Microsoft Word changed the way it generated html.

Two of the more discouraging instances of rot were:

• Many instances of math formulas are now out of line with the surrounding text. This happened without my doing anything. It varies by browser and by when I last revised the article.
• Some textboxes deteriorated. In particular, textboxes generated by newer versions of Word were sometimes nearly illegible. Part of the reason for this is that Word started saving them as images.

Failed Forays

The main consequence of all this was that I was afraid of trying to revise articles (or complete them) because it would make them harder to read or ugly. So I set out to find new ways to produce abmath articles. This has taken a couple of years, while abmath is a big mess sprawling there on its website. A mostly legible big mess, and most of the links work, but frustrating to its appearance-sensitive author.

Automatically convert to a new system

My first efforts were to find another system with the property that I could convert my present Word files or html files to the new system without much hand massaging.

I tried converting the Word files to LaTeX input. This was made easier (I thought) because MathType now provided a means for turning all the MathType itty bitty .gif files into LaTeX expressions. I wrote Word macros to convert much of the formatting (italics, bold, subheads, purple prose, and so on) into LaTeX formatting — although I did have to go through the Word text, select each specially formatted piece, and apply the correct macro.

But I had other problems.

• Converting the Mathype images files to LaTeX caused problems because it messed up the spaces before and after the formulas.
• I worked with great sweat and tears to write a macro to extract the addresses from the links — and failed. If I had presevered I probably would have learned how to do it, and learned a lot of Word macros programming in the process.

The automatic conversion process appeared to require more and more massaging.

I made some attempts at automatically converting the html files that Word generates (instead of the doc files), but they are an enormous mess. They insert a huge amount of code (especialy spans) into the text, making it next to impossible to read the code or find anything.

It was beginning to look like I would have to go to an entirely new system and rewrite all the articles from scratch. This was attractive in one respect: in writing this blog my style has changed and I was seeing lots of things I would say or do differently. I have also changed my mind about the importance of some things, and abmath now has stubs and incomplete articles that ought to be eliminated with references to Wikipedia.

Go for rewriting

Meanwhile, I was having trouble with Gyre&Gimble. The WordPress editor works pretty well, but two new products came along:

• MathJax was introduced, providing a much better way to use TeX to insert formulas. (Note: MathType recently implemented the use of MathJax into its html output.)

• Mathematica CDF files, which are interactive diagrams that can be inserted directly into html. (My post Improved Clouds has examples.)

Both MathJax and CDF Player require entering links directly in the html code the WordPress editor produces. The WordPress editor trashed the html code I had entered every time I switched back and forth between “visual” (wysiwyg) and html.

I switched to CKEdit, which preserved the html but has a lot of random behavior. I learned to understand some of the behavior but finally gave up. I started writing my blogs in html using the Coffee Cup HTML Editor — that is how I am writing this. Then I paste it into the WordPress editor.

My current plan is to start revising each abmath article in this way:

• Write html code for the special formatting I want, mostly the code that produces the header, but also purple prose and other things. Once done I can use this code for all the abmath articles with little massaging.
• Start with the Word doc file for an article and use MathType to toggle all the MathType-generated gif files into TeX.
• Generate the html file in a way that preserves the TeX code with dollar signs. (There are two ways to do this and I have not made up my mind which to use.)
• Start revising!

I have already begun doing this. My intention is to revise each abstractmath article, post it, and announce the posting on Gyre&Gimble or on Google+. If an article is heavily revised I expect to post it (or parts of it) on Gyre&Gimble. Some of these things will be ready soon.

Last minute notes

• I used WinEdt, a text editor, to write the Handbook of Mathematical Discourse. It is a powerful html editor, with an extensive macro language that in particular allows rearranging the menus and adding new code to call other applications. It is especially designed for TeX, so is not as convenient as it stands for html. However, its macro language would allow me to convert it to a system that will do most of what Coffee Cup can do. I might do this because Coffee Cup has no macro language and (as far as I can tell) has no way to revise or add to menus.
• It is early days yet, but I am thinking of including pieces of Abstracting Algebra into abstractmath.org.

Send to Kindle

Abstracting algebra

This post has been turned into a page on WordPress, accessible in the upper right corner of the screen.  The page will be referred to by all topic posts for Abstracting Algebra.

Send to Kindle

Apportionment 1

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome.

Election systems

This post begins a new thread in Gyre&Gimble: Election systems.  In 1968 I created a game called Parlement and ran a few games by mail before being absorbed by family and career.  In it you ran a political party in a parliament in the style of many European countries: The parliament forms a government, votes on bills & budgets, then an election is held where each party runs on its record.

My interest in election systems has continued sporadically since them.  Since the nineties I have been programming in Mathematica and made stabs at implementing various systems for achieving proportionality. Now I expect to devote several posts to Mathematica demos of election and apportionment systems.

Proportional representation

An elected body is chosen by a list method of proportional representation this way:

• The election is by districts, each electing several members.  In most cases the number of seats each district has in the body is fixed ahead of the election.
• Each voter votes for a party list.
• The proportion of the integer number of representatives that party will have out of the total number of seats alloted to the district is chosen to be near to the proportion of votes the party list receives out of the total votes.
• The method for choosing the number of seats for the party can be any one of many methods proposed in the past 200 or so years.  Only a few methods are actually used in practice.
• Once the number of members for the party is determined, that many persons on the list are chosen according to some method.  There are quite a few different methods used for this.  I will not write about this aspect at all.

This post looks at the method of equal proportions. This method may also be used to apportion the legislature of countries such as the USA that has states or provinces so that each state has a suitably proportionate number of seats.  For most of the history of the USA, that method has been the method of equal proportions, but in the early days other methods were used.

My impression is that the equal proportion method is the most common method used in legislatures elected by the list system, and is also the most common method used for apportioning legislative seats among states or provinces.  There is much information about these things scattered over many articles in Wikipedia, and a close study may prove me wrong about this.

Note: The summary above is oversimplified and leaves out many details.  The references list more details than most people would ever want to know.

The equal proportions method

Several sites listed in the references describe the equal proportions method in detail.  The method for calculation used in the demo (there are others) works this way:

• Create a list $V$ of weights indexed by the party number.
• For proportional representation for parties, each party starts with $0$ seats and  $V_p$ is initially the number of votes party $p$ has for the district.
• For state representation, each state starts with $1$ seat and the the initial $V_s$ is the number of votes state $s$ receives divided by $\sqrt{2}$.
• Suppose $S$ seats are to be assigned .
• Assign the first one to the party $m$ for which $V_m$ is the maximum of the list $V$.  (In the case of states, this is the first seat after the initial one.)
• Change the list by setting $V_m:=\frac{V_m}{\sqrt{2}}$ ($V_m:=\frac{V_m}{\sqrt{6}}$ in the case of states).
• At the $k$th step, if $n$ is the party for which $V_n$ is the max of the list $V$ in its current state, assign the $k+1$st seat to party $n$ and set $V_n:= \frac{V_n}{\sqrt{u(u+1)}}$ (the geometric mean), where $u$ is the number of seats party $n$ had before the new one was assigned.
• Stop which $k=S$.

Interactive demos of the method of equal proportions

To manipulate these demos, click on "Enable Dynamics".  At present the demo has a bug that makes the table pink (Mathematica's way of giving an error message). Move any slider and the pink will disappear forever.  The demos are also available on my website: PartySimple.cdf and PartyComparison.cdf.  If you download them onto a machine with CDF player installed and run them the pink table does not happen.  I can't imagine what could cause an error like that only when run embedded in html. These notebooks are available for free use under a Creative Commons Attribution-ShareAlike 2.5 License..

Both demos have the same controls.

• Five sliders labeled n1 through n5 control the number of votes they get in the election.
• The bottom slider controls the number of seats that district gets to elect.
• By moving a slider you control the information it represents.
• By clicking on the plus sign to the right of the slider, you toggle a list of controls below it.  The party vote sliders begin with the controls invisible and the seats slider begins with them visible.

How the EP method works

The demo below assumes that five parties, numbered 1 through 5, are running to get seats in the elected body.  You may change the votes (Column Votes) received by any party, and also the total number of representatives to be chosen (Seats).

Data

• Total votes is the total number of votes received by all five parties.
• Seats is the total number of representatives assigned to the elected body. It can be changed using the Seats slider.
• Quota is Total votes divided by Seats.  Some systems use slight variations on this quota.
• The Name of the party is given just as a number.  In a suitably fancy demo you might give each party a real name.
• Votes is the number of votes the party receives in the election, controlled by the relevant slider.
• SeatsAsgd  is the number of seats the equal proportions method assigns to that party.
• Weight: This number is $\frac{\text{Votes}}{\sqrt{\text{SeatsAsgd}\times(\text{SeatsAsgd}+1)}}$

Playing with the demo

• Start with any settings for the sliders, and press the $+$ button underneath the seat slider. This allots one more seat to the representatives.
• You will see that the party with the largest weight gets the new seat.  That is how the method works: The algorithm starts with no seats and adds one at a time until the correct number of seats is reached.
• The weight is a function of the number of seats allotted to the party.
• Try changing the Votes for a single party, letting the total number of seats remain the same.  Which parts of the data get changed by doing this?  Do you understand why?
• Try changing the votes for all the parties, so that one has most of the votes and the others have only a few votes apiece.  Start with Seats at zero and step the seats up one at a time.  Notice what happens in column SeatsAsgd and what happens to Weight.

How close to an accurate apportionment does it get?

• Quota is Total votes divided by Seats.  Note how it changes when you move any slider.
• The Name of the party is given just as a number.  In a suitably fancy demo you might give each party a real name.
• Votes is the number of votes the party receives in the election, controlled by the relevant slider.
• SeatsAsgd is the number of seats the equal proportions method assigns to that party, given the total number of Seats allotted.
• SeatsIdeal is the party's Votes divided by Quota.  Note that this is generally close to SeatsAsgd, which is usually but not always either the floor or the ceiling of SeatsIdeal. Try to find a setting where that is not true (hint: Give one party most of the votes.)
• VotesPerSeat is Votes divided by SeatsAsgd.  Compare it to SeatsIdeal.  They are usually close, but can  be quite far off if only a few Seats are assigned.
• Deviation is VotesPerSeat divided by Quota.  This is a relative measure of how far away from exactness the representations of the parties are.

Playing with the demo

• Move Seats down to 2 or 3.  Notice that the deviations are quite bad, even $40\%$ off sometimes. Move Seats  up and see that deviations get much better.  Can you understand why that happens?
• Note that usually Seats is either the integer just below SeatsIdeal (the floor) or the integer just above it (the ceiling).  This is reasonable and is called "keeping quota".
• Make one or two parties large and the others small, then move the Seats slider around.  You find examples where Seats busts through the ceiling, "breaking quota".  Sometimes Seats is several units bigger than the ceiling.
• Note that if you step Seats up one at a time, the only thing that ever happens is that one party's seats goes up one unit.  Some other common systems cause some other party's seats to go down occasionally when the total seats is incremented.  That obviously never happens with EP.

About demos

These demos were designed for people to learn about a concept by experimenting with them.  Such demo should be fairly simple with only choices and displays relevant to what you are trying to show.

You can also build elaborate CDF's. Elaborate Riemann Sums Demo.nb contains a command PlotRiemann which allows for many options showing different kinds of Riemann sums with different options, and you could design a single demo of apportionment with many buttons, sliders and other gadgets that allow for all sorts of possibilities (but I have not designed such a monster).

I do expect to eventually design a command such as PlotRiemann that does for voting systems something like what PlotRiemann does for Riemann Sums, but the way to do that is to create one feature or option at a time.  I will be doing that and they will result in other election systems demos that I will post here from time to time.  (Promises, promises).

References

This post uses MathJax. If you see mathematical expressions with dollar signs around them, or badly formatted formulas, try refreshing the screen. Sometimes you have to do it two or three times.

To manipulate the demo in this post, you must have Wolfram CDF Player installed on your computer. It is available free from the Wolfram website. The code for the demo is in the Mathematica notebook Equal Proportions.nb.

Send to Kindle