Set theory. Union, intersection, complement, difference. Venn diagram. Algebra of sets. Countable set. Cardinality. Indexed sets. Cartesian product. Projection function. Partition. Partially, linearly and well ordered sets.

SolitaryRoad.com

Website owner:  James Miller

[ Home ] [ Up ] [ Info ] [ Mail ]

Def. Set. Any collection of objects.

No restriction is placed on the nature of the objects in a set. They can be anything: points, lines, numbers, people, countries, etc. Thus the mathematical meaning of the word set is the same as the regular, nontechnical meaning of the word.

Examples of sets.

- all points in a given line segment

- all lines through a given point in space

- the set of all rational numbers

- all solutions of the equation 3x² + 2y² - 1 = 0

- all citizens of England

- all rivers of Mexico

The individual objects in a set are called the members or elements of the set.

Synonyms for set: Collection, class, aggregate, ensemble

Methods of defining sets. A set can be defined in either of two ways:

1) explicitly listing each of the elements of the set e.g. the set {2, 3, 4, 5}.

2) describing the set by stating properties that define it e.g. the set of all black cats in France.

The first method is called the roster method and the second method is called the property method.

Notation. Sets are usually denoted by capital letters such as A, B, X, S, etc. and the elements within them by lower case letters such as a, b, x, s, etc. When the roster method is used to define a set, the elements of the set are usually enclosed in braces and separated by commas e.g. S = {3, 5, 7, 9} is the set S consisting of elements 3, 5, 7, 9. The notation x S means that x is an element of S; x ∉S means x is not an element of S. To indicate a set of objects having the property P, the notation {x | x has the property P} is used. The notation {x | } is called a set builder. The bar “ | ” is read “such that.” Example. S = {x | x is an even integer}, which is the set of all even integers. Some authors use the colon : instead of the bar i.e S = {x: x is an even integer}.

Def. Equal sets. Sets consisting of the same elements.

Two sets A and B are said to be equal if every element of A is an element of B and every element of B is an element of A. The equality of sets A and B is denoted by A = B. Inequality of two sets A and B is denoted by A ≠ B.

Examples.

● The sets A = {3, 4, 5, 6} and B = {5, 3, 4, 6} are equal since the order in which set elements are listed is immaterial.

● The sets A = {4, 5, 6} and B = {4, 5, 5, 6} are equal since repeating an element of a set does not change the set.

Def. Subset. Let S be a given set. Any set A, each of whose elements is also an element of S, is said to be contained in S and called a subset of S.

Example. The sets A = {5}, B = {3, 4, 5}, and C = {6, 7) are all subsets of S = {1, 2, 3, 4, 5, 6, 7, 8}. Reviewing the definition we note that the entire set S qualifies as a subset of S. Thus any set is a subset of itself.

We write “A is a subset of S” as A S.

Def. Proper subset. If A is a subset of S and A ≠ S, then A is called a proper subset of S. In the above example sets A, B and C are all proper subsets of S.

If A is a subset of S, then we can also write

S A

which is read “S is a superset of A”.

Note. Some authors use A S to indicate that A is a subset of S and reserve A B to indicate that A is a proper subset of S.

Theorem. If A B and B C, then A C.

The empty (or null) set ∅. However illogical it may seem, it is convenient and useful to have the concept of an empty set, a set containing no elements. We call such a set the empty (or null) set and denote it by ∅.

The null set ∅ is considered to be a subset of every set.

Universal set U. Often a discussion involves subsets of some particular set called the universe of discourse (or briefly universe), universal set or space. The elements of a space are often called the points of the space. We denote the universal set by U.

Example. The set of all even integers could be considered a subset of a universal set consisting of all the integers. Or they could be considered a subset of a universal set consisting of all the rational numbers. Or of all the real numbers.

Often the universal set may not be explicitly stated and it may be unclear as to just what it is. At other times it will be clear.

Complement of a set. The complement of a set A with respect to a given universal set U is the set of elements in U that are not in A. The complement of A is typically denoted by A^c or A'.

Finite and infinite sets. A finite set is a set with a finite number of elements and an infinite set is one with an infinite number of elements.

