Category Archives: understanding math

Notation for sets

This is a revision of the section of on notation for sets.

Sets of numbers

The following notation for sets of numbers is fairly standard.


  • Some authors use $\mathbb{I}$ for $\mathbb{Z}$, but $\mathbb{I}$ is also used for the unit interval.
  • Many authors use $\mathbb{N}$ to denote the nonnegative integers instead
    of the positive ones.
  • To remember $\mathbb{Q}$, think “quotient”.
  • $\mathbb{Z}$ is used because the German word for “integer” is “Zahl”.

Until the 1930’s, Germany was the world center for scientific and mathematical study, and at least until the 1960’s, being able to read scientific German was was required of anyone who wanted a degree in science. A few years ago I was asked to transcribe some hymns from a German hymnbook — not into English, but merely from fraktur (the old German alphabet) into the Roman alphabet. I sometimes feel that I am the last living American to be able to read fraktur easily.

Element notation

The expression “$x\in A$” means that $x$ is an element of the set $A$. The expression “$x\notin A$” means that $x$ is not an element of $A$.

“$x\in A$” is pronounced in any of the following ways:

  • “$x$ is in $S$”.
  • “$x$ is an element of $S$”.
  • “$x$ is a member of $S$”.
  • “$S$ contains $x$”.
  • “$x$ is contained in $S$”.


  • Warning: The math English phrase “$A$ contains $B$” can mean either “$B\in A$” or “$B\subseteq A$”.
  • The Greek letter epsilon occurs in two forms in math, namely $\epsilon$ and $\varepsilon$. Neither of them is the symbol for “element of”, which is “$\in$”. Nevertheless, it is not uncommon to see either “$\epsilon$” or “$\varepsilon$” being used to mean “element of”.
  • $4$ is an element of all the sets $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$.
  • $-5\notin \mathbb{N}$ but it is an element of all the others.

List notation

Definition: list notation

A set with a small number of elements may be denoted by listing the elements inside braces (curly brackets). The list must include exactly all of the elements of the set and nothing else.


The set $\{1,\,3,\,\pi \}$ contains the numbers $1$, $3$ and $\pi $ as elements, and no others. So $3\in \{1,3,\pi \}$ but $-3\notin \{1,\,3,\,\pi \}$.

Properties of list notation

List notation shows every element and nothing else

If $a$ occurs in a list notation, then $a$ is in the set the notation defines.  If it does not occur, then it is not in the set.

Be careful

When I say “$a$ occurs” I don’t mean it necessarily occurs using that name. For example, $3\in\{3+5,2+3,1+2\}$.

The order in which the elements are listed is irrelevant

For example, $\{2,5,6\}$ and $\{5,2,6\}$ are the same set.

Repetitions don’t matter

$\{2,5,6\}$, $\{5,2,6\}$, $\{2,2,5,6 \}$ and $\{2,5,5,5,6,6\}$ are all different representations of the same set. That set has exactly three elements, no matter how many numbers you see in the list notation.

Multisets may be written with braces and repeated entries, but then the repetitions mean something.

When elements are sets

When (some of) the elements in list notation are themselves sets (more about that here), care is required.  For example, the numbers $1$ and $2$  are not elements of the set \[S:=\left\{ \left\{ 1,\,2,\,3 \right\},\,\,\left\{ 3,\,4 \right\},\,3,\,4 \right\}\]The elements listed include the set $\{1, 2, 3\}$ among others, but not the number $2$.  The set $S$ contains four elements, two sets and two numbers. 

Another way of saying this is that the element relation is not transitive: The facts that $A\in B$ and $B\in C$ do not imply that $A\in C$. 

Sets are arbitrary

  • Any mathematical object can be the element of a set.
  • The elements of a set do not have to have anything in common.
  • The elements of a set do not have to form a pattern.
  • $\{1,3,5,6,7,9,11,13,15,17,19\}$ is a set. There is no point in asking, “Why did you put that $6$ in there?” (Sets can be arbitrary.)
  • Let $f$ be the function on the reals for which $f(x)=x^3-2$. Then \[\left\{\pi^3,\mathbb{Q},f,42,\{1,2,7\}\right\}\] is a set. Sets do not have to be homogeneous in any sense.

Setbuilder notation


Suppose $P$ is an assertion. Then the expression “$\left\{x|P(x) \right\}$” denotes the set of all objects $x$ for which $P(x)$ is true. It contains no other elements.

  • The notation “$\left\{ x|P(x) \right\}$” is called setbuilder notation.
  • The assertion $P$ is called the defining condition for the set.
  • The set $\left\{ x|P(x) \right\}$ is called the truth set of the assertion $P$.

In these examples, $n$ is an integer variable and $x$ is a real variable..

  • The expression “$\{n| 1\lt n\lt 6 \}$” denotes the set $\{2, 3, 4, 5\}$. The defining condition is “$1\lt n\lt 6$”.  The set $\{2, 3, 4, 5\}$ is the truth set of the assertion “n is an integer and $1\lt n\lt 6$”.
  • The notation $\left\{x|{{x}^{2}}-4=0 \right\}$ denotes the set $\{2,-2\}$.
  • $\left\{ x|x+1=x \right\}$ denotes the empty set.
  • $\left\{ x|x+0=x \right\}=\mathbb{R}$.
  • $\left\{ x|x\gt6 \right\}$ is the infinite set of all real numbers bigger than $6$.  For example, $6\notin \left\{ x|x\gt6 \right\}$ and $17\pi \in \left\{ x|x\gt6 \right\}$.
  • The set $\mathbb{I}$ defined by $\mathbb{I}=\left\{ x|0\le x\le 1 \right\}$ has among its elements $0$, $1/4$, $\pi /4$, $1$, and an infinite number of
    other numbers. $\mathbb{I}$ is fairly standard notation for this set – it is called the unit interval.

Usage and terminology

  • A colon may be used instead of “|”. So $\{x|x\gt6\}$ could be written $\{x:x\gt6\}$.
  • Logicians and some mathematicians called the truth set of $P$ the extension of $P$. This is not connected with the usual English meaning of “extension” as an add-on.
  • When the assertion $P$ is an equation, the truth set of $P$ is usually called the solution set of $P$. So $\{2,-2\}$ is the solution set of $x^2=4$.
  • The expression “$\{n|1\lt n\lt6\}$” is commonly pronounced as “The set of integers such that $1\lt n$ and $n\lt6$.” This means exactly the set $\{2,3,4,5\}$. Students whose native language is not English sometimes assume that a set such as $\{2,4,5\}$ fits the description.

Setbuilder notation is tricky

Looking different doesn’t mean they are different.

A set can be expressed in many different ways in setbuilder notation. For example, $\left\{ x|x\gt6 \right\}=\left\{ x|x\ge 6\text{ and }x\ne 6 \right\}$. Those two expressions denote exactly the same set. (But $\left\{x|x^2\gt36 \right\}$ is a different set.)

Russell’s Paradox

In certain areas of math research, setbuilder notation can go seriously wrong. See Russell’s Paradox if you are curious.

Variations on setbuilder notation

An expression may be used left of the vertical line in setbuilder notation, instead of a single variable.

Giving the type of the variable

You can use an expression on the left side of setbuilder notation to indicate the type of the variable.


The unit interval $I$ could be defined as \[\mathbb{I}=\left\{x\in \mathrm{R}\,|\,0\le x\le 1 \right\}\]making it clear that it is a set of real numbers rather than, say rational numbers.  You can always get rid of the type expression to the left of the vertical line by complicating the defining condition, like this:\[\mathbb{I}=\left\{ x|x\in \mathrm{R}\text{ and }0\le x\le 1 \right\}\]

Other expressions on the left side

Other kinds of expressions occur before the vertical line in setbuilder notation as well.


The set\[\left\{ {{n}^{2}}\,|\,n\in \mathbb{Z} \right\}\]consists of all the squares of integers; in other words its elements are 0,1,4,9,16,….  This definition could be rewritten as $\left\{m|\text{ there is an }n\in \mathrm{}\text{ such that }m={{n}^{2}} \right\}$.


Let $A=\left\{1,3,6 \right\}$.  Then $\left\{ n-2\,|\,n\in A\right\}=\left\{ -1,1,4 \right\}$.


Be careful when you read such expressions.


The integer $9$ is an element of the set \[\left\{{{n}^{2}}\,|\,n\in \text{ Z and }n\ne 3 \right\}\]It is true that $9={{3}^{2}}$ and that $3$ is excluded by the defining condition, but it is also true that $9={{(-3)}^{2}}$ and $-3$ is not an integer ruled out by the defining condition.


Sets. Previous post.


Toby Bartels for corrections.

Creative Commons License< ![endif]>

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

Send to Kindle

Rabbits out of a hat

This is a revision and expansion of the entry on rabbits in the abstractmath article Dysfunctional attitudes and behaviors.


Sometimes when you are reading or listening to a proof you will find yourself following each step but with no idea why these steps are going to give a proof. This can happen with the whole structure of the proof or with the sudden appearance of a step that seems like the prover pulled a rabbit out of a hat . You feel as if you are walking blindfolded.

Example (mysterious proof structure)

The lecturer says he will prove that for an integer $n$, if $n^2$ is even then $n$ is even. He begins the proof: Let $n^2$ be odd” and then continues to the conclusion, “Therefore $n$ is odd.”

Why did he begin a proof about being even with the assumption that $n$ is odd?

The answer is that in this case he is doing a proof by contrapositive . If you don’t recognize the pattern of the proof you may be totally lost. This can happen if you don’t recognize other forms, for example contradiction and induction.

Example (rabbit)

You are reading a proof that $\underset{x\to2}{\mathop{\lim }}{{x}^{2}}=4$. It is an $\varepsilon \text{-}\delta$ proof, so what must be proved is:

  • For any positive real number $\varepsilon $,
  • there is a positive real number $\delta $ for which:
  • if $\left| x-2 \right|\lt\delta$ then
  • $\left| x^2-4 \right|\lt\varepsilon$.


Here is the proof, with what I imagine might be your agitated reaction to certain steps. Below is a proof with detailed explanations .

1) Suppose $\varepsilon \gt0$ is given.

2) Let $\delta =\text{min}\,(1,\,\frac{\varepsilon }{5})$ (the minimum of the two numbers 1 and $\frac{\varepsilon}{5}$ ).

Where the *!#@! did that come from? They pulled it out of thin air! I can’t see where we are going with this proof!

3) Suppose that $\left| x-2 \right|\lt\delta$.

4) Then $\left| x-2 \right|\lt1$ by (2) and (3).

5) By (4) and algebra, $\left|x+2 \right|\lt5$.

Well, so what? We know that $\left| x+39\right|\lt42$ and lots of other things, too. Why did they do this?

6) Also $\left| x-2 \right|\lt\frac{\varepsilon }{5}$ by (2) and(3).

7) Then $\left| {{x}^{2}}-4\right|=\left| (x-2)(x+2) \right|\lt\frac{\varepsilon }{5}\cdot 5=\varepsilon$ by (5) and (6). End of Proof.


This proof is typical of proofs in texts.

  • Steps 2) and 5) look like they were rabbits pulled out of a hat.
  • The author gives no explanation of where they came from.
  • Even so, each step of the proof follows from previous steps, so the proof is correct.
  • Whether you are surprised or not has nothing to do with whether it is correct.
  • In order to understand a proof, you do not have to know where the rabbits came from.
  • In general, the author did not think up the proof steps in the order they occur in the proof. (See this remark in the section on Forms of Proofs.) See also look ahead.

