Generic Judgements

Basic judgements express properties of objects of the universe of discourse.

Hypothetical judgements express entailments between judgements, or rea-soning under hypotheses. Generic and parametric judgements express gen-erality with respect to variables and parameters, respectively. Generic judge-ments are given meaning by substitution, whereas parametric judgejudge-ments express uniform dependence on parameters.

4.1 Rule Schemes

An inductive definition consists of a set, R, of rules whose premises and conclusion are judgements involving syntactic objects generated by given sets of parameters and variables. We write Γ )^U_R^;X J to indicate that J is derivable from rulesRand hypotheses Γ over the universeB[U^;X ]^{. Thus,} for example, if a ∈ B[U^;X ], then the judgment a nat ) succ(a) nat is derivable from Rules (1.2) by applying Rule (1.2b) to the hypothesis a nat.

This definition hides a subtle issue of the interpretation of rules. When working over a fixed universe of syntactic objects, one may understand a rule of the form

a nat

succ(a) nat (4.1)

as standing for an infinite set of rules, one for each choice of object a in the universe. However, when considering the same rule over many different universes (for example, by expanding the set of variables), this rough-and-ready interpretation must be refined.

To allow for variation in the universe we regard (4.1) as a rule scheme in which the meta-variable, a, stands for a syntactic object in any expansion

34 4.2 Generic Derivability of the universe. So, for example, if the variable x is adjoined to the set of active variables, then (4.1) has as an instance the rule

x nat

succ(x) nat (4.2)

in which we have taken a to be the parameter, x. If we further adjoin an-other variable, y, then more instances of the rule are possible.

4.2 Generic Derivability

A generic derivability judgement expresses the uniform derivability of a judge-ment with respect to specified parameters and variables. Let us consider first variables, and expand out to accomodate parameters later. The generic derivability judgement!x | ^Γ )^X_R J states that for every fresh renaming π : !x ↔ !^x%, the judgement π·^Γ )^X_R^{,!x% π}·J holds. The renaming ensures that the choice of variables,!x, does not affect the meaning of the judge-ment; variables are simply placeholders that have no intrinsic meaning of their own.

Evidence for a generic derivability judgement!x | ^Γ )^X_R J consists of a generic derivation, ∇!x, such that for every fresh renaming π : !x ↔ !^{x%, the} derivation∇!x^% is evidence for π·^Γ)^X_R^{,!x% π}·J. For example, the derivation

∇xgiven by

x nat succ(x) nat succ(succ(x)) nat is evidence for the generic judgement

x |^{x nat} )^X(1.2)succ(succ(x)) nat.

The generic derivability judgement enjoys the following structural prop-erties:

Proliferation If!x|^Γ)^X_R ^{J, then}!x, x|^Γ)^X_R ^J.

Renaming If!x, x | ^Γ )^X_R ^{J, then}!x, x^% | [^x↔^x%]·^Γ )^X_R [x↔ ^x%]·^{J for any} x^% ∈ X/ ^,!x.

Substitution If!x, x|^Γ)^X_R ^{J and a}∈ B[X^,!x], then!x| [^a/x]Γ)^X_R [a/x]J.

4.3 Generic Inductive Definitions 35 Proliferation is guaranteed by the interpretation of rule schemes as ranging over all expansions of the universe. Renaming is built into the meaning of the generic judgement. Substitution follows from the meaning of a rule scheme, since a substitution instance of a rule instance is itself a rule in-stance.

4.3 Generic Inductive Definitions

A generic inductive definition admits generic hypothetical judgements in the premises of rules, with the effect of augmenting the variables, as well as the rules, within those premises. A generic rule has the form

!x!x₁ |^{Γ Γ}1 ) ^J1 . . . !x!x_n|^{Γ Γ}n) ^Jn

!x|^Γ) ^{J . (4.3)}

The variables!x are the global variables of the inference, and, for each 1≤ⁱ≤ n, the variables!x_i are the local variables of the ith premise. In most cases a rule is stated for all choices of global variables and global hypotheses. Such rules may be given in implicit form,

!x₁|^Γ1 ) ^J1 . . . !xn |^Γn) ^Jn

J . (4.4)

