In the book that I am reading, the author notes that " $\exists y \in B, \ \forall x \in A, \ P(x,y)$" is a "stronger" statement than "$\forall x \in A,\ \exists y \in B, \ P(x,y)$" because the first one implies the truth of the second one…but the second one does not imply the truth of the first.
I think I understand the if then comment quite well and have included pictures to express my understanding:
For the "stronger case", we have:
if $\ \ \exists y \in B, \ \forall x \in A, \ P(x,y)$, then $\ \forall x \in A,\ \exists y \in B, \ P(x,y)$
which can be illustrated as:
(Hopefully this is comprehensible…I'm basically showing two equivalent pictures and that both versions of this picture satisfy the 'meaning' of the antecedent and consequent. And by "equivalent" I mean that both pictures describe the same element pairs that result in truth)
For the "weaker case", we have:
if $\ \forall x \in A,\ \exists y \in B, \ P(x,y)$, then $\ \exists y \in B, \ \forall x \in A, \ P(x,y)$
Which can be illustrated as follows:
For this weaker case, which could be drawn multiple ways (I just happened to pick one way that would show why this if then statement is false), we see that while the antecedent can be satisfied by the picture, the consequent clearly cannot.
So, okay…cool. I see that the one if then statement is true and the one if then statement is false. But why exactly does this feature make the first case "Strong". In what sense is it strong? Does it allow you to construct proofs more rigorously? Does it allow you to utilize a trick that greatly simplifies proof construction?
In what way does knowing $\ \ \exists y \in B, \ \forall x \in A, \ P(x,y)$ prove more beneficial than knowing $\ \forall x \in A,\ \exists y \in B, \ P(x,y)$?
Any insight (or examples) is greatly appreciated!
Best Answer
If general, a statement $F$ is told stronger than another statement $G$ if the implication $F \Rightarrow G$ holds (i.e. if $G$ holds whenever $F$ holds) but the converse implication $G \Rightarrow F$ does not hold (i.e. it is possible that $G$ holds but $F$ does not hold).
As you said, this is the case for $F = \exists y \in B \, \forall x \in A \, P(x,y)$ and $G = \forall x \in A \, \exists y \in B \, P(x,y)$, because if you assume $F$ then you can always prove $G$ (independently from the meaning of $A$, $B$ or $P$) but clearly the converse is not true: indeed, in the situation where $A = B = \mathbb{N}$ and $P = \, <$, we have that $F = \exists y \in \mathbb{N} \, \forall x \in \mathbb{N} : x < y$ is false ($\mathbb{N}$ has no maximum) but $G = \forall x \in \mathbb{N}\, \exists y \in \mathbb{N} : x < y$ (for every natural number $x$, its successor $x+1$ is greater than $x$).