GUIDE TO LOGIC

Sets I

Contents

1. Sets and Elements
2. Symbols for Sets and their Elements
3. Sets Defined by Lists of Elements
4. Sets Defined by Properties of Elements
5. Equality of Sets
6. Union of Sets
7. Commutative Law for Unions
8. Associative Law for Unions
9. Intersection of Sets
10. Commutative Law for Intersections
11. Associative Law for Intersections
12. Distributive Law: Union over Intersection
13. Distributive Law: Intersection over Union
14. Universal Set
15. Empty Set
16. Complement
17. Complement of a Complement
18. Union of a set and its Complement
19. Intersection of a Set and its Complement
20. Complement of a Union
21. Complement of an Intersection

1. Sets and Elements

A collection of objects is called a set. The individual objects in a set are called the elements of the set. For example, Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday are the elements of the set of the days of the week.

2. Symbols for Sets and their Elements

Sets may be represented by capital letters, such as A, B, C, etc. The elements of a set may be represented by small letters, such as a, b, c, etc. Then the statements a is an element of the set A, or a belongs to A, or a is in A all have the same meaning, and are written in symbols as follows:

a is in A.

For example we may let A stand for the set of days of the week, and we may let a = Sunday, b = Monday, c = Tuesday, etc. Then a is in A means Sunday is a day of the week, b is in A means Monday is a day of the week, etc.

EXERCISE

Let A stand for the set of months, and let a = January, b = February, etc. Give the meaning of the symbols: a is in A, b is in A, etc.

3. Sets Defined by Lists of Elements

A set may be defined by listing its elements in brackets. For example, if A stands for the set of colours used in traffic lights, then we may write:

A = {red, yellow, green}.

EXERCISE

Give a definition of the set of days in the week by listing its elements in brackets.

4. Sets Defined by Properties of Elements

A set may be defined by means of a variable x and an incomplete statement P(x) giving the characteristic property of the elements in the set. The statement A is the set of all elements x such that P(x) is written in symbols as follows:

A = {x: P(x)}.

For example, let x stand for a person, and let P(x) = x is an artist. Then {x: P(x)} is the set of all artists.

EXERCISE

Let x stand for an animal, and let P(x) = x has four legs. Say which of the following animals belong to the set {x: P(x)}:
  1. A buffalo
  2. A cat
  3. A monkey
  4. A snake.

5. Equality of Sets

Two sets are called equal when they have exactly the same elements. When a set is defined by listing its elements the list may be in any order. For example, the sets of colours {yellow, red, green}, {green, yellow, red} and {red, yellow, green} are all equal.

If the same set is defined by different incomplete statements, then the incomplete statements must have the same meaning. For example, let x stand for a day of the week. Then we have

{Saturday, Sunday} = {x: x is at the weekend} = {x: x is the day after Friday or the day before Monday}.

EXERCISE

Let x stand for a whole number. Say which of the following pairs of sets are equal and which are not equal.
  1. {1, 2, 3, 4, 5}
    {x: x is odd and less than 6}
  2. {1, 3, 5}
    {5, 3, 1}
  3. {x: x is positive and not greater than 5}
    {x: 0 < x < 6}.

6. Union of Sets

From two given sets A and B we can make a new set that consists of all the elements of A and all the elements of B. This new set is called the union of A and B. It is represented by the symbol A + B.

For example, let A = {a, b, c, d} and let B = {c, d, e}. Then A + B = {a, b, c, d, e}. Notice that the elements c and d are in A as well as B, but they are written only once in the list for A + B.

The union of two sets is defined in symbols as follows:

A + B = {x: x is in A or x is in B}.

EXERCISE

Give the unions of the following pairs of sets.
  1. A = {Friday, Saturday, Sunday, Monday}
    B = {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday}.
  2. A = {x: x is a man over 40 years old}
    B = {x: x is a woman over 40 years old}.

7. Commutative Law for Unions

In the union of two sets it does not matter which set is written first. For example,

{a, b, c} + {c, d} = {a, b, c, d}

and

{c, d} + {a, b, c} = {a, b, c, d}.

This may also be seen in the definitions

A + B = {x: x is in A or x is in B}

and

B + A = {x: x is in B or x is in A}

because, by the commutative law for the logical OR, x is in A or x is in B has the same meaning as x is in B or x is in A.

This fact is called the commutative law for the union of sets. It is summarized in symbols as follows:

A + B = B + A.

8. Associative Law for Unions

The union of A + B with another set C is a composite union:

(A + B) + C = {x: (x is in A or x is in B) or x is in C}.

By the associative law for the logical OR, this is equal to:

{x: x is in A or (x is in B or x is in C)} = A + (B + C).

Therefore we have the associative law for unions, which is summarized as follows:

(A + B) + C = A + (B + C).
As a result of this law we may omit the brackets and write:

A + B + C.

For example, let A be the set of all African people, let B be the set of all Asian people, and let C be the set of all European people. Then the union A + B + C is the set of all the people in Africa, Asia, and Europe.

