Chapter 2
Sets and Open Statements

Section 1:   Introduction

[1.1] (Definitive conditions for sets)
   (a) An object is either in a set or not in a set.
   (b) Two sets are equal if and only if they contain exactly the same objects.

Sometimes the phrase "is a member of" a set may be used instead of "is in" a set.

In Volume B (Numerical systems) are discussions about objects called natural numbers and their properties. They are the familiar numbers without end for counting:

The objects 3, 5, 6 are in N₉. The objects 10, 11 are not members of N₉.
The reader can easily determine what objects are in the sets N₆, N₁₀₀, N_n where n=7.
In these discussions the name of the infinite set of all natural numbers is N,      N = {1,2,3,4,5,6,...............-->}. It is not always necessary to give names to sets. For example the set of all prime numbers in N₉is {2,3,5,7}.

Usually all objects involved in a discussion form a collection called a universe. Objects outside a universe are ignored. Aninterior of a rectangle may serve as an example of a universe. Let its name be U. In the adjacent figure a,b,c,d are names of points. Points a,c are in U, and points b,d is not in U.
However, there may be more than one universe, often because some objects are very different from some other objects in the discussion. For example, a single discussion involves a universe of numbers and a universe of points. The discussion may relate the numbers to the points.

It is important to distinguish objects from the sets that objects are in. The object 1 is not the same as the set N₁ = {1}.
------

Objects are inside universes. It is useful to consider a set inside a universe.

[1.2] A set inside a universe is a collection of objects that belong to that universe. It is also called a subset of that universe.

Below the letter S, sometimes with a numerical subscript, is used repeatedly as a name for some subsets in various discussions.

(Numerical) Example 1: The set {2,5,6,8} is a subset of the universe N₉.   But the set {5,7,100} is not a subset of N₉ because 100 is not in the universe.

The collection of objects in a subset may be made by selecting objects satisfying some rule, from all the objects in the universe. (But nothing is removed from the universe.)

(Numerical) Example 2: In the universe N₉ collect all the numbers between 3 and 8. This collection becomes the set {4,5,6,7}which is a subset of the universe N₉.

(Geometric) Example 3: In the adjacent figure the universe consists of all points inside and on the rectangle. The interior of the circle together with the circle itself is a subset of the universe. If c is the center then the subset consists of all the points whose distance from c is < the radius of the circle.

For any universe U, two extremes of selection are allowed:
   (a) All objects in U are selected Therefore, every universe is a subset of iteself.
   (b) No objects in U are selected. Then the subset is empty. It is given the permanent name Φ.   The empty set Φ is a subset of every universe.

-----

Consider the following statements:

Table 1 (Components):

Referring to the adjacent figure, let q(y) the open statement
                   q(y):   point y is inside the circle
It is impossible to list all of the components of q(y) because there are infinitely many points in the universe (inside the rectangle). But four components can be displayed because four points have names a,b,c,d:
                   q(a):   point a is inside the circle
                   q(b):   point b is inside the circle
                   q(c):   point c is inside the circle
                   q(d):   point d is inside the circle

[1.3] (Open statements and components) An open statement in a variable with universe is a form in which if the variable is replaced by (the name of) any object in the universe, then the open statement becomes a logical statement, called a component of the open statement.
Notation: if p(x) is an open statement in x with universe U and b,c,d are (names of) objects in U, then p(b), p(c), p(d),... are logical statements derived from p(x) by replacing   x by b,   or   x by c,   or   x by d.

Since components are logical statements they must have truth values. However, open statements do not have truth values. A componemt be true (T) or false (F). But objects produce these components upon substitution in the open statement. Table 2 displayes the function notation, the open statement, its components and truth values of the components

Table 2:

Taken from the last column of the above table, Table 3 shows the truth values assigned directly to the objects:

Table 3:

[1.4] (Open statements giving truth values to objects) A open statement with a universe assigns a truth value to each object in that universe by copying the truth value of the component containing that object.

