# 10   Analyzing the Meaning of Sentences (Extras)

## 10.1   Sets and Mathematical Functions

### Sets

A set is a collection of entities, called the members of the set. Sets can be finite or infinite, or even empty. In Python, we can define a set just by listing its members; the notation is similar to specifying a list:

 ```>>> set1 = set(['a', 'b', 1, 2, 3]) >>> set1 set(['a', 1, 2, 'b', 3])```

In mathematical notation, we would specify this set as:

 (1) {'a', 'b', 1, 2, 3}

Set membership is a relation — we can ask whether some entity x belongs to a set A (in mathematical notation, written xA).

 ```>>> 'a' in set1 True >>> 'c' in set1 False```

However, sets differ from lists in that they are unordered collections. Two sets are equal if and only if they have exactly the same members:

 ```>>> set2 = set([3, 2, 1, 'b', 'a']) >>> set1 == set2 True```
 ```>>> len(set1) 5```

The argument to the set() constructor can be any sequence, including a string, and just calling the constructor with no argument creates the empty set (written ∅).

 ```>>> set('123') set(['1', '3', '2']) >>> a = set() >>> b = set() >>> a == b True```
 ```>>> odds = set('13579') >>> evens = set('02468') >>> numbers = odds | evens >>> numbers set(['1', '0', '3', '2', '5', '4', '7', '6', '9', '8'])```
 ```>>> ints set(['1', '0', '2', '-1', '-2']) >>> ints & nats set(['1', '0', '2']) >>> odds & evens set([])```
 ```>>> nats - ints set(['3', '5', '4', '7', '6', '9', '8']) >>> odds == nats - evens True >>> odds == odds - set() True```

So far, we have described how to define 'basic' sets and how to form new sets out of those basic ones. All the basic sets have been specified by listing all their members. Often we want to specify set membership more succinctly:

 (2) the set of positive integers less than 10

 (3) the set of people in Melbourne with red hair

 (4) {x | x is a positive integer less than 10}

 (5) {x | x is a person in Melbourne with red hair}

In axiomatic set theory, the axiom schema of comprehension states that given a one-place predicate P, there is set A such that for all x, x belongs to A if and only if (written ≡) P(x) is true:

 (6) ∃A∀x.(x ∈ A ≡ P(x))

From a computational point of view, (6) is problematic: we have to treat sets as finite objects in the computer, but there is nothing to stop us defining infinite sets using comprehension. Now, there is a variant of (6), called the axiom of restricted comprehension, that allows us to specify a set A with a predicate P so long as we only consider xs which belong to some already defined set B:

 (7) ∀B ∃A∀x. (x ∈ A ≡ x ∈ B ∧ P(x))

(For all sets B there is a set A such that for all x, x belongs to A if and only if x belongs to B and P(x) is true.) This is equivalent to the following set in predicate notation:

 (8) {x | x ∈ B ∧ P(x))

(7) corresponds pretty much to what we get with list comprehension in Python: if you already have a list, then you can define a new list in terms of the old one, using an if condition. In other words, (9) is the Python counterpart of (7).

 (9) set([x for x in B if P(x)])

To illustrate this further, the following list comprehension relies on the existence of the previously defined set nats (n % 2 is the remainder when n is divided by 2):

 ```>>> nats = set(range(10)) >>> evens1 = set([n for n in nats if n % 2 == 0]) >>> evens1 set([0, 8, 2, 4, 6])```

Now, when we defined evens before, what we actually had was a set of strings, rather than Python integers. But we can use int to coerce the strings to be of the right type:

 ```>>> evens2 = set([int(n) for n in evens]) >>> evens1 == evens2 True```

If every member of A is also a member of B, we say that A is a subset of B (written AB). The subset relation is represented in Python with <=.

 ```>>> evens1 <= nats True >>> set() <= nats True >>> evens1 <= evens1 True```

As the above examples show, B can contain more members than A for AB to hold, but this need not be so. Every set is a subset of itself. To exclude the case where a set is a subset of itself, we use the relation proper subset (written AB). In Python, this relation is represented as <.

 ```>>> evens1 < nats True >>> evens1 < evens1 False```

Sets can contain other sets. For instance, the set A = {{a}, {b} } contains the two singleton sets {a} and {b}. Note that {a} ⊆ A does not hold, since a belongs to {a} but not to A. In Python, it is a bit more awkward to specify sets whose members are also sets; the latter have to be defined as frozensets, i.e., immutable objects.

 ```>>> a = frozenset('a') >>> aplus = set([a]) >>> aplus set([frozenset(['a'])])```

We also need to be careful to distinguish between the empty set ∅ and the set whose only member is the empty set: {∅}.