to express "is an element
of". For example, x A
means x is an element of set A. We put a slash through the symbol
to mean "not an element of".
A set is a collection of some sort of objects drawn from
some larger set called a universal set. If S is
a set and x is an object in S, x is called
an element of S. We use the symbol
to express "is an element
of". For example, x A
means x is an element of set A. We put a slash through the symbol
to mean "not an element of".
A set is defined by describing its elements in one of these ways:
The set with no elements is called the empty set or the
null set. One way to write it in symbols is { }, and another
way is 
.
A set with one element is called a singleton. Examples are {a} and {2}. Even {{1,2}} is a singleton because it has only one element, the set {1,2}.
Two sets are equal if they contain exactly the same elements. If sets A and B are equal, we write A=B.
There is no particular ordering of the elements of a set, and a set never contains duplicate elements. Thus all of the following sets are equal: {1,2,3}={1,2,2,3}={2,1,3,1}.
The number of elements in a set is called the cardinality of the set. The cardinality of set A is written |A|. If A = {a, b, c, f, g, h} then |A| = 6.
Sets are either finite or infinite depending on the number of elements in them. Set A just described is a finite set, since it contains a finite number (6) of elements. Some infinite sets are used so often that they have been given special names. Each of their names is a single fancy uppercase letter. See the text, page 12. Here we will use a non-fancy uppercase letter:
If every element of set A is also an element of set B, we say
that A is a subset of B. In symbols we write
A 
B.
If every element of set A is an element of set B but there
is at least one element in set B that is not in set A, then we
say that A is a proper subset of B. In symbols we write
A 
B. The book uses only one
symbol to suffice for both subset and proper subset. We will use two
different symbols.
There is a proper subset relationship among all of the special-named
sets above: N+
N Z
Q
R.
From the definition of subset, it follows that any set A is a subset of itself. It also follows that the empty set is a subset of every set, even of itself.
The idea of subset is different from set membership. For example, if A = {1,2,3} then
For another example, if A = {{e}, {f,g}} then
If set A is a subset of set B, then set B is a superset
of set A, B 
A.
If set A is a proper subset of set B, then set B is
a proper superset of set A,
B 
A.
The collection of all subsets of a set S is called the power
set of S, written 
(S). Our text
spells out the word power and writes power(S). There is a formula
for the cardinality of a power set:
|(S)| = 2|S|.
If set S = {5, 7, 9} then
(S) =
{{ }, {5}, {7}, {9}, {5,7}, {5,9}, {7,9}, {5,7,9}}.
Since there are 3 elements in S, there are 8
elements in P(S).
We can use the definition of subset to more precisely define set equality. Two sets are equal if and only if they are each a subset of the other.
To prove that set A is a subset of set B, you have two choices. If set A is very small you can take each of its elements one at a time and show that that element is in set B. If set A is large, show that for any arbitrary element of A that can be selected, that element must be in set B. In other words, say something like "Let x be any element of A" to begin your proof.
To show that set A is not a subset of set B, find one element that is in A and that is not in B.
To show that set A equals set B, show that A is a subset of B and that B is a subset of A.
The symbol for union is 
.
If A and B are sets then the union of A and B is the set of all
elements that are either in A or in B or in both. In other words,
A B = {x | x is in A or x is in B}.
If A and B are sets then the intersection of A and B is the set
of all elements that are both in A and in B. The symbol for intersection
is 
.
A B =
{x | x is in A and x is in B}.
In the following table, U is the universal set.
| Property | Union | Intersection |
| Identity | A
= A
| A U =
A |
| Commutativity | A B = B A
| A B = B A |
| Associativity | A (B C) = (A B) C
| A (B C) = (A B) C
|
| A A = A | A A = A
| |
| A U = U | A
{�} = {�}
| |
| A
B iff A
B = B
| A B iff A B = A
|
The following are distribution laws:
(B C) = (A B) (A C)
(B C) = (A B) (A
C)
The difference A-B is the set {x | x is in set A and x is not in set B}.
If A = {2, 4, 8, 9, 10} and B = {1, 2, 3, 4, 5}, then A-B = {8, 9, 10} and B-A = {1, 3, 5}.
The symmetric difference of sets A and B is the union of A-B and
B-A. The symbol for symmetric difference is
. Sometimes the symbol: 
is used.
Another definition of symmetric difference is
(A B) - (A
B). A way to think about
symmetric difference is this:
A B
contains elements that are either in A or in B, but not both.
If A = {2, 4, 8, 9, 10} and B = {1, 2, 3, 4, 5}, then A
B = {1, 3, 5, 8, 9, 10}.
If the sets we are working with are all subsets of a particular universal set U, then U is called the universe of discourse. The complement of set A with respect to U is written A' (pronounced A complement or A prime.) A' = U-A.
Here are some properties of set complement:
A' = {�} and
A A' = U
B iff
B' A'
B)' =
A' B' and
(A B)' = A'
B' (these are DeMorgan's Laws in logic)
B)'.
We can draw a picture with sets A and B in it, and color in the part
that would be contained in the set
(A B)'. For two sets,
we draw two circles overlapping them some. Example:
There are four different areas in a 2-set Venn diagram. The part outside the circles is the complement of the union of the two sets. Then there is an area that represents A-B, an area that represents B-A, and an area that represents the intersection of the two sets.
For three sets, we have to overlap the circles to form a total of 8
areas in the diagram. Here is a 3-set Venn diagram labeled to show its
different areas:
When doing a Venn diagram for the union of two sets A and B, you color all the areas in A then color any areas of B that are not already colored. When doing an intersection of A and B, it is often useful to make separate Venn diagrams for A and B, then do the intersection. In the Venn diagram for the intersection, color only the parts that are colored in both of the other diagrams. When doing a difference A-B, lightly color in the areas corresponding to A, then erase any colored areas of B.
Here are some samples of 3-set Venn diagrams:
Suppose we have two finite sets, A and B, and we want to know
the size of their union. We can add |A| + |B| but we will have
counted any elements that are both in A and in B twice. So we
must subtract the size of A
B from |A| + |B|. Here
is the principle of inclusion/exclusion for two sets:
|A B| = |A| + |B| -
|A B|
For three sets, the principle of inclusion/exclusion is:
|A B
C| =
|A| + |B| + |C| - |A B|
- |A C| -
|B
C| + |A
B C|
To determine the size of a difference set use the following difference rule:
|A - B| = |A| - |A B|
These principles are often used to solve word problems like the following:
A survey of 78 students is conducted. Of that number, 54 students own either a cat or a dog (or both). 46 students own a dog and 26 students own a cat. How many students own both a dog and a cat? How many dog owners do not own a cat? How many cat owners do not own a dog? How many students own only one kind of pet?
We can use the principle of inclusion/exclusion to determine the size of the set of students who own both a dog and a cat. Then using that number we can determine the answers to the remaining questions. Let D be the set of dog owners and C be the set of cat owners. The universal set is the set of students who were surveyed.
|D C| =
|D| + |C| - |D C|
54 = 46 + 26 - |D C|
|D C| = 72 - 54 = 18
This means that there are 18 students who own both a dog and a cat. Since there are 46 dog owners and 18 of them also own a cat, there are 46-18 = 28 dog owners who do not own a cat. Since there are 26 cat owners and 18 of them also own a dog, there are 8 cat owners who do not own a dog. Then 28 + 8 = 36 students own only one kind of pet.