# Is my logic for this proof okay?

• Feb 2nd 2010, 08:31 PM
swtdelicaterose
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!
• Feb 2nd 2010, 09:19 PM
harish21
Quote:

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".
• Feb 2nd 2010, 09:40 PM
swtdelicaterose
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!
• Feb 3rd 2010, 03:54 AM
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}$
• Feb 3rd 2010, 10:48 AM
novice
Quote:

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.
• Feb 3rd 2010, 11:49 AM
novice

My proof cannot stand because $\displaystyle m=0$ is a counter example.
• Feb 3rd 2010, 12:02 PM
novice
Quote:

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.
• Feb 3rd 2010, 12:06 PM
You should be ok, novice!

It works for any non-zero rational number.
• Feb 3rd 2010, 12:14 PM
novice

The $\displaystyle q = 0$ really bothers me because $\displaystyle \forall q \in \mathbb{Q}$ does not exclude $\displaystyle q=0$.
• Feb 3rd 2010, 12:20 PM
novice
Quote:

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.
• Feb 3rd 2010, 02:12 PM
swtdelicaterose
Quote:

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?
• Feb 3rd 2010, 03:18 PM
bmp05
$\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.