Proof with detailed explanations

  1. Suppose $\varepsilon >0$ is given. (We are starting a proof by universal generalization.)
  2. Let $\delta$ be the minimum of the two numbers $1$ and $\frac{\varepsilon}{5}$). (Rabbit out of the hat. You can “let” any symbol mean anything you want, so this is a legitimate thing to do even if you don’t see where this is all going.{
  3. Suppose $\left|x-2\right|\lt\delta$. (We are about to prove the conditional statement “If $\left| x-2 \right|\lt\delta$ then $\left| {{x}^{2}}-4 \right|\lt\varepsilon$” and we are proceeding by the direct method.)
  4. Then $\left| x-2 \right|\lt 1$ by (2) and (3). (The fact that $\delta =\text{min}\,(1,\,\frac{\varepsilon }{5})$ means that $\delta \le 1$ and that $\delta \le \frac{\varepsilon }{5}$. Since $\left| x-2 \right|\lt \delta $, the statement $\left| x-2 \right|\lt 1$ follows by transitivity of “$\lt $”. This is another rabbit. WHY do we want $\left| x-2 \right|\lt 1$? Be Patient.)
  5. By (4) and algebra, $\left| x+2 \right|\lt 5$. ($\left| x-2 \right|\lt 1$ means that $-1\lt x-2\lt 1$. Add $4$ to each term in this equation to get $3\lt x+2\lt 5$. This is another rabbit, but it is a correct statement!)
  6. Also $\left| x-2 \right|\lt \frac{\varepsilon }{5}$ by (2) and (3). ((2) says that $\delta\le\frac{\varepsilon }{5}$ and (3) says that $\left| x-2 \right|\lt\delta$, so $\left| x-2 \right|\lt \frac{\varepsilon }{5}$ follows by transitivity.)
  7. Then $\left| {{x}^{2}}-4\right|=\left| (x-2)(x+2) \right|\lt\frac{\varepsilon }{5}\cdot 5=\varepsilon$ by (5) and (6). End of Proof. (This last statement actually shows the algebra.)

Coming up with that proof

The author did not think up the proof steps in the order they occur in the proof. She looked ahead at the goal of proving that \[\left| {{x}^{2}}-4\right|\lt\varepsilon\] and thought of factoring the left side. Now she must prove that \[\left| (x-2)(x+2) \right|\lt\varepsilon\]

But if $\left|x-2\right|$ is small then $x$ has to be close to $2$, so that $x + 2$ can’t be too big. Since the only restriction on $\delta$ is that it has to be positive, let’s restrict it to being smaller than $1$. (The choice of $1$ is purely arbitrary. Any positive real number would do.)

In that case step (5) shows that $\left|x+2\right|\lt5$.. So how small do you have to make to make $\varepsilon$? In other words, how small do you have to make $\delta $ to make $\left| 5(x-2) \right|\lt\varepsilon$ (remembering that $\left| x-2 \right|\lt\delta $). Well, clearly $\frac{\varepsilon }{5}$ will do!

That explains her choice of $\delta$ be the minimum of the two numbers $1$ and $\frac{\varepsilon}{5}$. Notice that that choice is made very early in the proof but it was made only after experimenting with the sizes of $\left|x-2\right|$ and $\left|x+2\right|$.

You can check that if she had chosen to restrict $\delta $ to being less than 42, then she would need $\delta =\text{min}\,(42,\,\frac{\varepsilon }{47})$.


Thanks to Robert Burns for corrections and suggestions

Send to Kindle

Forms of proofs is a website I have been maintaining since 2005. It is intended for people beginning the study of abstract math, often a course that requires proofs and thinking about mathematical structures. The Introduction to the website and the article Attitude explain the website in more detail.

One of the chapters in covers Proofs. As everywhere in, there is no attempt at complete coverage: the emphasis is on aspects that cause difficulty for abstraction-newbies. In the case of proofs, this includes sections on how proofs are written (math language is a big emphasis all over One of those sections is Forms of Proof. This post is a fairly extensive revision of that section.

More than half of the section on Proofs has already been revised (the ones entitled “ 2.0)”, and my current task is to finish that revision.

Normally, I post the actual article here on Gyre&Gimble, but something has changed in the operation of WordPress which causes the html processor to obey linebreaks in the input, which would make the article look chaotic.

So this time, I have to ask you to click a button to read the revised section on Forms of Proof. I apologize for the excessive effort by your finger.

Creative Commons License

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

Send to Kindle

The many boobytraps of “if…then”


The truth table for conditionals

Conditionals and truth sets

Vacuous truth

Universal conditional assertions

Related assertions

Understanding conditionals

Modus ponens


This section is concerned with logical construc­tions made with the connective called the conditional operator. In mathe­matical English, applying the conditional operator to $P$ and $Q$ produces a sentence that may bewritten, “If $P$, then $Q$”, or “$P$ implies$Q$”. Sentences of this form are conditional assertions.

Conditional assertions are at the very heart of mathematical reasoning. Mathematical proofs typically consist of chains of conditional assertions.

Some of the narrative formats used for proving conditional assertions are discussed in Forms of Proof.

The truth table for conditional assertions

A conditional assertion “If $P$ then $Q$” has the precise truth table shown here.


$P$ $Q$ If $P$ then $Q$

The meaning of “If $P$ then $Q$” is determined entirely by the truth values of $P$ and $Q$ and this truth table. The meaning is not determined by the usual English meanings of the words “if” and “then”.

The truth table is summed up by this purple pronouncement:

The Prime Directive of conditional assertions:
A conditional assertion is true unless
the hypothesis is true and the conclusion is false.
That means that to prove “If $P$ then $Q$” is  FALSE
you must show that $P$ is TRUE(!) and $Q$ is FALSE.

The Prime Directive is harder to believe in than leprechauns. Some who are new to abstract math get into an enormous amount of difficulty because they don’t take it seriously.


The statement “if $n\gt 5$, then $n\gt 3$” is true for all integers

  • This means that “If $7\gt 5$ then $7\gt 3$” is true.
  • It also means that “If $2\gt 5$ then $2\gt 3$” is true!  If you really believe that “If $n\gt 5$, then $n\gt 3$” is true for all integers n, then you must in particular believe that  “If $2\gt 5$ then $2\gt 3$” is true.  That’s why the truth table for conditional assertions takes the form it does.
  • On the other hand, “If $n\gt 5$, then $n\gt 8$” is not true for all integers $n$.  In particular, “If $7\gt 5$, then $7\gt 8$” is false. This fits what the truth table says, too.

For more about this, see Understanding conditionals.


Most of the time in mathematical writing the conditional assertions which are actually stated involve assertions containing variables, and the claim is typically that the assertion is true for all instances of the variables. Assertions involving statements without variables occur only implicitly in the process of checking instances of the assertions. That is why a statement such as, “If $2\gt 5$ then $2\gt 3$” seems awkward and unfamiliar.

It is unfamiliar and occurs rarely. I mention it here because of the occurrence of vacuous truths, which do occur in mathematical writing.

Conditionals and Truth Sets

The set $\{x|P(x)\}$ is the set of exactly all $x$ for which $P(x)$ is true. It is called the truth set of $P(x)$.

  • If $n$ is an integer variable, then the truth set of “$3\lt n\lt9$” is the set $\{4,5,6,7,8\}$.
  • The truth set of “$n\gt n+1$” is the empty set.

Weak and strong

“If $P(x)$ then $Q(x)$” means that $\{x|P(x)\}\subseteq
\{x|Q(x)\}$.  We say $P(x)$ is stronger than $Q(x)$, meaning that $P$ puts more requirements on $x$ than $Q$ does.  The objects $x$ that make $P$ true necessarily make $Q$ true, so there might be objects making $Q$ true that don’t make $P$ true.


The statement “$x\gt4$” is stronger than the statement “$x\gt\pi$”. That means that $\{x|x\gt4\}$ is a proper subset of $\{x|x\gt\pi\}$. In other words, $\{x|x\gt4\}$ is “smaller” than $\{x|x\gt\pi\}$ in the sense of subsets. For example, $3.5\in\{x|x\gt\pi\}$ but $3.5\notin\{x|x\gt4\}$. This is a kind of reversal (a Galois correspondence) that confused many of my students.

“Smaller” means the truth set of the stronger statement omits elements that are in the truth set of the weaker statement. In the case of finite truth sets, “smaller” also means it has fewer elements, but that does not necessarily work for infinite sets, such as in the example above, because the two truth sets $\{x|x\gt4\}$ and $\{x|x\gt\pi\}$ have the same cardinality.

Making a statement stronger
makes its truth set “smaller”.

Terminology and usage

Hypothesis and conclusion

In the assertion “If $P$, then $Q$”:

  • P is the hypothesis or antecedent
    of the assertion.  It is a constraint or condition that holds in the very narrow context of the assertion.  In other words, the assertion, “If $P$, then $Q$” does not say that $P$ is true. The idea of the direct method of proof is to assume that $P$ is true during the proof.
  • $Q$ is the conclusion or consequent. It is also incorrect to assume that $Q$ is true anywhere else except in the assertion “If $P$, then $Q$”.


Conditionals such as “If $P$ then $Q$” are also called implications , but be wary: “implication” is a technical term and does not fit the meaning of the word in conversational English.

  • In ordinary English, you might ask, “What are the implications of knowing that $x\gt4$? Answer: “Well, for one thing, $x$ is bigger that $\pi$.”
  • In the terminology of math and logic, the whole statement “If $x\gt4$ then $x\gt\pi$” is called an “implication”.

Vacuous truth

The last two lines of the truth table for conditional assertions mean that if the hypothesis of the assertion is false, then the assertion is automatically true.
In the case that “If $P$ then $Q$” is true because $P$ is false, the assertion is said to be vacuously true.

The word “vacuous” refers to the fact that in the vacuous case the conditional assertion says nothing interesting about either $P$ or $Q$. In particular, the conditional assertion may be true even if the conclusion is false (because of the last line of the truth table).


Both these statements are vacuously true!

  • If $4$ is odd, then $3 = 3$.
  • If $4$ is odd, then $3\neq3$.

If $A$ is any set then $\emptyset\subseteq A.$ Proof (rewrite by definition): You have to prove that if $x\in\emptyset$, then $x\in A$. But the statement “$x\in\emptyset$” is false no matter what $x$ is, so the statement “$\emptyset\subseteq A$” is vacuously true.

Definitions involving vacuous truth

Vacuous truth can cause surprises in connection with certain concepts which are defined using a conditional assertion.

  • Suppose $R$ is a relation on a set $S$. Then $R$ is antisymmetric if the following statement is true: If for all $x,y\in S$, $xRy$ and $yRx$, then $x=y$.
  • For example, the relation “$\leq$” on the real numbers is antisymmetric, because if $x\leq y$ and $y\leq x$, then $x=y$.
  • The relation “$\lt$” on the real numbers is also antisymmetric. It is vacuously antisymmetric, because the statement

    (AS) “if $x\gt y$ and $y\gt x$, then $x = y$”

    is vacuously true. If you say it can’t happen that $x\gt y$ and $y\gt x$, you are correct, and that means precisely that (AS) is vacuously true.


Although vacuous truth may be disturbing when you first see it, making either statement in the example false would result in even more peculiar situations. For example, if you decided that “If $P$ then $Q$” must be false when $P$ and $Q$ are both false, you would then have to say that this statement

“For any integers $m$ and $n$, if $m\gt 5$ and $5\gt n$, then $m\gt n$”


is not always true (substitute $3$ for $m$ and $4$ for $n$ and you get both $P$ and $Q$ false). This would surely be an unsatisfactory state of affairs.

How conditional assertions are worded

A conditional assertion may be worded in various ways.  It takes some practice to get used to understanding all of them as conditional.

Our habit of swiping English words and phrases and changing their meaning in an unintuitive way causes many problems for new students, but I am sure that the worst problem of that kind is caused by the way conditional assertions are worded.

In math English

The most common ways of wording a conditional assertion with hypothesis $P$ and conclusion $Q$ are:

  • If $P$, then $Q$.
  • $P$ implies $Q$.
  • $P$ only if $Q$.
  • $P$ is sufficient for $Q$.
  • $Q$ is necessary for $P$.

In the symbolic language

  • $P(x)\to Q(x)$
  • $P(x)\Rightarrow Q(x)$
  • $P(x)\supset Q(x)$

Math logic is notorious for the many different symbols used by different authors with the same meaning. This is in part because it developed separately in three different academic areas: Math, Philosophy and Computing Science.


All the statements below mean the same thing. In these statements $n$ is an integer variable.

  • If $n\lt5$, then $n\lt10$.
  • $n\lt5$ implies $n\lt10$.
  • $n\lt5$ only if $n\lt10$.
  • $n\lt5$ is sufficient for $n\lt10$.
  • $n\lt10$ is necessary for $n\lt5$.
  • $n\lt5\to n\lt10$
  • $n\lt5\Rightarrow n\lt10$
  • $n\lt5\supset n\lt10$

Since “$P(x)\supset Q(x)$” means that $\{x|P(x)\}\subseteq
\{x|Q(x)\}$, there is a notational clash between implication written “$\supset $” and inclusion written “$\subseteq $”. This is exacerbated by the two meanings of the inclusion symbol “$\subset$”.

These ways of wording conditionals cause problems for students, some of them severe. They are discussed in the section Understanding conditionals.

Usage of symbols

The logical symbols “$\to$”, “$\Rightarrow$”,
“$\supset$” are frequently used when writing on the blackboard, but are not common in texts, except for texts in mathematical logic.

More about implication in logic

If you know some logic, you may know that there is a subtle difference between the statements

  • “If $P$ then $Q$”
  • “$P$ implies $Q$”.

Here is a concrete example:

  1. “If $x\gt2$,  then $x$ is positive.”
  2. “$x\gt2$ implies that $x$ is positive.”

Note that the subject of sentence (1) is the (variable) number $x$, but the subject of sentence (2) is the assertion
“$x\lt2$”.   Behind this is a distinction made in formal logic between the material conditional “if $P$ then $Q$” (which means that $P$ and $Q$ obey the truth table for “If..then”) and logical consequence ($Q$ can be proved given $P$). I will ignore the distinction here, as most mathematicians do except when they are proving things about logic.

In some texts, $P\Rightarrow Q$ denotes the material conditional and $P\to Q$ denotes logical consequence.

Universal conditional assertions

A conditional assertion containing a variable that is true for any value of the correct type of that variable is a universally true conditional assertion. It is a special case of the general notion of universally true assertion.

  1. For all $x$, if $x\lt5$, then $x\lt10$.
  2. For any integer $n$, if $n^2$ is even, then $n$ is even.
  3. For any real number $x$, if $x$ is an integer, then $x^2$ is an integer.

These are all assertions of the form “If $P(x)$, then $Q(x)$”. In (1), the hypothesis is the assertion “$x\lt5$”; in (2), it is the assertion “$n^2$ is even”, using an adjective to describe property that $n^2$ is even; in (3), it is the assertion “$x$ is an integer”, using a noun to assert that $x$ has the property of being an integer. (See integral.)

Expressing universally true conditionals in math English

The sentences listed in the example above provide ways of expressing universally true conditionals in English. They use “for all” or “for any”, You may also use these forms (compare in this discussion of universal assertions in general.)

  • For all functions $f$, if $f$ is differentiable then it is continuous.
  • For (every, any, each) function $f$, if $f$ is differentiable then it is continuous.
  • If $f$ is differentiable then it is continuous, for any function $f$.
  • If $f$ is differentiable then it is continuous, where $f$ is any function.
  • If a function $f$ is differentiable, then it is continuous. (See indefinite article.)

Sometimes mathematicians write, “If the function $f$ is differentiable, then it is continuous.” At least sometimes, they mean that every function that is differentiable is continuous. I suspect that this usage occurs in texts written by non-native-English speakers.

Disguised conditionals

There are other ways of expressing universal conditionals that are disguised, because they are not conditional assertions in English.

Let $C(f)$ mean that $f$ is continuous and and $D(f)$ mean that $f$ is differentiable. The (true) assertion

“For all $f$, if $D(f)$, then $C(f)$”


can be said in the following ways:

  1. Every (any, each) differentiable function is continuous.
  2. All differentiable functions are continuous.
  3. Differentiable functions are continuous. Or: “…are always continuous.”
  4. A differentiable function is continuous.
  5. The differentiable functions are continuous.


  • Watch out for (4). Beginning abstract math students sometimes don’t recognize it as universal. They may read it as “Some differentiable function is continuous.” Authors often write, “A differentiable function is necessarily continuous.”
  • I believe that (5) is obsolescent. I don’t think younger native-English-speaking Americans would use it. (Warning: This claim is not based on lexicographical research.)

Assertions related to a conditional assertion


The converse of a conditional assertion “If $P$ then $Q$” is “If $Q$ then $P$”.

Whether a conditional assertion is true
has no bearing on whether its converse it true.

  • The converse of “If it’s a cow, it eats grass” is “If it eats grass, it’s a cow”. The first statement is true (let’s ignore the Japanese steers that drink beer or whatever), but the second statement is definitely false. Sheep eat grass, and they are not cows..
  • The converse of “For all real numbers $x$, if $x > 3$, then $x > 2$.” is “For all real numbers $x$, if $x > 2$, then $x > 3$.” The first is true and the second one is false.
  • “For all integers $n$, if $n$ is even, then $n^2$ is even.” Both this statement and its converse are true.
  • “For all integers $n$, if $n$ is divisible by $2$, then $2n +1$ is divisible by $3$.” Both this statement and its converse are false.


The contrapositive of a conditional assertion “If $P$ then $Q$” is “If not $Q$ then not $P$.”

A conditional assertion and its contrapositive
are both true or both false.


The contrapositive of
“If $x > 3$, then $x > 2$”
is (after a little translation)
“If $x\leq2$ then $x\leq3$.”
For any number $x$, these two statements are both true or both false.

This means that if you prove “If not $P$ then not $Q$”, then you have also proved “If $P$ then $Q$.”

You can prove an assertion by proving its contrapositive.

This is called the contrapositive method and is discussed in detail in this section.

So a conditional assertion and its contrapositive have the same truth value. Two assertions that have the same truth value are said to be equivalent. Equivalence is discussed with examples in the Wikipedia article on necessary and sufficient.

Understanding conditional assertions

As you can see from the preceding discussions, statements of the form “If $P$ then Q” don’t mean the same thing in math that they do in ordinary English. This causes semantic contamination.



In ordinary English, “If $P$ then $Q$” can suggest order of occurrence. For example, “If we go outside, then the neighbors will see us” implies that the neighbors will see us after we go outside.

Consider “If $n\gt7$, then $n\gt5$.” If $n\gt7$, that doesn’t mean $n$ suddenly gets greater than $7$ earlier than $n$ gets greater than $5$. On the other hand, “$n\gt5$ is necessary for $n\gt7$” (which remember means the same thing as “If $n\gt7$, then $n\gt5$) doesn’t mean that $n\gt5$ happens earlier than $n\gt7$. Since we are used to “if…then” having a timing implication, I suspect we get subconscious dissonance between “If $P$ then $Q$” and “$Q$ is necessary for $P$” in mathematical statements, and this dissonance makes it difficult to believe that that can mean the same thing.


“If $P$ then $Q$” can also suggest causation. The the sentence, “If we go outside, the neighbors will see us” has the connotation that the neighbors will see us because we went outside.

The contrapositive is “If the neighbors won’t see us, then we don’t go outside.” This English sentence seems to me to mean that if the neighbors are not around to see us, then that causes us to stay inside. In contrast to contrapositive in math, this means something quite different from the original sentence.

Wrong truth table

For some instances of the use of “if…then” in English, the truth table is different.

Consider: “If you eat your vegetables, you can have dessert.” Every child knows that this means they will get dessert if they eat their vegetables and not otherwise. So the truth table is:

$P$ $Q$ If $P$ then $Q$

In other words, $P$ is equivalent to $Q$. It appears to me that this truth table corresponds to English “if…then” when a rule is being asserted.

These examples show:

The different ways of expressing conditional assertions
may mean different things in English.

How can you get to the stage where you automatically understand the meaning of conditional assertions in math English?

You need to understand the equivalence of these formulations so well that it is part of your unconscious reaction to conditionals.

How can you gain that intuitive understanding? One way is by doing abstract math regularly for several years! (Of course, this is how you gain expertise in anything.) In other words, Practice, Practice!


But it may help to remember that when doing proofs, we must take the rigorous view of mathematical objects:

  • Math objects don’t change.
  • Math objects don’t cause anything to happen.

The integers (like all math objects) just sit there, not doing anything and not affecting anything. $10$ is not greater than $4$ “because” it is greater than $7$. There is no “because” in rigorous math. Both facts, $10\gt4$ and $10\gt7$, are eternally true.

Eternal is how we think of them – I am not making a claim about “reality”.

  • When you look at the integers, every time you find one that is greater than $7$ it turns out to be greater than $4$. That is how to think about “If $n > 7$, then $n > 4$”.
  • You can’t find one that is greater than $7$ unless it is greater than $4$: It happens that $n > 7$ only if $n > 4$.
  • Every time you look at one less than or equal to $4$ it turns out to be less than or equal to $7$ (contrapositive).

These three observations describe the same set of facts about a bunch of things (integers) that just sit there in their various relationships without changing, moving or doing anything. If you keep these remarks in mind, you will eventually have a natural, unforced understanding of conditionals in math.


None of this means you have to think of mathematical objects as dead and fossilized all the time. Feel free to think of them using all the metaphors and imagery you know, except when you are reading or formulating a proof written in mathematical English. Then you have to be rigorous!

Modus ponens

The truth table for conditional assertions may be summed up by saying: The conditional assertion “If $P$, then $Q$” is true unless $P$ is true and $Q$ is false.

This fits with the major use of conditional assertions in reasoning:

Modus Ponens

  • If you know that a conditional assertion is true
  • and
    you know that its hypothesis is true,
  • then you know its conclusion is true.

In symbols:

(1) When “If $P$ then $Q$” and $P$ are both true,

(2) then $Q$ must be true as well.

Modus Ponens is the most used method of deduction of all.


Modus ponens is not a method of proving conditional assertions. It is a method of using a conditional assertion in the proof of another assertion. Methods for proving conditional assertions are found in the chapter Forms of proof.

Creative Commons License<![endif]>

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


Send to Kindle

The role of proofs in mathematical writing

This post outlines the way that proofs are used in mathematical writing. I have been revising the chapter on Proofs in, and I felt that giving an overview would keep my mind organized when I was enmeshed in writing up complicated details.

Proofs are the sole method for ensuring that a math statement is correct.

  • Evidence that something is true gooses us into trying to prove it, but as all research mathematicians know, evidence only means that some instances are true, nothing else.
  • Intuition, metaphors, analogies may lead us to come up with conjectures. If the gods are smiling that day, they may even suggest a method of proof. And that method may even (miracle) work. Sometimes. If it does, we get a theorem, but not a Fields medal.
  • Students may not know these facts about proof. Indeed, students at the very beginning probably don’t know what a proof actually is: “Proof” in math is not at all the same as “proof” in science or “proof” in law.

A proof has two faces: Its logical structure and its presentation.

The logical structure of a proof consists of methods of compounding and quantifying assertions and methods of deduction.

  • The logical structure is usually expressed as a mathematical object.
  • The most familiar such math objects are the predicate calculus and type theory.
  • Mathematical logic does not have standard terminology (see Math reasoning.) Because of that, the chapter on Proofs uses English words, for example “or” instead of symbols such as $P\lor Q$ or $P+Q$ or $P||Q$.
  • For beginning students, throwing large chunks of mathematical logic at them doesn’t work. The expressions and the rules of deduction need to be introduced to them in context, and in my opinion using few or no logical symbols.
  • Students vary widely in their ability to grasp foreign languages, and symbolic logic in any of its forms is a foreign language. (So is algebra; see my rant.)
  • The rules of deduction do not come naturally to the students, and yet they need to have the rules operate automatically and subconsciously. They should know the names of the nonobvious rules, like “proof by contradiction” and “induction”, but teaching them to be fluent with logical notation is probably a waste of time, since they would have to learn the rules of deduction and a new foreign language at the same time.
  • I hasten to add, a waste of time for beginning students. There are good reasons for students aiming at certain careers to be proficient in type theory, and maybe even for predicate calculus.

Presentation of proofs

  • Proofs are usually written in narrative form
  • A major source of difficulties is that the presentation of a proof (the way it is written in narrative form) omits the reasons that most of the proof steps follow from preceding ones.
  • Some of the omitted reasons may depend on knowledge the reader does not have. “Let $S\subset\mathbb{Q}\times\mathbb{Q}$. Let $i:S\to\mathbb{N}$ be a bijection…” Note: I am not criticizing someone who writes an argument like this, I am just saying that it is a problem for many beginning students.
  • Some reasons are given for some of the steps, presumably ones that the writer thinks might not be obvious to the reader.
  • Sometimes the narrative form gives a clue to the form of proof to be used. Example: “Prove that the length $C$ of the hypotenuse of a right triangle is less than the sum of the other two sides $A$ and $B$. Proof: Assume $C\geq A+B$…” So you immediately know that this is going to be a proof by contradiction. But you have to teach the student to recognize this.
  • Another example: in proving $P$ implies $Q$, the author will assume that $Q$ is false implies $P$ is false without further comment. The reader is suppose to recognize the proof by contrapositive.

Translation problem

  • The Translation problem is the problem of translating a narrative proof into the logical reasoning needed to see that it really is a proof.
  • Many experienced professional mathematicians say it is so hard for them to read a narrative proof that they read the theorem and the try to recreate the proof by thinking about it and glancing at the written proof for hints from time to time. That is a sign of how difficult the translation problem really is.
  • Nevertheless, the students need to learn the unfamiliar proof techniques such as contrapositive and contradiction and the wording tricks that communicate proof methodology. Learning this is hard work. It helps for teachers to be more explicit about the techniques and tricks with students who are beginning math major courses.


Added 2014-12-19

Creative Commons License

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

Send to Kindle

Those monks

In my long post, Proofs without dry bones, I discussed the Monk Theorem (my name) in the context of my ideas about rigorous proof. Here, I want to amplify some of my remarks in the post.

This post was stimulated by Mark Turner’s new book on conceptual blending. That book has many examples of conceptual blending, including the monk theorem, that go into deep detail about how they work. I highly recommend reading his analysis of the monk theorem. Note: I haven’t finished reading the book.

The Monk Theorem

A monk starts at dawn at the bottom of a mountain and goes up a path to the top, arriving there at dusk. The next morning at dawn he begins to go down the path, arriving at dusk at the place he started from on the previous day. Prove that there is a time of day at which he is at the same place on the path on both days.

Proof: Envision both events occurring on the same day, with a monk starting at the top and another starting at the bottom at the same time and doing the same thing the original monk did on different days. They are on the same path, so they must meet each other. The time at which they meet is the time required.

The proof

One of the points in Proofs without dry bones was that the proof above is a genuine mathematical proof, in spite of the fact that it uses no recognizable math theorems or math objects. It does contain unspoken assumptions, but so does any math proof. Some of the assumptions:

  • A path has the property that if two people, one at each end, start walking to the opposite end, they will meet each other at a certain time.
  • A day is a period of time which contains a time “dawn” and a later time “dusk”.

From a mathematician’s point of view, the words “people”, “walking”, “meet”, “path”, “day”, “dawn” and “dusk” could be arbitrary names having the properties stipulated by the assumptions. This is typical mathematical behavior. “Time” is assumed to behave as we commonly perceive it.

If you think closely about the proof, you will probably come up with some refinements that are necessary to reveal other hidden assumptions (particularly about time). That is also typical mathematical behavior. (Remember Hilbert refining Euclid’s postulates about geometry after thousands of year of people not noticing the enthymemes in the postulates.)

This proof does not require that walking on the path be modeled by a function \[t\mapsto (x,y,z):\mathbb{R}\to\mathbb{R}\times\mathbb{R}\times\mathbb{R}\] followed by an appeal to the intermediate value theorem, which I mentioned in “Proofs without dry bones”.

You could simply proceed to make your assumptions about “path”, “meet”, “time”, and so on more explicit until you (or the mathematician you are arguing with) is satisfied. It is in that sense that I claim the proof given above is a genuine mathematical proof.


  • The Origin of Ideas: Blending, Creativity, and the Human Spark, by Mark Turner. Oxford University Press, 2014.
  • The Way We Think: Conceptual Blending And The Mind’s Hidden Complexities, by Giles Fauconnier and Mark Turner. Basic Books, 2003.
  • Proofs without dry bones. Blog post.
  • The rigorous view: inertness. Article on
  • Conceptual blending in Wikipedia.
Send to Kindle

Math majors attacked by cognitive dissonance

In some situations you may have conflicting information from different sources about a subject.   The resulting confusion in your thinking is called cognitive dissonance.

It may happen that a person suffering cognitive dissonance suppresses one of the ways of understanding in order to resolve the conflict.  For example, at a certain stage in learning English, you (small child or non-native-English speaker) may learn a rule that the past tense is made from the present form by adding “-ed”. So you say “bringed” instead of “brought” even though you may have heard people use “brought” many times.  You have suppressed the evidence in favor of the rule.

Some of the ways cognitive dissonance can affect learning math are discussed here

Metaphorical contamination

We think about math objects using metaphors, as we do with most concepts that are not totally concrete.  The metaphors are imperfect, suggesting facts about the objects that may not follow from the definition. This is discussed at length in the section on images and metaphors here.

The real line

Mathematicians think of the real numbers as constituting a line infinitely long in both directions, with each number as a point on the line. But this does not mean that you can think of the line as a row of points. Between any two points there are uncountably many other points. See density of the reals.

Infinite math objects

One of the most intransigent examples of metaphorical contamination occurs when students think about countably infinite sets. Their metaphor is that a sequence such as the set of natural numbers $\{0,1,2,3,4,\ldots\}$ “goes on forever but never ends”. The metaphor mathematicians have in mind is quite different: The natural numbers constitute the set that contains every natural number right now.


An excruciating example of this is the true statement
$.999\ldots=1.0$.” The notion that it can’t be true comes from thinking of “$0.999\ldots$” as consisting of the list of numbers \[0.9,0.99,0.999,0.9999,0.99999,\ldots\] which the student may say “gets closer and closer to $1.0$ but never gets there”.

Now consider the way a mathematician thinks: The numbers are all already there, and they make a set.

The proof that $.999\ldots=1.0$ has several steps. In the list below, I have inserted some remarks in red that indicate areas of abstract math that beginning students have trouble with.

  1. The elements of an infinite set are all in it at once. This is the way mathematicians think about infinite sets.
  2. By definition, an infinite decimal expansion represents the unique real number that is a limit point of its set of truncations.
  3. The problem that occurs with the word “definition” in this case is that a definition appears to be a dictatorial act. The student needs to know why you made this definition. This is not a stupid request. The act can be justified by the way the definition gets along with the algebraic and topological characteristic of the real numbers.

  4. It follows from $\epsilon-\delta$ machinations that the limit of the sequence $0.9,0.99,0.999,0.9999,0.99999,\ldots$ is $1.0$
  5. That means “$0.999\ldots$” represents $1.0$. (Enclosing a mathematical expression in quotes turns it into a string of characters.)
  6. The statement “$A$” represents $B$ is equivalent to the statement $A=B$. (Have you ever heard a teacher point this out?)
  7. It follows that that $0.999\ldots=1.0$.

Each one of these steps should be made explicit. Even the Wikipedia article, which is regarded as a well written document, doesn’t make all of the points explicit.

Semantic contamination

Many math objects have names that are ordinary English words. 
(See names.) So the person learning about them is faced with two inputs:

  • The definition of the word as a math object.
  • The meaning and connotations of the word in English.

It is easy and natural to suppress the information given by the definition (or part of it) and rely only on the English meaning. But math does not work that way:

If another source of understanding contradicts the definition


The connotations of a name may fit the concept in some ways and not others. Infinite cardinal numbers are a notorious example of this: there are some ways in which they are like numbers and other in which they are not. 

For a finite set, the cardinality of the set is the number of elements in the set. Long ago, mathematicians started talking about the cardinality of an infinite set. They worked out a lot of facts about that, for example:

  • The cardinality of the set of natural numbers is the same as the cardinality of the set of rational numbers.
  • The cardinality of the number of points on the real line is the same as the cardinality of points in the real plane.

The teacher may even say that there are just as many points on the real line as in the real points. And know-it-all math majors will say that to their friends.

Many students will find that totally bizarre. Essentially, what has happened is that the math dictators have taken the phrase “cardinality” to mean what it usually means for finite sets and extend it to infinite sets by using a perfectly consistent (and useful) definition of “cardinality” which has very different properties from the finite case.

That causes a perfect storm of cognitive dissonance.

Math majors must learn to get used to situations like this; they occur in all branches of math. But it is bad behavior to use the phrase “the same number of elements” to non-mathematicians. Indeed, I don’t think you should use the word cardinality in that setting either: you should refer to a “one-to-one correspondence” instead and admit up front that the existence of such a correspondence is quite amazing.


Let’s look at the word “series”in more detail. In ordinary English, a series is a bunch of things, one after the other.

  • The World Series is a series of up to seven games, coming one after another in time.
  • A series of books is not just a bunch of books, but a bunch of books in order.
  • In the case of the Harry Potter series the books are meant to be read in order.
  • A publisher might publish a series of books on science, named Physics, Chemistry,
    Astronomy, Biology,
    and so on, that are not meant to be read in order, but the publisher will still list them in order.(What else could they do? See Representing and thinking about sets.)

Infinite series in math

In mathematics an infinite series is an object expressed like this:


where the ${{a}_{k}}$ are numbers. It has partial sums


For example, if ${{a}_{k}}$ is defined to be $1/{{k}^{2}}$ for positive integers $k$, then

about }1.49\]

This infinite series converges to $\zeta (2)$, which is about $1.65$. (This is not obvious. See the Zeta-function article in Wikipedia.) So this “infinite series” is really an infinite sum. It does not fit the image given by the English word “series”. The English meaning contaminates the mathematical meaning. But the definition wins.

The mathematical word that corresponds to the usual meaning of “series” is “sequence”. For example, $a_k:=1/{{k}^{2}}$ is the infinite sequence $1,\frac{1}{4},\frac{1}{9},\frac{1}{16}\ldots$ It is not an infinite series.

“Only if”

“Only if” is also discussed from a more technical point of view in the article on conditional assertions.

In math English, sentences of the form $P$ only if $Q$” mean exactly the same thing as “If $P$ then $Q$”. The phrase “only if” is rarely used this way in ordinary English discourse.

Sentences of the form “$P$ only if $Q$” about ordinary everyday things generally do not mean the same thing as “If $P$ then $Q$”. That is because in such situations there are considerations of time and causation that do not come up with mathematical objects. Consider “If it is raining, I will carry an umbrella” (seeing the rain will cause me to carry the umbrella) and “It is raining only if I carry an umbrella” (which sounds like my carrying an umbrella will cause it to rain).   When “$P$ only if $Q$” is about math objects,
there is no question of time and causation because math objects are inert and unchanging.

 Students sometimes flatly refuse to believe me when I tell them about the mathematical meaning of “only if”.  This is a classic example of semantic contamination.  Two sources of information appear to contradict each other, in this case (1) the professor and (2) a lifetime of intimate experience with the English language.  The information from one of these sources must be rejected or suppressed. It is hardly surprising that many students prefer to suppress the professor’s apparently unnatural and usually unmotivated claims.

These words also cause severe cognitive dissonance

  • “If” causes notorious difficulties for beginners and even later. They are discussed in abmath here and here.
  • A, an
    and the implicitly signal the universal quantifier in certain math usages. They cause a good bit of trouble in the early days of some students.

The following cause more minor cognitive dissonance.

References for semantic contamination

Besides the examples given above, you can find many others in these two works:

  • Pimm, D. (1987), Speaking Mathematically: Communications in Mathematics Classrooms.  Routledge & Kegan Paul.
  • Hersh, R. (1997),”Math lingo vs. plain English: Double entendre”. American Mathematical Monthly, vol 104,pages 48-51.
Send to Kindle

A very early satori that occurs with beginning abstract math students

In the previous post Pattern recognition and me, I wrote about how much I enjoyed sudden flashes of understanding that were caused by my recognizing a pattern (or learning about a pattern). I have had several such, shall we say, Thrills in learning about math and doing research in math. This post is about a very early thrill I had when I first started studying abstract algebra. As is my wont, I will make various pronouncements about what these mean for teaching and understanding math.


Early in any undergraduate course involving group theory, you learn about cosets.

Basic facts about cosets

  1. Every subgroup of a group generates a set of left cosets and a set of right cosets.
  2. If $H$ is a subgroup of $G$ and $a$ and $b$ are elements of $G$, then $a$ and $b$ are in the same left coset of $H$ if and only if $a^{-1}b\in H$. They are in the same right coset of $H$ if and only if $ab^{-1}\in H$.
  3. Alternative definition: $a$ and $b$ are in the same left coset of $H$ if $a=bh$ for some $h\in H$ and are in the same right coset of $H$ if $a=hb$ for some $h\in H$
  4. One of the (left or right) cosets of $H$ is $H$ itself.
  5. The relations
    $a\underset{L}\sim b$ if and only if $a^{-1}b\in H$


    $a\underset{R}\sim b$ if and only if $ab^{-1}\in H$

    are equivalence relations.

  6. It follows from (5) that each of the set of left cosets of $H$ and the set of right cosets of $H$ is a partition of $G$.
  7. By definition, $H$ is a normal subgroup of $G$ if the two sets of cosets coincide.
  8. The index of a subgroup in a group is the cardinal number of (left or right) cosets the subgroup has.

Elementary proofs in group theory

In the course, you will be asked to prove some of the interrelationships between (2) through (5) using just the definitions of group and subgroup. The teacher assigns these exercises to train the students in the elementary algebra of elements of groups.


  1. If $a=bh$ for some $h\in H$, then $b=ah’$ for some $h’\in H$. Proof: If $a=bh$, then $ah^{-1}=(bh)h^{-1}=b(hh^{-1})=b$.
  2. If $a^{-1}b\in H$, then $b=ah$ for some $h\in H$. Proof: $b=a(a^{-1}b)$.
  3. The relation “$\underset{L}\sim$” is transitive. Proof: Let $a^{-1}b\in H$ and $b^{-1}c\in H$. Then $a^{-1}c=a^{-1}bb^{-1}c$ is the product of two elements of $H$ and so is in $H$.
Miscellaneous remarks about the examples
  • Which exercises are used depends on what is taken as definition of coset.
  • In proving Exercise 2 at the board, the instructor might write “Proof: $b=a(a^{-1}b)$” on the board and the point to the expression “$a^{-1}b$” and say, “$a^{-1}b$ is in $H$!”
  • I wrote “$a^{-1}c=a^{-1}bb^{-1}c$” in Exercise 3. That will result in some brave student asking, “How on earth did you think of inserting $bb^{-1}$ like that?” The only reasonable answer is: “This is a trick that often helps in dealing with group elements, so keep it in mind.” See Rabbits.
  • That expression “$a^{-1}c=a^{-1}bb^{-1}c$” doesn’t explicitly mention that it uses associativity. That, too, might cause pointing at the board.
  • Pointing at the board is one thing you can do in a video presentation that you can’t do in a text. But in watching a video, it is harder to flip back to look at something done earlier. Flipping is easier to do if the video is short.
  • The first sentence of the proof of Exercise 3 is, “Let $a^{-1}b\in H$ and $b^{-1}c\in H$.” This uses rewrite according to the definition. One hopes that beginning group theory students already know about rewrite according to the definition. But my experience is that there will be some who don’t automatically do it.
  • in beginning abstract math courses, very few teachers
    tell students about rewrite according to the definition. Why not?

  • An excellent exercise for the students that would require more than short algebraic calculations would be:
    • Discuss which of the two definitions of left coset embedded in (2), (3), (5) and (6) is preferable.
    • Show in detail how it is equivalent to the other definition.

A theorem

In the undergraduate course, you will almost certainly be asked to prove this theorem:

A subgroup $H$ of index $2$ of a group $G$ is normal in $G$.

Proving the theorem

In trying to prove this, a student may fiddle around with the definition of left and right coset for awhile using elementary manipulations of group elements as illustrated above. Then a lightbulb appears:

In the 1980’s or earlier a well known computer scientist wrote to me that something I had written gave him a satori. I was flattered, but I had to look up “satori”.

If the subgroup has index $2$ then there are two left cosets and two right cosets. One of the left cosets and one of the right cosets must be $H$ itself. In that case the left coset must be the complement of $H$ and so must the right coset. So those two cosets must be the same set! So the $H$ is normal in $G$.

This is one of the earlier cases of sudden pattern recognition that occurs among students of abstract math. Its main attraction for me is that suddenly after a bunch of algebraic calculations (enough to determine that the cosets form a partition) you get the fact that the left cosets are the same as the right cosets by a purely conceptual observation with no computation at all.

This proof raises a question:

Why isn’t this point immediately obvious to students?

I have to admit that it was not immediately obvious to me. However, before I thought about it much someone told me how to do it. So I was denied the Thrill of figuring this out myself. Nevertheless I thought the solution was, shall we say, cute, and so had a little thrill.

A story about how the light bulb appears

In doing exercises like those above, the student has become accustomed to using algebraic manipulation to prove things about groups. They naturally start doing such calculations to prove this theorem. They presevere for awhile…

Scenario I

Some students may be in the habit of abandoning their calculations, getting up to walk around, and trying to find other points of view.

  1. They think: What else do I know besides the definitions of cosets?
  2. Well, the cosets form a partition of the group.
  3. So they draw a picture of two boxes for the left cosets and two boxes for the right cosets, marking one box in each as being the subgroup $H$.
  4. If they have a sufficiently clear picture in their head of how a partition behaves, it dawns on them that the other two boxes have to be the same.
Remarks about Scenario I
  • Not many students at the earliest level of abstract math ever take a break and walk around with the intent of having another approach come to mind. Those who do Will Go Far. Teachers should encourage this practice. I need to push this in
  • In good weather, David Hilbert would stand outside at a shelf doing math or writing it up. Every once in awhile he would stop for awhile and work in his garden. The breaks no doubt helped. So did standing up, I bet. (I don’t remember where I read this.)
  • This scenario would take place only if the students have a clear understanding of what a partition is. I suspect that often the first place they see the connection between equivalence relations and partitions is in a hasty introduction at the beginning of a group theory or abstract algebra course, so the understanding has not had long to sink in.

Scenario II

Some students continue to calculate…

  1. They might say, suppose $a$ is not in $H$. Then it is in the other left coset, namely $aH$.
  2. Now suppose $a$ is not in the “other” right coset, the one that is not $H$. But there are only two right cosets, so $a$ must be in $H$.
  3. But that contradicts the first calculation I made, so the only possibility left is that $a$ is in the right coset $Ha$. So $aH\subseteq Ha$.
  4. Aha! But then I can use the same argument the other way around, getting $Ha\subseteq aH$.
  5. So it must be that $aH=Ha$. Aha! …indeed.
Remarks about Scenario 2
  • In step (2), the student is starting a proof by contradiction. Many beginning abstract math students are not savvy enough to do this.
  • Step (4) involves recognizing that an argument has a dual. does not mention dual arguments and I can’t remember emphasizing the idea to my classes. Tsk.
  • Scenario 2 involves the student continuing algebraic calculations till the lightbulb strikes. The lightbulb could also occur in other places in the calculation.


Send to Kindle

Pattern recognition and me

Recently, I revised the article on pattern recognition. Doing that that prompted me to write about my own experiences with patterns. Recognizing patterns is something that has always delighted me: it is more of a big deal for me than it does for many other people. That, I believe, is what led me into doing research in math.

I have had several experiences with déjà vu, which is the result of pattern recognition with one pattern hidden. That will be a separate post. I expect to post about my experiences in recognizing patterns in math as well.

Patterns in language

As a teenager I was a page in the Savannah Public Library. There I discovered grammars for many languages. The grammars of other languages are astonishingly different from each other and are full of obscurities that I love to detect. Until I went to college, I was the only person I knew who read grammars for fun.

I am using the word “grammar” in the sense that linguists use it: patterns in our speech and writing, mostly unnoticed, that help express what we want to say)

