Tag Archives: cograph

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.

Segments posted so far

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}\]

Cograph

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.


Creative Commons License

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

Send to Kindle

Functions: Metaphors, Images and Representations

Please read this post at abstractmath.org. I originally posted the document here but some of the diagrams would not render, and I haven’t been able to figure out why. Sorry for having to redirect.

Send to Kindle

Demos for graph and cograph of calculus functions

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. The source code is the Mathematica Notebook GraphCograph.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work properly.

This post provides interactive examples of the endograph and cograph of real functions. Those two concepts were defined and discussed in the previous post Endograph and cograph of real functions.

Such representations of functions, put side by side with the conventional graph, may help students understand how to interpret the usual graph representation. For example: What does it mean when the arrows slant to the left? spread apart? squeeze together? flip over? Going back and forth between the conventional graph and the cograph or engraph for a particular function should make you much more in tune to the possibilities when you see only the conventional graph of another function.

This is not a major advance for calculus teachers, but it may be a useful tool.

Line segment

$y=a x+b$


Cubic

$y=a x^3-b x$

Sine

$y=\sin a x$.

Sine and its derivative

$y=\sin a x$ (blue) and $y=a\cos a x$ (red)

Quintic with three parameters

$y=a x^5-b
x^4-0.21 x^3+0.2 x^2+0.5 x-c$

Thanks to Martin Flashman for corrections.

Send to Kindle

Conceptual blending

This post uses MathJax.  If you see formulas in unrendered TeX, try refreshing the screen.

A conceptual blend is a structure in your brain that connects two concepts by associating part of one with part of another.  Conceptual blending is a major tool used by our brain to understand the world.

The concept of conceptual blend includes special cases, such as representations, images and conceptual metaphors, that math educators have used for years to understand how mathematics is communicated and how it is learned.  The Wikipedia article is a good starting place for understanding conceptual blending. 

In this post I will illustrate some of the ways conceptual blending is used to understand a function of the sort you meet with in freshman calculus.  I omit the connections with programs, which I will discuss in a separate post.

A particular function

Consider the function $h(t)=4-(t-2)^2$. You may think of this function in many ways.

FORMULA:

$h(t)$ is defined by the formula $4-(t-2)^2$.

  • The formula encapsulates a particular computation of the value of $h$ at a given value $t$.
  • The formula defines the function, which is a stronger statement than saying it represents the function.
  • The formula is in standard algebraic notation. (See Note 1)
  • To use the formula requires one of these:
    • Understand and use the rules of algebra
    • Use a calculator
    • Use an algebraic programming language. 
  • Other formulas could be used, for example $4t-t^2$.
    • That formula encapsulates a different computation of the value of $h$.

TREE: 

$h(t)$ is also defined by this tree (right).
  • The tree makes explicit the computation needed to evaluate the function.
  • The form of the tree is based on a convention, almost universal in computing science, that the last operation performed (the root) is placed at the top and that evaluation is done from bottom to top.
  • Both formula and tree require knowledge of conventions.
  • The blending of formula and tree matches some of the symbols in the formula with nodes in the tree, but the parentheses do not appear in the tree because they are not necessary by the bottom-up convention.
  • Other formulas correspond to other trees.  In other words, conceptually, each tree captures not only everything about the function, but everything about a particular computation of the function.
  • More about trees in these posts:

GRAPH:

