Category Archives: proof

language of math, math, proof, understanding math

The many boobytraps of “if…then”

Leave a comment

CONTENTS

The truth table for conditionals

Conditionals and truth sets

Vacuous truth

Universal conditional assertions

Related assertions

Understanding conditionals

Modus ponens

CONDITIONAL ASSERTIONS

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$
T T T
T F F
F T T
F F T

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.

Example

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

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

Remark

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)$.

Examples
  • 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.

Example

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$”.

“Implication”

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

Example

Both these statements are vacuously true!

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

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.

Example
  • 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.

Remark

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.

Example

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.

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

Notes

  • 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

Converse

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.

Examples
  • 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.

Contrapositive

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.

Example

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.

Examples

Time

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.

Causation

“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$
T T T
T F F
F T F
F F T

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!

Rigor

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.

Remark

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.

Remark

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
exposition, language of math, math, proof, understanding math

The role of proofs in mathematical writing

1 Comment

This post outlines the way that proofs are used in mathematical writing. I have been revising the chapter on Proofs in abstractmath.org, 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.

References

Added 2014-12-19

Creative Commons License

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

Send to Kindle
math, proof, understanding math

Those monks

Leave a comment

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.

References

  • 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 abstractmath.org.
  • Conceptual blending in Wikipedia.
Send to Kindle
category theory, math, proof, representations

Proofs using diagrams

Leave a comment

Introduction

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

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

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

The theorem

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

Subject Diagram

So what?

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

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

Commercial

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

Concepts needed for the graph-based proof

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

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

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

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

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

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

Color coding

I will use color coding to separate syntax from semantics.

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

Descriptions

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

The Subject Diagram

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

  • Shapes of diagrams are defined properly in Section 2.3 of
    GBLS and in Section 4.1 of Category Theory for Computing Science.

The description of the Subject Diagram

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


Diagram SDD

Definition of $\mathsf{ar}_2$

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

In the usual categorical notation this would be shown as

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

An enrichment of the description

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

Enriched Diagram SDD

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

Make the triangles commute

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

Diagram TC: The triangles commute

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

The outside square commutes

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

The outside square commutes

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

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

References

Creative Commons License

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

Send to Kindle
abstractmath.org, math, proof, representations, understanding math

A very early satori that occurs with beginning abstract math students

Leave a comment

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.

Cosets

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$

    and

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

Examples:

  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 abstractmath.org.
  • 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. Abstractmath.org 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.

References

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

Dysfunctions in doing math II

Leave a comment

This post continues Dysfunctions in doing math I, with some more revisions to the article in abstractmath on dysfunctions.

Elements

First Myth

MYTH: There are two kinds of mathematical objects: "sets" and "elements".

This is the TRUTH: Being an element is not a property that some math objects have and others don’t. “Element” is a binary relation; it relates an object and a set. So “$3$ is an element” means nothing, but “$3$ is an element of the set of integers” is true and relates two mathematical objects to each other.


Any mathematical object can be an element of a set
In particular, any set can be the
element of another set.

Examples

  • The number $42$ is not a set, but it is an element of the set $\{5,10,41,42,-30\}$.
  • The sine function is not a set, but it is an element of the set of all differentiable functions defined on the real numbers.
  • The set $\{1,2,5\}$ is a set, but it is also an element of the set $\left\{\{1,2,5\},\{3,5\}, \emptyset,\{42\}\right\}$. It is not an element of the set $\{1,2,3,4,5\}$.

If you find these examples confusing, read this.

Second Myth

MYTH: The empty set is an element of every set.

This is the TRUTH:
The empty set is an element of a set $S$ if and only if the definition of $S$ requires it to be an element.

Examples

  • The empty set is not an element of every set. It is not an element of the set $\{2,3\}$ for example; that set has only the elements $2$ and $3$.
  • The empty set is an element of the set $\{2,3,\emptyset\}$.
  • The empty set is a subset of every set.

Other ways to misunderstand sets

The myths just listed are explicit; students tell them to each other. The articles below tell you about other misunderstanding about sets which are usually subconscious.

Enthymeme

An enthymeme is an argument based partly on unexpressed beliefs. Beginners at the art of writing proofs often produce enthymemes.

Example

