Combinatory completeness without classical equality (Q1100189)

When equality is an applicative system (M,\(\cdot)\) is replaced by an arbitrary equivalence relation \(\approx\), an algebraic structure \((M,\cdot,\approx)\) results in which it is still possible to discuss combinatory completeness. This structure turns out to be the correct one for unifying such fixed point phenomena as Gödel's diagonal lemma and recursion theorem. The analysis of \((M,\cdot,\approx)\) is applied to illuminate generalized fixed point phenomena, Tarki's theorem, Gödel- Rosser incompleteness and precomplete numerations.