Finding Truth Values Of Nested Quantifiers

Question

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that $(x≥y+1)$ is true for every $y∈Y$.

So I can just chose a value of $x$ (one at random) and see if $(x≥y+1)$ evaluates to true for every $y∈Y$?

Example; $x$ and $y$ are sets of positive integers if I chose to make $x=1$ and start from say $y=1$ It would be $(1≥1+1)$ this is true, awesome. now I can make $y=2$ lets see if it's ok $(1≥2+1)$. this is true. I think now $x$ being $1$ and $y$ going on until it's the end of it's set will always evaluate to true.

knowing the information above I can see that $∃x∀y,P(x≥y+1)$ is true?

Answer 1

You want to prove:

$\exists x \forall y(x \geq y + 1)$, i.e., that there is an $x$ that is greater than or equal to the successor of every $y$.

Assuming that $x,y$ range over nonnegative integers, then you can't prove it:

Fact. There is no $x \in \mathbb N$ s.t. $x \geq y + 1$ for all $y \in \mathbb N$.

Proof. We want to prove: $\lnot\exists x \forall y(x \geq y + 1) \equiv\forall x \exists y(x \leq y + 1)$. Let $\varphi(x) \equiv \exists y(x \leq y + 1)$. The property holds for $0$; let $y := 0$, obtaining $0 \leq 0 + 1 \leq 1$. Our inductive hypothesis is that $\varphi(n) \equiv \exists y(n \leq y + 1)$ is true; we want to derive $\varphi(n+1)$. Suppose, for contradiction, that $\varphi(n+1)$ is false, i.e., that $\lnot\exists z(n+1 \leq z + 1) \equiv \forall z(n + 1 > z + 1)$. Since successor is order-preserving, it'll suffice to reduce $\forall z(n > z)$ to absurdity. Instantiate that with $y + 1$ for $z$ to get: $n > y + 1$. That contradicts the inductive hypothesis, so $\varphi(n + 1)$ must be true. Since propoerty $\varphi(x)$ holds for $0$ and is closed under succession, it holds for all natural numbers.

The fact is trivial, but as Mauro said, your approach is wrong, so take the proof above as an illustration of how you might go about actually proving properties of natural numbers by induction.