The open statement

There are different methods for asigning truth values to every object in some universe. One method is by selection. If an object is selected, assign a T to it. If rejected, assign an F. Different open statements also assign truth values to every object. Two methods for assigning truth values to all objects in a universe are logically equivalent if and only if they assign equal truth values to each object. In particular, this applies to open statements.

[1.5] (Equivalent open statements) Open statements with the same universe are logically equivalent if and only if they all assign equal truth values to each object in the universe.

The word "logically" often will be omitted.
The assignment of truth values to all objects in a universe can be done by selection. If an object is selected, assign a T to it. If rejected, assign an F.

If all the objects in a universe have been assigned truth values, then all those objects assigned a T form a distinguished set, called truth set. When open statements are equations, the truth sets are often called the solution sets. For example, the solution set of

The idea of truth sets reveals an intimite connection between sets and open statements. According to [1.4] every open statement has a (unique) truth set. Conversely for any set S in the universe there is an open statement   x is in S   whose truth set is S. It is called the trivial open statement for S. There are other open statements with that same universe and with that same truth set.

[1.6] (Relationship between sets and open statements)
   (a) Every open statement determines a subset of its universe, namely its truth set.
   (b) For every subset of a universe there is an open statement whose truth set equals that subset, namely the trivial open statement.

Often in the same discussion there are more than one open statement all with the same universe. Each independently assigns truth values to all the objects in that universe. If there are two open statements then each object receives two truth values.

For any set S in a universe U there are many open sets p(x), q(x), r(x), ... whose truth sets equal S. For example:

[1.7] (Equivalent open statements) Open statements with the same universe are equivalent if and only if they all have the same truth set.

The argument supporting [1.7] is simple.
If the open statements are equivalent, then each object in the universe receives equal truth values from the open statements. Therefore, the objects receiving a T from one open statement must also receive a T from all the other open statements. So their truth sets must be the same.
Conversely, suppose the open statements have the same truth set. Then all open statements assign a T to every object in the truth set and an F to every object not in the truth set. Therefore, equal truth values assigned to all objects in the universe. By [1.5] the open statements are equivalent.

Examples:
The equations   x + 1 = 5   and   x + 2 = 6   with universe N are equivalent because they have the solution set {4}.
If both sides of an equation are multiplied by the same natural number then an equivalent equation is obtained.

-----

In the following sections there are discussions involving more than one open statement, all with the same universe. Two open statements will assign two truth values to each object and determine two subsets (truth sets) in that universe, three open statements - three truth values to each object and three subsets (truth seets) in that universe, etc. The assignments of truth values to objects are done independently. Sometimes colors will be used to coordinate names, open sets and geometric models. The adjacent figure is the geometric model of the truth sets S₁, S₂ of two unspecified open statements p(x), q(x) . Depending on the positions of the circles, these open statements may assign any of the following pairs of truth values to each object in the universe:

Here is a numerical example of two specific open statements:
Let the universe be N₉, and p(x), q(x) be open statements with that universe, and defined by

Notice that no object in this example receives the pair FF. As will be seen later, such an omission means that some relation exists between the open statements, and also between their truth sets.

