Sets, multisets, lists and tuples

We assume familiarity with sets, multisets, lists and tuples.

Sets

A set is an unordered collection of distinct objects. For example, consider the set {1,3,5}. Another example is the set of natural numbers {0,1,...}. In our case, most sets are finite.

In general, we write {x_1,....,x_n} to denote a set of n elements where x_i refers to some element in the set. We write {} to denote the empty set.

The order among elements in a set does not matter. We consider the sets {x_1,....,x_n} and {x_n,....,x_1} equivalent.

We write x in A to denote that x is an element in the set A.

We write A cup B to denote the union of two sets. We have that x in A cup B if x in A or x in B. For example, {1,3,5} cup {3,6,7} equals {1,3,5,6,7}. Keep in mind that a set is a collection of distinct objects. This means that duplicates are removed.

We write A cap B to denote the intersection of two sets. We have that x in A cap B if x in A and x in B. For example, {1,3,5} cup {3,6,7} equals {1,3,5,6,7}.

We write A - B to denote set difference. We have that x in A - B if x in A and x not in B. For example, {1,3,5} - {3,6,7} equals {1,5}.

Set A is a subset of set B, written A subset B, if for each x in A we have that x in B.

Multisets

A multiset is an unordered collection of objects. For example, consider the multiset {{1,3,5, 5}}. The difference to sets is that duplicates are allowed.

Lists

A list is an ordered collection of objects. We write [x_1,....,x_n] to denote a set of n elements where x_i refers to i-th element in the list. We write [] to denote the empty set.

We write x:xs to refer to a non-empty list where x refers to the head element and xs to the tail.

For example, the list [1,2,3] can be equivalently represented as 1:[2,3].

We write l1 + l2 to refer to the concatenation of two lists. We have that [x_1,....,x_n] + [y_1,....,y_m] equals the list [x_1,....,x_n, y_1,....,y_m].

Tuples

A tuple is an ordered collection of objects. Unlike lists (that can grow and shrink), tuples are always of a fixed length. For example, consider the tuple (1,2,3).

We will often use combinations of lists, tuples etc. For example, consider the tuple (1,[2,3]) where the first component holds the number 1 and the second component holds the list [2,3].

First-order logic

We assume familiarity with propositional and first-order logic.

Ordering relations

We assume familiarity with total and partial ordering relations.