In the process of showing that the intersection of two equivalence relations $E$ and $E’$ is also an equivalence relation, a student may write “$E\cap E’$ is transitive because $E$ and $E’$ are transitive.”

  • This is an enthymeme; it omits stating, much less proving, that the intersection of transitive relations is transitive.
  • The student may “know” that it is obvious that the intersection of transitive relations is transitive, having never considered the similar question of the union of transitive relations.
  • It is very possible that the student possesses (probably subconsciously) a malrule to the effect that for any property $P$ the union or intersection of relations with property $P$ also has property $P$.
  • The instructor very possibly suspects this. For some students, of course, the suspicion will be unjustified, but for which ones?
  • This sort of thing is a frequent source of tension between student and instructor: “Why did you take points off because I assumed the intersection of transitive relations is transitive? It’s true!”

Malrule

A malrule is an incorrect rule for syntactic transformation of a mathematical expression.

Example

The malrule $\sqrt{x+y}=\sqrt{x}+\sqrt{y}$ invented by algebra students may come from the pattern given by the distributive law $a(x+y)=ax+ay$. The malrule invented by many first year calculus students that transforms $\frac{d(uv)}{dx}$ to $\frac{du}{dx}\frac{dv}{dx}$ may have been generated by extrapolating from the correct rule
\[\frac{d(u+v)}{dx}=\frac{du}{dx}+\frac{dv}{dx}\] by changing addition to multiplication. Both are examples of “every operation is linear”, which students want desperately to be true, although they are not aware of it.

Existential bigamy

Beginning abstract math students sometimes make a particular type of mistake that occurs in connection with a property $P$ of an mathematical object $x$ that is defined by requiring the existence of an item $y$ with a certain relationship to $x$. When students have a proof that assumes that there are two items $x$ and $x’$ with property $P$, they sometimes assume that the same $y$ serves for both of them. This mistake is called existential bigamy: The fact that Muriel and Bertha are both married (there is a person to whom Muriel is married and there is a person to whom Bertha is married) doesn’t mean they are married to the same person.

Example

Let $m$ and $n$ be integers. By definition, $m$ divides $n$ if there is an integer $q$ such that $n=qm$. Suppose you are asked to prove that if $m$ divides both $n$ and $p$, then $m$ divides $n+p$. If you begin the proof by saying, “Let $n = qm$ and $p = qm$…” then you are committing existential bigamy.

You need to begin the proof this way: “Let $n = qm$ and $p = q’m…”$

Send to Kindle
category theory, exposition, language of math, math, proof, understanding math

A proof by diagram chasing

1 Comment


In Rigorous proofs, I went through the details of a medium-easy epsilon-delta proof in great detail as a way of showing what is hidden by the wording of the proof. In this post, I will do the same for an easy diagram-chasing proof in category theory. This theorem is stated and proved in Category Theory for Computing Science, page 365, but the proof I give here maximizes the diagram-chasing as a way of illustrating the points I want to make.

Theorem (J. Lambek) Let $F$ be a functor from a category to itself and let $\alpha:Fa\to a$ be an algebra for $F$ which is initial. Then $\alpha$ is an isomorphism.

Proof

  1. $F\alpha:FFa\to Fa$ is also an $F$-algebra.
  2. Initiality means that there is a unique algebra morphism $\eta:a\to Fa$ from $\alpha:Fa\to a$ to $F\alpha:FFa\to Fa$ for which this diagram commutes:




  3. To that diagram we can adjoin another (obviously) commutative square:




  4. Then the outside rectangle in the diagram above also commutes.
  5. This means that $\alpha\circ\eta:a\to a$ is an $F$-algebra morphism from $\alpha:Fa\to a$ to itself.
  6. Another such $F$-algebra morphism is $\text{id}_{A}$.
  7. Initiality of $\alpha$ means that the diagram below commutes:




  8. Because the upper bow and the left square both commute we are justified in inserting a diagonal arrow as below.




  9. Now we can read off the diagram that $F\alpha\circ F(\eta)=\text{id}_{Fa}$ and $\eta\circ\alpha=\text{id}_a$. By definition, then, $\eta$ is a two-sided inverse to $\alpha$, so $\alpha$ is an isomorphism.

Analysis of the proof

