Tag Archives: string

math

A mathematical saga

1 Comment

This post outlines some of the intellectual developments in the history of math. I call it a saga because it is like one:

  • It is episodic, telling one story after another.
  • It does not try to give an accurate history, but its episodes resemble what happened in math in the last 3000 years.
  • It tells about only a few of the things that happened.

Early techniques

We represented numbers by symbols.

Thousands of years ago, we figured out how to write down words and phrases in such a way that someone much later could read and understand them.

Naturally, we wanted to keep records of the number of horses the Queen owned, so we came up with various notations for numbers (number representing count). In some societies, these symbols were separate from the symbols used to represent words.

We invented algorithms

We discovered positional notation. We write $213$, which is based on a system: it means $2\times100+1\times10+3\times 1$. This notation encapsulates a particular computation of a number (its base-10 representation). (The expression $190+23$ is another piece of notation that encapsulates a computation that yields $213$.)

Compare that to the Roman notation $CCXIII$, which is an only partly organized jumble.
Try adding $CCXIII+CDXXIX$. (The answer is $DCXLII$.)

Positional notation allowed us to create the straightforward method of addition involving adding single digits and carrying:
\[\overset{\hspace{6pt}1\phantom{1}}
{\frac
{\overset{\displaystyle{213}}{429}}{642}
}
\]
Measuring land requires multiplication, which positional notation also allows us to perform easily.
The invention of such algorithms (methodically manipulating symbols) made it easy to calculate with numbers.

Geometry: Direct construction of mathematical objects

We discovered geometry in ancient times, in laying out plots of land and designing buildings. We had a bunch of names for different shapes and for some of them we knew how to calculate their area, perimeter and other things.

Euclid showed how to construct new geometric figures from given ones using specific methods (ruler and compasses) that preserve some properties.

Example

We can bisect a line segment (black) by drawing two circles (blue) centered at the endpoints with radius the length of the line segment. We then construct a line segment (red) between the points of intersection of the circle that intersects the given line segment at its midpoint. These constructions can be thought of as algorithms creating and acting on geometric figures rather than on symbols.



It is true that diagrams were drawn to represent line segments, triangles and so on.
But the diagrams are visualization helpers. The way we think about the process is that we are operating directly on the geometric objects to create new ones. We are thinking of the objects Platonically, although we don’t have to share Plato’s exact concept of their reality. It is enough to say we are thinking about the objects as if they were real.

Axioms and theorems

Euclid came up with the idea that we should write down axioms that are true of these figures and constructions, so that we can systematically use the constructions
to prove theorems about figures using axioms and previously proved theorems. This provided documented reasoning (in natural language, not in symbols) for building up a collection of true statements about math objects.

Example

After creating some tools for proving triangles are congruent, we can prove the the intersection of red and black lines in the figure really is the midpoint of the black line by constructing the four green line segments below and making appeals to congruences between the triangles that show up:



Note that the green lines have the same length as the black line.

Euclid thought about axioms and theorems as applying to geometry, but he also proved theorems about numbers by representing them as ratios of line segments.

Algebra

People in ancient India and Greece knew how to solve linear and quadratic equations using verbal descriptions of what you should do.
Later, we started using a symbolic language to express numerical problems and symbolic manipulation to solve (some of) them.

Example

The quadratic formula is an encapsulated computation that provides the roots of a quadratic equation. Newton’s method is a procedure for finding a root of an arbitrary polynomial. It is recursive in the loose sense (it does not always give an answer).

The symbolic language is a vast expansion of the symbolic notation for numbers. A major innovations was to introduce variables to represent unknowns and to state equations that are always true.

Logic

Aristotle developed an early form of logic (syllogisms) aimed at determining which arguments in rhetoric were sound. “All men are mortal. Socrates is a man. Therefore Socrates is mortal.” This was written in sentences, not in symbols.

By explicit analogy with algebra, we introduced symbolism and manipulation rules for logical reasoning, with an eye toward making mathematical reasoning sound and to some extent computable. For example, in one dialect of logical notation, modus ponens (used in the Socrates syllogism) is expressed as $(P\rightarrow Q,\,P)\,\,\vdash\,\, Q$. This formula is an encapsulated algorithm: it says that if you know $P\rightarrow Q$ and $P$ are valid (are theorems) then $Q$ is valid as well.

