List

A list is an ordered collection of objects, such as 1, 2, 3 or “blue”, 0, “shoe”. Lists are generally denoted by square brackets, with elements separated by commas. Lists allow repetition (unlike sets) and are ordered (unlike bags).

Sometimes lists are typed, in which case they contain only one type of element. For example, 1, 2, 3 is a well-typed list of numbers, whereas the list “blue”, 0, “shoe” is not well-typed (because it contains both numbers and strings). The set of all lists of type \(X\) is usually denoted \([X]\) or \(X^{\le \omega}\), where \(\omega\) is the smallest infinite limit ordinal. The set of all finite lists of type \(X\) is usually denoted \(X^{< \omega}\), and the set of all infinite lists of type \(X\) is usually denoted \(X^{\omega}\).