[1.8] (Logically unrelated open sets) Two open statements with the same universe are unrelated if together their assignments of truth values to all the objects in the universe involves all four pairs of truth values in (#).
Notation: In the universe, unrelated open sets p(x), q(x) assign TT to some object,   assign TF to another object,   assign FT to another object,   assign FF to another object.

The adjacent figure shows the truth sets of two unrelated open sets. The trivial open statements involving point x

Section 2:   Some operations on sets: intersection, union and complement

Let S be any set in a universe U. Collect all objects in U but outside of S to form a new set ~S. In the adjacent figure, if S is the set of all points in the left part of the figure, then ~S is the set of all points in the right part.

[2.1] (Complement) The complement of a given set in a universe is the collection of all objects (in the universe) that are not in the given set.
Notation1: In a universe U,   x is in ~S   if and only if   x is not in S.
Notation2: ~S = {x in U | x is not in S}.
Notation3: In U, if S is a truth set then all objects in ~S have been assigned an F.
Notation4: Let p(x) be an open statement with universe U. If p(x) assigns a truth value to any object in U, then the negative ~p(x) assigns the opposite truth value to that same object. (The subset of U determined by ~p(x) is the complement of the subset determined by p(x).)

Another notation for complement is   U\S   (a special form of set subtraction defined in [2.12] below). This notation indicates the need for knowing the universe U as well as S in order to determine the complement of S.

Example: in the universe   N₉ = {1,2,3,4,5,6,7,8,9 }   let   S = {1,3,5,7,9}.   Then the complement of S is   ~S = {2,4,6,8}.

If a tilda (~) is "attached" to a set symbol S then the complement ~S of that set is formed. Therefore the tilda (~) is a unary operation on individual sets. Its attachment to the name of a given set denotes the results of the operation, namely, the creation of a single set which is the complement of the given set.
It is obvious that the complement of ~S must be S, because S contains all objects in the universe not in ~S. Therefore, the complement of the complement of a set is the set itself.   ~ ~S = S. This also means that ~~p(x), p(x) have the same truth set, and hence are equivalent. The operation of the tilda resembles the operation of negation in algebra: the negative of a negative of number w   = -(-w) = w. (Later such operations will be called involutions.)

Example: In the previous example S = {1,3,5,7,9}.   Then ~~S = ~(~S) = ~{2,4,6,8} = {1,3,5,7,9} = S.

The negative of the negative of an open statement is logically equivalent to the open statement itself.
Let p(x) be some open statement with universe U. Let b be any object in that universe.
   If p(b) = T then ~p(b) = F. Hence ~~p(b) = T.
   If p(b) = F then ~p(b) = T. Hence ~~p(b) = F.
Since b is any object in U, it can be said that p(x) and ~~p(x) assign the same truth value to each object in U. Therefore, p(x), ~~p(x) are equivalent open statements. If   p(x): x is in S,   then ~p(x): x is not in S,  and then   ~~p(x): x is back in S.

It was mentioned in the previous section that the empty set Φ is a subset of any universe U. Therefore, every object is not in Φ and therefore must be in ~Φ.   The complement of the empty set is the entire universe.:   ~Φ = U\Φ = U.   Similarly, the complement of the universe is the empty set:   ~U = U\U = Φ. Hence, every subset in a universe has a complement in that same universe

-----

Whereas a unary operation accepts only one thing (and produces a second thing) a binary operation accepts two things and produces a third thing. For example, the arithmetic operation of addition accepts 3 and 5 and produces 8. The operation of multiplication accepts 3 and 5 and produces 15. In the case of sets, each operation on sets accepts two given sets, often designated as S₁, S₂, and produces a single set from them, all in the same universe. At the same time there are two open sets whose truth sets are the given sets. In any case, there exist the two trivial open statements

[2.2] (Intersection) The intersection of two sets in the same universe consists of all objects that are in both sets.
Notation1: S₁ /\ S₂ = {x in U | x is in S₁ and x is in S₂}.
Notation2: x is in S₁ /\ S₂   if and only if   x is in S₁ and x is in S₂       (a true statement about universally true equivalence)
Notation3: In U, if S₁ is a truth set and S₂ is a truth set then all objects in S₁ /\ S₂ are assigned TT.

The common notation for intersection is an upside down U:
                                             
But for typographical reasons, the notation /\ will be used in all volumes to denote intersection.

Example: In N₉ the intersection   {2,3,4,5,6} /\ {4,5,6,7,8} = {4,5,6}.   Simply go through the two sets {2,3,4,5,6}, {4,5,6,7,8} and select those numbers in both sets:

For a determination of the truth set of a conjunction of open statements click here.

From the wording of definition [2.2] it is obvious that the intersection of two sets is the same no matter which set is written first.

[2.3] (Commutativity) The operation of intersection is commutative.
Notation:   S₁ /\ S₂ = S₂ /\ S₁.

But what happens to the intersection if one or both sets are empty? For example, what is the intersection {2,3,4,5,6} /\ Φ? The open statements

In general, if either of two sets is empty then their intersection is empty:    S /\ Φ = Φ,      Φ /\ S = Φ,      Φ /\ Φ = Φ
By definition, the open statement    x is in Φ    is universally false. Therefore, any conjunction involving that phrase will have to be universally false.

The intersection of any set and the universe is equal to that set:.    S /\ U = S,      U /\ S = U,      U /\ U = U
Click here to see the an argument supporting this statement.

These last statements about intersection are similar to statements about numbers and multiplication:

The intersection of more than two sets is defined in the obvious way:

[2.4] The intersection of sets in the same universe consists of all objects that are in all the given sets
Notation: x is in S₁ /\ S₂ /\ S₃ /\ ...     if and only if     x is in S₁   and   x is in S₂   and   x is in S₃   and ...

Parentheses surround an operation to be done first. Short arguments can be made to support the two equalities

[2.5] (Associativity) The operation of intersection is associative.
Notation: (S₁ /\ S₂) /\ S₃ = S₁ /\ (S₂ /\ S₃).

---------


The adjacent figure shows the union of a set and another set. It is the combined interiors of the two sets, including their intersection if they overlap.

[2.6] (union) (In the same universe) the union of two sets is the collection of all objects in either set (or both)
Notation1: S₁ \/ S₂ = {x in U | x is in S₁ or x is in S₂}.
Notation2: x is in S₁ \/ S₂   if and only if   x is in S₁ or x is in S₂       (a true statement about universally true equivalence)
Notation3: In U, if S₁ is a truth set and S₂ is a truth set then all objects in S₁ \/ S₂ are all objects not assigned FF.

The common notation for union is a U:
                                             
But for typographical reasons, the notation \/ will be used in all volumes to denote union.

Example: In N₉ the union   {2,3,4,5,6} \/ {4,5,6,7,8} = {2,3,4,5,6,7,8}.   Simply go through the two sets {2,3,4,5,6}, {4,5,6,7,8} and select those numbers in either set, but nothing outside both sets.

From the notation following [2.6] it obvious that that an alternation of open statements determines the union of sets. And in doing so, it shows how a union assigns truth values to each object in the universe. For a determination of the truth set of an alternation of open statements click here.

Notation3 of [2.6] provides a negative definition of a union of two sets. The following is actually equivalent to [2.6] (see [5.6c] in Volume A, chapter 1):

[2.7] (Negative definition a union) In a universe the objects outside a union of sets are exactly those outside every set.
Notation1: x is not in (S₁ \/ S₂)   if and only if   x is not in S₁ and x is not in S₂.
Notation2: ~(S₁ \/ S₂) = ~S₁ /\ ~S₁.    (Complement of a union of two sets in a common universe is equal to the intersection of their complements.)
Notation3 (De Morgan's law): ~(p(x) or q(x)) <==> ~p(x) and ~q(x)

-----

Click here for a discussion of duality between intersection and union.
The duality of notation 3 above is also called De Morgan's law:

[2.8] (Commutativity) The operation of union is commutative.
Notation:   S₁ \/ S₂ = S₂ \/ S₁.

-----

But what is the union {2,3,4,5,6} \/ Φ involving the empty set? The open statements

If 1 represents the universe U and 0 represents Φ then the representations of the four intersections of these two sets produce a strange (Boolean) addition table for 1 and 0. Click here to see this discussion.

The union of more than two sets is defined in the obvious way.

[2.9] The union of sets in the same universe consists of all objects that are in any of the sets
Notation: x is in (S₁ \/ S₂ \/ S₃ \/ ...)     if and only if     x is in S₁   or   x is in S₂   or   x is in S₃   or ...

It is sometimeds useful to discuss objects not in the union of two sets. It is a form of De Morgan's law.

[2.10] (Outside a union of sets) An object is not in a union of sets all in the same universe if and only if that object is in none of the sets.
Notation:
x is not in S₁ \/ S₂ \/ S₃ \/ ...     if and only if     all the open statements   x is in x is in S₁   or   x is in S₂   or   x is in S₃   or ...

Short arguments can be made to support the two equalities

[2.11] (Associativity) The operation of union is associative.
Notation: (S₁ \/ S₂) \/ S₃ = S₁ \/ (S₂ \/ S₃).

------

Occasionally useful is a type of subtraction of sets. Intuitively speaking, the subtraction of a second set set from a first set removes some of the objects in the first set.

[2.12] (Set difference) The result of a set subtraction of a second set from a first set is the collection of all objects in the first set that is not in the second set. The result is often called the set difference.
Notation: x is in (S₁\ S₂)   if and only if   x is in S₁ and x is not in S₂.

Intuitively speaking, the second set takes away objects from the first set. Also, it is the remaining part of the first set after the intersection of the two sets is removed.

Example: Let N₉ be the universe.

Let S be a any set in a universe U.
As expected, S\Φ = S because nothing is taken away from S.
But S\S = Φ because everything is taken away from S.
And for the same reason, S\U = Φ

Section 3:   Some relationships between two sets in the same universe

Any object in the universe that makes a relation between sets false is called a counterexample to the relation.

Sets are determined by the objects in them. The sets S₁ and S₂ are truth sets of the trivial open statements

[3.1] (Equality of sets) Two sets in the same universe are equal if and only if they contain exactly the same elements.
Notation 1: S₁ = S₂   if and only if   the open statements x is in S₁, x is in S₂ assign equal truth values to each object in the universe.
Notation 2: S₁ = S₂   if and only if   the equivalence   x is in S₁ <==> x is in S₂   is universally true.

Example: In universe N₉, {5,7,6,8,4} = {4,5,6,7,8} because they contain exactly the same numbers. Any number in N₉ is in both of them (is assigned TT) or it is in neither of them (is assigned FF). But notice that this shows the listing of the objects in a set can be written in different arrangements of the same objects (permutations).

Click here to see a discussion supporting the fact that all empty sets are equal. In other words, in any universe there is only one empty set. It is unique.

---------

For equality (&&) assignes equal truth values to each object in the universe. The other extreme is that (&&) assigns opposite truth values. But this means that each set is the complement of the other.

[3.2] (Complementary sets) Two sets inside the same universe are complementary if and only if one is the complement of the other.

In Fig 2, S₂ contains everything not in S₁ and conversely. Every object in the universe is assigned a pair of opposite truth values: TF or FT from the open sets in (&&).

Example: Inside the universe N₉ the two sets {1,3,5,7,9} and {2,4,6,8} are complementary.

[3.3] Two sets in the same universe are complementary if and only they satisfy both both of the following conditions:
   (a) their union is the universe;
   (b) their intersection is empty.

Notice that {1,3,5,7,9} /\ {2,4,6,8} = Φ   and that   {1,3,5,7,9} \/ {2,4,6,8} = N₉, the universe.

Click here for a discussion supporting [3.3].

------

Relax condition (a) in [3.3] to get a more general situation as shown in Fig 3. The two sets do not overlap. There is nothing in their intersection. No point in the universe can be assigned TT by the open statements (&&). However if their union is not the entire universe then some objects outside the union will be assigned FF.

[3.4] (Disjoint sets) In the same universe a pair of sets are disjoint   if and only if   their intersection is empty
Notation: S₁, S₂   are disjoint if and only if the open statements

A pair of complementary sets are always disjoint, but not conversely. Fig 3 shows disjoint sets that are not complementary.
Notice that in definition [3.4] the word "object" is not used. The definition is made at a higher level using only "sets."

-------

Fig 4 shows an important situation: all of one set may be part of another set. This means that all the points in first set are also in the second set.

[3.5] (Inclusion) One set is included in a second set if and only if every object in the first set is also in the second set.
Notation: S₁   <   S₂   if and only if   x is in S₁ => x is in S₂.

If one set is included in a second set then the first set is called a subset of the second set. Obviously, every set in a universe is a subset of that universe.

Example: Let the universe N₉ = {1,2,3,4,5,6,7,8,9}. It is obvious that {4,5,6} is included in {3,4,5,6,7,8}.
Also the implication   if x is in {4,5,6} then x is in {3,4,5,6,7,8}   is obviously .true.

If two sets are equal then the content of either set is included in the other. If one set is equal to a second set then the first set is included in the second set. The underline in the notation   < allows inclusion to extend to equality:

The reverse of inclusion is containment.
A set S₂ contains a set S₁ if and only if S₁ is included in S₂
Notation: S₂ >  S₁

If one set contains another then the first set is sometimes called a superset of the second set.

If S₁ = S₂ then trivially everything in S₁ is in S₂. Therefore every set is included it itself. It is a subset of itself.
The symbol   <   is used in these discussions to mean inclusion but not equality. It is called strict inclusion. The statement

There is also strict containment, S₂ > S₁. In this situation S₂ contains all of the objects in S₁ plus one or more objects not in S₁. The statement

Section 4:   More on inclusion, implication and proof

In Fig 4 and Fig 1, set S₁ is entirely inside set S₂. But in Fig 5, set S₁ is not entirely inside set S₂. Part of S₁ lies outside of S₂. There are points in that part. Any of those points is called a counterexample to the inclusion S₁ < S₂. If point b is one of those counterexamples, then (&&) assigns truth values TF to point b. That point b is also a counterexample to (the universality of) the implication

The following negative statement is equivalent to definition [3.5]. It is seemingly trivial, yet is sometimes useful as a basis for arguments supporting inclusions and universally true implications of open statements.

[4.1] (Inclusion) One set is included in another if and only if there are no counterexamples to this inclusion.
Notation1: S₁   <   S₂   if and only if   there exists no object b such that b is in S₁ and b is not in S₂.
Notation2: S₁ < S₂   if and only if   no object in the universe is assigned TF by the open statements (&&) respectively.

Example: Again let the universe be N₉ = {1,2,3,4,5,6,7,8,9}.
A counterexample to {1,2,3,4} < {3,4,5,6,7,8} is 1. So is 2. Each is in {1,2,3,4} but not in {3,4,5,6,7,8}. The remaining numbers 5,6,7,8,9 in U do not qualify as counterexamples, because none of them are in {1,2,3,4}. Therefore, they cannot produce false components. The statement about inclusion {1,2,3,4} < {3,4,5,6,7,8} is false because there are counterexamples.

The following statement provides a useful method to prove two sets are equal.

[4.2] (Equality from reverse inclusions) If two sets are included in each other then the two sets are equal.
Notation1: if   S₁   <   S₂   and   S₂   <   S₁    then    S₁   =   S₂
Notation2: if   p(x) ==> q(x) and q(x) ==> p(x)   then   p(x), q(x) are equivalent.

The inclusions if   S₁   <   S₂   and   S₂   <   S₁   prevent any object from being assigned TF or FT. Therefore every object is assigned equal truth values, TT or FF, which is what happens only with equal sets and their trivial equivalent open statements.

The implication q(x) ==> p(x) is called the converse of the implication p(x) ==> q(x). The converse of a (universally) true implication may or may not be (universally) true. For example, in universe N₉ the implication

Statement [4.1] can be used to prove that the empty set Φ is a subset of any set S in any universe U:

This argument uses a typical approach for denying the existance of a counterexample: assume that there is a counterexample and then arrive at an impossible situation because of that assumption. Such an argument is called an indirect argument.

Both the empty set and the set itself are called the trivial subsets of the set itself. Often they are less interesting than the other subsets called proper subsets.

It is true that 2 < 5. But it is also true that -5 < -2. Negation of numbers interchanges the sides of an inequality. (This can be proven by subtraction of the smaller number from the larger.)
It is obvious that if a first set is included in a second set, then objects outside of the second set must also be outside the first set. But being outside a set is the same as being in the complement of that set. Let the two sets be A and B. Then

[4.3] (Inclusion from complements) A first set is included in a second set   if   the complement of a second set is included in the complement of the first.
Notation1: if   ~S₂ < ~S₁   then   S₁ < S₂.
Notation2: if   ~q(x) ==> ~p(x)   then   p(x) ==> q(x).

The implication ~q(x) ==> ~p(x) is called the contrapositive of the implication p(x) ==> q(x). It can be proven that an implication and its contrapositive always have the same truth value. Consider the implications

In many situations it is possible to combine two inclusions into a single inclusion. It presupposes all sets and open statements have the same universe. (A long telescope can be compressed into a smaller, compact device that is easier to transport.)

[4.4] (Telescoping property of two inclusions) In any universe, if a first set is included in a second set, and the second set is included in a third set, then the first set is included in the third set.
Notation1: if S₁ < S₂ and S₂ < S₃ then S₁ < S₃.
Notation2: if x is in S₁ ==> x is in S₂   and   x is in S₂ ==> x is in S₃   then   x is in S₁ ==> x is in S₃.
Notation3: for any open statements p(x), q(x), r(x) with a common universe, if the implications   p(x) ==> q(x)   and   q(x) ==> r(x)   are both universally true,   then the implication   p(x) ==> r(x)   is universally true.

In notation2 there are three implications involved:

In notation3 let S₁, S₂, S₃ be the truth sets of p(x), q(x), r(x) respectively. Then the three implications

There is an obvious extension of [4.4] to more than two inclusions. It is discussed in the next section. (But see [5.3] there.)

Section 5:   Families of sets

The following is an example:
In the universe N₉ the following are subsets of this universe:

Since the empty set Φ and the universe U are genuine subsets of U, then Φ and U may be members of some families of subsets of U.

In the universe of the plane in plane geometry, straight lines are special sets of points. Therefore, any collection of straight lines is a family of sets. The family of all straight lines is a example of an infinite family of sets. The familiar properties of straight lines can be restated as properties of this family. Click here for more discussion of this geometric family of straight lines.

-----

For any given set, there is a unique family of all subsets of that set. For example, all the subsets of S={1,3,5} are

[5.1] (Size of the power set) If a set has n objects then its power set has 2ⁿ subsets in it.

Examples: There are 2³ = 8 subsets of {1,2,3}. There are 2⁹ = 512 subsets of the set N₉.

A discussion supporting [5.1] will be given in a later volume. The attempt to extend this statement to the power set of infinite sets like N leads to an interesting concept of transfinite numbers and their strange arithmetic.

Let the reader show that [5.1] is true even when the given set is the empty set Φ.

-----

If S₁, S₂, ..., S_n are n subsets of a common universe U, then they form a finite family of subsets of U:

     The conjunction   p₁(x)   and   p₂(x)   and   ...   and   p_n(x)   assigns a T to an object in U   if and only if
   every open statement (**) assigns a T to that same object.


[b] The union   S₁ \/ S₂ \/ ... \/ S_n   consists of all objects in that are in one or more subsets (*).
   x is in ( S₁ \/ S₂ \/ ... \/ S_n)   if and only if   (x is in S₁) or (x is in S₂) or ... or (x is in S_n)
     The alternation   p₁(x)   or   p₂(x) or and   ...   or   p_n(x)   assigns a T to an object in U   if and only if
   one or more open statement (**) assign a T to that same object.


[c] A family of sets covers a given set if and only if the given set is included in the union of all sets in the family.
     The family (*) covers set S   if and only if   S   is included in the union S₁ \/ S₂ \/ ... \/ S_n.
     (**) covers   S     if and only if   x is in S   implies   x is in S₁ or x is in S₂ or ... or x is in S_n.

Example: In N₉ if   S={4,5,9}   and   S₁={1,2},   S₂={4,5,6},   S₃={8,9}   then   {S₁, S₂, S₃}   covers   S
because   S   is included in   S₁ \/ S₂ \/ S₃ = {1,2,4,5,6,8,9}.

[d] A family of sets is disjoint if and only every pair of sets in the family is disjoint.
     The family (*) is disjoint   if and only if   for every distinct i,j, S_i /\ S_j = Φ

Example1: In N₉ if   S₁={1,3,5},   S₂={2},   S₃={6,8},  S₄={4},   then   {S₁, S₂, S₃, S₄}   is a family of disjoint sets.
Example2: A family of parallel lines is disjoint.

[e] A family of subsets of a given set is a partition of a given set if and only if the family is disjoint and covers the given set.

In other words, a family of sets is a partition of a given set   if and only if   the family satisfies three conditions:
  (i) every set in the family is included in the given sett;
  (ii) The family is a disjoint family;
  (iii) The family covers the given set.

[f] A family of sets is an increasing chain of sets if each set is included in the next set (except for the last set).
Notation: The family   {S₁, S₂, ..., S_n}   is an increasing chain of sets if and only if

Often the conjunctions are omitted:
Increasing chain: S₁ < S₂ < S₃ < ... < S_n
Strictly increasing chain: S₁ < S₂ < S₃ < ... < S_n
Decreasing chain: S₁ > S₂ > S₃ > ... > S_n
Strictly decreasing chain: S₁ > S₂ > S₃ > ... > S_n

If all the inclusions and containments are true, then the chains telescope into single relations:
  S₁ < S_n,    S₁ < S_n,    S₁ > S_n,    S₁ > S_n.




-----

Consider blankets on a very large bed. to cover the entire bed it may require several blankets that may overlap. The bed is under the combined collection of blankets. A similar situation may exist for some given set in a universe. A set may be "covered" by other sets in that universe. Notice that W does not cover the whole universe N₉, because 3 and 7 are not in any of the sets in W. Also the set {1,2} is in W, but it does not even intersect S. In an intuitive sense, {1,2} is not essential to the covering. (But it still is a member of the covering.)

It is quite possible that all the sets in a covering be disjoint. Then the family is called a disjoint covering of the set. The disjoint covering is a special family of sets. Intuitively speaking, the set is broken down into pieces which are subsets in the family.

[5.4] (Partitions) A partition of a set is a disjoint covering of the set by its own subsets.

In other words, a partition separates the entire given set into a family of disjoint subsets. The union of all those subsets is the given set. In the universe N₉ an example of a partition of S = {2,3,4,5,6,7,8} is the family

The adjacent figure shows a partition of the interior of a circle into colored subsets (sub-arias).

Sometimes it is useful to partition a large set into a family of smaller subsets which can be more easily measured. Nothing is lost during the partitioning process. For example, suppose a large number of coins in a pile are to be counted. Partition the coins into several smaller piles. Have each of the smaller piles counted by different people. Add together the number of coins in each smaller pile.

Suppose family

Example: if

[5.5] (Telescoping sets) For a family of n increasing sets, the first set is included in the last set.
Notation1: if S₁ < S₂ < S₃ < S₄ < ... < S_n then S₁ < S_n.
Notation2: if p₁(x) ==> p₂(x) ==> p₃(x) ==> ... ==> p_n(x) then p₁(x) ==> p_n(x).

A discussion supporting this statement will be given later after a discussion of positive integers, in particular mathematical induction. But it is pattered after the supporting statements for [4.4].