Set Theory

Two sets S and T are equal, if every element of the set S is also an element of the set T, and if every element Figure 1a. Illustration by Hans & Cassidy. Courtesy of Gale Group. Figure 2a. Illustration by Hans & Cassidy. Courtesy of Gale Group. Figure 2c. Illustration by Hans & Cassidy. Courtesy of Gale Group.
of the set T is also an element of the set S. This means that two sets are equal only if they both have exactly the same elements. A set T is called a proper subset of S if every element of T is contained in S, but not every element of S is in T. That is, the set T is a partial collection of the elements in S.

In set notation this is written T ⊂ S and read "T is contained in S." S is sometimes referred to as the parent or universal set. Also, S is a subset of itself, called an improper subset. The complement of a subset T is that part of S that is not contained in T, and is written T'. Note that if T' is the empty set, then S and T are equal.

Sets are classified by size, according to the number of elements they contain. A set may be finite or infinite. A finite set has a whole number of elements, called the cardinal number of the set. Two sets with the same number Figure 1b. Illustration by Hans & Cassidy. Courtesy of Gale Figure 2b. Illustration by Hans & Cassidy. Courtesy of Gale Group.


of elements have the same cardinal number. To determine whether two sets, S and T, have the same number of elements, a one-to-one correspondence must exist between the elements of S and the elements of T. In order to associate a cardinal number with an infinite set, the transfinite numbers were developed. The first transfinite number &NA;₀, is the cardinal number of the set of integers, and of any set that can be placed in one-to-one correspondence with the integers. For example, it can be shown that a one-to-one correspondence exists between the set of rational numbers and the set of integers. Any set with cardinal number &NA;₀ is said to be a countable set. The second transfinite number æ₁ is the cardinal number of the real numbers. Any set in one-to-one correspondence with the real numbers has a cardinal number of &NA;₁, and is referred to as uncountable. The irrational numbers have cardinal number &NA;₁. Some interesting differences exist between subsets of finite sets and subsets of infinite sets. In particular, every proper subset of a finite set has a smaller cardinal number than its parent set. For example, the set S = has a cardinal number of 10, but every proper subset of S (such as) has fewer elements than S and so has a smaller cardinality. In the case of infinite sets, however, this is not true. For instance, the set of all odd integers is a proper subset of the set of all integers, but it can be shown that a one-toone correspondence exists between these two sets, so that they each have the same cardinality.

A set is said to be ordered if a relation (symbolized by <) between its elements can be defined, such that for any two elements of the set:

1. either b < c or c < b for any two elements
2. b < b has no meaning
3. if b < c and c < d then b < d.

In other words, an ordering relation is a rule by which the members of a set can be sorted. Examples of ordered sets are: the set of positive integers, where the symbol (<) is taken to mean less than; or the set of entries in an encyclopedia, where the symbol (<) means alphabetical ordering; or the set of U.S. World Cup soccer players, where the symbol (<) is taken to mean shorter than. In this last example the symbol (<) could also mean faster than, or scored more goals than, so that for some sets more than one ordering relation can be defined.