Universal quantifier distributes over implication

1,128

As per this question

No; they are not.

$\forall x\;\forall y\; (P(x)\to Q(y))$ means "for every two things, if one is $P$ then the other is $Q$". Thus if there's is anything that is $P$, then everything is $Q$.

This is equivalent to $(\exists x\; P(x)) \to (\forall y\; Q(y))\;$.

...

On the other flipper, $( \forall x\; P(x) )\to (\forall y\; Q(y))$ means "if every $x$ is $P$ then every $y$ is $Q$."   That is not the same thing.


$$\begin{align} &\forall x\; \forall y\; [P(x) \to Q(y)] \\[1ex] \iff & (\text{implication equivalence}) \\[1ex]&\forall x\;\forall y\; (\neg P(x) \vee Q(y)) \\[1ex] \iff & (y\text{ is free in } P(x)) \\[1ex]&\forall x\; (\neg P(x) \vee (\forall y\; Q(y))) \\[1ex] \iff & (x\text{ is free in }\forall y\;Q(y)) \\[1ex]&(\forall x\; \neg P(x)) \vee (\forall y\; Q(y)) \\[1ex] \iff & (\text{dual negation}) \\[1ex]&(\neg \exists x\; P(x)) \vee (\forall y\; Q(y)) \\[1ex] \iff & (\text{implication equivalence}) \\[1ex]&(\exists x\; P(x)) \to (\forall y\; Q(y)) \end{align}$$

Share:
1,128

Related videos on Youtube

Kyle
Author by

Kyle

Updated on July 24, 2020

Comments

  • Kyle
    Kyle over 3 years

    Is

    $\forall x \forall y: P(x) \to Q(y)$

    the same thing as

    $(\forall x P(x)) \to (\forall y:Q(y))$

    ?

    If not can someone give an example as to why it isn't?

    I'm not getting the whole meaning of $\forall x \forall y:P(x) \to Q(y)$ at all. Does that mean for if $P(x)$ is satisfied, then $Q(y)$ is satisfied for all $y$? Or does it mean that if $P(x)$ is satisfied, then there is some $y$ out there that satisfied $Q(y)$?

    • Kyle
      Kyle over 8 years
      there is no typo. Idk if this helps but P(x) is a predicate on set P which is a subset of the set Q and Q(y) is a predicate for set Q
  • Kyle
    Kyle over 8 years
    so are x and y the same elements of the set? I'm not understanding what $\forall x\forall y (P(x)\to Q(y))$ is saying. If P(x) and Q(y) are both statements on two sets where one is a subset of the other one, then can you make up an example for P and Q? The two universal quantifies are confusing me . Is it saying that for every element in set P that satistys P(x) implies that some element in set Q satisfys Q(y)?
  • David
    David over 8 years
    $P(x)$ is any statement about a variable $x$ and $Q(y)$ is any statement about a variable $y$. Depending on what $P,Q,x$ and $y$ are the statement $P(x)\to Q(y)$, which means "if $P(x)$ is true then $Q(y)$ is true", is either true or false. Take some specific meaning for $P$ and $Q$. The statement $\forall x\forall y (P(x)\to Q(y))$ says that $P(x)\to Q(y)$ is true for all possible choices of $x,y$.
  • Kyle
    Kyle over 8 years
    so if $\forall x\forall y (P(x)\to Q(y))$ is true, then is $\forall x(P(x)) \to \forall y (Q(y))$ also true?
  • David
    David over 8 years
    in your question you didn't say $\forall x(P(x))\to\forall y(Q(y))$, you said $\forall x(P(x))\to\forall y(P(y))$. Please clarify.
  • Kyle
    Kyle over 8 years
    I'm sorry i reread it twice and didn't catch it. I meant $(\forall x P(x)) \to (\forall y:Q(y))$
  • David
    David over 8 years
    See revised answer.
  • Mauro ALLEGRANZA
    Mauro ALLEGRANZA over 8 years
    @Kyle - It may help to "incarnate" David's example into a simple mathematical one. Consider as $P(x)$ : $x=0$ and as $Q(y)$ : $y > 0$ and consider the domain $\mathbb N$ of natural numbers. We have that both $\forall x(x=0)$ and $\forall y(y > 0)$ are false in $\mathbb N$; thus, by truth conditions for $\rightarrow$ : $\forall x(x=0) \rightarrow \forall y(y > 0)$ is true. Consider now $(x = 0) \rightarrow (y > 0)$; for $0$ as value for both $x$ and $y$ we have : $(0 = 0) \rightarrow (0 > 0)$, which is false ($TRUE \rightarrow FALSE$ is $FALSE$). 1/2
  • Mauro ALLEGRANZA
    Mauro ALLEGRANZA over 8 years
    Thus $\forall y[(0=0)→(y>0)]$ is false and also $\forall x \forall y[(x=0)→(y>0)]$ is. Conclusion : the two formulae are not equivalent and thus - as per David's answer - they have not "the same meaning". 2/2