1
$\begingroup$

Is it possible to prove the above statement via contradiction? I initially tried solving the statement with that method, but all the solutions I see online use a direct proof. Here is what I had (any criticism would be great, too):

$\phi: (\forall x,y\in Q)[(x <y)\Rightarrow(\exists z \in Q)[(x<z)\land(z<y)]]$ $\lnot\phi: (\exists x,y\in Q)[(x < y)\land(\forall z \in Q)[(x\ge z)\lor(z\ge y)]]$ which is false. (Negation of $p\Rightarrow q$ is equivalent to $p \land \lnot q$).

I'm not very sure when I should give up on one method of proving something in favor of another way.

$\endgroup$
4
  • $\begingroup$ I think it depends on what you already "know" / have demonstrated. You have to be explicit about how you're constructing the real numbers. E.g. If we knew that the rationals were dense in R, then we have an easy contradiction. But, they are dnese in R because we could construct a rational between any two. $\endgroup$ – Calvin Lin Dec 9 '19 at 17:25
  • $\begingroup$ Sure: trivially, take any direct proof of the statement, add "Assume for contradiction that this is not true." to the start and "This contradicts our initial assumption, so we have the result." to the end. I imagine you have some rather more stringent requirements on your proof than that? $\endgroup$ – user3482749 Dec 9 '19 at 17:28
  • $\begingroup$ It's a question as part of a self-paced MOOC on mathematical thinking, so I'm pretty much on my own here. $\endgroup$ – Charybdis Dec 9 '19 at 17:30
  • $\begingroup$ Frankly, user3482749's comment, for which Kathy Rindhoops' post is a specific example, is pretty much how to do it. Both proofs by contradiction and direct proofs can always (under standard logic with the law of the excluded middle) be converted to the other form. But the results of the direct proof conversion is a proof where it is obvious contradiction is not needed, and the results of proof-by-contradiction conversion often involves convoluted statements that are annoying to follow. $\endgroup$ – Paul Sinclair Dec 10 '19 at 0:23
1
$\begingroup$

I guess you could, you would start with something like assuming that if you have 2 rationals x and y, then anything in between x and y must be irrational. So we want to contradict the statement

if $x < y ∈ ℚ$, then $\lnot\exists z∈ℚ,$ $x < z < y$

Then you could say since x and y are rational, you can write them as

$x = \frac{p}{q}$ and $x = \frac{r}{s}$

then find something between them, i.e

one option for z is $z = \frac{x + y}{2}$ since it is between x and y, and this can then be written as

$z = \frac{\frac{p}{q} + \frac{r}{s}}{2}$

which you can then reslove, and since we know that $p, q, r, s$ and $2$ are all rational, z must be rational which is a contradiction.

Is this what you were looking for?

$\endgroup$
4
  • $\begingroup$ Thanks Kathy! I think this is what I am looking for. But wouldn't the negation of ¬∃z∈Q(x<z<y) be ∀z∈Q(¬[x < z < y])? Rather than there exists a z not part of the rational numbers? $\endgroup$ – Charybdis Dec 10 '19 at 0:42
  • $\begingroup$ The two you posted there are actually equivalent, not negations. ¬∃z∈Q(x<z<y) means there are no rational numbers between x and y and ∀z∈Q(¬[x < z < y]) means if a number is rational, its not between x and y. $\endgroup$ – Kathy Rindhoops Dec 10 '19 at 10:00
  • $\begingroup$ What we're aiming to prove is that, given a number z between x and y, can we prove that z is always irrational, and once we find a contradiction we will have shown that there are some rational numbers between x and y. $\endgroup$ – Kathy Rindhoops Dec 10 '19 at 10:04
  • $\begingroup$ Ah, I think I get it now. Cheers, thank you for the clarification! $\endgroup$ – Charybdis Dec 10 '19 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.