Stuck in determining truth value using proof

Question

I need your advice/help regarding these questions.

Q. Let p(x,y) denotes the predicate x divides y. Determine truth value of each statement and give an example or a counter-example for the statements.

1) ∀x ∃y p(x,y)
A. I guess it is true, but I'm basically having difficulty in understanding how is it true?

My logic says that for example if we suppose x = 3 and y = 15 then y =15 can be divided by this x =3 and also x = 5 so it is true. But confusion is how this covers every x (How every x can divide y?)

2) ∀y ∃x p(x,y)
This looks false, but how?

3) ∃x ∀y p(x,y)
A. ?

4) ∃y ∀x p(x,y)
A.
?

I would appreciate if someone helps me in these questions. I'm basically struggling the in the concept of For all x and for some y here in such questions.

EDIT: For Q.4 Answer:
(0 | 0 and 1 | 0 and 2 | 0 and 3 | 0 and 4 | 0 .....)
----------------OR----------------------------
(0 | 1 and 1 | 1 and 2 | 1 and 3 | 1 and 4 | 1 .....)
--------------------OR---------------------------
(0 | 2 and 1 | 2 and 2 | 2 and 3 | 2 and 4 | 2 .....)

So, First Row is False as 0 | 0 is false and similarly second and third row is also false so it makes the whole statement false.

Answer 1

$$ \newcommand{\and} {~\text{and}~} \newcommand{\or} {~~\text{or}~~} \newcommand{\undef} {~~\text{undefined}~~}$$

Write the statements without quantifiers. I'll be using $x|y$ to indicate that $x$ divides $y$, that is, that $y$ is divisible by $x$:

1) $$\forall x \exists y ~ p(x,y) $$

$$\begin{array} {c} (0|0 \or 0|1 \or 0|2 \or 0|3 \dots )\\ \and \\ (1|0 \or 1|1 \or 1|2 \or 1|3 \dots )\\ \and \\ (2|0 \or 2|1 \or 2|2 \or 2|3 \dots )\\ \and \\ \vdots \\ \end{array}$$

Division by zero is undefined. Otherwise, each horizontal line has an expression of the form $n|n$ (the second line has $1|1$, the third has $2|2$, etc). So the expression is:

$$\begin{array} {c} (\undef \or \undef \or \undef \or \undef \dots )\\ \and \\ (1|0 \or \top \or 1|2 \or 1|3 \dots )\\ \and \\ (2|0 \or 2|1 \or \top \or 2|3 \dots )\\ \and \\ \vdots \\ \end{array}$$

which is

$$\undef \and \top \and \top \dots$$

So the entire expression is undefined.

2) $$\forall y \exists x ~ p(x,y) $$

$$\begin{array} {c} (0|0 \or 1|0 \or 2|0 \or 3|0 \dots )\\ \and \\ (0|1 \or 1|1 \or 2|1 \or 3|1 \dots )\\ \and \\ (0|2 \or 1|2 \or 2|2 \or 3|2 \dots )\\ \and \\ \vdots \\ \end{array}$$

Although division by zero is undefined, zero is divisible by everything (as $0/x$ is always an integer, $0$). Otherwise everything is divisible by itself:

$$\begin{array} {c} (\undef \or \top \or \top \or \top \dots )\\ \and \\ (\undef \or \top \or 2|1 \or 3|1 \dots )\\ \and \\ (\undef \or 1|2 \or \top \or 3|2 \dots )\\ \and \\ \vdots \\ \end{array}$$

which is:

$$\top \land \top \land \top \dots$$

which is true.

3) $$\exists x \forall y ~ p(x,y) $$

$$\begin{array} {c} (0|0 \and 0|1 \and 0|2 \and 0|3 \and 0|4 \dots )\\ \or \\ (1|0 \and 1|1 \and 1|2 \and 1|3 \and 1|4 \dots )\\ \or \\ (2|0 \and 2|1 \and 2|2 \and 2|3 \and 2|4 \dots )\\ \or \\ (3|0 \and 3|1 \and 3|2 \and 3|3 \and 3|4 \dots )\\ \or \\ \vdots \\ \end{array}$$

This time we look at how $n$ never divides $n + 1$, except when $n=1$, because $1$ divides everything:

$$\begin{array} {c} (\undef \and \undef \and \undef \and \undef \and \undef \dots )\\ \or \\ (\top \and \top \and \top \and \top \and \top \dots )\\ \or \\ (2|0 \and 2|1 \and 2|2 \and \bot \and 2|4 \dots )\\ \or \\ (3|0 \and 3|1 \and 3|2 \and 3|3 \and \bot \dots )\\ \or \\ \vdots \\ \end{array}$$

Which is:

$$\undef \or \top \or \bot \or \bot \dots$$

which is true. That one is pretty complicated.

4) $$\exists y \forall x ~ p(x,y) $$

Can you do this one?

Answer 2

I think what you need most is a translation (from math into English).

1) For each given $x$ there exists a $y$ such that $x|y$ (try to find one).

2) For each given $y$ there exists an $x$ such that $x|y$ (try to find one).

3) There exists a value of $x$ that satisfies $x|y$ for each given $y$.

4) There exists a value of $y$ that satisfies $x|y$ for each given $x$.