Sound Rejection Test

Definition

Sound Rejection Test

A sound rejection test for a predicate $P$ on a set $X$ is a sound algorithm

$$A:X\to \{\mathrm{no},\perp \}$$

satisfying

$$\forall x\in X:A(x)=\mathrm{no}⟹\neg P(x).$$

Every rejected instance therefore violates $P$. The test may return $\perp$ for an instance that violates $P$; soundness excludes false rejection, not inconclusive results.