Tag Archives: rigor

The many boobytraps of “if…then”

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

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.

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

Rigorous proofs

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

Extensional and Intensional

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

Freezing a family of functions

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook algebra1.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

Some background

  • Generally, I have advocated using all sorts of images and metaphors to enable people to think about particular mathematical objects more easily.
  • In previous posts I have illustrated many ways (some old, some new, many recently using Mathematica CDF files) that you can provide such images and metaphors, to help university math majors get over the abstraction cliff.
  • When you have to prove something you find yourself throwing out the images and metaphors (usually a bit at a time rather than all at once) to get down to the rigorous view of math [1], [2], [3], to the point where you think of all the mathematical objects you are dealing with as unchanging and inert (not reacting to anything else).  In other words, dead.
  • The simple example of a family of functions in this post is intended to give people a way of thinking about getting into the rigorous view of the family.  So this post uses image-and-metaphor technology to illustrate a way of thinking about one of the basic proof techniques in math (representing the object in rigor mortis so you can dissect it).  I suppose this is meta-math-ed.  But I don’t want to think about that too much…
  • This example also illustrates the difference between parameters and variables. The bottom line is that the difference is entirely in how we think about them. I will write more about that later.

 A family of functions

This graph shows individual members of the family of functions \( y=a\sin\,x\) for various values of a. Let’s look at some of the ways you can think about this.

  • Each choice of  “shows the function for that value of the parameter a“.  But really, it shows the graph of the function, in fact only the part between x=-4 and x= 4.
  • You can also think of it as showing the function changing shape as a changes over time (as you slide the controller back and forth).

Well, you can graph something changing over time by introducing another axis for time.  When you graph vertical motion of a particle over time you use a two-dimensional picture, one axis representing time and the other the height of the particle. Our representation of the function y=a\sin\,x is a two-dimensional object (using its graph) so we represent the function in 3-space, as in this picture, where the slider not only shows the current (graph of the) function for parameter value a but also locates it over a on the z axis.

The picture below shows the surface given by y=a\sin\,x as a function of both variables a and x. Note that this graph is static: it does not change over time (no slide bar!). This is the family of functions represented as a rigorous (dead!) mathematical object.

If you click the “Show Curves” button, you will see a selection of the curves in middle diagram above drawn as functions of x for certain values of a. Each blue curve is thus a sine wave of amplitude a. Pushing that button illustrates the process going on in your mind when you concentrate on one aspect of the surface, namely its cross-sections in the x direction.

Reference [4] gives the code for the diagrams in this post, as well as a couple of others that may add more insight to the idea. Reference [5] gives similar constructions for a different family of functions.

References

  1. Rigorous view in abstractmath.org 
  2. Representations II: Dry Bones (post)
  3. Representations III: Rigor and Rigor Mortis (post)
  4. FamiliesFrozen.nb.
  5. AnotherFamiliesFrozen.nb (Mathematica file showing another family of functions)
Send to Kindle

Proofs without dry bones

I have discussed images, metaphors and proofs in math in two ways:

(A) A mathematical proof

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

This example comes from Fauconnier, Mappings in Thought and Language, Cambridge Univ. Press, 1997. I discuss it in the Handbook, pages 46 and 153. See the Wikipedia article on conceptual blending.

(B) Rigor and rigor mortis

The following is quoted from a previous post here. See also the discussion in abstractmath.

When we are trying to understand or explain math, we may use various kinds of images and metaphors about the subject matter to construct a colorful and rich representation of the mathematical objects and processes involved. I described some of these briefly here. They can involve thinking of abstract things moving and changing and affecting each other.

When we set out to prove some math statement, we go into what I have called “rigorous mode”. We feel that we have to forget some of the color and excitement of the rich view. We must think of math objects as inert and static. They don’t move or change over time and they don’t interact with other objects or the real world. In other words, pretend that all math objects are dead.

