Understanding predicates and quantifiers ∀ , ∃ (my reasoning)

Question

So lets say we are trying to figure out if:

P(x, y) is the predicate of $x^2 < y$ as defined for x, y ∈ Z.

This means using quantifiers: ∀ and ∃, I can logically say:

1. ∀x∃y of P(x,y) is possible!

This is because we can say $ y = x^2 + 1 $ which means $ x < x^2 $. This means for every x there is a y.

This also means ∀y∃x of P(x,y) is possible!

There can exist any x that if squared is less than y such as if y was 5 and x was 2 ($2^2 < 5). This means for every y there exists a x.

BUT ∃y∀x of P(x, y) is not possible.

Why?

Because if x becomes $ x=y+1 $ then $y+1^2 > y$. This contradicts our understanding that $ x^2 < y $. There does not exist a y for every x.

Does my explaining of logic seem comprehensive and reasonable?

Answer 1

For the beginning I want to clarify the quantifiers (I am assuming that we are always working in $\mathbb{Z}$):

Let's take a look at $\forall x. A$. Where $A$ is a statement which can be either true or false.

The $\forall x.$ quantifier, says that the following statement has to be true for every possible $x$. If there exists one case for which the statement $A$ is false then the whole $\forall x. A$ is false.

Now let's look at $\exists x. A$. Here $A$ is again a statement which can be either true or false.

The $\exists x$ quantifier, says that the following statement has to be true for at least one $x$. So as long as there exists one $x$ for which $A$ is true then the whole $\exists x. A$ is true. Only if $A$ is false for every single value $x$ then $\exists x. A$ is false.

With that we can now evaluate your statements.

The predicate $P(x, y)$ is true if and only if $x^2<y$ holds.

First Case $\forall x.\exists y.P(x,y)$

Your explanation for the first case $(\forall x.\exists y.P(x,y))$ is correct. For every $x\in\mathbb{R}$ we can just choose $y=x^2+1$ and this is always greater then $x$. Because we can choose this $y$ for every possible $x$ the statement is true.

Here your "$x<x^2$" is strange and I am not really understanding what that should indicate. It would be better to write "... which means $x^2<y$".

Second Case $\forall y.\exists x.P(x,y)$

This case is not true. Changing the variables can have a huge impact on the truth value of your statement. You really have to check the meaning of each statement seperately and then check if the statement really holds for every $y$. What happens if we choose for example $y=0$? Can we choose a $x$ such that $x^2<y$ holds? No we can not. We can see that if we plug the $y=0$ into the equation: $x^2<0$. Now we can simply look at the graph of $x^2$ and we can see that it is never less then $0$.

So the statement $\exists x.P(x,y)$ doesn't hold for every value $y$. For example not for $y=0$. With giving a counter example you have shown that this can't be true. And thus the whole statement $\forall y.\exists x. P(x,y)$ is false.

Third case $\exists y.\forall x. P(x,y)$

Here you have correctly seen that this is false. Choosing $x=a+1$ will not be enough to show that this is wrong. But we can just show it like that:

Let $y=a$. Then $\forall x. P(x,a)$ doesn't hold for $x=a$. Because $a^2<a$, doesn't hold.

You did a good job with seeing that the first case is true and the third case is false. I think you looked at the second case a bit to fast. You really have to look at every case seperately and don't get influenced by the other cases to fast!

Answer 2

1. ∀x∃y of P(x,y) is possible!

This is because we can say $ y = x^2 + 1 $ which means $ x < x^2 $. This means for every x there is a y.

Almost ... when you pick $y = x^2+1$ it is the case that $x^2<y$ since $x^2<x^2+1$ ... But I am not sure what your $x < x^2$ has to with it .. and the latter is not true anyway: $x=0$ is a counterexample. But yes, if you pick $y = x^2+1$ it is the case that $x^2<y$, and so $\forall x \exists y \ P(x,y)$ is indeed true.

This also means ∀y∃x of P(x,y) is possible!

There can exist any x that if squared is less than y such as if y was 5 and x was 2 ($2^2 < 5). This means for every y there exists a x.

Nope. If $y=0$, then it is impossible to pick an $x$ such that $x^2<y$. So, with the interpretation and domain as given, $\forall y \exists x \ P(x,y)$ is false.

BUT ∃y∀x of P(x, y) is not possible.

Because if x becomes $ x=y+1 $ then $y+1^2 > y$. This contradicts our understanding that $ x^2 < y $. There does not exist a y for every x.

You are right that this is false, but your explanation is not quite right. If you pick $x = y+1$, then $x^2 = (y+1)^2 = y^2 + 2y + 1$ ... and while it is true that we never have that $y^2 + 2y + 1 < y$, this is a little harder to show ... . So instead, I would simply pick $x = y$ as a counterexample, since for the integers it is clear that we never have that $x^2<x$.