9. Intersection of Sets

From two given sets A and B we can make a new set that consists of all the elements that belong to both A and B at the same time. This new set is called the intersection of A and B. It is represented by the symbol A . B.

For example, let A = {a, b, c, d} and let B = {c, d, e}. Then A . B = {c, d}.

The intersection of two sets is defined in symbols as follows:

A . B = {x: x is in A and x is in B}.

EXERCISE

Give the intersections of the following pairs of sets.
  1. A = {2, 4, 6, 8, 10, 12}
    B = {3, 6, 9, 12}.
  2. A = the time from 6:00 a.m. to 6:00 p.m.
    B = the time from 12:00 noon to 12:00 midnight.

10. Commutative Law for Intersections

In the intersection of two sets it does not matter which set is written first. For example,

{a, b, c, d} . {c, d, e} = {c, d}

and

{c, d, e} . {a, b, c, d} = {c, d}.

This may also be seen in the definitions

A . B = {x: x is in A and x is in B}

and

B . A = {x: x is in B and x is in A}

because, by the commutative law for the logical AND, x is in A and x is in B has the same meaning as x is in B and x is in A.

This fact is called the commutative law for the intersection of two sets. It is summarized in symbols as follows:

A . B = B . A.

11. Associative Law for Intersections

The intersection of A . B with another set C is a composite intersection:

(A . B) . C = {x: (x is in A and x is in B) and x is in C}.

By the associative law for the logical AND, this is equal to

{x: x is in A and (x is in B and x is in C)} = A . (B . C).

Therefore we have the associative law for intersections, which is summarized in symbols as follows:

(A . B) . C = A . (B . C).
As a result of this law we may omit the brackets and write

A . B . C.

For example, let A be the set of all African people, let B be the set of all female people, and let C be the set of all children under 10 years old. Then A . B . C is the set of all African girls under 10 years old.

12. Distributive Law: Union over Intersection

The union of a set A with an intersection B . C is a composite expression:

A + (B . C) = {x: x is in A or (x is in B and x is in C)}.

By one of the distributive laws for composite statements, x is in A or (x is in B and x is in C) has the same meaning as (x is in A or x is in B) and (x is in A or x is in C). Therefore

A + (B . C) = {x: (x is in A or x is in B) and (x is in A or x is in C)}.

But

{x: (x is in A or x is in B) and (x is in A or x is in C)} = (A + B) . (A + C).

Therefore

A + (B . C) = (A + B) . (A + C).
This is one of the distributive laws for sets.

For example, suppose that applicants for a job must have either a university degree, or five years of work experience and a certificate of English language ability. Let A be the set of people with a degree, let B be the set of people with five years of experience, and let C be the set of people with a certificate of English. Then A + (B . C) is the set of people who may apply for the job. By the distributive law this is the same as (A + B) . (A + C). This shows that the applications may be checked in two separate ways before being accepted. One check makes sure that the applicant belongs to A + B (has a degree or five years of experience). The other check makes sure that the applicant belongs to A + C (has a degree or a certificate of English).

EXERCISE

Suppose a person has enough money to buy a small new motor-car or a large second-hand motor-car. Let A be the set of small cars, let B be the set of large cars, and let C be the set of second-hand cars. Use the distributive law to find another way of saying that this person may buy a car which is small or large, and small or second-hand.

13. Distributive Law: Intersection over Union

The intersection of a set A with a union B + C is a composite expression:

A . (B + C) = {x: x is in A and (x is in B or x is in C)}.

By one of the distributive laws for composite statements, x is in A and (x is in B or x is in C) has the same meaning as (x is in A and x is in B) or (x is in A and x is in C). Therefore

A . (B + C) = {x: (x is in A and x is in B) or (x is in A and x is in C)}.

But

{x: (x is in A and x is in B) or (x is in A and x is in C)} = (A . B) + (A . C).

Therefore

A . (B + C) = (A . B) + (A . C).
This is another distributive law for sets.

For example, let A be the set of children from 5 to 12 years old, let B be the set of boys, and let C be the set of girls. Then A . (B + C) means: the set of children who are 5 to 12 years old and either boys or girls. This is the same as the set (A . B) + (A . C), which means: children who are boys 5 to 12 years old or girls 5 to 12 years old.

EXERCISE

Let A be the set of windy days in a particular year at a particular place, let B be the set of sunny days, and let C be the set of rainy days. Give the meaning of the two composite expressions:
  1. A . (B + C)
  2. (A . B) + (A . C).

14. Universal Set

The universal set contains all the individual objects being studied.

For example, if the sets being studied consist of men, women, boys, and girls in a population, then the universal set is everyone in the population.

We shall use the letter U to stand for the universal set.

EXERCISE

What is the universal set if the sets being studied consist of elements such as the following: 10 January, 5 February, 15 March, 1 May, 28 June, 16 November, 23 December?

15. Empty Set