We don’t always go all the way into this rigorous mode, but if we use an image or metaphor in a proof and someone challenges us about it, we may rewrite that part to get rid of the colorful representation and replace it by a calculation or line of reasoning that refers to the math objects as if they were inert and static – dead.

I didn’t contradict myself.
I want to clear up some tension between these two ideas.

The argument in (A) is a genuine mathematical proof, just as it is written. It contains hidden assumptions (enthymemes), but all math proofs contain hidden assumptions. My remarks in (B) do not mean that a proof is not a proof until everything goes dead, but that when challenged you have to abandon some of the colorful and kinetic reasoning to make sure you have it right. (This is a standard mathematical technique (note 1).)

One of the hidden assumptions in (A) is that two monks walking the opposite way on the path over the same interval of time will meet each other. This is based on our physical experience. If someone questions this we have several ways to get more rigorous. One many mathematicians might think of is to model the path as a curve in space and consider two different parametrizations by the unit interval that go in opposite directions. This model can then appeal to the intermediate value theorem to assert that there is a point where the two parametrizations give the same value.

I suppose that argument goes all the way to the dead. In the original argument the monk is moving. But the parametrized curve just sits there. The parametrizations are sets of ordered pairs in R x (R x R x R). Nothing is moving. All is dry bones. Ezekiel has not done his thing yet.

This technique works, I think, because it allows classical logic to be correct. It is not correct in everyday life when things are moving and changing and time is passing.

Avoid models; axiomatize directly
But it certainly is not necessary to rigorize this argument by using parametrizations involving the real numbers. You could instead look at the situation of the monk and make some axioms the events being described. For example, you could presumably make axioms on locations on the path that treat the locations as intervals rather than as points.

The idea is to make axioms that state properties that intervals have but doesn’t say they are intervals. For example that there is a relation “higher than” between locations that must be reflexive and transitive but not antisymmetric. I have not done this, but I would propose that you could do this without recreating the classical real numbers by the axioms. (You would presumably be creating the intuitionistic real numbers.)

Of course, we commonly fall into using the real numbers because methods of modeling using real numbers have been worked out in great detail. Why start from scratch?

About the heading on this section: There is a sense in which “axiomatizing directly” is a way of creating a model. Nevertheless there is a distinction between these two approaches, but I am to confused to say anything about this right now.

First order logic.
It is commonly held that if you rigorize a proof enough you could get it all the way down to a proof in first order logic. You could do this in the case of the proof in (A) but there is a genuine problem in doing this that people don’t pay enough attention to.

The point is you replace the path and the monks by mathematical models (a curve in space) and their actions by parametrizations. The resulting argument calls on well known theorems in real analysis and I have no doubt can be turned into a strict first order logic argument. But the resulting argument is no longer about the monk on the path.

The argument in (A) involves our understanding of a possibly real physical situation along with a metaphorical transference in time of the two walks (a transference that takes place in our brain using techniques (conceptual blending) the brain uses every minute of every day). Changing over to using a mathematical model might get something wrong. Even if the argument using parametrized curves doesn’t have any important flaws (and I don’t believe it does) it is still transferring the argument from one situation to another.

Conclusion:
Mathematical arguments are still mathematical arguments whether they refer to mathematical objects or not. A mathematical argument can be challenged and tested by uncovering hidden assumptions and making them explicit as well as by transferring the argument to a classical mathematical situation.

Note 1. Did you ever hear anyone talking about rigor requiring making images and metaphors dead? This is indeed a standard mathematical technique but it is almost always suppressed, or more likely unnoticed. But I am not claiming to be the first one to reveal it to the world. Some of the members of Bourbaki talked this way. (I have lost the reference to this.)

They certainly killed more metaphors than most mathematicians.

Note 2. This discussion about rigor and dead things is itself a metaphor, so it involves a metametaphor. Metaphors always have something misleading about them. Metametaphorical statements have the potential of being far worse. For example, the notion that mathematics contains some kind of absolute truth is the result of bad metametaphorical thinking.

Send to Kindle