Uniform preorders are a class of combinatorial representations of Set-indexed preorders that generalize Hofstra's basic relational objects. An indexed preorder is representable by a uniform preorder if and only if it has a generic predicate. We study the ∃-completion of indexed preorders on the level of uniform preorders, and identify a combinatory condition (called `relational completeness') which characterizes those uniform preorders with finite meets whose ∃-completions are triposes. The class of triposes obtained this way contains relative realizability triposes, for which we derive a characterization as a fibrational analogue of the characterization of realizability toposes given in earlier work by the author. Besides relative partial combinatory algebras, the class of relationally complete uniform preorders contains filtered ordered partial combinatory algebras, and it is unclear if there are any others.
Keywords: realizability, tripos, partial combinatory algebra, cocompletion, uniform preorder, indexed preorder
2020 MSC: 03G30,03B40,18D30
Theory and Applications of Categories, Vol. 45, 2026, No. 4, pp 151-175.
Published 2026-01-16.
TAC Home