2

I'm very confused as to how to even begin, any explanation or help would be really appreciated. I understand Universal and Existential Quantifiers but the actual process of proving it is what confuses me.

John S.
  • 21
  • 1
    This is actually not always true; it depends on whether there are any values of $y$ in existence. – Ian Sep 16 '15 at 14:26
  • In order "to prove this in a step-wise manner" you have to specify the proof system you are workink with : Natural Deduction, axioms and rules, ... – Mauro ALLEGRANZA Sep 16 '15 at 15:46

2 Answers2

2

Hint:

  • Imagine a huge table/matrix with entries in $p_{x,y} \in \{0,1\}$, where $x$ determines the row and $y$ determines the column, for example $$\begin{array}{c|ccc} &y_1&y_2&y_3\\\hline x_1&p_{x_1,y_1}&p_{x_1,y_2}&p_{x_1,y_3} \\ x_2&p_{x_2,y_1}&p_{x_2,y_2}&p_{x_2,y_3} \\ x_3&p_{x_3,y_1}&p_{x_3,y_2}&p_{x_3,y_3} \end{array}$$

  • Suppose that $$P(x,y) \iff p_{x,y} = 1,$$ then $\exists x.\ \forall y.\ P(x,y)$ says \begin{align} &\exists x &&\text{ there exists a row such that }\\ &\forall y &&\text{ for all columns }\\ &P(x,y) && \text{ we have }p_{x,y} = 1. \end{align}

  • On the other hand $\exists y.\ \exists x.\ P(x,y)$ says \begin{align} &\exists y &&\text{ there exists a column such that }\\ &\exists x &&\text{ there exists a row where }\\ &P(x,y) && \text{ we have }p_{x,y} = 1. \end{align}
  • In other words, given there exists a row full of $1$'s, does a column that contains at least one value $1$ have to exist?
  • Observe that for the theorem to work we need an assumption that there is at least one column.

I hope this helps $\ddot\smile$

dtldarek
  • 37,381
  • Thank you for the explanation, I understand what the question is actually asking of me better. However, I need to be able to prove this in a step-wise manner. Sorry if my question was phrased a little to vaguely, I only just started learning discrete mathematics. – John S. Sep 16 '15 at 14:39
  • @JohnS. I suspected this is the case and intentionally provided that particular hint. Don't forget that it is you who has to learn to realize your thoughts in the language of math, which is the actual challenge of this problem. – dtldarek Sep 16 '15 at 14:47
  • I understand your point, thanks for taking the time to help me out. – John S. Sep 16 '15 at 14:49
0

You are given $\exists x\ \forall y\ P(x, y)$. So, writing this in words, we can say that there exists a special value of $x$ such that for all $y$ (no matter what $y$ is chosen), $P(x, y)$ is always going to be true. So lets choose this special value of $x$ and call it $x_0$. Now, no matter what $y$ value you choose, $P(x_0, y)$ is always going to be true. Can you finish the argument from there?

Raj
  • 964