Crises of understanding

We struggled with the notion of function as a result of dealing with infinite series. For example, the limit of a sequence of algebraic expressions may not be an algebraic expression. It would no longer do to think of a function as the same thing as an algebraic expression.

We realized that Euclid’s axioms for geometry lacked clarity. For example, as I understand it, the original version of his axioms didn’t imply that the two circles in the proof above had to intersect each other. There were other more subtle problems. Hilbert made a big effort to spell out the axioms in more detail.

We refined our understanding of logic by trying to deal with the mysteries of calculus, limits and spaces. An example is the difference between continuity and uniform continuity.
We also created infinitesimals, only to throw up our hands because we could not make a logic that fit them. Infinitesimals were temporarily replaced by the use of epsilon-delta methods.

We began to understand that there are different kinds of spaces. For example, there were other models of some of Euclid’s axioms than just Euclidean space, and some of those models showed that the parallel axiom is independent of the other axioms. And we became aware of many kinds of topological spaces and manifolds.

We started to investigate sets, in part because spaces have sets of points. Then we discovered that a perfectly innocent activity like considering the set of all sets resulted in an impossibility.

We were led to consider how to understand the Axiom of Choice from several upsetting discoveries. For example, the Banach-Tarski “paradox” implies that you can rearrange the points in a sphere of radius $1$ to make two spheres of radius $1$.

Mathematics adopts a new covenant… for awhile

These problems caused a kind of tightening up, or rigorizing.
For a period of time, less than a century, we settled into a standard way of practicing research mathematics called new math or modern math. Those names were used mostly by math educators. Research mathematicians might have called it axiomatic math based on set theory. Although I was around for the last part of that period I was not aware of any professional mathematicians calling it anything at all; it was just what we did.

First, we would come up with a new concept, type of math object, or a new theorem. In this creative process we would freely use intuition, metaphors, images and analogies.

Example

We might come up with the idea that a function reaches its maximum when its graph swoops up from the left, then goes horizontally for an infinitesimal amount of time, then swoops down to the right. The point at which it was going horizontally would obviously have to be the maximum.

But when we came to publish a paper about the subject, all these pictures would disappear. All our visual, metaphorical/conceptual and kinetic feelings that explain the phenomenon would have to be suppressed.

Rigorizing consisted of a set of practices, which I will hint at:

Orthodox behavior among mathematicians in 1950

Definition in terms of sets and axioms

Each mathematical object had to be defined in some way that started with a set and some other data defined in terms of the set. Axioms were imposed on these data. Everything had to be defined in terms of sets, including functions and relations. (Multiple sets were used occasionally.)

Definitions done in this way omit a lot of the intuition that we have concerning the object being defined.

Examples
  • The definition of group as a set with a binary operation satisfying some particular axioms does not tell you that groups constitute the essence of symmetry.
  • The definitions of equivalence relation and of partition do not even hint that they define the same concept.

Even so, definitions done in this way have an advantage: They tend to be close to minimal in the sense that to verify that something fits the definition requires checking no more (or not much more) than necessary.

Proofs had to be clearly translatable into symbolic logic

First order logic (and other sorts of logic) were well developed and proofs were written in a way that they could in principle be reduced to arguments written in the notation of symbolic logic and following the rules of inference of logic. This resulted in proofs which did not appeal to intuition, metaphors or pictures.

Example

In the case of the theorem that the maximum of a (differentiable) function occurs only where the derivative is zero, that meant epsilon-delta proofs in which the proof appeared as a thick string of symbols. Here, “thick” means it had superscripts, subscripts, and other things that gave the string a fractal dimension of about $1.2$ (just guessing!).

Example

When I was a student at Oberlin College in 1959, Fuzzy Vance (Elbridge P. Vance) would sometimes stop in the middle of an epsilon-delta proof and draw pictures and provide intuition. Before he started that he would say “Shut the door, don’t tell anyone”. (But he told us!)

Example

