Unsound Algorithm

Definition

Unsound Algorithm

An algorithm $A:X\to Y\cup \{\perp \}$ is unsound with respect to a validity relation $R\subseteq X\times Y$ if it can return a conclusive but incorrect result:

$$\exists x\in X\exists y\in Y:A(x)=y\wedge (x,y)\notin R.$$

For a decision predicate $P$, unsoundness means that at least one false acceptance or false rejection is possible:

$$\exists x\in X:(A(x)=\mathrm{yes}\wedge \neg P(x))\vee (A(x)=\mathrm{no}\wedge P(x)).$$

Returning $\perp$ does not witness unsoundness because an inconclusive algorithm makes no claim about the answer.