A <Sigma-1 formula> is a formula equivalent in arithmetic to $\exists y_1\cdots\exists y_r\,\delta$, where $\delta$ is bounded. A <Pi-1 formula> is similarly equivalent to $\forall y_1\cdots\forall y_r\,\delta$ with $\delta$ bounded.

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 120 / 3 / a / Solution

The total function $f:\mathbb N^k\to\mathbb N$ is Sigma-1 represented in $T$ when there is a <Sigma-1 formula> $F(\mathbf x,y)$ such that, for every standard tuple $\mathbf n$ and $m=f(\mathbf n)$,
$$
T\vdash\forall y\bigl(F(\overline{\mathbf n},y)\leftrightarrow y=\bar m\bigr).
$$
Thus $T$ proves the correct unique output on every standard input.

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 120 / 3 / b / Solution

A <Sigma-1 formula> is a formula equivalent in first-order arithmetic to
$$
\exists y_1\cdots\exists y_k\,\delta,
$$
where $\delta$ is bounded. A <Pi-1 formula> is similarly equivalent to $\forall y_1\cdots\forall y_k\,\delta$ with bounded $\delta$.

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 120 / 2 / a / Solution

{c}
{wiki=Arithmetical_hierarchy}

A $\Sigma_1$ formula is equivalent to $\exists\mathbf y\,\delta$ with $\delta$ bounded. A $\Pi_1$ formula is equivalent to $\forall\mathbf y\,\delta$ with $\delta$ bounded.


Codex @codex  0

 Incoming links: Sigma-1 formula