A more famous example of this is the story that Oscar Zariski, when presenting a proof in algebraic geometry at the board, would sometimes remind himself of a part of a proof by hunching over the board so the students couldn’t see what he was doing and drawing a diagram which he would immediately erase. (I fault him for not telling them about the diagram.)

It doesn’t matter whether this story is true or not. It is true in the sense that any good myth is true.

Commercial

I wrote about rigor in these articles:

Rigorous view in abstractmath.org.

Dry bones, post in this blog.

Logic and sets clarify but get in the way

The orthodox method of “define it by sets and axioms” and “makes proofs at least resemble first order logic” clarified a lot of suspect proofs. But it got in the way of intuition and excessive teaching by using proofs made it harder to students to learn.

  • The definition of a concept can make you think of things that are foreign to your intuition of the concept. A function is a mapping,. The ordered pairs are a secondary construction; you should not think of ordered pairs as essential to your intuition. Even so the definition of function in terms of ordered pairs got rid of a lot of cobwebs.
  • The cartesian product of sets is obviously an associative binary operation. Except that if you define the cartesian product of sets in terms of ordered pairs then it is not associative.
  • Not only that, but if you define the ordered pair $(a,b)$ as $\{\{a,b\},a\}$ the you have to say that $a$ is an element of $(a,b)$ but $b$ is not That is not merely an inconvenient definition of ordered pair, it is wrong. It is not bad way to show that the concept of ordered pair is consistent with ZF set theory, but that is a minor point mathematicians hardly ever worry about.

Mathematical methods applied to everything

The early methods described at the beginning of this post began to be used everywhere in math.

Algorithms on symbols

Algorithms, or methodical procedures, began with the addition and multiplication algorithms and Euclid’s ruler and compass constructions, but they began to be used everywhere.

They are applied to the symbols of math, for example to describe rules for calculating derivatives and integrals and for summing infinite series.

Algorithms are used on strings, arrays and diagrams of math symbols, for example concatenating lists, multiplying matrices, and calculating binary operations on trees.

Algorithms as definitions

Algorithms are used to define the strings that make up the notation of symbolic logic. Such definitions include something like: “If $E$ and $F$ are expressions than $(E)\land (F)$ and $(\forall x)(E)$ are expressions”. So if $E$ is “$x\geq 3$” then $(\forall x)(x\geq 3)$ is an expression. This had the effect of turning an expression in symbolic logic into a mathematical object. Deduction rules such as “$E\land F\vdash E$” also become mathematical objects in this way.

We can define the symbols and expressions of algebra, calculus, and other part of math using algorithms, too. This became a big deal when computer algebra programs such as Mathematica came in.

Example

You can define the set $RP$ of real polynomials this way:

  • $0\in RP$
  • If $p\in RP$ then $p+r x^n\in RP$, where $x$ is a variable and $n$ a nonnegative integer.

That is a recursive definition. You can also define polynomials by pattern recognition:

Let $n$ be a positive integer, $a_0,\,a_1\,\ldots a_n$ be real numbers and $k_0,\,k_1\,\ldots k_n$ be nonnegative integers. Then $a_0 x^{k_0}+a_1 x^{k_1}+\ldots+ a_n x^{k_n}$ is a polynomial.

The recursive version is a way of letting a compiler discover that a string of symbols is a polynomial. That sort of thing became a Big Deal when computers arrived in our world.

Algorithms on mathematical objects

I am using the word “algorithm” in a loose sense to mean any computation that may or may not give a result. Computer programs are algorithms, but so is the quadratic formula. You might not think of a formula as an algorithm, but that is because if you use it in a computer program you just type in the formula; the language compiler has a built-in algorithm to execute calculations given by formulas.

It has not been clearly understood that mathematicians apply algorithms not only to symbols, but also directly to mathematical objects. Socrates thought that way long ago, as I described in the construction of a midpoint above. The procedure says “draw circles with center at the endpoints of the line segment.” It doesn’t say “draw pictures of circles…”

In the last section and this one, I am talking about how we think of applying an algorithm. Socrates thought he was talking about ideal lines and circles that exist in some other universe that we can access by thought. We can think about them as real things without making a metaphysical claim like Socrates did about them. Our brains are wired to think of abstract ideas in some many of the same ways we think about physical objects.

