logic | College Math Teaching

May 12, 2012

A simple demonstration of Cantor’s Diagonal Arugment

Filed under: advanced mathematics, infinity, logic, pedagogy, sequences — collegemathteaching @ 7:27 pm

February 16, 2012

The “equals” sign: identities, equations to be solved and all that…

Filed under: basic algebra, calculus, differential equations, logic, mathematical ability, mathematics education, pedagogy, student learning, vector spaces — collegemathteaching @ 7:09 pm

Here is the sort of thing that got me thinking about this topic: a colleague had a student complain about how one of her quiz problems was scored. The problem stated: “show that $\sqrt{2} + \sqrt{3} \neq \sqrt{5}$ “. She was offended that her saying “ $\sqrt{x} + \sqrt{y} \neq \sqrt{x+y}$ ” wasn’t enough to receive credit and would NOT take his word for it. In fact, she took this to the student ombudsman!!!

But that raised the question: “what do we mean when we tell our students “ $\sqrt{x} + \sqrt{y} \neq \sqrt{x+y}$ “?

Of course, there are some central issues here. The first issues is that our “sure of herself” student thought that “ $\sqrt{x} + \sqrt{y} \neq \sqrt{x+y}$ ” meant that this relation is NEVER true for any choice of $x, y$ , which of course, is false (e. g. let $y = 0$ and $x \ge 0$ .) In fact, $\sqrt{x} + \sqrt{y} \neq \sqrt{x+y}$ is the logical negation of the statement $\sqrt{x} + \sqrt{y} = \sqrt{x+y}$ ; the latter means that “this statement is true for ALL $x, y$ and its negation means “there is at least one choice of $x, y$ for which the statement is not true. “Equal” and “not equal” are not symmetric states when it comes identities, which can be thought of as elements in the vector space of functions.

So, $\sqrt{x} + \sqrt{y} \neq \sqrt{x+y}$ means that $\sqrt{x} + \sqrt{y}$ and $\sqrt{x+y}$ are not equal in function space, though they might evaluate to the same number for certain choices in the domain.

So, what is the big deal?

Well, what about equations such as $x^2 + 3x + 2 = 0$ or $y^{\prime \prime} + y = 0$ ?
These are NOT equalities in the space of functions; the first means “what values in the domain does $f^{-1}(0)$ take given $f(x)=x^2 + 3x + 2$ and the second asks one to find the inverse image of 0 for the operator $D^2+1$ where the domain is the set of all, say, twice differentiable functions.

But, but…would the average undergraduate student understand ANY of this? My experience tells me “no”; hence I intentionally allow for this vagueness and only address it as I need to.

April 8, 2011

A possible way to explain the contrapositive

Filed under: class room experiment, logic, mathematical ability, mathematics education, media — collegemathteaching @ 2:16 am

Mathematics Education

This post at Schneier’s security blog is very interesting. The gist of the post is this: do you remember the simple logical rule: “P implies Q” is equivalent to “not Q implies not P”. Example: if you have the statement “green apples are sour” means that if you bite an apple and it isn’t sour, then it can’t be green. In my opinion, there is nothing hard about this. We use this principle all of the time in mathematics! As an example, consider how we prove that there is no largest prime: Suppose that there was a largest prime $q_n$ with the previous (finite) primes indexed. Now form the number $p = q_1q_2q_3....q_n + 1$ Now $p$ cannot be prime because it is bigger than $q_n$ So it is composite and therefore has prime factors. But this is impossible because $q_k$ can never divide $p$ because it divides $p - 1$ . QED.

The whole structure of the proof by contradiction is the principle that “p implies q” is equivalent “not q implies not p”. Here the q is “there is no biggest prime” and the “suppose there IS a biggest prime” is the “not q” which ended up implying “not p” where p is the true statement that $p$ and $p -1$ are relatively prime.
No mathematician would have a problem using that bit of logic.

But evidently mathematicians are in the minority.

Consider this experiment:

Consider the Wason selection task. Subjects are presented with four cards next to each other on a table. Each card represents a person, with each side listing some statement about that person. The subject is then given a general rule and asked which cards he would have to turn over to ensure that the four people satisfied that rule. For example, the general rule might be, “If a person travels to Boston, then he or she takes a plane.” The four cards might correspond to travelers and have a destination on one side and a mode of transport on the other. On the side facing the subject, they read: “went to Boston,” “went to New York,” “took a plane,” and “took a car.”

So, which card needs to be turned over? Of course, the card has to be “went to Boston” because there is nothing in the rule about going to New York, there is nothing that says that Boston is the only place you can fly to, and turning over the “car card” might reveal “New York” as a destination. Evidently, this problem is hard for most people.
But here is where this gets interesting: if the exact same logical problem is phrased as a “fairness rule”; say “for you to play in a game, you must attend practice” then the problem because very easy for people to solve! Schneier concludes:

Our brains are specially designed to deal with cheating in social exchanges. The evolutionary psychology explanation is that we evolved brain heuristics for the social problems that our prehistoric ancestors had to deal with. Once humans became good at cheating, they then had to become good at detecting cheating — otherwise, the social group would fall apart.

So, maybe I can use the fact that people seem to understand this rule in this setting when it comes to teaching this point of logic?

Comments (1)

March 6, 2010

The Principle of Mathematical Induction: why it works

Filed under: induction, logic, transfinite induction, Uncategorized — collegemathteaching @ 11:03 pm

For those who prefer a video:

I am writing this post because I’ve seen that there is some misunderstanding of what mathematical induction is and why it works.

What is mathematical induction? It is a common proof technique. Basically, if one wants to show that a statement is true in generality and that one can index the set of statements via the integers (or by some other appropriate index set), then one can use induction.Here is a common example: suppose one wants to show that
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ for all positive integers $k$
(for example, $1 + 2 + 3 + 4 + 5 = (1/2)*(5)*(5+1) = 15$ ).

Initial step: $1 = (1/2)*(1)*(1+1)= 1$ so the statement is true for $k = 1$ .

Inductive step: assume that the formula holds for some integer $k$ .
Finish the proof: show that if the formula holds for some integer $k$ , then it holds for $k+1$ as well.

So $1 + 2 + 3 +....+ k + (k+1) = (1 + 2 + ...+ k) + (k+1) =(1/2)*(k)*(k+1) + (k + 1)$
(why? because we assumed that $k$ was an integer for which
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ . )

so $1 + 2 + 3 +....+ k + (k+1) = (1/2)*(k)*(k+1) + (k + 1) = ((1/2)*k + 1)*(k+1)$ (factor out a k+1 term)
$= (1/2)*2*((1/2)*k + 1)*(k+1) = (1/2)*(k+2)*(k+1)=(1/2)*(k+1)*(k+2)=(1/2)*(k+1)*(k+1 + 1)$
which is what we needed to show. So the proof would be done.
Why does induction “prove” anything? Mathematical induction is equivalent to the so called “least positive integer” principle in mathematics.
What is the least positive integer principle? It says this: “any non-empty set of positive integers has a smallest element”. That statement is taken as an axiom; that is, it isn’t something that can be proved.
Notice that this statement is false if we change some conditions. For example, is is NOT true that, say, any set of positive numbers (or even rational numbers) has a smallest element. For example, the set of all numbers between 0 and 1 (exclusive; 0 is not included) does NOT have a least element (not according to the “usual” ordering induced by the real number line; it is an easy exercise to see that the rationals can be ordered so as to have a least element). Why? Let $b$ be a candidate to be the least element. Then $b$ is between 0 and 1. But then $(1/2)b$ is greater than zero but is less than $b$ ; hence $b$ could not have been the least element. Neither could any other number.

Note that the set of negative integers has no least element; hence we need the condition that the integers are positive.

Notice also that there could be groups of positive integers with no greatest element. For example, Let $x$ be the largest element in the set of all even integers. But then $2x$ is also even and is bigger than $x$ . Hence it is impossible to have a largest one.
What does this principle have to do with induction? This is what: an induction proof is nothing more than a least integer argument in disguise. Lets return to our previous example for a demonstation; that is, our proof that $1 + 2 + ....+ n = (1/2)n(n+1)$ We start by labeling our statements: $1 = (1/2)(1)(1+1)$ is statement P(1),
$1 + 2 = (1/2)(2)(2+1)$ is statement P(2), … $1+2+...+ 5 = (1/2)(5)(5+1)$ is statement P(5) and so on.

We assume that the statement is false for some integer. The set of integers for which the statement is false has a least element by the least element principle for positive integers.

We assume that the first integer for which the statement is false is $k+1$ . We can always do this, because we proved that the statement is true for $k = 1$ , so the first possible false statement is $k = 2$ or some larger integer, and these integers can always be written in the form $k + 1$ .

That is why the anchor statement (the beginning) is so important.

We now can assume that the statement is true for $n = 1,....n = k$ since $k+1$ is the first time the statement fails.

Now when we show “if statement P( $k$ ) is true then P( $k+1$ ) is also true (this is where we did the algebra to add up $1 + 2 + .....+ k + (k+1) = ((1/2)k(k+1)) + (k+1) )$ . This contradicts that statement P( $k+1$ ) is false.

Hence the statement cannot be false for ANY positive integer $k$ .
Weak versus strong induction. As you can see, the least positive integer principle supposes that the statement is true for all statements P(1) through P( $k$ ), so in fact there is no difference (when inducting on the set of positive integers) between weak induction (which assumes the induction hypothesis for some integer $k$ ) and strong induction (which assumes the induction hypothesis for $n = 1$ through $n = k$ ).
Other index sets: any index set that one has to induct on has to have the “least element principle” to its subsets. Also, if there is a cardinal w that has no immediate predecessor, then one must “reanchor” the induction hypothesis as $k = w$ prior to proceeding.