Examples.

● The set of all black cats in France is a finite set.

● The set of all even integers is an infinite set.

Comparability. Two sets A and B are said to be comparable if

A B or B A

i.e. if one of the sets is a subset of the other. Two sets A and B are said to be not comparable if

A B and B A

We thus note that if two sets A and B are not comparable there is necessarily an element in A that is not in B and an element in B that is not in A.

Def. Disjoint sets. Two sets are called disjoint if they have no elements in common i.e. the intersection of the sets is the null set. A system of more than two sets is pairwise disjoint (sometimes called simply disjoint) if every pair of sets in the system is disjoint.

Sets of sets. Sometimes the members of a set are sets themselves. If the members of a set A are themselves sets it is common to call A a “family of sets” or a “class of sets” rather than call it a “set of sets”.

Example. A family of lines in geometry can be regarded as a set of sets since lines can be regarded as sets of points.

Def. Power set of a set. The collection of all subsets of the set. The power set of a set A, denoted by P(A) or 2^A, is the set consisting of all subsets of A.

Example. The power set of A = {a, b, c} is the set

P(a) = {A, {a, b}, {a, c}, {b, c,}, {a}, {b}, {c}, ∅}

In general, if A is finite with n elements, P(a) will have 2ⁿ elements.

Union of sets. The union of two sets A and B is the set consisting of all elements in A plus all elements in B and is denoted by A∪B or A + B.

Synonyms. sum, join

Example. If A = {a, b, c, d} and B = {b, c, e, f, g} then A∪B = {a, b, c, d, e, f, g}.

Intersection of sets. The intersection of two sets A and B is the set consisting of all elements that occur in both A and B (i.e. all elements common to both) and is denoted by A∩B, A · B or AB.

Synonyms. product, meet

Example. If A = {a, b, c, d} and B = {b, c, e, f, g} then A∩B = {b, c}.

Difference of two sets. The set consisting of all elements of a set A that do not belong to a set B is called the difference of A and B and denoted by A - B.

Example. If A = {a, b, c, d} and B = {b, c, e, f, g} then A - B = {a, d}.

Venn diagrams. The union, intersection, difference and complement of sets can be depicted graphically by means of Venn diagrams. In a Venn diagram the universe U is represented by points within a rectangle and sets A, B, C, etc. are represented by points inside circles within the rectangle. Figure 1 graphically depicts the union A∪B of two sets A and B, Figure 2 depicts the intersection A∩B of two sets A and B, Fig. 3 depicts the difference A - B of two sets A and B and Fig. 4 depicts the complement of a set A.

Algebra of sets. Let A, B, C be any three subsets of a universe U. Then the following laws hold:

1. Closure laws

(a) There exists a unique set

(b) There exists a unique set

2. Commutative laws

3. Associative laws

4. Distributive laws

5. Idempotent laws

6. Properties of universe U. Identity laws

7. Properties of null set ∅. Identity laws

8. Properties of inclusion

9. Properties of complement

10. Difference laws

11. Absorption laws

12. Consistency property

The conditions

are equivalent.

Dual statements. If we interchange ∩ and ∪, U and ∅, and ⊂ and ⊃ in any statement about sets the new statement is called the dual of the original one.

Example. The dual of

Duality principle. If in any true statement about sets we interchange ∩ and ∪, U and ∅, and and , the resulting statement is also true. That is, the dual of any true statement is also true.

Def. One-to-one correspondence. A correspondence between the members of two sets in which each member of either set is paired with exactly one member of the other set.

Synonyms. bijection, one-to-one function, one-to-one mapping, one-to-one transformation

Example. A one-to-one correspondence between the two sets {a, b, c, d, e} and {1, 2, 3, 4, 5} is given by the pairing

{(a,3), (b, 5), (c, 1), d, 4), (e, 2)}

See Fig. 5.

Def. Equivalent sets. Sets that can be put into one-to-one correspondence. If set A is equivalent to set B, we write A ~ B.

Synonyms. equinumerable sets, equipotent sets