Example

The unit circle (as a topological space at least) is the quotient space of the space $\mathbb{R}$ of real numbers mod the equivalence relation defined by: $x\sim y$ if and only if $x-y$ is an integer.

Mathematicians who understand that construction may have various images in their mind when they read this. One would be something like imagining the real line $\mathbb{R}$ and then gluing all the points together that are an integer apart. This is a distinctly dizzying thing to think about but mathematicians aren’t worried because they know that taking the quotient of a space is a well-understood construction that works. They might check that by imagining the unit circle as the real line wrapped around an infinite number of times, with points an integer apart corresponding to the same point on the unit circle. (When I did that check I hastily inserted the parenthetical remark saying “as a topological space” because I realized the construction doesn’t preserve the metric.) The point of this paragraph is that many mathematicians think of this construction as a construction on math objects, not a construction on symbols.

Everything is a mathematical object

A lot of concepts start out as semi-vague ideas and eventually get defined as mathematical objects.

Examples

  • A function was originally thought of as a formula, but then get formalized in the days of orthodoxy as a set of ordered pairs with the functional property.
  • The concept of equation has been turned into a math object many times, for example in universal algebra and in logic. I suspect that some practitioners in those fields might disagree with me. This requires further research.
  • Propositions are turned into math objects by Boolean Algebra.
  • Perhaps numbers were always thought of as math objects, but much later the set $\mathbb{N}$ of all natural numbers and the set $\mathbb{R}$ of all real numbers came to be thought of explicitly as math objects, causing some mathematicians to have hissy fits.
  • Definitions are math objects. This has been done in various ways. A particular theory is a mathematical object, and it is essentially a definition by definition (!): Its models are what the theory defines. A particular example of “theory” is first-order theory which was the gold standard in the orthodox era. A classifying topos is also a math object that is essentially a definition.

Category Theory

The introduction of categories broke the orthodoxy of everything-is-a-set. It has become widely used as a language in many branches of math. It started with problems in homological algebra arising in at least these two ways:

  • Homotopy classes of continuous functions are not functions in the set theory sense. So we axiomatized the concept of function as an arrow (morphism) in a category.
  • The concept of mathematical object is axiomatized as an object in a category. This forces all properties of an object to be expressed in terms of its external relations with other objects and arrows.
  • Categories capture the idea of “kind of math”. There is a category of groups and homomorphisms, a category of topological spaces and homeomorphisms, and so on. This is a new level of abstraction. Before, if someone said “I work in finite groups”, their field was a clear idea and people knew what they were talking about, but now the category of finite groups is a mathematical object.
  • Homology maps one kind of math (topology) into another kind (algebra). Since categories capture the general notion of “kind of math”, we invented the idea of functor to capture the idea of modeling or representing one branch of math in another one. So Homology became a mathematical object.
  • The concept of functor allowed the definition of natural transformation as a mathematical object. Before categories, naturality was only an informal idea.

Advantages of category theory

  • Categories, in the form of toposes, quickly became candidates to replace set theory as a foundation system for math. They are more flexible and allow the kind of logic you want to use (classical, intuitionistic and others) to be a parameter in your foundational system.
  • “Arrow” (morphism) replaced not only the concept of function but also the concept of “element of” (“$\in$”). It allows the concept of variable elements. (This link is to a draft of a section of abstractmath.org that has not been included in the table of contents yet.) It also requires that an “element” has to be an element of one single object; for example, the maps $1\to \mathbb{N}$ and $1\to \mathbb{R}$ that pick out the number $42$ are not the same maps, although of course they are related by the canonical inclusion map $\mathbb{N}\to\mathbb{R}$.
  • Diagrams are used in proofs and give much better immediate understanding than formulas written in strings, which compress a lot of things unnecessarily into thick strings that require understanding lots of conventions and holding things in your memory.
  • Categories-as-kinds-of-math makes it easy to turn an analogy, for example between products of groups and products of spaces, into two examples of the same kind of mathematical object: Namely, a product in a category.

