# Can someone verify my proof by contraposition?

This is a problem from Discrete Mathematics and its Applications

Is there a way to tell right away what type of proof to use or does that just come with practice (build intuition - oh here i should use proof by contradiction, or by contraposition, etc)

Anyways I chose to use proof by Contraposition because I didn't really have any experience with it

Here is my book's summary on proof by Contraposition

Basically what I got from this was to assume $$\sim q$$, take logical steps to reach conclusion, $$\sim p$$.

Here is my work so far

Here is my thought process I started off with a regular implication describing the situation if a function from $$\mathbb{R}$$ to itself is strictly decreasing, then it is one to one. To form this implication, there are two propositions, $$p$$: the function is strictly decreasing, and $$q$$: the function is one-to-one.

After reading the book section on proof by contraposition, I know the method just was proving that the contrapositive is true, which is $$\sim q \Rightarrow\sim p$$, or if a function is not one to one, it is not strictly decreasing. I then treated this as a direct proof basically and assumed $$\sim q$$ was true and took logical steps to get to $$\sim p$$.

If a function is not one to one, there are a pair of real numbers $$x$$ and $$y$$ such that $$f(x) = f(y)$$ but $$x\neq y$$. My next step was to logically reason that if $$x\neq y$$, then either $$x > y$$ or $$x < y$$. In both cases, the function would not be strictly decreasing because strictly decreasing means that if $$x > y$$, then $$f(x) > f(y)$$, not $$f(x) = f(y)$$. Therefore I have proved that a strictly decreasing function from $$\mathbb{R}$$ to itself is one to one because I have proved that if a function is not one to one, it is not strictly decreasing.

Does everything look logically coherent/organized? Was proof by contraposition the best proof method to use here?

• Thanks! I just fixed that. Commented Jan 20, 2015 at 23:27
• Not sure if one also has to consider a non surjective function.
– mvw
Commented Jan 20, 2015 at 23:28
• Looks good, and also proves the same for strictly increasing functions. Commented Jan 20, 2015 at 23:41

In the last line, it should be $f(x)>f(y)$, since it's decreasing as opposed to increasing. Besides that, this looks fine to me. In terms of whether proof by contraposition was the "best method," it's important to keep in mind that the various proof methods are logically equivalent, and will therefore (usually) use the same ideas/manipulations. In my opinion, then, the "best method" is the one that makes the most sense to you.
That being said, I do know people who refuse to use contradiction/contrapositive whenever possible, since these proofs can (again, usually) be reformulated into direct proofs. In your case, a direct proof would look something like this: Suppose $f$ is strictly decreasing, and let $x,y\in\mathbb{R}$ be such that $x\neq y$. WLOG, suppose $x<y$. Then $f(y)<f(x)$. Since $x\neq y \implies f(x)\neq f(y)$, $f$ is one-to-one. Depending on the definition of "one-to-one" you have, you may argue that this is the contrapositive, but again, they're all pretty much the same.