retagged by
269 views
7 votes
7 votes

Suppose $P(x, y)$ is some binary predicate defined on a very small domain of discourse: just the integers $1,2,3$, and $4.$ For each of the $16$ pairs of these numbers, $P(x, y)$ is either true or false, according to the following table $( x$ values are rows, $y$ values are columns).
$$
\begin{array}{c|cccc}
& 1 & 2 & 3 & 4 \\
\hline 1 & \mathrm{~T} & \mathrm{~F} & \mathrm{~F} & \mathrm{~F} \\
2 & \mathrm{~F} & \mathrm{~T} & \mathrm{~T} & \mathrm{~F} \\
3 & \mathrm{~T} & \mathrm{~T} & \mathrm{~T} & \mathrm{~T} \\
4 & \mathrm{~F} & \mathrm{~F} & \mathrm{~F} & \mathrm{~F}
\end{array}
$$
For example, $P(1,3)$ is false, as indicated by the $\mathrm{F}$ in the first row, third column.

Which of the following statements are false?

  1. $\forall x \exists y P(x, y)$.
  2. $\forall y \exists x P(x, y)$.
  3. $\exists x \forall y P(x, y)$.
  4. $\exists y \forall x P(x, y)$.
retagged by

2 Answers

Best answer
4 votes
4 votes

$\color{red}{\text{Detailed Video Solution:}}$ Detailed Video Solution with Complete Analysis

Option A Explanation:
Option A says "For every element $x$, there is an element $y$ such that $\mathrm{P}(x, y)$ is true". This is false, and the counterexample is the element $x=$ 4. (Since there is No element $y$ such that $\mathrm{P}(4, y)$ is true.)

Option B Explanation:
Option B says "For every element $y$, there is an element $x$ such that $\mathrm{P}(x, y)$ is true". This is true because:

  • For $y=1$, we have $x=1$ or 3 . (Since $P(1,1)=T, P(3,1)=T)$
  • For $y=2$, we have $x=2$ or 3. (Since $\mathrm{P}(2,2)=\mathrm{T}, \mathrm{P}(3,2)=\mathrm{T}$ )
  • For $y=3$, we have $x=2$ or 3 . (Since $P(2,3)=T, P(3,3)=T$ )
  • For $y=4$, we have $x=3$. $($ Since $P(3,4)=T)$

Option C Explanation:
Option C says "There is some element $x$, such that for all elements $y$, $P(x, y)$ is true".. This is true because of $x=3$.
For $x=3$, we have $\mathrm{P}(3,1)=\mathrm{T}, \mathrm{P}(3,2)=\mathrm{T}, \mathrm{P}(3,3)=\mathrm{T}, \mathrm{P}(3,4)=\mathrm{T}$.

Option D Explanation:
Option D says "There is some element $y$, such that for all elements $x$, $\mathrm{P}(x, y)$ is true". This is false there is no such element $y$.

  • For $y=1$, we have $P(2,1)=F$.
  • For $y=2$, we have $\mathrm{P}(1,2)=\mathrm{F}$.
  • For $y=3$, we have $P(1,3)=F$.
  • For $y=4$, we have $\mathrm{P}(1,4)=F.$

$\color{red}{\text{Detailed Video Solution:}}$ Detailed Video Solution with Complete Analysis 

edited by
Answer:

Related questions

6 votes
6 votes
1 answer
2