# Thread: Is my logic for this proof okay?

1. ## Is my logic for this proof okay?

$\displaystyle \forall q \in \textbf{Q}, \exists r \in\textbf{Q}$ so that $\displaystyle q + r \notin \textbf{Z}$ and $\displaystyle qr \in \textbf{Z}$
(where Q is set of all rationals, and Z is set of all integers)

So my approach was to write out the contrapositive, which is the same statement logically. Which is (I think):

$\displaystyle \exists q \in \textbf{Q}, \forall r \in\textbf{Q}$ so that either $\displaystyle q + r \in \textbf{Z}$ or $\displaystyle qr \notin \textbf{Z}$

I'm not sure about the and statement. Is this contrapositive correct?

(if it is correct, then)
So now I just need to let q = a rational number and find a counter example r so that one of the statements in the or fails. So for example, let q = 0 which is rational, and r = 1, q + r is an integer, but qr is also an integer, however since q+r is an integer, the or statement is true, which should mean the original statement is false?

Is my logic correct? I'm not asking for how to prove this, I'm just asking if I can form a proof from what I've established so far.

Thanks!

2. Originally Posted by swtdelicaterose
$\displaystyle \forall q \in \textbf{Q}, \exists r \in\textbf{Q}$ so that $\displaystyle q + r \notin \textbf{Z}$ and $\displaystyle qr \in \textbf{Z}$
(where Q is set of all rationals, and Z is set of all integers)

So my approach was to write out the contrapositive, which is the same statement logically. Which is (I think):

$\displaystyle \exists q \in \textbf{Q}, \forall r \in\textbf{Q}$ so that either $\displaystyle q + r \in \textbf{Z}$ or $\displaystyle qr \notin \textbf{Z}$

I'm not sure about the and statement. Is this contrapositive correct?

(if it is correct, then)
So now I just need to let q = a rational number and find a counter example r so that one of the statements in the or fails. So for example, let q = 0 which is rational, and r = 1, q + r is an integer, but qr is also an integer, however since q+r is an integer, the or statement is true, which should mean the original statement is false?

Is my logic correct? I'm not asking for how to prove this, I'm just asking if I can form a proof from what I've established so far.

Thanks!

You seem to have been negating the given statement, whereas the contrapositive of a statement " A => B" is "~B => ~A".

3. Whoops! Yeah, I meant to do the contrapositive. But, if I prove the negation is true, doesn't that prove the original to be false?

I'll rewrite the contrapositive tomorrow and see if I can solve it. Gotta sleep now, thanks!

4. $\displaystyle (\forall q)(\exists r)(\exists z)[z | z = q + r \wedge z = q \cdot r], q \in \mathbb{Q}, z \in \mathbb{Z}$
Let $\displaystyle q = \frac{1}{2}$
following the above there exists some r so that (q + r) is an integer.
$\displaystyle \frac{1}{2} + \frac{2m + 1}{2} = z, m \in \mathbb{Z}$
then we can test the second condition (q.r) is integer:
$\displaystyle \frac{1}{2} \cdot \frac{2m + 1}{2} = \frac{2m + 1}{4}$
Contradiction: $\displaystyle \frac{2m + 1}{4} \notin \mathbb{Z}$

5. Originally Posted by bmp05
$\displaystyle (\forall q)(\exists r)(\exists z)[z | z = q + r \wedge z = q \cdot r], q \in \mathbb{Q}, z \in \mathbb{Z}$
Let $\displaystyle q = \frac{1}{2}$
following the above there exists some r so that (q + r) is an integer.
$\displaystyle \frac{1}{2} + \frac{2m + 1}{2} = z, m \in \mathbb{Z}$
then we can test the second condition (q.r) is integer:
$\displaystyle \frac{1}{2} \cdot \frac{2m + 1}{2} = \frac{2m + 1}{4}$
Contradiction: $\displaystyle \frac{2m + 1}{4} \notin \mathbb{Z}$
You are to find any rational number $\displaystyle q$ and some rational number $\displaystyle r$ so that the proposition is true, not the contrary.

Suppose for any integer $\displaystyle m,n \in \mathbb{Z}-\{0\}$ and any rational number $\displaystyle q \in \mathbb{Q}$, $\displaystyle q = \frac{m}{n}$ .

There exist some rational number $\displaystyle r \in \mathbb{Q}$ such that $\displaystyle r = \frac{m}{1}$ . Then