This is an analysis of the proof showing what is not mentioned in the proof, similar to the analysis in Rigorous proofs.

  • An $F$-algebra is any arrow of the form $\alpha:Fa\to a$. This definition directly verifies statement (1). You do need to know the definition of “functor” and that the notation $Fa$ means $F(a)$ and $FFa$ means $F(F(a))$.
  • When I am chasing diagrams, I visualize the commutativity of the diagram in (2) by thinking of the red path and the blue path as having the same composites in this graph:





    In other words, $F\alpha\circ F\eta=\eta\circ\alpha$. Notice that the diagram carries all the domain and codomain information for the arrows, whereas the formula “$F\alpha\circ F\eta=\eta\circ\alpha$” requires you to hold the domains and codomains in your head.

  • (Definition of morphism of $F$-algebra) The reader needs to know that a morphism of $F$ algebras is any arrow $\delta:c\to d$ for which




    commutes.
  • (Definition of initial $F$-algebra) $\alpha$ is an initial $F$-algebra means that for any algebra $\beta:Fb\to b$, there is a unique arrow $\delta$ for which the diagram above commutes.
  • (2) is justified by the last two definitions.
  • Pulling a “rabbit out of a hat” in a proof means introducing something that is obviously correct with no motivation, and then checking that it results in a proof. Step (9) in the proof given in Rigorous proofs has an example of adding zero cleverly. It is completely OK to pull a rabbit out of a hat in a proof, as long as the result is correct, but it makes students furious.
  • In statement (3) of the proof we are considering here, the rabbit is the trivially commutative diagram that is adjoined on the right of the diagram from (2).
  • Statement (4) uses a fact known to all diagram chasers: Two joined commutative squares make the outside rectangle commute. You can visualize this by seeing that the three red paths shown below all have the same composite. When I am chasing a complicated diagram I trace the various paths with my finger, or in my head.



    You could also show it by pointing out that $\alpha\circ F\alpha\circ F\eta=\alpha\circ\eta\circ\alpha$, but to check that I think most of us would go back and look at the diagram in (3) to see why it is true. Why not work directly with the diagram?

  • The definition of initiality requires that there be only one $F$-algebra morphism from $\alpha:Fa\to a$ to itself. This means that the upper and lower bows in (7) commute.
  • The diagonal identity arrow in (8) is justified by the fact that the upper bow is exactly the same diagram as the upper triangular diagram in (8). It follows that the upper triangle in (8) commutes. I visualize this as moving the bow down and to the left with the upper left node $Fa$ as a hinge, so that the two triangles coincide. (It needs to be flipped, too.) I should make an interactive diagram that shows this.
  • The lower triangle in (8) also commutes because the square in (2) is given to be commutative.
  • (Definition of isomorphism in a category) An arrow $f:a\to b$ in a category is an isomorphism if there is an arrow $g:b\to a$ for which these diagrams commute:


    xx


    This justifies statement (9).

Remark: I have been profligate in using as many diagrams as I want because this can be seen on a screen instead of on paper. That and the fact that much more data about domains and codomains are visible because I am using diagrams instead of equations involving composition means that the proof requires the readers to carry much less invisible data in their heads.

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

Rigorous proofs

2 Comments

Rich and rigorous

When we try to understand a math statement, we visualize what the statement says using metaphors, images and kinetic feelings to feel how it is true, or to suggest that the statement is not true.

If we are convinced that it is true, we may then want to prove it. Doing that involves pitching out all the lovely pictures and metaphors and gestures and treating the mathematical objects involved in the proof as static and inert. “Static” means the object does not change. “Inert” means that it does not affect anything else. I am saying how we think about math objects for the purpose of rigorous proof. I am not saying anything about “what math objects are”.

In this post I give a detailed example of a proof of the rigorous sort.

Example

Informal statement

First, I’ll describe this example in typical spoken mathematical English. Suppose you suspect that the following statement is true:

Claim: Let $f(x)$ be a differentiable function with $f'(a)=0$.
Going from left to right, suppose the graph of $f(x)$ goes UP before $x$ reaches $a$ and then DOWN for $x$ to the right of $a$
Then $a$ has to be a local maximum of the function.

This claim is written in informal math English. Mathematicians talk like that a lot. In this example they will probably wave their hands around in swoops.

The language used is an attempt to get a feeling for the graph going up to $(a,f(a))$ and then falling away from it. It uses two different metaphors for $x\lt a$ and $x\gt a$. I suspect that most of us would want to clean that up a bit even in informal writing.

A more formal statement

Theorem: Let $f$ be a real valued differentiable function defined on an open interval $R$. Let $a$ be a number in $R$ for which $f'(a)=0$. Suppose that for all $x\in R$, $f$ increases for $x\lt a$ and decreases for $x\gt a$. Then $f(a)$ is a maximum of $f$ in $R$.