$h(t)$ is represented by its graph (right). (See note 2.)

  • This is the graph as visual image, not the graph as a set of ordered pairs.
  • The blending of graph and formula associates each point on the (blue) graph with the value of the formula at the number on the x-axis directly underneath the point.
  • In contrast to the formula, the graph does not define the function because it is a physical picture that is only approximate.
  • But the formula does represent the function.  (This is "represents" in the sense of cognitive psychology, but not in the mathematical sense.)
  • The blending requires familiarity with the conventions concerning graphs of functions. 
  • It sets into operation the vision machinery of your brain, which is remarkably elaborate and powerful.
    • Your visual machinery allows you to see instantly that the maximum of the curve occurs at about $t=2$. 
  • The blending leaves out many things.
    • For one, the graph does not show the whole function.  (That's another reason why the graph does not define the function.)
    • Nor does it make it obvious that the rest of the graph goes off to negative infinity in both directions, whereas that formula does make that obvious (if you understand algebraic notation).  

GEOMETRIC

The graph of $h(t)$ is the parabola with vertex $(2,4)$, directrix $x=2$, and focus $(2,\frac{3}{4})$. 

  • The blending with the graph makes the parabola identical with the graph.
  • This tells you immediately (if you know enough about parabolas!) that the maximum is at $(2,4)$ (because the directrix is vertical).
  • Knowing where the focus and directrix are enables you to mechanically construct a drawing of the parabola using a pins, string, T-square and pencil.  (In the age of computers, do you care?)

HEIGHT:

$h(t)$ gives the height of a certain projectile going straight up and down over time.

  • The blending of height and graph lets you see instantly (using your visual machinery) how high the projectile goes. 
  • The blending of formula and height allows you to determing the projectile's velocity at any point by taking the derivative of the function.
  • A student may easily be confused into thinking that the path of the projectile is a parabola like the graph shown.  Such a student has misunderstood the blending.

KINETIC:

You may understand $h(t)$ kinetically in various ways.

  • You can visualize moving along the graph from left to right, going, reaching the maximum, then starting down.
    • This calls on your experience of going over a hill. 
    • You are feeling this with the help of mirror neurons.
  • As you imagine traversing the graph, you feel it getting less and less steep until it is briefly level at the maximum, then it gets steeper and steeper going down.
    • This gives you a physical understanding of how the derivative represents the slope.
    • You may have seen teachers swooping with their hand up one side and down the other to illustrate this.
  • You can kinetically blend the movement of the projectile (see height above) with the graph of the function.
    • As it goes up (with $t$ increasing) the projectile starts fast but begins to slow down.
    • Then it is briefly stationery at $t=2$ and then starts to go down.
    • You can associate these feelings with riding in an elevator.
      • Yes, the elevator is not a projectile, so this blending is inaccurate in detail.
    • This gives you a kinetic understanding of how the derivative gives the velocity and the second derivative gives the acceleration.

OBJECT:

The function $h(t)$ is a mathematical object.

  • Usually the mental picture of function-as-object consists of thinking of the function as a set of ordered pairs $\Gamma(h):=\{(t,4-(t-2)^2)|t\in\mathbb{R}\}$. 
  • Sometimes you have to specify domain and codomain, but not usually in calculus problems, where conventions tell you they are both the set of real numbers.
  • The blend object and graph identifies each point on the graph with an element of $\Gamma(h)$.
  • When you give a formal proof, you usually revert to a dry-bones mode and think of math objects as inert and timeless, so that the proof does not mention change or causation.
    • The mathematical object $h(t)$ is a particular set of ordered pairs. 
    • It just sits there.
    • When reasoning about something like this, implication statements work like they are supposed to in math: no causation, just picking apart a bunch of dead things. (See Note 3).
    • I did not say that math objects are inert and timeless, I said you think of them that way.  This post is not about Platonism or formalism. What math objects "really are" is irrelevant to understanding understanding math [sic].

DEFINITION

definition of the concept of function provides a way of thinking about the function.

  • One definition is simply to specify a mathematical object corresponding to a function: A set of ordered pairs satisfying the property that no two distinct ordered pairs have the same second coordinate, along with a specification of the codomain if that is necessary.
  • A concept can have many different definitions.
    • A group is usually defined as a set with a binary operation, an inverse operation, and an identity with specific properties.  But it can be defined as a set with a ternary operation, as well.
    • A partition of a set is a set of subsets of a set with certain properties. An equivalence relation is a relation on a set with certain properties.  But a partition is an equivalence relation and an equivalence relation is a partition.  You have just picked different primitives to spell out the definition. 
    • If you are a beginner at doing proofs, you may focus on the particular primitive objects in the definition to the exclusion of other objects and properties that may be more important for your current purposes.
      • For example, the definition of $h(t)$ does not mention continuity, differentiability, parabola, and other such things.
      • The definition of group doesn't mention that it has linear representations.

SPECIFICATION

A function can be given as a specification, such as this:

If $t$ is a real number, then $h(t)$ is a real number, whose value is obtained by subtracting $2$ from $t$, squaring the result, and then subtracting that result from $4$.

  • This tells you everything you need to know to use the function $h$.
  • It does not tell you what it is as a mathematical object: It is only a description of how to use the notation $h(t)$.

Notes

1. Formulas can be give in other notations, in particular Polish and Reverse Polish notation. Some forms of these notations don't need parentheses.

2. There are various ways to give a pictorial image of the function.  The usual way to do this is presenting the graph as shown above.  But you can also show its cograph and its endograph, which are other ways of representing a function pictorially.  They  are particularly useful for finite and discrete functions. You can find lots of detail in these posts and Mathematica notebooks:

3. See How to understand conditionals in the abstractmath article on conditionals.

References

  1. Conceptual blending (Wikipedia)
  2. Conceptual metaphors (Wikipedia)
  3. Definitions (abstractmath)
  4. Embodied cognition (Wikipedia)
  5. Handbook of mathematical discourse (see articles on conceptual blendmental representationrepresentation, and metaphor)
  6. Images and Metaphors (article in abstractmath)
  7. Links to G&G posts on representations
  8. Metaphors in Computing Science (previous post)
  9. Mirror neurons (Wikipedia)
  10. Representations and models (article in abstractmath)
  11. Representations II: dry bones (article in abstractmath)
  12. The transition to formal thinking in mathematics, David Tall, 2010
  13. What is the object of the encapsulation of a process? Tall et al., 2000.

 

Send to Kindle

A tiny step towards killing string-based math

I discussed endographs of real functions in my post  Endographs and cographs of real functions.  Endographs of finite functions also provide another way of thinking about functions, and I show some examples here.  This is not a new idea; endographs have appeared from time to time in textbooks, but they are not used much, and they have the advantage of revealing some properties of a function instantly that cannot be seen so easily in a traditional graph or cograph.

In contrast to endographs of functions on the real line, an endograph of a finite function from a set to itself contains all the information about the function.  For real functions, only some of the arrows can be shown; you are dependent on continuity to interpolate where the infinite number of intermediate arrows would be, and of course, it is easy to produce a function, with, say, small-scale periodicity, that the arrows would miss, so to speak.  But with an endograph of a finite function, WYSIATI (what you see is all there is).

Here is the endograph of a function.  It is one function.  The graph has four connected components.

You can see immediately that it is a permutation  of the set \{1,2,3,4,5,6\}, and that it is involution (a permutation f for which f f=\text{id}).  In cycle notation, it is the permutation (1 2)(5 6), and the connected components of the endograph correspond to the cycle structure.

Here is another permutation:

You can see that to get f^n=\text{id} you would have to have n=6, since you have to apply the 3-cycle 3 times and the transposition twice to get the identity.   The cycle structure (1 2 4)(0 3) tells you this, but you have to visualize it acting to see that.  The endograph gives the newbie a jumpstart on the visualization.  “The power to understand and predict the quantities of the world should not be restricted to those with a freakish knack for manipulating abstract symbols” (Brett Victor).   This is an argument for insisting that this permutation is the endograph, and the abstract string of symbols (1 2 4)(0 3) is a representation of secondary importance.  [See Note 1.]

Here is the cograph of the same function.  It requires a bit of visualization or tracing arrows around to see its cycle structure.

If I had rearranged the nodes like this

the cycle structure would be easier to see.  This does not indicate as much superiority of the endograph metaphor over the cograph metaphor as you might think:  My endograph code [Note 2] uses Mathematica’s graph-displaying algorithm, which automatically shows cycles clearly.   The cograph code that I wrote specifies the placement of the nodes explicitly, so I rearranged them to obtain the second cograph above using my knowledge of the cycle structure.

The following endographs of functions that are not permutations exhibit the general fact that the graph of a finite function consists of cycles with trees attached.   This structure is obvious from the endographs, and it is easy to come up with a proof of this property of finite functions by tracing your finger around the endographs.

This is the endograph of the polynomial 2 n^9+5 n^8+n^7+4 n^6+9 n^5+1 over the finite field of 11 elements.

Here is another endograph:

I constructed this explicitly by writing a list of rules, and then used Mathematica’s interpolating polynomial to determine that it is given by the polynomial

6 x^{16}+13 x^{15}+x^{14}+3 x^{13}+10 x^{12}+5  x^{11}\\ +14 x^{10}+4 x^9+9 x^8+x^7+14 x^6\\ +15  x^5+16 x^4+14 x^3+4 x^2+15 x+11

in GF[17].

Quite a bit is known about polynomials over finite fields that give permutations.  For example there is an easy proof using interpolating polynomials that a polynomial that gives a transposition must have degree q-2.  The best reference for this stuff is Lidl and Niederreiter, Introduction to Finite Fields and their Applications

The endographs above raise questions such as what can you say about the degree or coefficients of a polynomial that gives a digraph like the function f below that is idempotent (f f=f).  Students find idempotence vs. involution difficult to distinguish between.  Digraphs show you almost immediately what is going on.  Stare at the digraph below for a bit and you will see that if you follow f to a node and then follow  it again you stay where you are (the function is the identity on its image).  That’s another example of the insights you can get from a new metaphor for a mathematical object.

The following function is not idempotent even though it has only trivial loops.  But the digraph does tell you easily that it satisfies f^4=f^3.

Notes

[1] Atish Bagchi and I have contributed to this goal in Graph Based Logic and Sketches, which gives a bare glimpse of the possibility of considering that the real objects of logic are diagrams and their limits and morphisms between them, rather than hard-to-parse strings of letters and logical symbols.  Implementing this (and implementing Brett Victor’s ideas) will require sophisticated computer support.  But that support is coming into existence.  We won’t have to live with string-based math forever.

[2] The Mathematica notebook used to produce these pictures is here.  It has lots of other examples.

Send to Kindle

Comparing graph and cograph (Version 2)

This post has been superseded by the post Demos for graph and cograph of calculus functions.

New Version 6 July 2011

This is a new version of a post originally created on 30 June, 2011. –Charles Wells

When you put the graph and cograph of a function with parameters side by side, interesting things may happen.  I have created the files CographExample.nb and CographExample.cdf to illustrate this.

The .nb form is a Mathematica Notebook, which requires Mathematica to run and allows you to manipulate the objects and change the code in the notebook as you wish.  The .cdf file contains the same material and can be viewed using Mathematica CDF Player, which is available free here.  The CDF Player allows you to change the parameters with the slidebars, so that you can experience the phenomena discusses in the example, but you cannot otherwise modify the file.

You cannot include a Mathematica computable document directly into a Word Press document, so here are screenshots of the cograph example with several different settings of its parameters.

Some Screenshots and sample questions follow.  These not in the original version.  I added these thanks to encouragement by Sam Alexander.

Screenshots


Questions for discussion

My idea is that students will manipulate the slider to see what happens and do some algebra on the relations between a, b and x to explain the phenomena that occur.

Questions about the graph (left figure).

G1. Prove that the two straight lines are parallel for any choice of a and b.

G2. When do the red and blue straight lines in the graph coincide? Answer: The lines coincide when a=1 or b=0 .

  • “When do the…” translates into “for what values of a and b do the…”. I predict that which way you ask the question will make a big difference for some students. To answer this question, you are not solving for x but for a and b. If you ask “When…” they have to discover this for themselves.
  • The answer is disjunctive: This may be a new idea for some of the students.

G3. Find a formula in terms of a and b for the distance between the two straight lines in the graph. Answer: |b-ab|.

Questions about the cograph.

C1. When do the red and blue arrows in the cograph coincide? Answer: Same as answer to Question G1.

C2. In the cograph, for what aand b are the arrow targets for a given choice of x closer together than the arrow sources? Answer: $latex  |a|>1$. b is irrelevant.

C3. Manipulate a and b. For some values the blue arrows all cross each other at the same point. (Same question for red arrows.) When does this happen? Answer: When a is negative.

  • The abstract setting of the cograph is shifted by this question (and the next) as follows: The arrows originally provided a visual pointer from the input to the output of the function. All of a sudden we are treating them as mathematical objects(straight line segments in the plane).
  • The abstraction is also broken in another way: The space between the source line and the target line is just a visual separation, but after this question both lines lie on the xy plane. The question turns a visual illustration into a mathematical object.

C4.  Describe the common point where all the red arrows cross when a is negative. (Same question for blue arrows.) Answer: The point is \left(\frac{b}{1-a},\frac{3 a}{a-1}\right).

Send to Kindle

Endograph and cograph of real functions

This post is covered by the Creative Commons Attribution – ShareAlike 3.0 License, which means you may use, adapt and distribute the work provided you follow the requirements of the license.

Introduction

In the article Functions: Images and Metaphors in abstractmath I list a bunch of different images or metaphors for thinking about functions. Some of these metaphors have realizations in pictures, such as a graph or a surface shown by level curves. Others have typographical representations, as formulas, algorithms or flowcharts (which are also pictorial). There are kinetic metaphors — the graph of {y=x^2} swoops up to the right.

Many of these same metaphors have realizations in actual mathematical representations.

Two images (mentioned only briefly in the abstractmath article) are the cograph and the endograph of a real function of one variable. Both of these are visualizations that correspond to mathematical representations. These representations have been used occasionally in texts, but are not used as much as the usual graph of a continuous function. I think they would be useful in teaching and perhaps even sometimes in research.

A rough and unfinished Mathematica notebook is available that contains code that generate graphs and cographs of real-valued functions. I used it to generate most of the examples in this post, and it contains many other examples. (Note [1].)

The endograph of a function

In principle, the endograph (Note [2]) of a function {f} has a dot for each element of the domain and of the codomain, and an arrow from {x} to {f(x)} for each {x} in the domain. For example, this is the endograph of the function {n\mapsto n^2+1 \pmod 11} from the set {\{0,1,\ldots,10\}} to itself:


“In principle” means that the entire endograph can be shown only for small finite functions. This is analogous to the way calculus books refer to a graph as “the graph of the squaring function” when in fact the infinite tails are cut off.

Real endographs

I expect to discuss finite endographs in another post. Here I will concentrate on endographs of continuous functions with domain and codomain that are connected subsets of the real numbers. I believe that they could be used to good effect in teaching math at the college level.

Here is the endograph of the function {y=x^2} on the reals:

I have displayed this endograph with the real line drawn in the usual way, with tick marks showing the location of the points on the part shown.

The distance function on the reals gives us a way of interpreting the spacing and location of the arrowheads. This means that information can be gleaned from the graph even though only a finite number of arrows are shown. For example you see immediately that the function has only nonnegative values and that its increase grows with {x}.(See note [3]).

I think it would be useful to show students endographs such as this and ask them specific questions about why the arrows do what they do.

For the one shown, you could ask these questions, probably for class discussion rather that on homework.

  • Explain why most of the arrows go to the right. (They go left only between 0 and 1 — and this graph has such a coarse point selection that it shows only two arrows doing that!)
  • Why do the arrows cross over each other? (Tricky question — they wouldn’t cross over if you drew the arrows with negative input below the line instead of above.)
  • What does it say about the function that every arrowhead except two has two curves going into it?

Real Cographs

The cograph (Note [4] of a real function has an arrow from input to output just as the endograph does, but the graph represents the domain and codomain as their disjoint union. In this post the domain is a horizontal representation of the real line and the codomain is another such representation below the domain. You may also represent them in other configurations (Note [5]).

Here is the cograph representation of the function {y=x^2}. Compare it with the endograph representation above.

Besides the question of most arrows going to the right, you could also ask what is the envelope curve on the left.

More examples

Absolute value function

Arctangent function

Notes

[1] This website contains other notebooks you might find useful. They are in Mathematica .nb, .nbp, or .cdf formats, and can be read, evaluated and modified if you have Mathematica 8.0. They can also be made to appear in your browser with Wolfram CDF Player, downloadable free from Wolfram site. The CDF player allows you to operate any interactive demos contained in the file, but you can’t evaluate or modify the file without Mathematica.

The notebooks are mostly raw code with few comments. They are covered by the Creative Commons Attribution – ShareAlike 3.0 License, which means you may use, adapt and distribute the code following the requirements of the license. I am making the files available because I doubt that I will refine them into respectable CDF files any time soon.

[2] I call them “endographs” to avoid confusion with the usual graphs of functions — — drawings of (some of) the set of ordered pairs {x,f(x)} of the function.

[3] This is in contrast to a function defined on a discrete set, where the elements of the domain and codomain can be arranged in any old way. Then the significance of the resulting arrangement of the arrows lies entirely in which two dots they connect. Even then, some things can be seen immediately: Whether the function is a cycle, permutation, an involution, idempotent, and so on.

Of course, the placement of the arrows may tell you more if the finite sets are ordered in a natural way, as for example a function on the integers modulo some integer.

[4] The text [1] uses the cograph representation extensively. The word “cograph” is being used with its standard meaning in category theory. It is used by graph theorists with an entirely different meaning.

[5] It would also be possible to show the domain codomain in the usual {x-y} plane arrangement, with the domain the {x} axis and the codomain the {y} axis. I have not written the code for this yet.

References

[1] Sets for Mathematics, by F. William Lawvere and Robert Rosebrugh. Cambridge University Press, 2003.

[2] Martin Flashman’s website contains many exampls of cographs of functions, which he calls mapping diagrams.

Send to Kindle