The word “grammar” is also used to mean rules laid down by the ruling classes about phrases like “between you and I” and the uses of “whom”. Such rules primarily divide the underprivileged from the privileged, and many will disappear when the older members of the privileged class die (but they will think of new ones).

Grammar-induced glee


I got pretty good at reading and speaking Russian when I was a student (1959-62), but most of it has disappeared. In 1990, we hosted a Russian cello student with the Soviet-American Youth Orchestra for a couple of days. I could hardly say anything to him. One time he noticed one of our cats and said “кошка”, to which I replied “два кошки” (“two cats”). He responded by correcting me: “две кошки”. Then I remembered that the word for “two” in Russian is the only word in the language that distinguishes gender in the plural. I excitedly went around telling people about this until I realized that no one cared.


Recently I visited a display about the Maya at the Minnesota Science Museum that had all its posters in English and Spanish. I discovered a past subjunctive in one of the Spanish texts. That was exciting, but I had no one to be excited with.

The preceding paragraph is an example of a Pity Play.

Just the other day our choir learned a piece for Christmas with Spanish words. It had three lines in a row ending in a past subjunctive. (It is in rhyming triples and if you use all first conjugation verbs they rhyme.) Such excitement.


During the Cold War, I spent 18 months at İncirlik Air Base in Turkey. Turkish is a wonderful language for us geeks, very complicated yet most everything is regular. Like a computer language.

I didn’t know about computer languages during the Cold War, although they were just beginning to be used. I did work on a “computer” that you programmed by plugging cables into holes in various ways.

In Turkish, to modify a noun by a noun, you add an ending to the second noun. “İş Bankası” (no dot over the i) means “business bank”. (We would say “commercial bank”.) “İş” means “business” and “bank” by itself is “banka”. Do you think this is a lovably odd pattern? Well I do. But that’s the way I am.

A spate of spit

We live a couple blocks from Minnehaha Falls in Minneapolis. Last June the river flooded quite furiously and I went down to photograph it. I thought to my self, the river is in full spate. I wondered if the word “spate” came from the same IE root as the word “spit”. I got all excited and went home and looked it up. (No conclusion –it looks like it might be but there is no citation that proves it). Do you know anyone who gets excited about etymology?

Secret patterns in nature

All around us there are natural patterns that people don’t know about.

Cedars in Kentucky

For many years, we occasionally drove back and forth between Cleveland (where we lived) and Atlanta (where I had many relatives). We often stopped in Kentucky, where Jane grew up. It delighted me to drive by abandoned fields in Kentucky where cedars were colonizing. (They are “red cedars,” which are really junipers, but the name “cedar” is universal in the American midwest.)

What delighted me was that I knew a secret pattern: The presence of cedars means that the soil is over limestone. There is a large region including much of Kentucky and southern Indiana that lies over limestone underneath.

That gives me another secret: When you look closely at limestone blocks in a building in Bloomington, Indiana, you can see fossils. (It is better if the block is not polished, which unfortunately the University of Indiana buildings mostly are.) Not many people care about things like this.

The bump on Georgia

The first piece of pattern recognition that I remember was noticing that some states had “bumps”. This resulted in a confusing conversation with my mother. See Why Georgia has a bump.

Maybe soon I will write about why some states have panhandles, including the New England state that has a tiny panhandle that almost no one knows about.

Minnesota river

We live in Minneapolis now and occasionally drive over the Mendota Bridge, which crosses the Minnesota River. That river is medium sized, although it is a river, unlike Minnehaha Creek. But the Minnesota River Valley is a huge wide valley completely out of proportion with its river. This peculiarity hides a Secret Story that even many Minnesotans don’t know about.

The Minnesota River starts in western Minnesota and flows south and east until it runs into the Mississippi River. The source of the Red River is a few miles north of the source of the Minnesota. It flows north, becoming the boundary with North Dakota and going by Fargo and through Winnipeg and then flows into Lake Winnipeg. Thousands of years ago, all of the Red River was part of the Minnesota River and flowed south, bringing huge amounts of meltwater from the glaciers. That is what made the big valley. Eventually the glaciers receded far enough that the northern part of the river changed direction and started flowing north, leaving the Minnesota River a respectable medium sized river in a giant valley.