$\displaystyle q+r = \frac{m}{n}+\frac{n}{1}=\frac{m+n^2}{n}$ , which is rational for all $\displaystyle m$ and $\displaystyle n$ in $\displaystyle \mathbb{Z}-\{0\}$ . Hence $\displaystyle q+r \notin \mathbb{Z}$ , and

$\displaystyle qr=\frac{m}{n} \cdot \frac{n}{1}=m$ , which is an integer in $\displaystyle \mathbb{Z}$ .

Consequently, the proposition, $\displaystyle \forall q \exists r (q,r \in \mathbb{Q}, q+r \notin \mathbb{Z} \wedge qr \in \mathbb{Z})$, is true.

My proof cannot stand because $\displaystyle m=0$ is a counter example.

7. Originally Posted by swtdelicaterose
$\displaystyle \forall q \in \textbf{Q}, \exists r \in\textbf{Q}$ so that $\displaystyle q + r \notin \textbf{Z}$ and $\displaystyle qr \in \textbf{Z}$
(where Q is set of all rationals, and Z is set of all integers)

So my approach was to write out the contrapositive, which is the same statement logically. Which is (I think):

$\displaystyle \exists q \in \textbf{Q}, \forall r \in\textbf{Q}$ so that either $\displaystyle q + r \in \textbf{Z}$ or $\displaystyle qr \notin \textbf{Z}$

I'm not sure about the and statement. Is this contrapositive correct?

(if it is correct, then)
So now I just need to let q = a rational number and find a counter example r so that one of the statements in the or fails. So for example, let q = 0 which is rational, and r = 1, q + r is an integer, but qr is also an integer, however since q+r is an integer, the or statement is true, which should mean the original statement is false?

Is my logic correct? I'm not asking for how to prove this, I'm just asking if I can form a proof from what I've established so far.

Thanks!
I stared at this and found that the proposition is not a logical implication. If it's not a logical implication, it cannot have a contrapositive statement.

I tried to prove it true, but I found at least one counter example, namely the rational numbers q =0. So the statement is not always true, and a counter example is sufficient, see the proof shown by the poster immediately above me.

Note: a counter example and a contrapositive statement are not synonymous.

8. You should be ok, novice!

It works for any non-zero rational number.

The $\displaystyle q = 0$ really bothers me because $\displaystyle \forall q \in \mathbb{Q}$ does not exclude $\displaystyle q=0$.

10. Originally Posted by Archie Meade
You should be ok, novice!

It works for any non-zero rational number.
Thank you for the link to Wolfram math in regard to the rational numbers. It's an interesting reading. I have learned something new.

11. Originally Posted by bmp05
$\displaystyle (\forall q)(\exists r)(\exists z)[z | z = q + r \wedge z = q \cdot r], q \in \mathbb{Q}, z \in \mathbb{Z}$
Let $\displaystyle q = \frac{1}{2}$
following the above there exists some r so that (q + r) is an integer.
$\displaystyle \frac{1}{2} + \frac{2m + 1}{2} = z, m \in \mathbb{Z}$
then we can test the second condition (q.r) is integer:
$\displaystyle \frac{1}{2} \cdot \frac{2m + 1}{2} = \frac{2m + 1}{4}$
Contradiction: $\displaystyle \frac{2m + 1}{4} \notin \mathbb{Z}$

For this proof to work, don't you have to prove that for all r, instead of just one example of r. Logically, since it says there exists an r, showing that (2k+1)/2 doesn't work just means it doesn't work for this particular example.

So in this proof, q = 1/2, so r is an arbitrary rational number a/b where a and b are integers and b is not 0.

1/2 + a/b is not an integer if a/b is not an integer, if a/b is not an integer then a/b*1/2 = a/2b, now i have to prove a/2b is an integer...
i dunno, i think i'm confusing myself further...

Or am I mistaken?

To prove a counter example is just proving the negation is true, right?

12. $\displaystyle (\forall q)(\exists r)[P(n)], q, r \in \mathbb{S}$

This means that for each element q (in S) there is at least 1 element r in the set S with some property P(n). The property might be $\displaystyle (q + r)$ is not a whole number, but it could be some other property such as "r divides q" etc.

It means that to prove the proposition is false you only have to find one example of q, i.e. one element of S, for which there is no (or can be no) r satisfying the property.