Section SET Sets

Definition SET
Set
A set is an unordered collection of objects. If S is a set and x is an object that is in the set S, we write x ∈ S. If x is not in S, then we write x∉S. We refer to the objects in a set as its elements.

Hard to get much more basic than that. Notice that the objects in a set can be anything, and there is no notion of order among the elements of the set. A set can be finite as well as infinite. A set can contain other sets as its objects. At a primitive level, a set is just a way to break up some class of objects into two groupings: those objects in the set, and those objects not in the set.

Example SETM
Set membership
From the set of all possible symbols, construct the following set of three symbols,

\eqalignno{ S & = \left \{■,\kern 1.95872pt ♦,\kern 1.95872pt ⋆\right \} & & }

Then the statement ■∈ S is true, while the statement ▴∈ S is false. However, then the statement ▴∉S is true. ⊠

A portion of a set is known as a subset. Notice how the following definition uses an implication (if whenever…then…). Note too how the definition of a subset relies on the definition of a set through the idea of set membership.

Definition SSET
Subset
If S and T are two sets, then S is a subset of T, written S ⊆ T if whenever x ∈ S then x ∈ T.

If we want to disallow the possibility that S is the same as T, we use the notation S ⊂ T and we say that S is a proper subset of T. We’ll do an example, but first we’ll define a special set.

Definition ES
Empty Set
The empty set is the set with no elements. Its is denoted by ∅.

Example SSET
Subset
If S = \left \{■,\kern 1.95872pt ♦,\kern 1.95872pt ⋆\right \}, T = \left \{⋆,\kern 1.95872pt ♦\right \}, R = \left \{▴,\kern 1.95872pt ⋆\right \}, then

\eqalignno{ T & ⊆ S &R &⊈T &∅ &⊆ S & & & & & & \cr T & ⊂ S &S & ⊆ S &S &⊄S & & & & & & }

What does it mean for two sets to be equal? They must be the same. Well, that explanation is not really too helpful, is it? How about: If A ⊆ B and B ⊆ A, then A equals B. This gives us something to work with, if A is a subset of B, and vice versa, then they must really be the same set. We will now make the symbol “ =” do double-duty and extend its use to statements like A = B, where A and B are sets. Here’s the definition, which we will reference often.

Definition SE
Set Equality
Two sets, S and T, are equal, if S ⊆ T and T ⊆ S. In this case, we write S = T.

Sets are typically written inside of braces, as \left \{\ \right \}, as we have seen above. However, when sets have more than a few elements, a description will typically have two components. The first is a description of the general type of objects contained in a set, while the second is some sort of restriction on the properties the objects have. Every object in the set must be of the type described in the first part and it must satisfy the restrictions in the second part. Conversely, any object of the proper type for the first part, that also meets the conditions of the second part, will be in the set. These two parts are set off from each other somehow, often with a vertical bar (\vert ) or a colon (:).

I like to think of sets as clubs. The first part is some description of the type of people who might belong to the club, the basic objects. For example, a bicycle club would describe its members as being people who like to ride bicycles. The second part is like a membership committee, it restricts the people who are allowed in the club. Continuing with our bicycle club analogy, we might decide to limit ourselves to “serious” riders and only have members who can document having ridden 100 kilometers or more in a single day at least one time.

The restrictions on membership can migrate around some between the first and second part, and there may be several ways to describe the same set of objects. Here’s a more mathematical example, employing the set of all integers, ℤ, to describe the set of even integers.

\eqalignno{ E & = \left \{x ∈ ℤ\mathrel{∣}x\text{ is an even number}\right \} & & \cr & = \left \{x ∈ ℤ\mathrel{∣}2\text{ divides }x\text{ evenly}\right \} & & \cr & = \left \{2k\mathrel{∣}k ∈ ℤ\right \} & & }

Notice how this set tells us that its objects are integer numbers (not, say, matrices or functions, for example) and just those that are even. So we can write that 10 ∈ E, while 17∉E once we check the membership criteria. We also recognize the question

\eqalignno{ \left [\array{ 1&−3&5 \cr 2& 0 &3 } \right ] ∈ E\text{?} & & }

Subsection SC: Set Cardinality

On occasion, we will be interested in the number of elements in a finite set. Here’s the definition and the associated notation.

Definition C
Cardinality
Suppose S is a finite set. Then the number of elements in S is called the cardinality or size of S, and is denoted \left \vert S\right \vert .

Example CS
Cardinality and Size
If S = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ■\right \}, then \left \vert S\right \vert = 3. ⊠

Subsection SO: Set Operations

In this subsection we define and illustrate the three most common basic ways to manipulate sets to create other sets. Since much of linear algebra is about sets, we will use these often.

Definition SU
Set Union
Suppose S and T are sets. Then the union of S and T, denoted S ∪ T, is the set whose elements are those that are elements of S or of T, or both. More formally,

\eqalignno{ x ∈ S ∪ T\text{ if and only if }x ∈ S\text{ or }x ∈ T & & }

Notice that the use of the word “or” in this definition is meant to be non-exclusive. That is, it allows for x to be an element of both S and T and still qualify for membership in S ∪ T.

Example SU
Set union
If S = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ■\right \} and T = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ▴\right \} then S ∪ T = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ■,\kern 1.95872pt ▴\right \}. ⊠

Definition SI
Set Intersection
Suppose S and T are sets. Then the intersection of S and T, denoted S ∩ T, is the set whose elements are only those that are elements of S and of T. More formally,

\eqalignno{ x ∈ S ∩ T\text{ if and only if }x ∈ S\text{ and }x ∈ T & & }

Example SI
Set intersection
If S = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ■\right \} and T = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ▴\right \} then S ∩ T = \left \{♦,\kern 1.95872pt ⋆\right \}. ⊠

The union and intersection of sets are operations that begin with two sets and produce a third, new, set. Our final operation is the set complement, which we usually think of as an operation that takes a single set and creates a second, new, set. However, if you study the definition carefully, you will see that it needs to be computed relative to some “universal” set.

Definition SC
Set Complement
Suppose S is a set that is a subset of a universal set U. Then the complement of S, denoted \overline{S}, is the set whose elements are those that are elements of U and not elements of S. More formally,

\eqalignno{ x ∈\overline{S}\text{ if and only if }x ∈ U\text{ and }x∉S & & }

Notice that there is nothing at all special about the universal set. This is simply a term that suggests that U contains all of the possible objects we are considering. Often this set will be clear from the context, and we won’t think much about it, nor reference it in our notation. In other cases (rarely in our work in this course) the exact nature of the universal set must be made explicit, and reference to it will possibly be carried through in our choice of notation.

Example SC
Set complement
If U = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ■,\kern 1.95872pt ▴\right \} and S = \left \{♦,\kern 1.95872pt ⋆,\kern 1.95872pt ■\right \} then \overline{S} = \left \{▴\right \}. ⊠

There are many more natural operations that can be performed on sets, such as an exclusive-or and the symmetric difference. Many of these can be defined in terms of the union, intersection and complement. We will not have much need of them in this course, and so we will not give precise descriptions here in this preliminary section.

There is also an interesting variety of basic results that describe the interplay of these operations with each other. We mention just two as an example, these are known as DeMorgan’s Laws.

\eqalignno{ \overline{\left (S ∪ T\right )} & = \overline{S} ∩\overline{T} & & \cr \overline{\left (S ∩ T\right )} & = \overline{S} ∪\overline{T} & & \cr & & }

Besides having an appealing symmetry, we mention these two facts, since constructing the proofs of each is a useful exercise that will require a solid understanding of all but one of the definitions presented in this section. Give it a try.