2.2. Sets

A set is a collection of zero or more things that are called the members of the set. By convention, we write sets in curly braces, such as {1,2,3}. Sets have two important properties.

  1. A set is unordered. There is no first or last member of a set. So {1,2,3} is the same as {2,3,1}. Typically, we write sets of numbers in ascending order, but that is nothing more than a convention.

  2. Each thing is either in the set or not in the set. Nothing can be in the set twice. There are no duplicates, and writing something twice is equivalent to writing it once. So {1,2,3} is the same as {1,1,2,3}.

Set comprehensions

A set comprehension is a way of describing a set by indicating properties of its members. Notation

{x | xs and property of x}
indicates the set of all members of s that have the given property. For example,
{x | x ∈ {1,2,3,4,5,6,7,8,9} and x is even} = {2,4,6,8}.

Set comprehension notation is generalized to allow putting some function of x in the set. For example,

{x2 | x ∈ {2,4,6,8}} = {4, 16, 36, 64}.

Technically, it is required to say which values of x to consider (the set {1,2,3,4,5,6,7,8,9} above). But we often omit that when it is clear from ceontext which values of x are under consideration.

For example, if it is clear that we are talking about integers, then

{x | x is even}
is the set of all even integers.

More Notation

  1. An empty set is written either { } or ∅.

  2. The cardinality of a set is the number of members that the set has. The cardinality of set s is written |s|. For example, |{2,4,6}| = 3, |{8}| = 1 and |{ }| = 0.

  3. Notation xs indicates that x is a member of set s. For example, 9 ∈ {2,9,15,19} but 5 ∉ {2,9,15,19}.

  4. Two sets are equal if they have exactly the same members. So, if s and t are sets, then

    s = t  ⇔  ∀ x (xsxt)

  5. Notation st indicates that s is a subset of t. The definition is that

    st  ⇔  ∀ x (xsxt)
    For example, {2,4,6} ⊆ {2,3,4,6,7}. Notice that, according to that definition,
    1. { } ⊆ s for every set s.
    2. ss for every set s.

  6. Notation st indicates that s is a proper subset of t. We say that st just when st and st.

  7. The intersection st of two sets s and t is the set

    st = {x | xs and xt}.
    For example {1,2,3,4,5} ∩ {3,4,5,6,7} = {3,4,5}.

  8. The union st of two sets s and t is the set

    st = {x | xs or xt}.
    For example {1,2,3,4,5} ∪ {3,4,5,6,7} = {1,2,3,4,5,6,7}.

  9. The difference st of two sets s and t is the set

    st = {x | xs and xt}.
    For example {1,2,3,4,5} − {3,4,5,6,7} = {1,2}.

Sets of sets

The members of a set can, in general, be anything. If we are talking about strings, we might talk about the set {"dog", "cat"}.

The members of a set can even be other sets. For example, {{1,2}, {2,3,4}, {5,6}} is a perfectly good set. Notice that

|{{1,2}, {2,3,4}, {5,6}}| = 3,
since there are 3 members, {1,2}, {2,3,4} and {5,6}.

Be careful not to confuse ∈ with ⊆. That is, do not confuse the members of a set with the subsets of a set. Here are some illustrations.

{ } ⊆ {2,4,6} is true.

{ } ∈ {2,4,6} is false. ({2,4,6} only has 3 members, 2, 4, and 6, and none of them are { }.)

{2} ⊆ {{2}, {4}} is false.

{2} ∈ {{2}, {4}} is true.

2 ∈ {{2}, {4}} is false.

Also be careful about the empty set. You can write the empty set either as { } or ∅. Each of those sets has cardinality 0.

But {∅} is not an empty set. It has cardinality 1, since it has exactly one member, ∅. Use braces to list the members of a set, not as decoration to emphasize that something is a set.

Finite and infinite sets

A finite set has a cardinality that is a natural number. That is, you can write down all of the members. For example, {2,4,6,8} is a finite set of cardinality 4.

An infinite set has infinitely many members. For example, the set of all positive integers, {1,2,3,…} is infinite. We will need to deal with infinite sets a lot in this course.

Some standard sets

Z is the set of all integers (including negative integers). N is the set of all nonnegative integers.