1
$\begingroup$

Determine the truth value of $$(\forall x)(\exists y)(x=y\to x>y)$$ over the integers.

My work:

$(\forall x)(\exists y)(x=y\to x>y)$ means "For all $x$, there exists a $y$ where $x=y\to x>y$".

Since $x=y$, we can replace the $y$ with the $x$ and vice-versa. We can get $$x>x$$ once we replaced.

This statement is always false, no matter what $x$ is. So in this case $x=y$ is true, but $x>y$ is not true, or false. So, using the truth table below, $$\begin{array}{c|c|c}x=y&x>y&x=y\to x>y\\\hline\mathrm{T}&\mathrm{T}&\mathrm{T}\\\color{red}{\mathrm{T}}&\color{red}{\mathrm{F}}&\color{red}{\mathrm{F}}\\\mathrm{F}&\mathrm{T}&\mathrm{T}\\\mathrm{F}&\mathrm{F}&\mathrm{T}\end{array}$$ we can say that this statement is false.

(Image that replaced text).

$\endgroup$
9
  • 2
    $\begingroup$ What you wrote in that solution explains why $x=y\to x>y$ is not always true. So that shows that $\forall x\forall y(x=y\to x>y)$ is false, but it doesn't say anything about the given problem. $\endgroup$ Jul 13 '19 at 23:31
  • $\begingroup$ What do you mean by that? $\endgroup$ Jul 13 '19 at 23:32
  • $\begingroup$ I mean your solution is wrong. $\endgroup$ Jul 13 '19 at 23:33
  • 1
    $\begingroup$ You don't. It's true. $\endgroup$ Jul 13 '19 at 23:34
  • 3
    $\begingroup$ What was wrong about the first solution was you sort of missed the point to the $\forall x\exists y$ part (the "quantifiers"). Here's an outline of the solution that deals properly with the quantifiers, with blanks you should be able to fill in: "Given $x$, let $y=\dots$. Then ..., so $x=y\to x>y$ is true." $\endgroup$ Jul 13 '19 at 23:42
6
$\begingroup$

Hint: $\forall x~\color{red}\exists y~(P(x,y)\to Q(x,y))$ is true exactly when: every $x$ has some $y$ where $Q(x,y)$ is true or $P(x,y)$ is false.


Since $x=y$, we can replace the $y$ with the $x$ and vice-versa. We can get $$x>x$$ once we replaced.

This statement is always false, no matter what $x$ is. So in this case $x=y$ is true, but $x>y$ is not true, or false. So, using the truth table below, $$\begin{array}{c|c|c}x=y&x>y&x=y\to x>y\\\hline\mathrm{T}&\mathrm{T}&\mathrm{T}\\\color{red}{\mathrm{T}}&\color{red}{\mathrm{F}}&\color{red}{\mathrm{F}}\\\mathrm{F}&\mathrm{T}&\mathrm{T}\\\mathrm{F}&\mathrm{F}&\mathrm{T}\end{array}$$ we can say that this statement is false.

No. What the truth table is telling you is that the implication is true in three cases.

Case 1: $x=y$ and $x>y$. Well, for any $x$ that cannot happen. However we must check the other two cases.

Case 2: $\lnot(x=y)$ and $x>y$. Well, for any $x$ there is some $y$ where both of these are true.

Case 3: $\lnot (x=y)$ and $\lnot(x>y)$. Well, for any $x$ there is some $y$ where both of these are true.

Since for any $x$ there is a $y$ where $\lnot (x=y)$, then cases $2$ and $3$ may be satisfied for any $x$. Thus we confirm that for any $x$ there is some $y$ where the implication holds.

$\endgroup$
1
$\begingroup$

If $P(x)$ is false for some $x$, then $P(x) \to Q(x)$ is true no matter what the value of $Q(x)$ is so if you find an $y$ where $y \neq x$(e.g $x-1$), the statement would always hold.

Also, this is related: $\lnot\exists x(S(x) \Rightarrow R(x))$ VS $\forall x(S(x) \Rightarrow R(x))$ Without Using De Morgan's Law

$\endgroup$

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.