Discrete Math (Proof Techniques)

Question

I'd like to get a bit of an explanation with the correct answer, for the following questions that I missed on my hw.

1. Consider the following proof that all squares are positive:

   Let $n$ be an integer; $n$ is either positive or negative. If $n$ is positive, then $n^2$ must be positive since it's the product of positive numbers; if $n$ is negative then $n^2$ must be positive as the product of two negative numbers. Therefore $n^2$ is always positive.

   What is wrong with this proof?

   • There's an issue with the logic in one of the cases.

   • The case structure doesn't cover all possibilities.

   • The case structure contains overlapping cases.

   • Nothing, this is a perfectly good proof.

   (I thought there would be nothing wrong, because both parts of the statement are always true)

2. Which of the following statements are true?

   • Contraposition is a more powerful proof method than contradiction, because anything we can prove by contraposition can also be proved by contradiction.

   • Contradiction is a more powerful proof method than contraposition, because we're not limited to proving universal conditional statements.

   • The methods of contradiction and contraposition are completely equivalent to each other.

   • Anything that we can prove by contradiction can also be proved by direct methods.

3. Suppose you need to prove that all perfect numbers are even; you proceed by showing that any odd perfect number must also be even. This is an example of:

   • An invalid argument.

   • Proof by contraposition.

   • Proof by contradiction.

   • Proof by division into cases.

   (I believe I had my contraposition and contradiction mixed up, and the correct answer to this question should be contradiction?)

4. Which of these would disprove the universal assertion "All pentagonal numbers are either triangular or square"?

   • An example of a number that is both square and triangular, but not pentagonal.

   • A proof that there are no pentagonal numbers.

   • An example of a pentagonal number that was neither triangular nor square.

   • A proof that no triangular number can be pentagonal.

   • An example of a pentagonal number that is both square and triangular.

Thank you

Answer 1

1. HINT: which number is neither positive nor negative?
2. Unclear what you are asking/being asked.
3. It is indeed a proof by contradiction!
4. HINT: The negation of "For all x, either y or z" is "There exists x, for which neither y nor z".

Answer 2

1) You proved all squares of positive numbers are positive, and all squares of negative numbers are positive. Does this cover all cases? What about if $n=0$.

2)

a)"Contraposition is a more powerful proof method than contradiction, because anything we can prove by contraposition can also be proved by contradiction."

Wouldn't that make contradiction the more powerful method as you can use it in at least as many cases?

"Contradiction is a more powerful proof method than contraposition, because we're not limited to proving universal conditional statements."

Hmm, that's true... but I don't see how proving a contradiction occurs is necessarily any easier then proving universal conditional statements. They may be intending this to be the true statement but... I don't like it.

"The methods of contradiction and contraposition are completely equivalent to each other."

Not quite. One is proving a statement, the contrapositive, is true. The other is showing a contradiction occurs if if we assume a statement is true.

"Anything that we can prove by contradiction can also be proved by direct methods."

I might be wrong but I don't think so.

3) The contrapositive of "All perfect are even" is "No odd numbers are perfect" or "All odd numbers are not perfect". So a proof by contrapositive would be: Assume $n$ is odd, and then proving $n$ is not perfect.

A proof by contradiction is assuming the statement is false and getting a contradiction: Not all perfect numbers are even $\iff$ at least one perfect number is odd. So assume an odd perfect number exist. Then we find that the number must also be even which is a contradiction.

So it's a proof by contradiction:

One thing to keep in mind is that if $P$ is a (supposedly) true statement. e.g. All cows are animals. The negation of it $\not P$ is NOT true. e.g. Some cows are not animals. (not true)

But the contrapositive is an equivalent statement that IS true. $Q \implies R$ is equivalent to contrapositive $-R \implies - Q$. e.g. All cows are animals $\iff $ all things that are not animals are also not cows. (Both are true.)

4) Disprove "All pentagonal numbers are triangular or square"

a) a number that is both triangular and square but not triangular is interesting in itself, but it sees nothing about the other numbers that are pentagonal. This is equivalent to "All cows are black or white". But a penguin is both black AND white but it isn't a cow. So what? That black and white non-cows exist says nothing about what properties cows have to have.

b) proof that there are no pentagonal numbers.

Okay, that would be what is called a vacuuos truth. This is equivalent to "All vampires live on mars". Well, there are no vampires, but that means all vampires that that exist (all zero of them) will do whatever we want because there aren't any that don't. There's no vampire that doesn't live on Mars. So the all (all zero of them) do.

c) a pentagonal number that is neither triangular or square.

That will do it. We said all X do Y. But here is an X that doesn't do Y. That... means we were wrong. "All cows are black and white", but here is a brown cow. It's a cow, and it's neither black nor white. It's hard to prove something wrong than that!

d) A proof that no triangular number is pentagonal.

Well, that proves no pentagonal number is triangular (those two statements are equivalent contrapositive statements). But "all pentagonal numbers are triangular or square" if all pentagonal numbers turn out to be square.

e) An example of a pentagonal number that is square and triangular.

Well, our statement allows they can be both. If we have an example of a number that is both then it is an example of a number that is one, or it is the other, and in this case both.