Books: Maths Proving Techniques

Do you know any good books on proving techniques (barring basics like Book of Proof)? I came across pic related in a footnote.

Bump

OP here. I know this one too, haven't read it though.

Basic techniques are all there are.

Direct
Induction (weak, strong, well ordering)
Contradiction
Contrapositive
Diagonalization
Proof by last lecture

This is not a book on proving techniques, but rather on the best proofs of all. Many of the proofs have some kind of "divine insight" that only applies in that one case and which makes them extremely elegant. As such, it's not really usable as a learning resource.

>Contradiction
Say that again?

i dont know any books on the subject

but i've watched that course by The Great Courses called 'The art and craft of mathematical problem solving', not sure if thats what you need though

>Basic techniques are all there are.

No, I mean stuff like Vieta jumping.

Say we want to prove that the sum of an even and an odd number is odd. If the numbers are m and n, respectively, then we can express them as m=2a and n=2b+1 for some integers a and b. Suppose the sum isn't odd. Then we can express it as m+n=2c for some integer c, but now we have m+n=2a+2b+1=2(a+b)+1=2c giving us 1=2(c-a-b). Since a, b and c are integers, so is c-a-b, but, for the equation to hold, it must be that c-a-b=1/2, and that is a contradiction.

>Suppose the sum isn't odd
Why would you do that? You can prove this trivial proposition purely constructively.

It was an example. I could have given a more sophisticated one, but, for someone asking how to prove stuff by contradiction, that would probably have been an overkill.

One could ofcourse take the n-dimensional, n>1, Euclidean space into consideration and suppose the (n-1)-sphere is a retract of the closed n-ball. Denote by [math]i[/math] the inclusion [math]S^{n-1} \to D^n[/math], and by r the retraction [math]D^n \to S^{n-1}[/math]. Now, [math]ri=1_{S^{n-1}}[/math], so this would then induce maps [math]r_* \colon H_{n-1}(D^n) \to H_{n-1}(S^{n-1})[/math] and [math]i_* \colon H_{n-1}(S^{n-1}) \to H_{n-1}(D^n)[/math], with [math]r_* i_* =1_{H_{n-1}(S^{n-1})}[/math], in singular homology, but [math]H_{n-1}(D^n)=0[/math] and [math]H_{n-1}(S^{n-1}) \cong \mathbb{Z}[/math], which is a contradiction.

You can build up all of algebraic topology constructively, as well.

How do you prove without using contradictions that a sphere is not a retract of the ball it bounds? Just out of curiosity.

Just ignore him, he's an idiot. Proof by contradiction is perfectly valid.

Theorem: OP is a cuck.

Proof (by contradiction): Suppose OP were not a cuck. Then he wouldn't be posting on Veeky Forums. But clearly he is posting on Veeky Forums, hence we have reached a contradiction. We conclude that OP is a cuck.

I know. Either he was trying to provoke me or he was just stupid. Independent on which holds, he has lost in life anyway.

These two are actually different proving techniques even though they are both often referred to as contradiction in classical mathematics.

In one method you suppose a statement is true and after contradiction you conclude it is false. This method is valid in intuitionistic logic and the picture refers to it as proof by contraposition (because one justification is that you're just restating the original statement as the contrapositive).

In the other method you start with a false statement (not P), after a contradiction deduce that it is not false (not not P), and then use double negation elimination to deduce it is true. The only part of this not valid in intuitionistic logic is the double negation elimination (furthermore, this is the only difference between intuitionistic and classical logic). Really the only difference between this method and the other one is the double negation part.

Depending on the text, three methods may be referred to by different terms. I've even seen texts that refer to the first method as contradiction and the second method as double negation. To avoid confusion I refer to them as positive contradiction and negative contradiction.

(cont.)

(cont.)

To illustrate the difference between a double negated sentence and a true sentence (in intuitionistic logic) suppose I give you a set, A. Now suppose it is possible to prove that the set is non-empty (note, non-empty is formally a double negated sentence in set theory, to out it informally: it is not the case that there are not any elements in the set) but it is not possible to demonstrate any element inside the set. In this case it is impossible to prove that the set is inhabited but one can prove that it is non-empty.

In classical logic we ignore this sort of distinction and basically their away that extra structure. Doing so makes some things easier to prove and makes it so that one isn't struggling to sort out multiple layers of negations. We can view classical logic as a special case of intuitionistic logic where things are just easier. Note: axiom of choice and a few other statements are actually stronger than double negation elimination, so using them actually puts you in an even more special case.

>Depending on the text, these methods
Fixed

>to put it informally:
>and basically throw away
Fixed

Fucking auto complete.

Hey, I've got that book right next to me on my desk. Neat.

No need for contradiction, the proof is trivial.

Also just bought this, and heard good things about it. I'm waiting for it to ship.

I thought about saying that after I'd already posted. Oh well.

And I've never actually heard of it. What level is it at? Similar to How to Prove It or Book of Proof?

See for yourself

>https:// math. la.asu.edu/~ifulman/spring13/mat194/problem-solving. pdf