Theorems · Inductive type · logic and foundations
Primcodable
Type u_1 → Type u_1
A Primcodable type is, essentially, an Encodable type for which
the encode/decode functions are primitive recursive.
However, such a definition is circular.
Instead, we ask that the composition of decode : ℕ → Option α with
encode : Option α → ℕ is primitive recursive. Said composition is
the identity function, restricted to the image of encode.
Thus, in a way, the added requirement ensures that no predicates
can be smuggled in through a cunning choice of the subset of ℕ into
which the type is encoded.
- Defined in
- Mathlib.Computability.Primrec.Basic
- Cited by
- 325 results in Mathlib
- Foundations
- Depth 0 from the axioms, rests on 1 definitions · uses no axioms
Around this declaration
Dashed lines are statement dependencies; solid lines are citations in proofs.
Cites0
Mathlib declarations this one mentions in its statement or cites explicitly in its proof. Plumbing is filtered out.
Nothing in Mathlib beyond the foundations.
Cited by355
Results whose statement or proof uses this declaration.
- Primrecstatement and proof · cited by 141
- Primrec₂statement and proof · cited by 93
- Computablestatement and proof · cited by 80
- Primrec.compstatement and proof · cited by 80
- Primrec.sndstatement and proof · cited by 66
- Primrec.fststatement and proof · cited by 58
- Primrec.conststatement and proof · cited by 57
- Primrec₂.compstatement and proof · cited by 55
- Primrec.of_eqstatement and proof · cited by 50
- Partrecstatement and proof · cited by 48
- Primrec.idstatement and proof · cited by 40
- Primrec.to_compstatement and proof · cited by 40
Showing the 200 most cited of 355.