In Section of Element and set, the notation A⊆B was defined to mean that set A is contained within set B. When we wish to refer to the symbol ⊆without specific reference to any sets, we call it set inclusion just as (+) is referred to as union. The laws in Section (Fundamental laws.)refer only to intersection, union, and complementation. Set inclusion also satisfies some basic laws which are interesting and useful. These laws can be verified directly from the definition or by making use of Venn diagrams.

Still another approach is to make use of the fact pointed out in Section (The combination of sets.)  that X ⊆ Y if and only if XY' = 0. The proofs given here are based onthe definition of c.

THEOREM 1. If X ⊆Y and Y ⊆ Z, then X ⊆ Z. (This is known as the transitive property of inclusion.)

Proof. Let x be an arbitrary element of X. Then since X ⊆Y we have,  by definition, x ∈ Y. Similarly, from Y ⊆Z it follows that x ∈ Z. But x was an arbitrary element of X and hence X ⊆ Z.

THEOREM 2. If X ⊆Y and X c Z, then X ⊆ YZ.

Proof. Let x be an arbitrary element of X. Then from X ⊆Y it follows that x ∈ Y, and from X ⊆ Z, it follows that x ∈Z. Together, these statements imply that x ∈YZ by the definition of intersection, and hence X⊆YZ.

THEOREM 3. If X ⊆ Y, then X⊆Y + Z for any set Z.

Proof. Since Y ⊆ Y + Z by the definition of union, this theorem follows at once from Theorem 1.

THEOREM 4. X c Y if and only if Y' ⊆ X'.

Proof. First, assume that X ⊆Y and let y' be an arbitrary element in Y.

Then y' is not an element in Y, by definition of complement. But every element in X is an element in Y and hence y' is not an element in X.

Hence y' must be an element in X'. Since y' represented any element of Y', it follows that Y' ⊆X'.

Next, assume that Y' ⊆ X. Then by the first part of this proof,  (X')' ⊆(Y')' which reduces to X ⊆Y, by the law of double complementation. This completes the proof of the theorem.

These theorems, which were easy to prove, have some rather interesting applications, one of which is to problems of a logical nature. although we are not primarily interested in logic in this chapter, the algebra of logic and the algebra of sets are very closely related. For instance, one of the basic laws of logic is the law of syllogism, which is equivalent to Theorem 1.

A classic example of the use of this law is the following.

EXAMPLE 1. Given that Socrates is a man, and that all men are mortal, it is required to show that Socrates is mortal. Although this type of argument is so familiar that any proof may seem absurd, the necessary steps in a formal proof using Theorem 1 are given to illustrate the general method.

Solution. Let the universal set be the set of all animate things; let X denote the set of all men, Y the set of all mortal things, and S the unit set consisting of Socrates alone. We are given that S ⊆X and X ⊆F. By Theorem 1 it follows that S⊆Y, which is the desired conclusion that Socrates is mortal.

The principle involved in the law of syllogism is familiar to everyone.

Problems of similar type referring to Theorem 2, 3, or 4 are not quite so

familiar. The following example and some of the problems in the exercises

use several of these theorems in combination. These problems are artificial,

but they illustrate the way in which the algebra of sets can help in inter-

preting complicated sets of statements. The use of symbolic notation

makes trivial the forming of logical conclusions that would be difficult

otherwise.

EXAMPLE 2. What conclusion can be drawn from the following statements?

(a) A man who is unhappy is not his own boss.

(b) All married men have responsibilities.

(c) Every man is either married, or is his own boss (or both).

(d) No man with responsibilities can fish every day.

Solution. Let the universal set be the set of all men, and denote other sets as follows:

                  H is the set of happy men,

                  B is the set of men who are their own bosses,

                  M is the set of married men,

                 R is the set of men with responsibilities,

                 F is the set of men who fish every day.

Statement (a) translates immediately into H' ⊆ B', but by applying Theorem 4 we may also write the statement in symbols as follows:

(a) B ⊆ H.

Statement (b) tells us that M ⊆ R or, equally well, by Theorem 4 we have

(b) R' ⊆M'.

Statement (c) gives that M+ B = 1, or referring to the equivalence of this statement with a condition of inclusion, we obtain

(c) M'⊆B.

Finally, from (d) we obtain the fact that RF = 0, which is equivalent to

(d) F ⊆R'.