Propositionvalued

Proposition-valued describes expressions, predicates, or functions whose results are propositions rather than concrete data types or boolean values. In logic and type theory, a proposition-valued expression yields a statement that can be true or false within a formal system, and often carries a proof object when treated constructively.

In dependent type theory and proof assistants such as Coq or Lean, many predicates have codomains in a universe of propositions (for example Prop). A function f: A -> Prop is called proposition-valued because, for each input a in A, it specifies a proposition about a. This contrasts with boolean-valued predicates, which return true or false directly. The proposition-valued form aligns with the Curry-Howard correspondence, where proofs are terms of the corresponding proposition.

Proposition-valued predicates are widely used to express properties, invariants, and theorems in formal specifications. Examples include is_prime(n): Nat -> Prop, has_length(xs): List T -> Nat -> Prop, or belongs_to_set(x, S): α -> Prop. These allow formal reasoning about all inputs, with proofs contributing to the constructive content of a theory.

Semantically, proposition-valued expressions are closed under logical connectives and quantifiers, enabling compositional reasoning. They are particularly important in environments that separate computation from proof, since proofs (terms of type P) can often be manipulated without affecting computational content.

See also: predicate, predicate logic, dependent type theory, Curry-Howard correspondence, Prop (in proof assistants).