Def. Countable (or denumerable) set. (1) An infinite set whose members can be put into one-to-one correspondence with the positive integers. Syn. countably infinite, enumerable, denumerable, denumerably infinite. (2) A set which either has a finite number of members or can be put into one-to-one correspondence with the positive integers.

There is some variation in usage in regard to the term “countable set”, some writers using definition (1) and others using definition (2). We will use definition (1).

The sets of all integers and of all rational numbers is countable, but the set of all real numbers is not.

A set which cannot be put into one-to-one correspondence with the positive integers is called non-countable or non-denumerable.

Theorem 1. The set of all rational numbers is countable.

Proof. Let us arrange the rational numbers in the manner shown in Table 1. All the natural numbers are placed in the first row as shown, zero and the negative numbers are put in the second row in decreasing order as shown, positive reduced fractions with denominator 2 are put in the third row in ascending order, negative reduced fractions with denominator 2 are put in the fourth row in descending order, etc. It can be seen that every rational number occurs once and only once in the table. Let us now write down all the numbers in the table in the order indicated by the arrows. We obtain the following sequence:

1, 2, 0, ,3, -1, 1/2, 4, -2, 3/2, ....

We have thus devised a scheme for writing all the rational numbers in a single sequence and have thus shown that they can be put into one-to-one correspondence with the natural numbers. Thus we have shown that the rational numbers are countable.

Theorem 2. The closed interval [0, 1] is non-denumerable.

Def. Cardinal number. A number that indicates the manyness of a set of things i.e. the number of units, not the order in which they are arranged.

Cardinal number of a set. Two sets are said to have the same cardinal number if and only if they can be put into one-to-one correspondence i.e. if and only if they are equivalent.

A set A is said to have the cardinal number n if and only if there exists a one-to-one correspondence between the elements of A and the natural numbers 1, 2, 3, .... , n.

Synonyms. The cardinal number of a set is also called the potency of the set or power of the set.

Cardinal number of a denumerable (countably infinite) set. The cardinal number of a denumerable (or countably infinite) set is called Aleph-null or Aleph-zero and is denoted by N₀. This is the cardinal number of the natural numbers 1, 2, 3, .....

Cardinal number of the continuum. The cardinal number of the continuum is defined as the cardinal number of the interval [0, 1]. The cardinal number of the continuum is denoted by either N₁ or c.

Synonyms. The cardinal number of the continuum is also called the power of the continuum.

Theorem 3. The set of points of any open interval (a, b) or of the entire real line has the cardinal number of the continuum.

Proof. If we can set up a one-to-one correspondence between the points on a line segment AB

and those of the interval [0, 1] we have proved the theorem. In Fig. 6 we show such a correspondence where P corresponds to P'.

Def. Partition of a set. A collection of disjoint sets whose union is the given set. A set {A, B, C, ..... }of non-empty subsets of a set S is a partition of S if

and

2) the intersection of every pair of distinct subsets is the null set.

Examples.

1. Let S = {1, 2, 3, 4, 5, 6}, A = {1, 5), B ={3, 4, 6} and C = {2}. Then the collection of sets {A, B, C} represents a partition of S.

2. Let N be the set of positive integers

N = {1, 2, 3, .....},

E be the set

E = {2, 4, 6, .......}

and F be the set

F = {1, 3, 5, .....}.

Then {E, F} is a partition of N.

Properties of infinite sets. If we have two finite sets A and B with no elements in common the number of elements in their sum C = A + B is equal to the sum of the number of elements in A plus the number of elements in B. Or, stated differently, if a set C is partitioned into two disjoint subsets A and B, the number of elements in C is equal to the sum of the elements in its two constituent subsets A and B. Let us now consider the case of infinite sets. Let A, B and C be the following infinite sets:

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

B = {1, 3, 5, ..... }

C = (1, 2, 3, ...... }

Here C is the sum of the sets A and B. Sets A, B and C are all denumerable (countable infinite) sets and all have the same cardinal number, the cardinal number N₀. Thus the cardinal number of C is the same as one of its subsets and not equal to the sum of the cardinal numbers of its constituent subsets as one might expect. Thus if we think of the cardinal number of a set as representing the number of elements in the set our use of a one-to-one correspondence as a device for establishing the cardinal number of the set leads to odd results. The rule, “the whole is equal to the sum of the parts” is violated.

