Valige vasakul üks märksõnadest ...

Sets and functionsLists

Lugemise aeg: ~10 min

Sets are data containers with very little structure: you can check membership (and perform membership-checking-related operations like unions or complements), but that's all. We will define various other types of collections which provide additional structure.

For example, suppose you do care about the order in which the items appear on your grocery list; perhaps because you want to be able pick the items up in a certain order as you move across the store. Also, you might want to list an item multiple times as a way of reminding yourself that you should pick up more than one. Lists can handle both of these extra requirements:

Definition (List)
A list is an ordered collection of finitely many elements.

For example, if we regard \{1,2,3\} and \{2,1,3\} as lists, then they are unequal because the orders in which the elements appear are different. Also, the list \{1,1,2\} has three elements, since repeated elements are not considered redundant.

We don't distinguish sets and lists notationally, so we will rely on context to make it clear whether order matters and repetitions count.

How many sets A have the property that A \subset \{1,2,3\}?

How many lists of length 4 have all of their elements in \{1,2,3\}?

Solution. There are 8 subsets of \{1,2,3\}:

\begin{align*}\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}.\end{align*}

There are 3^4 = 81 length-4 lists with elements in \{1,2,3\}, because the set of such lists is equal to \{1,2,3\} \times \{1,2,3\} \times \{1,2,3\} \times \{1,2,3\}, and the cardinality of a Cartesian product of sets is the product of the cardinalities of the sets.

Bruno Bruno