Proof

  1. By definition of derivative, \[\lim_{x\to a}\frac{f(x)-f(a)}{x-a}=0.\]
  2. By definition of limit, then for any positive $\epsilon$ there is a positive $\delta$ for which if $0\lt|x-a|\lt\delta$ then \[\left|\frac{f(x)-f(a)}{x-a}\right|\lt\epsilon.\]
  3. By requiring that $\delta\lt 1$, it follows from (2) that for any positive $\epsilon$, there is a positive $\delta$ for which if $0\lt|x-a|\lt\delta$, then $|f(x)-f(a)|\lt\epsilon$.
  4. “$f$ increases for $x\lt a$” means that if $x$ and $y$ are numbers in $R$ and $x\lt y\lt a$, then $f(x)\lt f(y)$.
  5. “$f$ decreases for $x\gt a$” means that if $x$ and $y$ are numbers in $R$ and $a\lt x\lt y$, then $f(x)\gt f(y)$.
  6. “$f(a)$ is a maximum of $f$ in $R$” means that for $x\in R$, if $x\neq a$, then $f(x)\lt f(a)$.
  7. Suppose that $x\in R$ and $x\lt a$. (The case that $x\gt a$ has a symmetric proof.)
  8. Given $\epsilon\gt0$ with $\delta$ as given by (3), choose $y\in R$ such that $x\lt y\lt a$ and $|f(y)-f(a)|\lt\epsilon$.
  9. By (4), $f(x)\lt f(y)$. So by (8), \[\begin{align*}
    f(x)-f(a)&=
    f(x)-f(y)+f(y)-f(a)\\ &\lt f(y)-f(a)\\ &\leq|f(y)-f(a)|\lt\epsilon\end{align*}\]
    so that $f(x)\lt f(a)+\epsilon$. By inserting “$-f(y)+f(y)$” into the second formula, I am “adding zero cleverly”, an example of pulling a rabbit out of a hat. Students hate that. But you have to live with it; as long as the statements following are correct, it makes a valid proof. Rabbit-out-of-a-hat doesn’t make a proof wrong, but it does make you wonder how the author thought of it. Live with it.
  10. Since (9) is true for all positive $\epsilon$, it follows that $f(x)\leq f(a)$.
  11. By the same argument as that leading up to (10), $f(\frac{x-a}{2})\leq f(a)$.
  12. Since $f(x)\lt f(\frac{x-a}{2})$, it follows that $f(x)\lt f(a)$ as required.

About the proof

This proof is intended to be a typical “rigorous” proof. I suspect it tends to be more rigorous than most mathematicians would find necessary,

Extensionality

The point about “rigor”, about insisting that the objects be static and inert, is that this causes symbols and expression to retain the same meaning throughout the text. This is one aspect of extensionality.

Of course, some of the symbols denote variables, or variable objects. This does not mean they are “varying”. I am taking this point of view: A variable refers to a math object but you don’t know what it is. Constraints such as $x\lt a$ rule out some possible values but don’t generally tell you exactly what $x$ is. There is more about this in Variable Objects

The idea in (6), for example, is that $y$ denotes a real number. You don’t know which number it is, but you do know some facts about it: $x\lt y\lt a$, $|f(y)\lt f(a)|\lt\epsilon$ and so on. Similarly you don’t know what function $f$ is, but you do know some facts about it: It is differentiable, for example, and $f'(a)=0$.

My statement that the variables aren’t “varying” means specifically that each unbound occurrence of the variable refers to the same value as any other occurrence, unless some intervening remark changes its meaning. For example, the references to $x$ in (7) through (10) refer to the same value it has in (6), and (10), in particular, constitutes a statement that the claim about $x$ is correct.

Checkability

The elimination of metaphors that lets the proof achieve rigor is part of a plan in the back of the mind of at least some mathematicians who write proofs. The idea is that the proof be totally checkable:

  • Every statement in the proof has a semantics, a meaning, that is invariant (given the remark about variables above).
  • Each statement is justified by some of the previous statements. This justification is given by two systems that the reader is supposed to understand.
  • One system is the rules of symbol manipulation that are applied to the symbolic expressions, ordinary algebra, and higher-level manipulations used in particular branches of math.
  • The other system consists of the rules of logical reasoning that justify the claims that each statement follows logically from preceding ones.
  • These two systems are really branches of one system, the entire system of math computation and reasoning. It can be obscure which system is being used in a particular step.