The Mendota Bridge is also one of the few places in the area where you can see the skyscrapers of Minneapolis and of St Paul simultaneously.


Baroque music

I love baroque music because of patterns such as fugues, which I understood, and the harmony it uses, which I still don’t understand. When I was 10 years old I had already detected its different harmony and asked my music teacher about it. She waved her hands and declaimed, “I don’t understand Bach.” (She was given to proclamations. Once she said, “I am never going out of the State of Georgia again because in Virginia they put mayonnaise on their hamburgers!”)

Some baroque music uses a ground bass, which floored me when I first heard it. I went on a rampage looking for records of chaconnes and passacaglias. Then I discovered early rock music (Beatles, Doors) and figured out that they sometimes used a ground bass too. That is one of the major attractions of rock music for me, along with its patterns of harmony.

Shape note music

Some shape note tunes (for example, Villulia), as well as some early rock music, has a funny hollow sound that sounds Asian to me. I delight in secretly knowing why: They use parallel fifths.

The Beatles have one song (I have forgotten which) that had a tune which in one place had three or four beats in a row that were sung on the same pitch — except once, when the (third I think) beat was raised a fourth. I fell in love with that and excitedly pointed it out to people. They looked at me funny. Later on, I found several shape note tunes that have that same pattern.


Creative Commons License

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

Send to Kindle


I have been working my way through, revising the articles and turning them into pure HTML so they will be easier to update. In some cases I am making substantial revisions. In particular, many of the articles need a more modern point of view.


The math community’s understanding of sets and structures has changed because of category theory and will change
because of homotopy type theory.