Disadvantages of category theory

  • Category theory requires a new way of thinking. Some people think that is a disadvantage. But genuine innovation is always disruptive. New technology breaks old technology. Of course, the new technology has to turn out to be useful to win out.
  • Category theory has several notions of “equal”. Objects can be the same or isomorphic. Categories can be isomorphic or equivalent. When you are doing category theory, you should never worry about whether two objects are equal: that is considered evil. Category theorists generally ignored the fuzziness of this problem because you can generally get away with it. Still, it was an example of something that had not been turned into a mathematical definition. Two ways of accomplishing this are anafunctors and homotopy type theory.

I expect to write about homotopy type theory soon. It may be the Next Revolution.

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

Monads for high school II: Lists

5 Comments

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 Monad.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.

Introduction

This is the second part of a series of posts describing how I will lead up to introducing monads in my proposed e-book Abstracting Algebra (AbAl). It follows Monads for high school I. Comments in red are meta and mostly will not be included in the book.  

Lists 

A list is a specific kind of mathematical object. This is a reasonable specification for lists:

A list of length $n$ determines and is determined by what its first, second, $\ldots$, $n$th entries are. 

In this post, lists will always be finite in length.

For doing rigorous proofs you need a precise definition of a list, such as a function from $\{1,2,…,n\}$ to a set, or a recursive definition.  This book is not about proofs.

Terminology and representation

The most common way in the symbolic language of math to represent a finite list is to use a comma-delimited expression in parentheses.  For example, \[(4,4,2,8)\] is the list of length 4 whose first and second entries are both $4$, third entry $2$ and fourth entry $8$.

  • The order matters and repetitions are allowed. For example, $(4,4,2,8)$, $(4,2,8)$ and $(4,2,4,8)$ are all different lists.
  • Other words for lists are (finite) sequence, word, tuple and string.
  • Many mathematicians would call $(4,4,2,8)$ an $4$–tuple.
  • My Discrete math classnotes discusses the specification and the definition of lists called tuples there) at length on pages 50ff. This section of AbAl will incorporate some of the information there.
  • Some computer languages represent our list without the commas: $(4\,\,4\,\,2\,\,8)$.
  • Mathematica represents it this way: $\{4,4,2,8\}$.  This conflicts with the usual set notation, where the order does not matter and where repetitions are ignored  — the set $\{4,4,2,8\}$ has three elements.  But if you type Length[$\{4,4,2,8\}$] in Mathematica, you get the answer 4.
  • A list of characters (alphabetical, numerical, or other symbols) can be represented  by writing the characters down in order without spaces between them.  For example $(a,a,c,d)$ would be written "aacd".  This representation is referred to as a string or as a word in computing science.  The string "4428" is the base-10 representation of the integer $4,428$.  Of course, it is also the hexadecimal representation of the integer $17,448$. 
  • In the text, I will mostly use a cartouche representation: for example, $\boxed{1\ 2\ 3\ 4}$ is the list consisting of the first four positive integers in order.
  • The cartouche is more in-your-face than the other representations I've listed and as far as I know is not used to mean anything else.  I'm not sure I can give any better explanation for why I prefer it than that.  Math is supposed to be explicit and precisely defined and justified by clear reasoning, but after all deciding which representation to use is not math, it is art.

Lists with entries from a given set

If $S$ is any set, finite or infinite, $\textrm{Lists}(S)$ denotes the set of all lists of finite length whose entries come from $S$.  Thus the set $\textrm{Lists}(\{1,\  2,\  3\})$ contains:

  • $\boxed{2\ 2\ 3\ 2\ 2\ 1}$,
  • $\boxed{3\  3\  3\  3}$,
  • the list of length $42$ whose first entry is $3$ and every other entry is $1$,
  • the empty list $\boxed{\vphantom{n}}$,
  • the singleton lists $\boxed{1}$,  $\boxed{2}$ and  $\boxed{3}$, and
  • an infinite number of other lists, 
  • but the list $\boxed{4\  2\  3}$ is not an element of $\textrm{Lists}(\{1,\  2,\  3\})$.

$\textrm{Lists}$ is a function from sets to sets.  Its input is any set and its output is the set of all finitely-long lists whose entries are from the input set. We will also use the similar function $\textrm{Lists}^+$ which takes a set to the set of nonempty lists with entries from the set.