Suppression of reasons

The logical and symbolic-manipulation reasons justifying the deductions may not be made completely explicit. In fact, for many steps they may not be mentioned at all, and for others, one or two phrases may be used to give a hint. This is standard practice in writing “rigorous” proofs. That is a descriptive statement, made without criticism. Giving all the reasons is essentially impossible without a computer.

I am aware that some work has been done to write proof checkers that can read a theorem like the one we are considering, stated in natural language, and correctly implement the semantics I have described in this list. I don’t know of any references to such work and would appreciate information about it.

Suppression of reasons makes it difficult to mechanically check a proof written in this standard “rigorous” writing style. Basically, you must be at at least the graduate student level to be able to make sense of what is said, and even experienced math research people find it difficult to read a paper in a very different field. Writing the proof so that it can be checked by a proof checker requires understanding of the same sort, and it typically makes the proof much longer.

One hopeful new approach is to write the proofs using homotopy type theory. The pioneers in that field report that the proofs don’t expand nearly as much as is required by first order logic.

Examples of suppression

Here are many examples of suppression in the $\epsilon$-$\delta$ proof above. This is intended to raise your consciousness concerning how nearly opaque writing in math research is to anyone but the cognoscenti.

  • The first sentence of the theorem names $R$ and $f$ and puts constraints on them that can be used to justify statements in the proof. The naming of $R$ and $f$ requires that every occurrence of $R$ in the proof refers to the same mathematical object, and similarly for $f$.

Remark: The savvy reader “knows” the facts stated in (a), possibly entirely subconsciously. For many of us there is no conscious thought of constraints and permanence of naming. My goal is to convince those who teach beginning abstract math course to become conscious of these phenomena. This remark applies to all the following items as well.

  • The second sentence gives $a$ a specific meaning that will be maintained throughout the proof. It also puts constraints on $a$ and an additional constraint on $f$.
  • The third sentence gives a constraint on $R$, $f$ and $a$. It does not give a constraint on $x$, which is a bound variable. Nor does it name $x$ as a specific number with the same meaning in the rest of the proof. (That happens later).
  • The fact that the first three sentences impose constraints on various objects is signaled by the fact that the sentences are introduced by “let” and “suppose”. The savvy reader knows this.
  • The fourth sentence announces that “$f(a)$ is a maximum of $f$ in $R$” is a consequence of the constraints imposed by the preceding three sentences. (In other words, it follows from the context.) This is signaled by the word “then”.
  • The fact that the paragraph is labeled “Theorem” informs us that the fourth sentence is therefore a statement of what is to be proved, and that every constraint imposed by the first three sentences of the Theorem may be used in the proof.
  • In the proof, statements (1), (4), (5) and (6) rewrite the statements in the theorem according to the definitions of the words involved, namely “derivative: “increases”, “decreases” and “maximum”. Rewriting statements according to the definitions of the words involved is a fundamental method for starting a proof.
  • (2) follows from (1) by rewriting using the definition of “limit”. Note that pattern-matching against the definition of limit requires understanding that there is a zero inside the absolute value signs that is not written down. Could a computer proof-checker handle that?
  • (3) follows from (2). The reader or proof-checker must:
    • Know that it is acceptable to put an upper bound on $\delta$ in the definition of limit.
    • Notice that you can move $|x-a|$ out of the denominator because $x\neq a$ by (2).
  • The conclusion in (6) that we much show that $f(x)\lt f(a)$ is now the statement we must prove.

Remark: In the following items, I mention the context of the proof. I am using the word informally here. It is used in some forms of formal logic with a related but more precise meaning. The context consists of the variables you must hold in your head as you read each part of the proof, along with their current constraints. “Current” means the “now” that you are in when considering the step of the proof you are reading right now. I give some references at the end of the post.

  • At the point between (6) and (7), our context consists of $a$, $R$ and $f$ all subject to some constraints. $x$ is not yet in the context of our proof because its previous occurrences in the theorems and in (1) through (6) have been bound, mostly by an unexpressed universal quantifier. Now we are to think of $x$ as a specific number bound by some constraints.
  • The statement in (7) that the case $x\gt a$ as a symmetric proof is a much higher-level claim than the other steps in this proof, even though in fact it is not very high level compared to statements such as “An application of Serre’s spectral sequence shows$\ldots$”. Most mathematicians with even a little experience will read this statement and accept it in the confidence that they will know how to swap “$\lt$” and “$\gt$” in the proof in the correct way (which is a bit picky) to provide a dual proof. Some students might write out the dual proof to make sure they understand it (more likely because writing it out was a class assignment). I await the day that an automated proof checker can handle a statement like this.
  • (8) introduces three new math objects $\epsilon$, $\delta$ and $y$ subject to several constraints. The symbols occur earlier but they are all bound. $\epsilon$ will be fixed in our context from now until (10). The others don’t appear later.
  • (9) consists of several steps of algebraic computation. A cognoscent (I am tired of writing “savvy”) reader first looks at the computation as a whole and notices that it deduces that $|f(x)-f(a)|\lt\epsilon$, which is almost what is to be proved. This helps the reader understand the reason for the calculation. No mention whatever is made in this step of all this stuff that should go through your mind (or the proof-checker’s “mind”).
  • The computations in (9) are are basic algebra not explained step by step, except that the remark that $f(x)\lt f(y)$ explains how you get $f(x)-f(y)+f(y)-f(a) \lt f(y)-f(a)$.
  • (10) banishes $\epsilon$ from the context by universally quantifying over it. That $f(x)\leq f(a)$ follows by the garbage-dump-in-Star-Wars trick that often baffles first year analysis students: Since for all positive $\epsilon$, $f(x)\lt f(a)+\epsilon$, then $f(x)\leq f(a)$. (See also Terry Tao’s article in Tricks Wiki.)
  • (11) “By the same argument as leading up to (10)” puts some demands on the reader, who has to discover that you have to go back to (7) and do the following steps with a new context using a value of $x$ that is halfway closer to $a$ than the “old” $x$ was. This means in particular that the choice of $\frac{x-2}{2}$ is unnecessarily specific. But it works.
  • (12) suppresses the reference to (11).

    • References

    I have written extensively on these topics. Here are some links.

    Rich-rigorous bifurcation in math thinking

The symbolic language

Math English and the language of proofs

Proofs and context

Send to Kindle
math, proof, representations, understanding math

Guest post by F. Kafi

Leave a comment

Before I posted Extensional and Intensional, I had emailed a draft to F. Kafi.  The following was his response.  –cw

 

In your example, “Suppose you set out to prove that if $f(x)$ is a differentiable function and $f(a)=0$ and the graph going from left to right goes UP to $f(a)$ and then DOWN after that then $a$ has to be a maximum of the function”, could we have the graph of the function $f(x)$ without being aware of the internal structure of the function; i.e., the mathematical formulation of $f(x)$ such as $f(x):=-(x-a)^2$ or simply its intensional meaning? Certainly not.

Furthermore, what paves the way for the comparison with our real world experiences leading to the metaphoric thinking is nothing but the graph of the function. Therefore, it is the intensional meaning of the function which makes the metaphoric mode of thinking possible.

The intensional meaning is specially required if we are using a grounding metaphor. A grounding metaphor uses concepts from our physical and real world life. As a result we require a medium to connect such real life concepts like “going up” and “going down” to mathematical concepts like the function $f(x)$. The intensional meaning of function $f(x)$ through providing numbers opens the door of the mind to the outer world. This is possible because numbers themselves are the result of a kind of abstraction process which the famous educational psychologist Piaget calls empirical abstraction. In fact, through empirical abstraction we transform the real world experience to numbers.

 

 

Let’s consider an example. We see some racing cars in the picture above, a real world experience if you are the spectator of a car match. The empirical abstraction works something like this:

 

 

Now we may choose a symbol like "$5$" to denote our understanding of "|||||".

It is now clear that the metaphoric mode of thinking is the reverse process of “empirical abstraction”. For example, in comparing “|||||||||||” with “||||” we may say “A car race with more competing cars is much more exciting than a much less crowded one.” Therefore, “|||||||||||”>“||”, where “>” is the abstraction of “much more exciting than”.

In the rigorous mode of thinking, the idea is almost similar. However, there is an important difference. Here again we have a metaphor. But this time, the two concepts are mathematical. There is no outer world concept. For example, we want to prove a differentiable function is also a continuous one. Both concepts of “differentiability” and “continuity” have rigorous mathematical definitions. Actually, we want to show that differentiability is similar to continuity, a linking metaphor. As a result, we again require a medium to connect the two mathematical concepts. This time there is no need to open the door of the mind to the outer world because the two concepts are in the mind. Hence, the intensional meaning of function $f(x)$ through providing numbers is not helpful. However, we need the intensional meanings of differentiability and continuity of $f(x)$; i.e., the logical definitions of differentiability and continuity.

