. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Expressions 11 3.1 Universes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5 Other Commands 37 5.1 Universes and Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Reference Manual, Release 3.3.0 10 Chapter 2. Lexical Structure CHAPTER THREE EXPRESSIONS 3.1 Universes Every type in Lean is, by definition, an expression of type Sort u for some universe level u. A

type theory known as the Calculus of Constructions, with a countable hierarchy of non-cumulative universes and inductive types. By the end of this chapter, you will understand much of what this means. 2 discuss Prop in the next chapter. We want some operations, however, to be polymorphic over type universes. For example, list α should make sense for any type α, no matter which type universe α lives in also just syntactic sugar for Sort (u+1). Prop has some special features, but like the other type universes, it is closed under the arrow constructor: if we have p q : Prop, then p → q : Prop. There are

Predicate . . . . . . . . . 164 IV Mathematics 165 11 Logical Foundations of Mathematics 167 11.1 Universes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 11.2 The Peculiarities type of nat.succ is N → N, whose type is Type. Types of types, such as Type and Prop, are called universes. We will study them more closely in Chapter 11. Regrettably, the intuitive syntax (x : σ) → τ used type ���� N : Type : · · · true.intro � �� � proof : true � �� � proposition : Prop : · · · universes types terms According to the broad senses, any expression is a term, any expression that may

(id2 : Π α : Type, α → α) In the next section, we will see that Lean supports a hierarchy of type universes, so that the following definition of the identity function is more general: universe u def id {α of the Calculus of Inductive Constructions implemented by Lean, we start with a sequence of type universes, Sort 0, Sort 1, Sort 2, Sort 3, … The universe Sort 0 is called Prop and has special properties notation Type is shorthand for Type 0, which is a shorthand for Sort 1. In addition to the type universes, the Calculus of Inductive Constructions provides two means of forming new types: • pi types •

(id2 : Π α : Type, α → α) In the next section, we will see that Lean supports a hierarchy of type universes, so that the following definition of the identity function is more general: universe u def id {α of the Calculus of Inductive Constructions implemented by Lean, we start with a sequence of type universes, Sort 0, Sort 1, Sort 2, Sort 3, … The universe Sort 0 is called Prop and has special properties notation Type is shorthand for Type 0, which is a shorthand for Sort 1. In addition to the type universes, the Calculus of Inductive Constructions provides two means of forming new types: • pi types •

an explanation of all options using help options. pp.implicit : display implicit arguments pp.universes : display universe variables pp.coercions : show coercions pp.notation : display output using defined