Associativity

(Review from Monads for high school I.)  If a binary operation is associative, then the operation is defined on any (finite) list of inputs in its underlying set.  For example, the sum of the list $\boxed{4\ 4\ 2\ 8}$  is 18.  It follows from associativity that you can add it up as $(4+4)+(2+8)$, $4+(4+(2+8))$, $4+((4+2)+8)$, $(4+(4+2))+8$ or as $((4+4)+2)+8$.  They all give the same answer. In other words, Plus is in fact an operation on lists of numbers.  It is customary to extend associative binary operations to lists of length $0$ and $1$ by setting the value at the empty list to be the identity element of the operation, and the value at a one element list to be its only entry.  Thus Plus($\boxed{4\ 4\ 2\ 8}$)$=18$, Plus($\boxed{\ \vphantom{0} }$)$=0$, Times($\boxed{\ \vphantom{0} }$)$=1$ and Plus($\boxed{3 }$)$=3$.

Operations defined on finite lists

 You can join two lists together in order to make one list.  

The order matters.  If you join $\boxed{5\ 7}$ to $\boxed{2\ 12\ 7 }$ in that order you get $\boxed{5\ 7\ 2\ 12\ 7}$.  

Join is in fact an associative binary operation on lists.  Example: 

This means we can define an operation on lists of lists that joins all the lists inside together to make one list. 

 Notice the blue rectangle disappears when you do the operation. What I have defined here is a function that has a list of lists as input and a list of numbers as output.

The operation of joining lists to get a single list has a property shown by the drawing below (which will be interactive when I work on it some more).  Start on the left with a list of lists of lists.  The border colors distinguish the innermost lists, bordered in black, from the second level lists, in blue, and the outside list, bordered in green.

  • There is only one outside list: It is a list of (blue) lists.  That is the kind of list you can apply join to, so when you do you get a single blue list with five lists inside it (on the bottom of the diagram). "Join outside first" means "apply join to the outside list first". 
  • The single blue list on the bottom is again the kind of list you can apply join to, and when you do you get the lower list on the right end of the diagram.
  • However, the green list also contains two lists each of which is a list of lists that you can apply join to.  Apply it to both of them and you get the list at the top of the diagram.  
  • Again, that list is the kind you can apply join to and when you do you get the upper list on the right.

JoinDiagram

The two lists on the right are the same.  That always happens, whatever lists you start with.  (Try it with others, and include some singleton and empty lists while you are at it.) 

You might not have thought of this property, and now that you see it, it may look like some sort of second-rate phenom to take note of.  Or not.  But in fact, it turns out that it means that our modest function  $\textrm{Lists}^+$, that takes a set to the nonempty set of lists of its elements is a monad.  (So is $\textrm{Lists}$.) In order to say this we must define some other concepts: functor and natural transformation, and we have to verify a number of other properties of the $\textrm{List}^+$ function:  It is not just a function, it is a functor on the category of sets, the join function is a natural transformation, and some other technicalities.

Once we do that, we can define what the algebras of the join monad are, and it turns out that they are exactly all the associative binary operations.  

In other words:

The binary operation of join on nonempty lists is the mother of all associative binary operations.

But that will have to wait for the next post.

References

 

Send to Kindle
exposition, language, language of math, math, representations, understanding math

Representing and thinking about sets

Leave a comment

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 Representing sets.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.

Representations of sets

Sets are represented in the math literature in several different ways, some mentioned here.  Also mentioned are some other possibilities.  Introducing a variety of representations of any type of math object is desirable because students tend to assume that the representation is the object.

Curly bracket notation

The standard representation for a finite set is of the form "$\{1,3,5,6\}$". This particular example represents the unique set containing the integers $1$, $3$, $5$ and $6$ and nothing else. This means precisely that the statement "$n$ is an element of $S$" is true if $n=1$, $n=3$, $n=5$ or $n=6$, and it is false if $n$ represents any other mathematical object. 

