3
$\begingroup$

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:first case

(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:

second case

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!

$\endgroup$
5
$\begingroup$

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$).

$\endgroup$
2
$\begingroup$

It is stronger in the sense that anything you can prove with $\forall x \ \epsilon \ A,\ \exists y \ \epsilon \ B, \ P(x,y)$, can also be proven with $\exists y \ \epsilon \ B, \ \forall x \ \epsilon \ A, \ P(x,y)$ because the latter implies the former. As an analogy: Every nut you can crack with a rubber hammer can also be cracked with a sledge hammer. But there might be nuts that can only be cracked with a sledge hammer. Therefore the sledge hammer is stronger than the rubber hammer.

$\endgroup$
  • $\begingroup$ Hmmm, I see. So, it seems like there may be times where I really need to prove "$\forall x \ \epsilon \ A,\ \exists y \ \epsilon \ B, \ P(x,y)$"...but to do so directly is very hard. However, it just so happens in this hypothetical, that " $\exists y \ \epsilon \ B, \ \forall x \ \epsilon \ A, \ P(x,y)$" is much easier to prove. Therefore, I can use this to my advantage and prove this "easier" one...which then gives me access to the statement that I actually wanted. Is that sort of right? $\endgroup$ – S.Cramer Aug 7 at 17:21
  • 1
    $\begingroup$ Not quite. Although this could happen, too, it is rather that if you are trying to prove something with $\exists y \ \epsilon \ B, \ \forall x \ \epsilon \ A, \ P(x,y)$, it might be easier or solve the problem quicker than $\forall x \ \epsilon \ A,\ \exists y \ \epsilon \ B, \ P(x,y)$. So if you are unlucky and only have $\forall x \ \epsilon \ A,\ \exists y \ \epsilon \ B, \ P(x,y)$ (the small hammer) your proof might be harder or take longer than if you had $\exists y \ \epsilon \ B, \ \forall x \ \epsilon \ A, \ P(x,y)$ (the sledge hammer). $\endgroup$ – Klaus Aug 7 at 18:27
2
$\begingroup$

Suppose $$ \exists y\in B,\forall x\in A,P(x,y). $$

Let $x_0\in A$. According to the previous assertion, there exists $y\in B$ such that for all $x\in A$, $P(x,y)$. In particular for $x=x_0$, we have $P(x_0,y)$. We just proved that for all $x_0\in A$, there exists $y\in B$ such that $P(x_0,y)$, which can be rewritten $$ \forall x_0\in a,\exists y\in B,P(x_0,y). $$

Of course you can replace $x_0$ with $x$, which gives $$ \forall x\in A,\exists y\in B,P(x,y). $$

Therefore, $$ \left( \exists y\in B,\exists x\in A,P(x,y)\right)\implies\left(\forall x\in A,\exists y\in B,P(x,y)\right). $$

The left-hand side is stronger in the sense that it implies the right-hand side. If you want to prove the right-hand side, it is succifient to prove the left-hand side, but it is not necessary. If you prove the right-hand side by proving the left-hand side, we consider that you prove a stronger result.

$\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.