This post considers some issues and possibilities concerning the chapter on sets.

The references listed at the end of the article include several about homotopy type theory. They provide different viewpoints and require different levels of sophistication.

A specification of the concept of set

The abmath article Specification of sets specifies what a set is in this way:

A set is a single math object distinct from but completely determined by what its elements are.

I have used this specification for sets since the eighties, first in my Discrete Math lecture notes and then in It has proved useful because it is quite simple and the statement implies lots of immediate consequences. Each of the first four consequences in this list below exposes a confusion that some students have.

Consequences of the specification

  1. A set is a math object. It has the same status as the number “$143$” and the sine function and the real line: they are all objects of math. A set is not merely a typographically convenient way to define a certain collection of things.
  2. A set is a single object. Many beginners seem to have in their head that the set $\{3,4\}$ is two things.
  3. A set is distinct from its elements. The set $\{3,4\}$ is not $3$, it is not $4$, it is not a number at all.
  4. The spec implies that $\{3,4\}$ is the same set as $\{4,3\}$. Some students think they understand this but some of their mistakes show that they don’t really understand it.
  5. On the other hand, $\{3,5\}$ is a different set from $\{3,4\}$. I haven’t noticed this bothering students but it bothers me. See the discussion on ursets below.

Those consequences make the spec a useful teaching tool. But if a beginning abstract math student gets very far in their studies, some complications come up.

Defining “set”

In the late nineteenth century, math people started formally defining particular math structures such as groups and various
kinds of spaces. This was normally done by starting with a set and adding structure.

You may think that “starting with a set and adding structure” brushes a lot of complications under the rug. Well, don’t look under the rug, at least not right now.

The way they thought about sets was a informal version of what is now called naive set theory. In particular, they freely defined particular sets using what is essentially setbuilder notation, producing sets in a way which (I claim) satisfies my specification.

Bertrand Russell wakes everyone up

Then along came Russell’s paradox. In the context of this discussion, the paradox implied that the spec for sets is not a definition.The spec provides a set of necessary conditions for being a set. But it is not sufficient. You can say “Let $S$ be the set of all sets that…[satisfy some condition]” until you are blue in the face, but there are conditions (including the empty condition) that don’t define a set.

The Zermelo-Fraenkel axioms

The Zermelo-Fraenkel axioms were designed to provide a definition that didn’t create contradictions. The axioms accomplish this by creating a sort of hierarchy that requires that each set must be defined in terms of sets defined previously. They provide a good way (but not the only one) of providing a way of legitimizing our use of sets in math.

Observe that the “set of all sets” is certainly not “defined” in terms of previously defined sets!

Sets as a foundation

During those days there was a movement to provide a solid foundation for mathematics. After Zermelo-Fraenkel came along, the progress of thinking seemed to be:

  1. Sets are in trouble.
  2. Zermelo-Fraenkel solves our set difficulties.
  3. So let’s require that every math object be a set.

That list is oversimplified. In particular, the development of predicate logic was essential to this approach, but I can’t write about everything at once.

This leads to monsters such as the notorious definition of ordered pair:

The ordered pair $(a,b)$ is the set $\{a,\{b\}\}$.

This leads to the ludicrous statement that $a$ is an element of $(a,b)$ but that $b$ is not.

By saying every math object may be modeled as a set with structure, ZF set theory becomes a model of all of math. This approach gives a useful proof that all of math is as consistent as ZF set theory is.

But many mathematicians jumped to the conclusion that every math object must be a set with structure. This approach does not match the way mathematicians think about math objects. In particular, it makes computerized proof assistance hard to use because you have to translate your thinking into sets and first order logic.

Sets by category theory

“A mathematical object is determined by the role it plays in a category.” — A. Grothendieck

In category theory, you define math structures in terms of how they relate to other math structures. This shifts the emphasis from

What is it?


What are its properties?

For example, an ordered pair is a mathematical object $p$ determined by these properties:

  • It determines mathematical objects $p_1$ and $p_2$.
  • $p$ is completely determined by what $p_1$ is and what $p_2$ is.
  • If $p$ and $q$ are ordered pairs and $p_1=q_1$ and $p_2=q_2$ then $p=q$.

Categorical definition of set

“Categorical” here means “as understood in category theory”. It unfortunately has a very different meaning in model theory (set of axioms with only one model up to isomorphism) and in general usage, as in “My answer is categorically NO” said by someone who is red in the face. The word “categorial” has an entirely different meaning in linguistics. *Sigh*.

William Lawvere has produced an axiomatization of the category of sets.
The most accessible introduction to it that I know of is the article Rethinking set theory, by Tom Leinster. This axiomatization defines sets by their relationship with each other and other math objects in much the same way as the categorical definition of (for example) groups gives a definition of groups that works in any category.

“Set” means two different things

The word set as used informally has two different meanings.

  • According to my specification of sets, $\{3,4\}$ is a set and so is $\{3,5\}$.
  • $\{3,4\}$ and $\{3,5\}$ are not the same set because they don’t have the same elements.
  • But in the category of sets, any two $2$-element sets are isomorphic. (So are any two seven element sets.)
  • From a categorical point of view, two isomorphic objects in a category can be be thought of as the same object, with a caveat that you have better make it clear which isomorphism you are thinking of.

One of the great improvements in mathematics that homotopy type theory supplies is a systematic way of keeping track of the isomorphisms, the isomorphisms between the isomorphisms, and so on ad infinitum (literally). But note: I am just beginning to understand htt, so regard this remark as something to be suspicious of.

  • But $\{3,4\}$ and $\{3,5\}$ may not be thought of as the same object according to the spec I gave, because they don’t have the same elements.
  • This means that the traditional idea of set is not the same as the strict categorical idea of set.

I suggest that we keep the word “set” for the traditional concept and call the strict categorical concept an urset.

A traditional set is a structure on an urset

The traditional set $\{3,5\}$ consists of the unique two-element urset coindexed on the integers.

A (ur)set $S$ coindexed by a math structure $A$ is a monic map from $S$ to the underlying set of $A$. In this example, the map has codomain the integers and takes one element of the two-element urset to $3$ and the other to $5$.

Note added 2014-10-05 in response to Toby Bartels’ comment: I am inclined to use the names “abstract set” for “urset” and “concrete set” for coindexed sets when I revise the articles on sets. But most of the time we can get away with just “set”.

There is clearly no isomorphism of coindexed sets from $\{3,4\}$ to $\{3,5\}$, so those two traditional sets are not equal in the category of coindexed sets.

I made up the phrase “coindexed set” to use in this sense, since it is a kind of opposite of indexed set. If terminology for this already exists, lemme know. Linguists will tell you they use the word “coindexed” in a different sense.


The concept of “element” in categorical thinking is very different from the traditional idea, where an element of a set can be any mathematical object. In categorical thinking, an element of an object $A$ of a category $\mathbf{C}$ is an arrow $1\to A$ where $1$ is the terminal object. Thus $4$ as an integer is the arrow $1\to \mathbb{Z}$ whose unique value is the number $4$.

An object is an element of only one set

In the usage of category theory, the arrow $1\to\mathbb{R}$ whose value is the real number $4$ is a different math object from the arrow $1\to\mathbb{Z}$ whose value is the integer $4$.

A category theorist will probably agree that we can identify the integer $4$ with the real number $4$ via the well known canonical embedding of the ring of integers into the field of real numbers. But in categorical thinking you have to keep all such embeddings in mind; you don’t say the integer $4$ is the same thing as the real number $4$. (Most computer languages keep them distinct, too.)

This difference is actually not hard to get used to and is in fact an improvement over traditional set theory. When you do category theory you use lots of commutative diagrams. The embeddings show up as monic arrows and are essential in keeping the different objects ($\mathbb{Z}$ and $\mathbb{R}$ in the example) separate.

The paper Relating first-order set theory and elementary toposes, by Awodey, Butz, Simpson and Streicher, introduces a concept of “structural system of inclusions” that appears to me to restore the idea of object being an element of more than one set for many purposes.

Homotopy type theory allows an object to have only one type, with much the same effect as in the categorical approach.

Variable elements

The arrow $1\to \mathbb{Z}$ that picks out the integer $4$ is a constant function. It is useful to think of any arrow $A\to B$ of any category as a variable element (or generalized element) of the object $B$. For example, the function $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=x^2$ allows you to
think of $x^2$ as a variable number with real parameter. This is another way of thinking about the “$y$” in the equation $y=x^2$, which is commonly called a dependent variable.

One way to think about $y$ is that some statements about it are true, some are false, and many statements are neither true nor false.

  • $y\geq 0$ is true.
  • $y\lt0$ is false.
  • $y\leq1$ is neither true nor false.

This way of thinking about variable objects clears up a lot of confusion about variables and deserves to be more widely used in teaching.

The book Category theory for computing science provides some examples of the use of variable elements as a way of thinking about categorical ideas.


Creative Commons License< ![endif]>

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

Send to Kindle