Number Transformation Clause Samples

Number Transformation. The proposition n ≤ m asserts that either “n is less than m” or “n is equal to m”; but what exactly does this mean? Clearly, if n and m are equal, the proposition is true in virtue of the right disjunct “n is equal to m”, but what if n and m are not equal? A type-theoretic approach to this problem is to associate the proposition with a type, and to define the type in such a way that the proposition is true if and only if the type is inhabited. So, “type 1 ≤ 1” is inhabited whereas “type 2 ≤ 1” is not. A suitable definition of “type n ≤ m” is given by the following introduction rules. n : Nat (@≤ I1) . n : Nat m : Nat h : n ≤ m (@≤ I2) . @1 n : n ≤ n @2 n m h : n ≤ S m The first rule asserts that @1 n is an object of type n ≤ n, if n is a natural number, so ≤ S m, if n and m are natural numbers, and h is an object (a proof) that n ≤ m. So e.g. 1 ≤ 3 if 1 ≤ 2. Recall that S is the successor function. Using these rules, it is relatively easy to 1Type n ≤ m is actually a dependent type over natural numbers, whose inhabitants vary with n and m so that, for example, the inhabitants of type 1 ≤ 1 differ from those of type 1 ≤ 2. The use of infix notation makes the types easier to read. An alternative notation, which is less readable, is given by ≤ n m, or le n m as in Coq. prove that n ≤ m for some n and m, when n really is less than or equal to m according to these rules, by finding a suitable object that inhabits type n ≤ m.