10   Analyzing the Meaning of Sentences (Extras)

>>> 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 x ∈ A).

>>> '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

>>> 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))

>>> 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: {∅}.

Tuples

Given two sets A and B, we can form a set of ordered pairs by drawing the first member of the pair from A and the second from B. The Cartesian product of A and B, written A × B, is the set of all such pairs. More generally, we have for any sets S₁, …, S_n,

(10)

S1 × … × Sn = {〈x1, …, xn〉 ∣ xi ∈ Si}

In Python, we can build Cartesian products using list comprehension. As you can see, the sets in a Cartesian product don't have to be distinct.

>>> A = set([1, 2, 3])
>>> B = set('ab')
>>> AxB = set([(a, b) for a in A for b in B])
>>> AxB
set([(1, 'b'), (3, 'b'), (3, 'a'), (2, 'a'), (2, 'b'), (1, 'a')])
>>> AxA = set([(a1, a2) for a1 in A for a2 in A])
>>> AxA
set([(1, 2), (3, 2), (1, 3), (3, 3), (3, 1), (2, 1),
(2, 3), (2, 2), (1, 1)])

Relations and Functions

Given a binary relation R over two sets A and B, not everything in A need stand in the R relation to something in B. As an illustration, consider the set evens and the relation mod defined as follows:

>>> evens = set([2, 4, 6, 8, 10])
>>> mod = set([(m,n) for m in evens for n in evens if n % m == 0 and m < n])
>>> mod
set([(4, 8), (2, 8), (2, 6), (2, 4), (2, 10)])

(11)

dom(R) = {x ∣ ∃y.〈x, y〉 ∈ A × B}

1. For every a ∈ A there is at most one b ∈ B such that 〈a, b〉.
2. The domain of R is equal to A.

Thus, the mod relation defined earlier is not a function, since the element 2 is paired with four items, not just one. By contrast, the relation doubles defined as follows is a function:

>>> odds = set([1, 2, 3, 4, 5])
>>> doubles = set([(m,n) for m in odds for n in evens if n == m * 2])
>>> doubles
set([(1, 2), (5, 10), (2, 4), (3, 6), (4, 8)])

(12)

fS(x) = True if x ∈ S fS(x) = False if x ∉ S

f_S is a member of the set {True, False}^S.

Exercises