List

A list is an or­dered col­lec­tion of ob­jects, such as 1, 2, 3 or “blue”, 0, “shoe”. Lists are gen­er­ally de­noted by square brack­ets, with el­e­ments sep­a­rated by com­mas. Lists al­low rep­e­ti­tion (un­like sets) and are or­dered (un­like bags).

Some­times lists are typed, in which case they con­tain only one type of el­e­ment. For ex­am­ple, 1, 2, 3 is a well-typed list of num­bers, whereas the list “blue”, 0, “shoe” is not well-typed (be­cause it con­tains both num­bers and strings). The set of all lists of type \(X\) is usu­ally de­noted \([X]\) or \(X^{\le \omega}\), where \(\omega\) is the small­est in­finite limit or­di­nal. The set of all finite lists of type \(X\) is usu­ally de­noted \(X^{< \omega}\), and the set of all in­finite lists of type \(X\) is usu­ally de­noted \(X^{\omega}\).