Laboratoire de l'Informatique et du Parallélisme » Linear Arithmetic

\section{Soundness}

\label{sect:soundness}

The main result of this section is the following:

\begin{theorem}

	If $\arith^i$ proves $\forall \vec u^\normal . \forall \vec x^\safe . \exists y^\safe . A(\vec u ; \vec x , y)$ then there is a $\mubci{i-1}$ program $f(\vec u ; \vec x)$ such that $\Nat \models A(\vec u ; \vec x , f(\vec u ; \vec x))$.

\end{theorem}

The main problem for soundness is that we have predicates, for example equality, that take safe arguments in our theory but do not formally satisfy the polychecking lemma for $\mubc$ functions.

For this we will use length-bounded witnessing, borrowing a similar idea from Bellantoni's previous work \cite{Bellantoni95}.

\begin{definition}

[Length bounded basic functions]

We define \emph{length-bounded equality}, $\eq(l;x,y)$ as the characteristic function of the predicate:

\[

x \mode l = y \mode l

\]

\end{definition}

\anupam{Do we need the general form of length-boundedness? E.g. the $*$ functions from Bellantoni's paper? Put above if necessary. Otherwise just add sequence manipulation functions as necessary.}

Notice that $\eq$ is a polymax bounded polyomial checking function on its normal input, and so can be added to $\mubc$ without problems.

\begin{definition}

	[Length bounded characteristic functions]

	We define $\mubci{}$ programs $\charfn{}{A} (l , \vec u; \vec x)$, parametrised by a formula $A(\vec u ; \vec x)$, as follows.

%	If $A$ is a $\Pi_{i}$ formula then:

	\[

	\begin{array}{rcl}

	\charfn{}{s\leq t} (l, \vec u ; \vec x, w) & \dfn & \leqfn(;s,t) \\

	\smallskip

	\charfn{}{s=t} (l, \vec u ; \vec x, w) & \dfn & \eq(;s,t) \\

	\smallskip

	\charfn{}{\neg A} (l, \vec u ; \vec x, w) & \dfn & \neg (;\charfn{}{A}(l , \vec u ; \vec x)) \\

	\smallskip

	\charfn{}{A\cor B} (l, \vec u ; \vec x , w) & \dfn & \cor (; \charfn{}{A} (l, \vec u ; \vec x , w), \charfn{}{B} (\vec u ;\vec x, w) ) \\

	\smallskip

	\charfn{}{A\cand B} (l, \vec u ; \vec x , w) & \dfn & \cand(; \charfn{}{A} (l, \vec u ; \vec x , w), \charfn{}{B} (\vec u ;\vec x, w) ) \\

	\smallskip

	\charfn{}{\exists x^\safe . A(x)} (l, \vec u ;\vec x,  w) & \dfn & \begin{cases}

	1 & \exists x^\safe . \charfn{}{A(x)} (l, \vec u ;\vec x , x, w) = 1 \\

	0 & \text{otherwise}

	\end{cases} \\

	\smallskip

	\charfn{\vec u; \vec x}{\forall x^\safe . A(x)} (l, \vec u ;\vec x , w) & \dfn &

	\begin{cases}

	0 & \exists x^\sigma. \charfn{}{ A(x)} (l, \vec u; \vec x , x) = 0 \\

	1 & \text{otherwise}

	\end{cases}

	\end{array}

	\]

\end{definition}

\begin{definition}

	[Length bounded witness function]

	We now define $\Wit{\vec u ; \vec x}{A} (l , \vec u ; \vec x)$ for a $\Sigma_{i+1}$-formula $A$ with free variables amongst $\vec u; \vec x$.

	\[

	\begin{array}{rcl}

	\Wit{\vec u ; \vec x}{A} (l, \vec u ; \vec x , w) & \dfn & \charfn{}{A} (l, \vec u ; \vec x)  \text{ if $A$ is $\Pi_i$} \\

	\smallskip

	\Wit{\vec u ; \vec x}{A \cor B} (l,\vec u ; \vec x , \vec w^A , \vec w^B) & \dfn & \cor ( ; \Wit{\vec u ; \vec x}{A} (l,\vec u ; \vec x , \vec w^A) ,\Wit{\vec u ; \vec x}{B} (l,\vec u ; \vec x , \vec w^B)  )  \\

	\smallskip

	\Wit{\vec u ; \vec x}{A \cand B} (l,\vec u ; \vec x , \vec w^A , \vec w^B) & \dfn & \cand ( ; \Wit{\vec u ; \vec x}{A} (l,\vec u ; \vec x , \vec w^A) ,\Wit{\vec u ; \vec x}{B} (l,\vec u ; \vec x , \vec w^B)  )  \\

	\smallskip

	\Wit{\vec u ; \vec x}{\exists x^\safe . A(x)} (l,\vec u ; \vec x , \vec w , w) & \dfn & \Wit{\vec u ; \vec x , x}{A(x)} ( l,\vec u ; \vec x , w , \vec w )

	\\

	\smallskip

	\Wit{\vec u ; \vec x}{\forall u \leq |t(\vec u;)| . A(x)} (l , \vec u ; \vec x, w) & \dfn &

	\forall u \leq |t(\vec u;)| . \Wit{u , \vec u ; \vec x}{A(u)} (l, u , \vec u ; \vec x, \beta(u;w) )

	\end{array}

	\]

\end{definition}

\anupam{may as well use a single witness variable since need it for sharply bounded quantifiers anyway.}

\anupam{sharply bounded case obtained by sharply bounded lemma}