22 November 2002

All in the Family

by George E. Hrabovsky, President, MAST

Where We Have Been

Up to now we have laid the foundations of how mathematics is done. We have discussed sets, logic, proof techniques, and quantifiers. Last column we covered the definition and theory of union, intersection, difference, and symmetric difference.

Where Will We Go in This Column

In this column we expand our discussion of sets to groupings of sets.

Families of Sets

In the last column we established that set could not be an element of itself. This begs the question, "What is a set with sets as its elements?" A special term has been devised to account for a set composed of other sets, it is called a family of sets or just family. We will denote families by scripted upper case letters. So, we have sets denoted A, B, C, etc. and we have families denoted ÷p, !,, ÷r, etc.

Indexed Sets

Let us assume that we have some family of sets ÷p, composed of a number of sets. We will fall back on tradition and call this number n. Each set has a place in the list of sets from 1 to n. This number will appear as a subscript to place the set as first, second, and so on up to the nth set. We can write this symbolically,

÷p = {A _ 1, A _ 2, A _ 3, ..., A _ n} .

We can write a special set,

I = (1, 2, 3, ..., n)

called the indexed set. We can then write,

FormBox[RowBox[{÷p = {A _ i | i ∈ I}, ,, RowBox[{Cell[       ... bsp;           ], (1)}]}], TraditionalForm]

this is called an indexed family of sets.

Union of a Family

Given (1), we can extend the definition of a union to an entire indexed family like this,

FormBox[RowBox[{Underscript[∪, i ∈ I] A _ i, =, RowBox[{RowBox[{{x | (∃ i &# ... p;           ]}], (2)}]}], TraditionalForm]

If there is no confusion about the indexed set, we can write this

FormBox[RowBox[{∪ A _ i, =, RowBox[{{x | (∃ i ∈ I) (x ∈ A _ i)}, ., Cell[]}]}], TraditionalForm]

Here are some pertinent theorems,

Theorem 6-1:

∪ ∅ = ∅ .

Proof: By the definition of the empty set ¬ (∃ x) (x ∈ ∅). Hence, by (2) we know that ∪ ∅ = {x | (x ∉ ∅)}. This is the same as ∅. Thus the theorem is proved.

Theorem 6-2:

∪ {∅} = ∅ .

Proof: If we say that a set A ∈ {∅} then A = ∅. This implies that x ∉ A. By (2) we have x ∉ ∪ {∅}. This is the same as ∅. Thus the theorem is proved.

Theorem 6-3:

∪ {A} = A .

Proof: I leave this as an exercise to the reader. You should think about (2) and the definition of the indexed set in this case.

Theorem 6-4:

∪ {A ∪ B} = {∪ A} ∪ {∪ B} .

Proof: By (2) we have ∪ {A ∪ B} = {x | (x ∈ {A ∪ B})}. By the definition of union, {x | (x ∈ {A ∪ B})} = {x | (∃ x) (x ∈ A ∨ x ∈ B)}. We can rewrite this, {x | (∃ x) (x ∈ A) ∨ (∃ x) (x ∈ B) }. By (2) this becomes x ∈ ∪ A ∨ x ∈ ∪ B. By the definition of union we then have x ∈ {∪ A} ∪ {∪ B}. Thus the theorem is proved.

Theorem 6-5:

A ⊆ B = {∪ A} ⊆ {∪ B} .

Proof: I leave this as an exercise using (2) and the definition of a subset.

Theorem 6-6:

A ∈ B = A ⊆ ∪ B .

Proof: I leave this as an exercise using (2), the definition of an element, and the definition of a subset.

Theorem 6-7:

(∀ A) (A ∈ B ==> A ⊆ C) ==> ∪ B ⊆ C .

Proof: I leave this as an exercise using (2), the definition of an element, and the definition of a subset.

Theorem 6-9:

(∀ A) (A ∈ B ==> A ∩ C = ∅) ==> ∪ B ∩ C = ∅ .

Proof: I leave this as an exercise using (2), the definition of an element, the definition of the empty set, and the definition of intersection.

Intersection of a Family

Given (1), we can extend the definition of an intersection to an entire indexed family like this,

FormBox[RowBox[{Underscript[∩, i ∈ I] A _ i, =, RowBox[{RowBox[{{x | (∀ i &# ... p;           ]}], (3)}]}], TraditionalForm]

If there is no confusion about the indexed set, we can write this

FormBox[RowBox[{∩ A _ i, =, RowBox[{{x | (∀ i ∈ I) (x ∈ A _ i)}, ., Cell[]}]}], TraditionalForm]

Here are some pertinent theorems,

Theorem 6-10:

∩ ∅ = ∅ .

Proof: Assume ∩ ∅ != ∅. This implies that (∃ x) (x ∈ ∩ ∅), thus by (3) we have x ∈ ∅. Thus is an absurd result. Thus the theorem is proved.

Theorem 6-11:

∩ {∅} = ∅ .

Proof: Assume ∩ {∅} != ∅. This implies that (∃ x) (x ∈ ∩ {∅}), thus by (3) we have x ∈ ∅. Thus is an absurd result. Thus the theorem is proved.

Theorem 6-12:

∩ {A} = A .

Proof: I leave this as an exercise for the reader using (3).

Theorem 6-13:

A ⊆ B ∧ (∃ C) (C ∈ A) ==> ∩ B ⊆ ∩ A .

Proof: Let x ∈ ∩ B. Then (∀ C) (C ∈ A) ==> x ∈ C. By the hypothesis we can infer that C ∈ A ==> C ∈ B. So (∀ C) (C ∈ A) ==> x ∈ C. This in turn implies that x ∈ ∩ A. This proves the theorem.

Theorem 6-14:

A ∈ B = ∩ B ⊆ A .

Proof: I leave this as an exercise for the reader using (3), the notion of an element and the definition of a subset.

Theorem 6-15:

A ∈ B ∧ A ⊆ C ==> ∩ B ⊆ C .

Proof: I leave this as an exercise for the reader using (3), the definition of the conjunction, the notion of an element, and the definition of a subset.

Theorem 6-16:

A ∈ B ∧ A ∩ C = ∅ ==> (∩ B) ∩ C = ∅ .

Proof: I leave this as an exercise for the reader using (3), the definition of the conjunction, the notion of an element, the definition of intersection, and the definition of the empty set.

Theorem 6-17:

A ∩ ∪ B _ i = ∪ (A ∩ B _ i)

Proof: I leave this as an exercise for the reader using (2) and the definition of intersection.

Theorem 6-18:

A ∪ ∩ B _ i = ∩ (A ∪ B _ i)

Proof: I leave this as an exercise for the reader using (3) and the definition of union.

Theorem 6-19:

∩ A = ∪ A .

Proof: I leave this as an exercise for the reader using (2) and (3).

Suggested Practice Problems

1. Invent three families of sets.
2. For each family develop an expression for its indexed set.
3. Prove Theorem 6-3.
4. Prove Theorem 6-5.
5. Prove Theorem 6-7.
6. Prove Theorem 6-8.
7. Prove Theorem 6-9.
8. Prove Theorem 6-12.
9. Prove Theorem 6-14.
10. Prove Theorem 6-15.
11. Prove Theorem 6-16.
12. Prove Theorem 6-17.
13. Prove Theorem 6-18.
14. Prove Theorem 6-19.

Converted by Mathematica  (November 19, 2002)