Theorems for denumerable (countably infinite) sets

1] Every infinite set contains a denumerable subset.

2] Every infinite subset of a denumerable set is denumerable.

3] A denumerable sum of denumerable sets is denumerable.

Schroeder-Bernstein theorem. If A B C and A ~ C, then A ~ B.

Indexed sets. A collection of sets

{A₁, A₂, A₃, ..... }

can be denoted by such notations as

{A_i : i ε I}, {A_i}_{i ε I}, or {A_i}

In these notations the set I is called the index set and the sets A_i are called indexed sets. Each i ε I is called an index. These notations can be viewed as functions that assigns a set A_i to each i ε I i.e. functions from I into some collection of sets.

Def. Cartesian product A B of two sets A and B. The Cartesian product A B (read “A cross B”) of two sets A and B is defined as the set of all ordered pairs (a, b) where a is a member of A and b is a member of B.

Syn. Product set, direct product, direct sum.

Example 1. If A = {1, 2, 3} and B = {a, b} the Cartesian product A B is given by

A B = { (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) }

Comments. Some comments are in order in regard to the concept of a Cartesian product of two arbitrary sets A and B. One is certainly justified in asking: Does this concept make any sense? What meaning can be attached to a Cartesian product? What meaning can be attached to the ordered pairs? Well, in general, an ordered pair has no meaning unless one has been assigned. In specific cases, when an ordered pair does have meaning, the concept of a Cartesian product may become meaningful and useful. The Cartesian product finds meaning and use in different places including the theory of abstract mathematical systems such as groups, rings and vector spaces. One can view the concept of a Cartesian product as a generalization / abstraction of a concept relating to the Cartesian plane. That concept is this: The set of all points in the Cartesian plane can be viewed as the set of all ordered pairs (x, y) where x ε R and y ε R, R being the set of all real numbers. In fact, a Cartesian product is so defined that R R is the set of all points in what we know as the Cartesian plane. Thus the motivation for the term. In analogy to the way we view number pairs (x, y) as points in the Cartesian plane we can view the ordered pairs of a Cartesian product as points in a Cartesian frame. Figure 7 shows such a representation for the sets A = {1, 2, 3, 4} and B = {a, b, c}.

Example 2. Let A be the set of numbers in the interval [3, 5] and B be the set of numbers in the interval [2, 3]. Then the Cartesian product A B corresponds to the rectangular region shown in Fig. 8. It consists of all points (x, y) within the region. In the same way, if A is the set of numbers in the interval [3, 5], B is the set of numbers in the interval [2, 3] and C is the set of numbers in the interval [6, 7] the Cartesian product A B C consists of all points (x, y, z) in a rectangular parallelepiped in three-dimensional space defined by

3 x 5

2 y 3

6 z 7 .

Example 3. Let I denote the unit interval [0, 1] and C¹ the interior and boundary of the unit circle. Then I I is the unit square and C¹ I is a cylinder. See Fig. 9.

The Cartesian product A₁ A₂ A_n . The Cartesian product A₁ A₂ A_n of n sets A₁, A₂, ...... , A_n is defined in a similar way. It is the set of all ordered n-tuples (a₁, a₂, .... , a_n) for a_i ε A_i (each a_i assumes all the values in A_i, i = 1, 2, ...., n). We can view an n-tuple (a₁, a₂, .... , a_n) as a point in an n-dimensional space defined by the Cartesian product A₁ A₂ A_n . The component sets A_1, A_2, , A_n of the product are called the coordinate sets of the space. The set A_i is called the i-th coordinate set of the product. The i-th component of the n-tuple (a₁, a₂, .... , a_n) is called the i-th coordinate of the vector (a₁, a₂, .... , a_n) in n-space. This i-th coordinate of the point is called the projection of the vector (a₁, a₂, .... , a_n) onto the i-th coordinate set A_i.

The above represents a generalization of concepts associated with the usual 3-space R³ and n-space Rⁿ. The space Rⁿ becomes a special case of the above when A₁= A₂ = .... = A_n = R.