A generic inductive definition is just an ordinary inductive definition of a family of formal generic judgements of the form!x | ^Γ ) J. Formal generic judgements are identified up to renaming of variables, so that the latter judgement is treated as identical to the judgement !x^% | ^π·^Γ ) ^π·^{J for} any renaming π : !x ↔ !^{x%. If} R is a collection of generic rules, we write

!x|^Γ)_R J to mean that the formal generic judgement!x |^Γ ) J is derivable from rulesR^.

When specialized to a collection of generic rules, the principle of rule induction states that to showP(!^x |^Γ ) ^J)whenever!x |^Γ)R J, it is enough to show thatP is closed under the rulesR. Specifically, for each rule inR of the form (4.3), we must show that

ifP(!^x!x₁ |^{Γ Γ}1) ^J1) . . . P(!^x!xn|^{Γ Γ}n ) ^Jn)thenP(!^x |^Γ) ^J). Because of the identification convention the property P must respect re-namings of the variables in a formal generic judgement. It is common to use notations such as P!x(Γ) ^J)or P_!x^Γ(J)or similar variations to indicate thatP holds of the judgement!x |^Γ) ^J.

REVISED03.02.11 DRAFT VERSION1.2

36 4.4 Parametric Derivability To ensure that the formal generic judgement behaves like a generic judgement, we must always ensure that the following structural rules are admissible in any generic inductive definition:

!x|^{Γ, J}) ^{J (4.5a)}

!x|^Γ) ^J

!x|^{Γ, J%} ) ^{J (4.5b)}

!x|^Γ) ^J

!x, x|^Γ) ^{J (4.5c)}

!x, x^% | [^x↔^x%]·^Γ) [^x↔ ^x%]·^J

!x, x|^Γ) ^{J (4.5d)}

!x |^Γ) ^J !x|^{Γ, J}) ^J%

!x|^Γ) ^{J% (4.5e)}

!x, x|^Γ) ^{J a}∈ B[!^x]

!x | [^a/x]Γ) [^a/x]J (4.5f) The admissibility of Rule (4.5a) is, in practice, ensured by explicitly includ-ing it. The admissibility of Rules (4.5b) and (4.5c) is assured if each of the generic rules is uniform, since we may assimilate the additional parameter, x, to the global parameters, and the additional hypothesis, J, to the global hypotheses. The admissibility of Rule (4.5d) is ensured by the identifica-tion convenidentifica-tion for the formal generic judgement. The second premise of Rule (4.5f) is the local form of the requirement that a ∈ B[X^,!x], in which the global variables are made explicit.

4.4 Parametric Derivability

The parametric derivability judgement!u/ !^x|^Γ)^U_R^;X J states that the generic judgement holds uniformly for all choices of parameters!u. That is, for all π:!u↔ !^{u%such that}!u^%∩ U =∅, the generic judgement!x|^π·^Γ )^U_R^{,!u%;X π}·^J is derivable.

The parametric judgement satisfies the following structural properties:

Proliferation If!u/ !^x |^Γ)^U_R^{;X J, then}!u, u/ !^x|^Γ)^U_R^{;X J.}

Renaming If!u/ !^x|^Γ)^U_R^{;X J and π :}!u↔ !^{u%, then}!u^% / !^x|π·^Γ)^U_R^;X π·^J.

4.5 Exercises 37 Proliferation states that parametric derivability is sensitive only to the pres-ence, but not the abspres-ence, of parameters. Renaming states that parametric derivability is independent of the choice of parameters. (There is no ana-logue of the structural property of substitution for parameters.)

We may also extend the concept of a generic inductive definition to al-low for local parameters, as well as local variables. To do so, rules are defined on formal parametric judgements of the form!u / !^x | ^Γ ) ^{J, with} parameters!u, as well as variables,!x. Such formal judgements are identi-fied up to renaming of both its parameters and its variables to ensure that the meaning is independent of the choice of names. Usually we segregate the hypotheses into two zones, written!u/ !^x|^{Σ Γ}) J, where Σ governs the parameters,!u, and Γ governs the variables,!x. Once separated into zones, it is natural to write this judgement in the form!x | ^Γ )!u/^Σ J, or even just Γ)Σ J, to reduce notational clutter.

4.5 Exercises

REVISED03.02.11 DRAFT VERSION1.2

38 4.5 Exercises

Part II