The empty set does not contain anything. In other words, it is the set that has no elements. We shall use the letter O to stand for the empty set.

For example, let A be the set of all men, and let B be the set of all women. Then the intersection of these two sets is empty, that is: A . B = O.

EXERCISE

Say whether or not the intersection of the following pairs of sets is the empty set.
  1. {1, 2, 3}
    {2, 4, 6}
  2. {a, b, c}
    {d, e, f}.

16. Complement

The complement of a set A is the set of all elements in the universal set that do not belong to A. The complement of A is represented by the symbol A'. It is defined in symbols as follows:
A' = {x: x is not in A}.
For example, let the universal set be the set of whole numbers from 1 to 10, and let A be the set of all even numbers from 2 to 10. That is:

A = {2, 4, 6, 8, 10}.

Then A' is the set of all odd numbers from 1 to 9:

A' = {1, 3, 5, 7, 9}.

EXERCISE

Let the universal set be the set of all people. Give the complement of the set of all people who can swim.

17. Complement of a Complement

The complement of a complement is written in symbols as follows: (A')' = {x: not-(x is not in A)}.

Since not-(x is not in A) has the same meaning as x is in A, it follows that (A')' = {x: x is in A}. But {x: x is in A} = A. Therefore we have the complement law:

(A')' = A.
For example, let the universal set be the set of whole numbers from 1 to 10, and let A be the set of even numbers from 2 to 10. Then A' is the set of odd numbers from 1 to 9, and (A')' is the original set A of even numbers from 2 to 10.

EXERCISE

Let the universal set consist of all the books in a library. Let A be the set of books written in English. What are the sets A' and (A')'?

18. Union of a Set and its Complement

The union of a set and its complement is the universal set.

For example, let x stand for an animal, let A = {x: x is male}, and let A' = {x: x is female}. Then A + A' = {x: x is male or x is female} = the set of all animals.

We write this law briefly as follows:

A + A' = U.

EXERCISE

Give the universal sets for the following sets and their complements:
  1. A = all buildings with only one floor.
    A' = all buildings with two or more floors.
  2. A = all students who passed an examination
    A' = all students who failed the examination.

19. Intersection of a Set and its Complement

The intersection of a set and its complement is the empty set.

For example, let A consist of all the unbroken plates in a set of plates, and let A' consist of all the broken plates. Then A . A' is empty because there are no plates that are unbroken and broken at the same time.

We summarize this law in symbols as follows:

A . A' = O.

EXERCISE

Say whether or not the intersection of the following pairs of sets is the empty set:
  1. A = all sunny days in a year
    B = all windy days in the year.
  2. A = all wet days in a year
    B = all dry days in the year.

20. Complement of a Union

Since the union of two sets A and B is given by

A + B = {x: x is in A or x is in B},

the complement of the union is given by

(A + B)' = {x: not-(x is in A or x is in B)}

But not-(x is in A or x is in B) has the same meaning as x is not in A and x is not in B, and

{x: x is not in A and x is not in B} = A'.B'.

Therefore, we have the following law for the complement of a union:

(A + B)' = A' . B'.
This is one of De Morgan's laws for sets.

For example, let the universal set be the set of all substances. Let A be the set of all solids, such as stone and iron. Let B be the set of all liquids, such as water and oil. Then A + B is the set all substances that are solid or liquid. The complement (A + B)' is the set of all substances that are not solid or liquid, in other words the set A' . B' of all substances that are not solid and not liquid, such as oxygen and nitrogen (which are gases).

EXERCISE

Let A = all women and girls, let B = all children (girls and boys). Say what people are members of the complement of A + B.

21. Complement of an Intersection

Since the intersection of two sets A and B is given by

A . B = {x: x is in A and x is in B},

the complement of this intersection is given by

(A . B)' = {x: not-(x is in A and x is in B)}.

But not-(x is in A and x is in B) has the same meaning as x is not in A or x is not in B, and

{x: x is not in A or x is not in B} = A' + B'.

Therefore, we have the following law for the complement of an intersection:

(A . B)' = A' + B'.
This is another of De Morgan's laws for sets.

For example, let the universal set be the whole numbers from 1 to 10. Let A = {1, 2, 3, 4, 7, 8, 9, 10} and let B = {2, 4, 6, 8, 10}. Then A . B = {2, 4, 8, 10}, and so (A . B)' = {1, 3, 5, 6, 7, 9}. Also A' = {5, 6}, B' = {1, 3, 5, 7, 9} and A' + B' = {1, 3, 5, 6, 7, 9}. Therefore, in this example, (A . B)' = A' + B'.

EXERCISE

Let A = all women and girls, and let B = all children (girls and boys). Say what people are members of the complement of A . B when the universal set is all people.

Backward links: Statements I   Statements II   Quantifiers I   Quantifiers II

Forward links: Sets II   Relations I   Relations II

By R. H. B. Exell, 1998. King Mongkut's University of Technology Thonburi.
Back to Home Page