# Proof by contradiction - Predicates and quantifiers

Consider statement,

For all integers, b,c,d, if x is a rational number such that $x^2+bx+c=d$, than x is an integer.

a) express above statment in the form, $Q_1 b,c,d\in U_1 ( Q_2 x\in U_2(p(x)\rightarrow Q(x)))$ , specifying the universes, $U_1, U_2$, and the quantifiers, $Q_1, Q_2$, and the statement $p(x), q(x)$.

b)Prove the statement by contradiction. Use the fact that if a rational number $x$ is not an integer than there are integers $m,n$ such that $x=m/n$ with $n>1$.

My answer for a) was that

U_1: All Integer

U_2: All Rational #

Q_1: all

Q_2: there is an $x$ such that p(x)

p(x): x is rational

q(x): rational #

I don't know what I've done wrong. For b),

Since I have to prove it by contradiction, I know I should start with 'not p' than 'not $p\Rightarrow\ not q$, and we derive a contradiction, and we find out 'not p' is false, thus p is true.

Not p(x) would be $x$ is irrational, than how should I apply this 'irrational number' to the equation, $x^2+bx+c=d$?

For all integers, b,c,d, if x is a rational number such that $x^2+bx+c=d$, than x is an integer.

a) $$\forall b,c,d \in \mathbb{Z} : x \in \Bbb{Q}\; x^2+bx+c=d \Rightarrow x \in \Bbb{Z}$$ $$Q_1 b,c,d\in U_1 ( Q_2 x\in U_2(p(x)\rightarrow Q(x)))$$

U_1: All Integer (ok)

U_2: All Rational # (ok)

Q_1: all (ok)

Q_2: there is an $x$ such that p(x) (ok)

p(x): x is rational (no) p(x): $x$ such that $x^2+bx+c=d$

q(x): rational # (no) (integer)

b) Consider $x = \frac{m}{n}$ with $m,n$ co-primes (that is, the fraction is irreducible). Now write

$$\bigg(\frac{m}{n}\bigg)^2+b\frac{m}{n}+c=d \Rightarrow \frac{m^2}{n^2}+b\frac{m}{n} \in \mathbb{Z} \Rightarrow \frac{m^2}{n} + bm \in \mathbb{Z} \Rightarrow \frac{m^2}{n} \in \mathbb{Z} \Rightarrow n \text{ divides } m$$ Absurd

• In proof by contradiction, don't we start with 'not p'? Than, for me, it sounds like 'not p(x)' should be $x^2+bx+c$ not equal to $d$. – Minjae Jul 1 '15 at 0:40
• this is the contradiction, since we assumed (m,n) coprimes – Conrado Costa Jul 1 '15 at 0:41
• So we can refer to contradiction with the fact that 'not p' is false. – Minjae Jul 1 '15 at 0:44
• I mean, I don't get the point for applying $x=m/n$ into the equation. – Minjae Jul 1 '15 at 0:46
• The way I think is: we assumed that $x$ was not integer and we arrived at the fact that $x$ is an integer. Note that if $n$ divides $m$ then $x = \frac{m}{n} \in \mathbb{Z}$ this is a contradiction – Conrado Costa Jul 1 '15 at 0:48