In the case of comparing the graph of $f(x$) with a real hill we associated dots on the graph with the path on the hill. Right? Here we need to do the the same. We need to associate the $f(x)$’s in the definition of differentailblity to the $f(x)$’s used in the definition of continuity. The $f(x)$’s play the role of dots on the graph. As the internal structure of dots on the graph are unimportant to the association process in the grounding metaphor, the internal structure of $f(x)$’s in the logical definition are unimportant to the association process in the linking metaphor. Therefore, we only need the extensional meaning of the function $f(x)$; i.e., syntactically valid roles it can play in expressions.

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

Extensional and Intensional

2 Comments

This post uses the word intensional, which is not the word "intentional" and doesn't mean the same thing.

 

The connection between rich view/rigorous view and intensional/extensional

 

In the abmath article Images and Metaphors I wrote about the rigorous view of math, in contrast to the rich view which allows metaphors, images and intuition. F. Kafi has proposed the following thesis:

The rigorous mode of thinking deals with the extensional meaning of mathematical objects while the metaphoric mode of thinking deals with the intensional meaning of mathematical objects.

This statement is certainly suggestive as an analogy. I have several confused and disjointed thoughts about it.

What does "intensional" mean?

Philosophy

Philosophers say that "the third largest planet in the solar system" has intensional meaning and "Neptune" has extensional meaning. Among other things we might discover a planet ridiculously far out that is bigger than Neptune. But the word "Neptune" denotes a specific object.

The intensional meaning of "the third largest planet in the solar system" has a hidden time dimension that, if made overt, makes the statement more nearly explicit. (Don't read this paragraph as a mathematical statement; it is merely thrashing about to inch towards understanding.)

Computing science

Computer languages are distinguishes as intensional or extensional, but their meaning there is technical, although clearly related to the philosophers' meaning.

I don't understand it very well, but in Type Theory and in Logic, an intensional language seems to make a distinction between declaring two math objects to be equal and proving that they are equal. In an extensional language there is no such distinction, with the effect that in a typed language typing would be undecidable.

Here is another point: If you define the natural numbers by the Peano axioms, you can define addition and then prove that addition is commutative. But for example a vector space is usually defined by axioms and one of the axioms is a declaration that addition of vectors is commutative. That is an imposed truth, not a deduced one. So is the difference between intensional and extensional languages really a big deal or just a minor observation?

What is "dry-bones rigor"?

Another problem is that I have never spelled out in more than a little detail what I mean by rigor, dry-bones rigor as I have called it. This is about the process mathematicians go through to prove a theorem, and I don't believe that process can be given a completely mathematical description. But I could go into much more detail than I have in the past.

Suppose you set out to prove that if $f(x)$ is a differentiable function and $f(a)=0$ and the graph going from left to right goes UP before $x$ reaches $a$ and then DOWN for $x$ to the right of $a$, then $a$ has to be a maximum of the function. That is a metaphorical description based on the solid physical experience of walking up to the top of a hill. But when you get into the proof you start using lots of epsilons and deltas. This abandons ideas of moving up and down and left to right and so on. As one of the members of Bourbaki said, rigorous math is when everything goes dead. That sounds like extensionality, but isn't their work really based on the idea that everything has to be reduced to sets and logic? (This paragraph was modified on 2013.11.07)

Many perfectly rigorous proofs are based on reasoning in category theory. You can define an Abelian group as a categorical diagram with the property that any product preserving functor to any category will result in a group. This takes you away from sets altogether, and is a good illustration of the axiomatic method. It is done by using nodes, arrows and diagrams. The group is an object and the binary operation is an arrow from the square of the object. Commutativity is required by stating that a certain diagram must commute. But when you prove that two elements in an Abelian group (an Abelian topological group, an Abelian group in the category of differentiable manifolds, or whatever) can be added in either order, then you find yourself staring at dead arrows and diagrams rather than dead collections of things and so you are still in rigor mortis mode.

I will write a separate post describing these examples in much more detail than you might want to think about.

Metaphors and intensionality

One other thing I won't go into now: How are thinking in metaphors and intensional descriptions related? It seems to me the two ideas are related somehow, but I don't know how to formulate it.

Send to Kindle