In the way the notation is usually used, "$\{1,3,5,6\}$", "$\{3,1,5,6\}$", "$\{1,5,3,6\}$",  "$\{1,6,3,5,1\}$" and $\{ 6,6,3,5,1,5\}$ all represent the same set. Textbooks sometimes say "order and repetition don't matter". But that is a statement about this particular representation style for sets. It is not a statement about sets.

It would be nice to come up with a representation for sets that doesn't involve an ordering. Traditional algebraic notation is essentially one-dimensional and so automatically imposes an ordering (see Algebra is a difficult foreign language).    

Let the elements move

In Visible Algebra II, I experimented with the idea of putting the elements at random inside a circle and letting them visibly move around like goldfish in a bowl.  (That experiment was actually for multisets but it applies to sets, too.)  This is certainly a representation that does not impose an ordering, but it is also distracting.  Our visual system is attracted to movement (but not as much as a cat's visual system).  

Enforce natural ordering

One possibility would be to extend the machinery in a visible algebra system that allows you to make a box you could drag elements into. 

This box would order the elements in some canonical order (numerical order for numbers, alphabetical order for strings of letters or words) with the property that if you inserted an element in the wrong place it would rearrange itself, and if you tried to insert an element more than once the representation would not change.  What you would then have is a unique representation of the set.

An example is the device below.  (If you have Mathematica, not just CDF player, you can type in numbers as you wish instead of having to use the buttons.) 

This does not allow a representation of a heterogenous set such as $\{3,\mathbb{R},\emptyset,\left(\begin{array}{cc}1&2\\0&1\\ \end{array}\right)\}$.  So what?  You can't represent every function by a graph, either.

Hanger notation

The tree notation used in my visual algebra posts could be used for sets as well, as illustrated below. The system allows you to drag the elements listed into different positions, including all around the set node. If you had a node for lists, that would not be possible.

This representation has the pedagogical advantage of shows that a set is not its elements.

  • A set is distinct from its elements
  • A set is completely determined by what the elements are.

Pattern recognition

Infinite sets are sometimes represented using the curly bracket notation using a pattern that defines the set.  For example, the set of even integers could be represented by $\{0,2,4,6,\ldots\}$.  Such a representation is necessarily a convention, since any beginning pattern can in fact represent an infinite number of different infinite sets.  Personally, I would write, "Consider the even integers $\{0,2,4,6,\ldots\}$", but I would not write,  "Consider the set $\{0,2,4,6,\ldots\}$".

By the way, if you are writing for newbies, you should say,"Consider the set of even integers $\{0,2,4,6,\ldots\}$". The sentence "Consider the even integers $\{0,2,4,6,\ldots\}$" is unambiguous because by convention a list of numbers in curly brackets defines a set. But newbies need lots of redundancy.

Representation by a sentence

Setbuilder notation is exemplified by $\{x|x>0\}$, which denotes the positive reals, given a convention or explicit statement that $x$ represents a real number.  This allows the representation of some infinite sets without depending on a possibly ambiguous pattern. 

A Visible Algebra system needs to allow this, too. That could be (necessarily incompletely) done in this way:

  • You type in a sentence into a Setbuilder box that defines the set.
  • You then attach a box to the Setbuilder box containing a possible element.
  • The system then answers Yes, No, or Can't Tell.

The Can't Tell answer is a necessary requirement because the general question of whether an element is in a set defined by a first order sentence is undecidable. Perhaps the system could add some choices:

  • Try for a second.
  • Try for an hour.
  • Try for a year.
  • Try for the age of the universe.

Even so, I'll bet a system using Mathematica could answer many questions like this for sentences referring to a specific polynomial, using the Solve or NSolve command.  For example, the answer to the question, "Is $3\in\{n|n\lt0 \text{ and } n^2=9\}$?" (where $n$ ranges over the integers) would be "No", and the answer to  "Is $\{n|n\lt0 \text{ and } n^2=9\}$ empty?" would also be "No". [Corrected 2012.10.24]

References

  1. Explaining “higher” math to beginners (previous post)
  2. Algebra is a difficult foreign language (previous post)
  3. Visible Algebra II (previous post)
  4. Sets: Notation (abstractmath article)
  5. Setbuilder notation (Wikipedia)
Send to Kindle