1

In general how does one formulate a proof by controposition or contradiction for the following general form: $\forall x\exists ! y (P(x)\wedge Q(y) \rightarrow R(x,y))$

Or more specifically: $\forall x\exists ! y (x\geq 0 \wedge y\geq 0 \rightarrow (y^2\leq x<(y+1)^2))$

EDIT: $x$ and $y$ are (non-negative) integers.

If it makes it easier to disregard the uniqueness, I would be interested in that as well. FYI: I know how to prove it directly by using the floor function to define $y$, I just was wondering how it would be done indirectly.

Carl Mummert
  • 81,604
Sonny
  • 11
  • For a proof by contradiction, you have to assume the negation of your statement and derive a contradiction; if we disregard uniqueness, the negation of the statement above is : $\exists x \forall y \lnot ((P(x)∧Q(y))→R(x,y))$ i.e. $\exists x \forall y (P(x) \land Q(y) \land \lnot R(x,y))$. – Mauro ALLEGRANZA Jan 27 '15 at 16:44
  • Thank you very much that is helpful. So going from your comment would the following be correct (ignoring the quantifier): Assume $\exists x \forall y (x\geq 0\wedge y\geq 0 \wedge (y^2>x\geq(y+1)^2))$. Clearly the conjuction is never true (it requires $y<0$ at the least), therefore the orginial implication is true (ignoring the quantifier). Does that work? It seems too easy though I'm not sure where the error would be. – Sonny Jan 27 '15 at 16:51
  • Not exactly ... The formula $R(x,y)$, written "in extenso", is a conjunction : $(y^2 ≤ x \land x < (y+1)^2)$. When we negate it, we have to apply De Morgan; thus $\lnot R(x,y)$ must be : $(y^2 > x \lor x \ge (y+1)^2)$ ... – Mauro ALLEGRANZA Jan 27 '15 at 17:31

0 Answers0