Simple existence proofs without bounds

Question

Which is/are the most simple proof/s of an existential statement like $$ \exists x P(x) $$ or $$ \forall x \exists y P(x,y) $$ where the variables rage over the integers, such that the proof doesn't provide any information about how far is the number that is claimed to exist in the first case or how far is $y$ as a function of $x$ in the second case.

Answer 1

$\forall x \exists y $ s.t. $y > x$ where $x,y \in \mathbb{N}$

If not then $\mathbb{N}$ has a largest element $\implies$ $\mathbb{N}$ is finite. Q.E.D. by contradiction.

Answer 2

A silly example: given any integer $n$ and a Gödel numbering system, let $\{ n \}$ denote the Turing machine with Gödel number $n$. Let $P(n)$ be the proposition "$\{n\}$ halts on input $0$".

The halting problem is unsolvable, which means that if the Gödel numbering system is horrible, we can't determine which the first index is of a halting machine. We just know that one exists.

---

If you want something on a related question which is not quite the same: Let $P(x)$ be the statement that $x$ is a prime factor of some large fixed semiprime $n$. (That is, $n = pq$ where $p, q$ are prime.)

Then by the Fundamental Theorem of Arithmetic, there is some $x$ which divides $n$, but factoring is thought to be algorithmically a very hard problem. All we really know is that there is some $x$ with $2 \leq x \leq \sqrt{n}$.

This is an example where we have a bound, but no real idea where $x$ lies within that bound.