1
$\begingroup$

This is a problem from Discrete Mathematics and its Applications enter image description here

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 enter image description here

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 enter image description here

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is WLOG necessary in this case? There's only two cases. $\endgroup$ Commented Jan 28, 2015 at 19:33
  • $\begingroup$ You can do both cases if you want. It doesn't make too much of a difference here. $\endgroup$
    – Glare
    Commented Jan 29, 2015 at 1:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .