0
$\begingroup$

I am grading an introduction to proofs course at my university. We have a question that reads something along the lines of:

Prove that $$\forall \ n \in \Bbb N, [\exists \ a \in \Bbb N : n + 1 = 3a \Rightarrow \exists \ b \in \Bbb N : n^2 + 4n + 1 = b].$$ Students attempt to prove this by writing $$n+1 =3a$$ $$n = 3a - 1$$ $$n^2 + 4n + 1 = b$$ $$(3a-1)^2 + 4(3a-1)+1 = b$$ $$ 9a^2 + 6a-2 = b.$$

Now while this calculation is necessary to understand the problem, I believe this is not a logically sound argument because they have assumed the conclusion (albeit they have not written their assumptions explicitly). If the correct logical connectives and quantifiers are introduced, the most this string of reasoning could prove is the statement

$$ \forall \ n \in \Bbb N, [(\exists \ a : n+1 = 3a \text{ and } \exists \ b : n^2 + 4n + 1 = b) \Rightarrow b = 9a^2 + 6a - 2.]$$

This argument is remedied by writing $$\text{Let } n \in \Bbb N.$$ $$\text{Assume } \exists \ a \in \Bbb N \text{ such that } n+1 = 3a.$$ $$\text{Then } n = 3a - 1.$$ $$\text{Take } b = 9a^2 + 6a - 2 \in \Bbb N.$$ $$\text{Then } n^2 + 4n + 1 = \cdots = b\text{, as required.}$$ In essence, the author of the original "proof" needs to note that his string of equalities can be written in the opposite order. But our convention in mathematics is that invisible $\Leftrightarrow$ symbols have been inserted at the beginning of each line, so explaining this to a student might be difficult.

So my question is, in the general case of proving a statement $$\exists \ a \text{ with property } P \Rightarrow \exists \ b \text{ with property } Q,$$ are there counterexamples where reasoning of the first kind does not suffice to prove the statement, i.e. where it does not suffice to prove that $$\exists \ a \text{ with property } P \text{ and } \exists \ b \text{ with property } Q \Rightarrow b \text{ may be represented in terms of } a \text{ in some particular way}.$$

$\endgroup$
5
  • $\begingroup$ I think the students proof would have been okay if s/he had said. "we will assume it is true and see if we either arrive at a contradiction or at a formula to find such a b". and then concluded. "Such a b satisfies the condition so our result is shown". .. so this is a tough call on grading. I think it is clear the student didn't understand the the question was to prove a condition and mistakingly assumed to solve an equation, but solving an equation can serve as a proof. So... I don't know what I would grade... $\endgroup$ Commented Feb 23, 2016 at 18:25
  • 1
    $\begingroup$ $\exists b \in\Bbb N : n^2 + 4n + 1 = b$ is trivially true for all $n\in\Bbb N$, so the implication $\exists a \in\Bbb N : n + 1 = 3a \implies \exists b\in\Bbb N : n^2 + 4n + 1 = b$ is also true for all $n\in\Bbb N$. $\endgroup$ Commented Feb 23, 2016 at 18:31
  • $\begingroup$ Counterexample: n may be written as 2a a an integer. prove n may be written as 2b + 1 b an integer. Let n = 2a = 2b + 1 then b = 2(b + 1)/2 = b + 1/2. Not an integer. But thats not a counter example but a proof by contradiction. I think this is a valid method of proof. After all 80 percent of the time we do delta epsilon proofs we do just this. cond A => cond B. Assume so and derive the conditions required to be so. Show conditions can be met. That's a valid proof. $\endgroup$ Commented Feb 23, 2016 at 18:31
  • 1
    $\begingroup$ @Martín-BlasPérezPinilla I guess it's trivially true if you assume 4n, n^2, n+1, and n+m in N if n and m are. ... but if we don't then we can't assume (3a-1)^n + 4(3a -1) + 1 = b in N either. You raise a point that this is a pretty silly exercise and we can't really be surprised that a student will respond in confusion as to the point of it. $\endgroup$ Commented Feb 23, 2016 at 18:38
  • $\begingroup$ @Martin-Blas This is true, but the point of this exercise is to practice this (common) form of mathematical proof-writing. $\endgroup$ Commented Feb 23, 2016 at 18:41

1 Answer 1

Reset to default
1
$\begingroup$

I would say that you have a few choices:

a) You can tell them they need to say something like... "suppose such a number exists - we will find a formula for it."

b) You can point out explicitly to them as you note that the if and only if statements are invisible, but really need to be pointed out at this stage - advanced mathematicians won't, but since they are learning to be rigorous, they need to.

c) You can more subtly ask them if the reasoning they are using is going in the right direction - perhaps they are proving the converse.

I never graded a course like this, but I did grade an introductory linear algebra course which was aimed at students with only some experience with proof-based mathematics. On the problems involving arguments, I was lax originally, just leaving comments highlighting the rationale for the argument and what was missing. As the course went on, I was a little more strict about arguing seriously.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.