Playground Documentation Challenges Full Docs

type

Declaring new types

Overview

The type(...) command declares new primary types. Types are the foundation of Formall's type system.

type(typeName)type(typeName1, typeName2, typeName3)type(enumTypeName = valueAtomName1 | valueAtomName2 | valueAtomName3) // enumerated typetype("'typeVariableName") // a type variable: atoms with it in their type are polymorphic
typeName1, …
Names of new types. Inside a theorem (a block whose statements are called elsewhere) a declared type is a parameter: a call substitutes another type for it.
enumTypeName = value1 | …
An enumeration: the type and its values (atoms of that type), every two different, every element one of them. The declaration generates the axiom schemes of distinct values and of cases that decide, cases and the lemma contradict of the library rest on; a label on the declaration holds them (+ColorSchemas: type(Color = red | green)), to pass to a call.
"'typeVariableName"
A type variable (a name starting with '): an atom whose type contains it is polymorphic, a statement with it is a schema; each use instantiates it.

Command Properties

Group
Context
Produces
Nothing for a plain type; an enumeration generates the axiom schemes of distinct values and of cases
Delivery & Label
A label on type holds the schemes of an enumeration (+ColorSchemas: type(Color = red | green)), to pass to a call.
Creates scope
Yes.
Mechanism
Declares the types in its scope; inside a theorem a declared type is a parameter that a call substitutes. An enumeration also declares its values as atoms of the type.

Basic examples

Type names can use mathematical Unicode symbols:

Declaring types

▶ Run

Enumerated types

type(T = c1 | c2 | … | cn) declares the type T and its values: atoms c1 … cn of type T. They are constants, not parameters of theorems. Two rules come with the declaration:

  • distinct values — two values of one expression give anything: from X -> ci and X -> cj follows every a -> b (Distinct);
  • exhaustion — the type has no other elements: what follows from each value of X follows (Cases).

For a function between two enumerated types that takes every value once (a grid puzzle), see rule("bijective"). In Lean this is inductive Color | red | yellow | green, in Isabelle datatype.

What the declaration writes

The rules are not built into the interpreter. The declaration writes them as text of the language: a lock under the declaring block, one axiom per rule, and the code after the declaration lies inside that lock. For +Abool: type(bool = false | true) the text is this (names with a dot are internal, '𝓐 is the type of «anything»):

for (𝓨: bool; 𝓪, 𝓫: '𝓐) {
	// Distinct: two values of one 𝓨 give anything
	+𝓟: lock() { axiom(𝓨 -> false; 𝓨 -> true | 𝓟); bool.Distinct.false.true: axiom(𝓪 -> 𝓫 | bool.Enumeration); }
	// Cases: what follows from each value follows
	+𝓒: lock() {
		if (𝓨 -> false) axiom(𝓪 -> 𝓫 | 𝓒);
		if (𝓨 -> true) axiom(𝓪 -> 𝓫 | 𝓒);
		bool.Cases: axiom(𝓪 -> 𝓫 | bool.Enumeration);
	}
}
// Flip, for two values only: a lemma, not an axiom. If 𝓨 -> true follows from 𝓨 -> false, then 𝓨 -> true.
// Proved by Cases: the case false is the premise, the case true is its own hypothesis.
for (𝓨: bool) +𝓟: lock() { +𝓡0, +𝓡1; if (𝓨 -> false) 𝓡0: axiom(𝓨 -> true | 𝓟); 𝓡1: if (𝓨 -> true) {} bool.Flip.false.true: bool.Cases[𝓨 := 𝓨, 𝓪 := 𝓨, 𝓫 := true | 𝓡0, 𝓡1]; }
for (𝓨: bool) +𝓟: lock() { +𝓡0, +𝓡1; 𝓡0: if (𝓨 -> false) {} if (𝓨 -> true) 𝓡1: axiom(𝓨 -> false | 𝓟); bool.Flip.true.false: bool.Cases[𝓨 := 𝓨, 𝓪 := 𝓨, 𝓫 := false | 𝓡0, 𝓡1]; }

With three values there are three Distinct axioms (one per pair), a Cases axiom with three branches, and no Flip. The label on the declaration (Abool) holds all of them. A call Abool[…] tries each one; the ones whose conditions and lock do not fit are skipped (the log says which), the one that fits is applied. The kernel sees only these axioms: it has no rule for enumerations.

Why contradict works

The library proves the contradiction lemma from these axioms in one line (logic/bool.fl, here with false/true for ❌/✔):

+L: lock() if (P -> true) { +AX: axiom(X -> false; X -> true | L); contradict: Abool[| Abool[_, P, false | AX]]; }

Read it from the inside out:

  1. Abool[_, P, false | AX] — the values are 𝓪 := P, 𝓫 := false; 𝓨 is left to the realization. AX holds X -> false and X -> true: exactly the two axioms of the lock 𝓟 of Distinct, so 𝓨 := X. Of the four schemas only Distinct fits. Result: P -> false — inside if (P -> true), from the contradiction (ex falso).
  2. Abool[| …] — no values written; the proof after the bar is P -> false under if (P -> true). Flip.true.false has exactly this lock axiom: if (𝓨 -> true) 𝓨 -> false. The call takes the if block as its realization, with 𝓨 := P, and stands above it: P -> false outside the if, inside the lock L.
  3. The label contradict catches it there. The lemma says: for any P, X, if under if (P -> true) both X -> false and X -> true hold, then P -> false. The two axioms of L are what a user must show.

So if (Q -> true) contradict[| )>] works like this: the proof after the bar gives not(Q) -> false, the fact not(Q) -> true is visible, together they realize the lock of contradict with X := not(Q); the call takes the if and delivers Q -> false above it. The second half of the lemma (contradict+, under if (P -> false)) gives P -> true the same way through Flip.false.true.

The schemas by hand, and contradict from them

The same text as the declaration writes, with readable names and without the second Flip. The three lines of contradict are the three steps above. A three-colour version is in Leaving a Block.

▶ Run

Working with the values

The booleans are the case of two values: refuting one value gives the other, so a case split is a branch if (P -> false) and the same step after it (decide). refute of logic/equality.fl turns x = c -> false into a refutation of x -> c the same way. Two values of an expression of any type contradict too, without an enumeration: the fact a = b -> false says they differ, and distinct[_, a, b | A, B] of the same file closes the assumption (A, B hold X -> a and X -> b). Over more values decide finds the value of an expression from the facts and the tables of the functions; its lemma is a call of Cases with a refutation by Distinct in each branch.

Exhaustion by elimination

decide tries the three values: stop(red) -> true and stop(yellow) -> true contradict the fact, so the signal is green.

▶ Run

Subtypes

A subtype makes a new type out of a part of an old one: the type and its embedding are declared as usual, and subtype states that the embedding is a one-to-one map onto the elements with the property:

type(ℝ⁺) for(ι: [ℝ⁺ -> ℝ]) +Sub: subtype(ι, {x: ℝ | 0 < x}, ∃, ⇒);

The elements of ℝ⁺ are then exactly the positive reals, through ι. This is typedef in Isabelle/HOL and Subtype in Lean. A subtype is how a structure built inside another one — positive reals inside ℝ, natural numbers inside ℝ, real numbers as sets — becomes a type to which a theory can be applied with import with substitution.

What «true» means here. subtype(ι, φ, ∃, ⇒) takes an embedding ι: [S -> T] declared before it, a property φ: [T -> 𝔹] — a name or a set {x: T | …} — and the existential quantifier and the implication its premises are written with. The property is an expression of the truth type (𝔹), and the subtype does not evaluate it: «y has the property» is a statement φ[y] -> ✔ to be proved like any other. The value of truth and the other notions come from the theorems named at the command: ∀ from notation("apply" | A∀Apply), = and ✔ from notation("hint" | A=Rewrite, …); the quantifiers and the equality must be polymorphic ('α, as in the library), so that they speak about the new type too. The set may be empty. The command introduces no names; it writes three premises, and a label on it receives them:

StatementMeaning
S1∀{u: S | φ[ι(u)]} -> ✔the embedding lands in the set
S2∀{u, w: S | ι(u) = ι(w) ⇒ u = w} -> ✔the embedding is injective
S3∀{y: T | φ[y] ⇒ ∃{u: S | ι(u) = y}} -> ✔every element of the set is an image

So a property is proved for an element of the subtype by S1, an element of the subtype is obtained from an element with the property by S3, and equality in the subtype is decided by its images in T (S2). Applied to a label with the three statements, a call uses those that fit its arguments: Sub[a] with a: S gives S1 and S2, Sub[y] with y: T gives S3. Operations on the subtype are defined with define from unique existence (the value of a ⊙ b is the element whose image is ι(a) × ι(b)).

Nothing is trusted here. subtype is a generator, like decide: it writes what could be written by hand. S is a type parameter of the type block, the embedding a parameter of the for block, and S1–S3 are the axioms of a lock under the command; the code after it continues inside the lock. The embedding is an ordinary atom of for: a constant defined under it takes it as an argument, as it takes the other atoms of the block. A theorem proved there holds for every type and embedding satisfying S1–S3, so nothing new follows about the old notions. An interpretation of a theory with a subtype realizes S1–S3 by the subtype of its own copy.

A subtype may be empty

No proof of nonemptiness is needed: any Formall type may be empty. A variable introduced by for is hypothetical, so a contradiction under it cannot be moved outside its scope (a contradiction closes the assumption it stands under, not a for), and S1–S3 are hypotheses of the subtype's lock. If no element satisfies φ, the subtype is an empty type: an element u of it would give φ[ι(u)] and a contradiction, but only for that u, so nothing new follows about T. Nonemptiness is assumed or proved exactly where a proof needs an element.

A result about T proved through a subtype leaves the subtype's block with a model of it (a type and an embedding satisfying S1–S3): Leaving a Block.

The embeddings of nested subtypes compose to give an embedding of the inner type into the original one; they do not automatically supply operations or prove the axioms of a mathematical theory.

A function with a restricted domain does not always need a subtype. A predicate D: [T -> 𝔹] can restrict statements to arguments satisfying D(x), including an empty domain. If a separate domain type is useful, declare the subtype. A limit at a point needs a stronger condition for uniqueness: every punctured neighborhood of that point must contain a domain element.

Even numbers as a type

The subtype declaration supplies an embedding into the original type, membership in the defining set, injectivity of that embedding, and a preimage for every element of the set.

▶ Run

Scoping

Types are scoped to the block of their type command:

Type scoping

▶ Run
ℹ
Unlike dependent type systems, Formall types are simple — no type constructors or type families. For complex structures, use predicates.