Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?

Question

I'm currently trying to prove that $\exists n\forall m~P(m,n)\Rightarrow \forall m\exists n P(m,n)$ formally. This is important to me because my professor and various only sources have hinted that in the statement "$\forall m \exists n~P(m,n)$", the identity of $n$ might (or might not) depend on $m$. This is clear to me when I started to study limits but the underlying reason as to why this is so remains elusive. I want to understand what it is meant precisely when we say that "$n$ might (or might not) depend on $m$", but before that I need a precise understand what a $\forall x\exists y P(x,y)$ statement means. Likewise, I need to understand what a $\exists x \forall y P(x,y)$ means. I can't find any online elaboration on what those statements mean formally. Any help?

edit: please do not get distracted by my attempt to prove $\exists n\forall m~P(m,n)\Rightarrow \forall m\exists n P(m,n)$. That is just the motivation of my question, not the actual question itself. Please do not answer that instead of the original question as stipulated in the title.

Answer 1

The statement

$$\exists n\forall m: P(m,n)$$

reads

There exists such a value $n$ that for every value $m$, the statement $P(m,n)$ is true.

While the statement

$$\forall m\exists n: P(m,n)$$

reads

For every value of $m$, there exists such a value $n$ that $P(m,n)$ is true.

The difference between these statements can be best seen in an example. Let's say that $P(m, n) = m<n$ and that we are dealing with integers.

Then the first statement says:

There exists such a number $n\in\mathbb N$ that for every other number $m\in\mathbb N$, we have $m<n$.

In other words, this statement says "there exists an integer larger than all other integers", which is false.

The second statement says:

For every $m\in\mathbb N$, there exists some $n\in\mathbb N$ that $m<n$

In other words, "for every integer, there exists some larger integer", which is true.

---

In your case, you want to prove that one statement (i.e.: $\exists n\forall m: P(m,n)$) implies the other. You can do this by assuming that the first statement is true and prove the second one.

You therefore need to prove that $\forall m\exists n P(m,n)$. You start by taking an arbitrary $m$. Then, you know that, since

$$\exists n_0\forall m P(m, n_0)$$

is true, you take the $n_0$ that satisfies the above equation. By assumption, you therefore know that $P(m, n_0)$ is true. You have, for this particular $m$, found a value of $n$ (i.e.: $n=n_0$) for which $P(m, n)$ is true, so you have, for this $m$, proven that $\exists n:P(m, n)$ is true.

Furthermore, because $m$ was arbitrary, you have proven the above statement for all values of $m$, so you have proven the statement

$$\forall m\exists n P(m,n).$$

Answer 2

You can if your universe is finite$^\dagger$. If it is, then $$\forall x \in X.\ \Phi(x)\quad\text{ is equivalent to }\quad\bigwedge_{x \in X}\Phi(x),$$ that is, a big conjunction of $\Phi$'s for each element of $X$. However, if $X$ is infinite, then that would give you infinitely long formula, which we would have trouble valuating. Precisely for this reason we introduce quantifier $\forall$ which can be informally thought of as a way of valuating this particular infinitely long conjunction.

The same is true for $\exists x \in X.\ \Phi(x)$ and $\bigvee_{x \in X}\Phi(x)$, only this time we form the term using $\lor$ rather than $\land$: $$\Phi(x_1) \lor \Phi(x_2) \lor \ldots$$

Now to form a toy example, consider $X = \{x_1,x_2\}$ and $Y = \{y_1,y_2\}$, then \begin{align*} \forall x \in X.\ \exists y \in Y.\ P(x,y) &\iff \forall x \in X.\ P(x,y_1) \lor P(x,y_2) \\ &\iff \Big(P(x_1,y_1) \lor P(x_1,y_2)\Big) \land \Big(P(x_2,y_1) \lor P(x_2,y_2)\Big), \\ \forall x \in X.\ \exists y \in Y.\ P(x,y) &\iff \Big(\exists y \in Y.\ P(x_1,y)\Big) \land \Big(\exists y \in Y.\ P(x_2,y)\Big) \\ &\iff \Big(P(x_1,y_1) \lor P(x_1,y_2)\Big) \land \Big(P(x_2,y_1) \lor P(x_2,y_2)\Big), \\ \exists y \in Y.\ \forall x \in X.\ P(x,y) &\iff \exists y \in Y.\ P(x_1,y) \land P(x_2,y) \\ &\iff \Big(P(x_1,y_1) \land P(x_2,y_1)\Big) \lor \Big(P(x_1,y_2) \land P(x_2,y_2)\Big). \end{align*}

It is not that had to see that if the last formula is true, then both $P(x_1,y)$ and $P(x_2,y)$ are true for some $y \in Y$, so the first two formulas also have to be true. Note that what I wrote

both $P(x_1,y)$ and $P(x_2,y)$ are true for some $y \in Y$

is exactly the meaning of $\exists y \in Y.\ \forall x \in X.\ P(x,y)$ for the $X$ and $Y$ as defined above.

I hope this helps $\ddot\smile$

---

$\dagger$ Actually, as Noah Schweber points out in his comment, that's not quite right—we still need to be able to somehow reach these elements. However, I don't want to make things too complicated, so let's leave these issues aside (see the comments for more details).

Answer 3

If I said

For any woman, there is a food that she loves.

$$\forall W \in \text{ Women } \exists F \in \text{ Food } ~:~ W \text{ Loves } F$$

would you answer with "Ok, which food?" Hopefully not, because my response would be "it depends on the woman." Some women like cake, some like wine, some like ice cream-- it depends on the woman.

If I say "for any woman, there is a food that she loves" and you assume that you can go to the store and buy one food that will please every woman, you will be very mistaken. Because it depends.

However, if I say

There is a song that every woman loves.

$$\exists S \in \text{ Songs } \forall W \in \text{ Women } ~:~ W \text{ Loves } S$$

you would be correct to say "which song?" Because, I suggested that there is a universal song.

So if I say:

If there is a holiday that every woman likes, then every woman likes at least one holiday.

$$\exists n \forall m P(m, n) \implies \forall m \exists n P(m, n)$$

Hopefully that statement is obviously true. However, it is odd to ask if the holiday depends on the woman: the above statement would be true even if there were no holidays.