Notations. The Cartesian product A₁ A₂ A_i of an indexed collection of sets {A_i}_{i ε I} is sometimes denoted by

Projection function. The projection function works as follows: Let X = (a₁, a₂, .... , a_n) be a point in the n-dimensional space defined by the Cartesian product A₁ A₂ A_n. The projection function π_i(X) is defined as

π_i(X) = a_i

where a_i is the i-th coordinate of the point X = (a₁, a₂, .... , a_n). Here a_i represents the projection of the vector (a₁, a₂, .... , a_n) onto the i-th coordinate set A_i , hence the name. The projection function π is a function from the n-dimensional space defined by the Cartesian product A₁ A₂ A_n into the i-th coordinate set X_i.

Example. Let R₁, R₂ and R₃ denote copies of R. Consider the point X = (3.1, 6.5, 2.8) in three dimensional space R R R = R₁ R₂ R₃. Then

π₁(X) = 3.1 is the projection of X in R₁.

π₂(X) = 6.5 is the projection of X in R₂.

π₃(X) = 2.8 is the projection of X in R₃.

Cartesian product R R R. The Cartesian product R R R corresponds to the set of all points in three-dimensional space i.e. the set of all number triplets (x, y, z), x ε R, y ε R, z ε R.

Cartesian products R², R³, .... , Rⁿ. The Cartesian product R R is usually denoted by R², the Cartesian product R R R is usually denoted by R³ and the Cartesian product R R ..... R (n times) consisting of all n-tuples (x₁, x₂, .... , x_n) is usually denoted by Rⁿ.

Generally a Cartesian product A B is thought of as a two dimensional array of points with each point corresponding to an ordered pair (x, y), a Cartesian product A B C is thought of as a three dimensional array of points with each point corresponding to an ordered triple (x, y, z) and a Cartesian product A₁ A₂ A_n is thought of as an n-dimensional array of points with each point corresponding to an n-tuple (or n-vector). An exception to this is illustrated in Example 3 above because C¹ is two-dimensional.

Def. Partially ordered set. A partially ordered set is a set which has the relation x < y, or “x precedes y”, defined on it such that for all members x, y and z of the set:

1) It is never the case that x < x (the relation < is non-reflexive)

2) If x < y, then y < x cannot also be true. (the relation < is anti-symmetric)

3) If x < y and y < z, then x < z (the relation < is transitive)

Example. The relation “is a proper subset of” defines a partial ordering of the subsets of a set.

Strict and non-strict partial orders. The partial order defined above is called a strict (or non-reflective) partial order. A non-strict (or weak or reflective) partial order is a relation ≤ defined on the set such that for all members x, y and z of the set:

1) x ≤ x (the relation ≤ is reflective)

2) x ≤ y and y ≤ x implies x = y (the relation ≤ is anti-symmetric)

3) If x < y and y < z, then x < z (the relation ≤ is transitive)

Example. The relation “is a subset of” defines a non-strict partial ordering of the subsets of a set.

Def. Linearly ordered set. A set that satisfies the following conditions:

1) It is never the case that x < x.

2) If x < y, then y < x cannot also be true.

3) If x < y and y < z, then x < z.

4) For any two members x and y, exactly one of the following is true:

a) x < y

b) x = y

c) y < x

Syn. ordered set, serially ordered set, simply ordered set, chain

Example. The set of positive integers in their natural order.

Def. Well ordered set. A linearly ordered set for which each subset has a first member i.e. a member that precedes all other members.

Example 1. The set of positive integers in their natural order is a well ordered set since all subsets have a first member.

Example 2. The set of all integers in their natural order is not well ordered since the set itself has no first member.

Example 3. The set of nonnegative real numbers in their natural order is not well ordered since the subset consisting of numbers greater than, say 3, has no first member.

References

Mathematics, Its Content, Methods and Meaning. Vol. 3

Lipschutz. Set Theory. (Schaum)

James & James. Mathematics Dictionary

Burington. Handbook of Mathematical Tables and Formulas

Ayres. Modern Algebra. (Schaum)

Spiegel. Real Variables. (Schaum)

Natanson. Theory of Functions of a Real Variable.