∀a∀b[a ⊆ b ” ∀x(x ∈ a ’ x ∈ b)]

It doesn™t make much di¬erence which way you think of it. Di¬erent people

prefer di¬erent understandings. The ¬rst is probably the most common, since

it keeps the o¬cial language of set theory pretty sparse.

Let™s prove a proposition involving the subset relation that is very obvious,

but worth noting.

Proposition 2. For any set a, a ⊆ a.

Proof: Let a be an arbitrary set. For purposes of general conditional

proof, assume that c is an arbitrary member of a. Then trivially (by

reiteration), c is a member of a. So ∀x(x ∈ a ’ x ∈ a). But then

we can apply our de¬nition of subset to conclude that a ⊆ a. Hence,

∀a(a ⊆ a). (You are asked to formalize this proof in Exercise 15.12.)

The following proposition is very easy to prove, but it is also extremely

useful. You will have many opportunities to apply it in what follows.

Proposition 3. For all sets a and b, a = b if and only if a ⊆ b and b ⊆ a.

In symbols:

∀a∀b(a = b ” (a ⊆ b § b ⊆ a))

Proof: Again, we use the method of universal generalization. Let a

and b be arbitrary sets. To prove the biconditional, we ¬rst prove

that if a = b then a ⊆ b and b ⊆ a. So, assume that a = b. We need

to prove that a ⊆ b and b ⊆ a. But this follows from Proposition 2

and two uses of the indiscernability of identicals.

Section 15.2

414 / First-order Set Theory

To prove the other direction of the biconditional, we assume that

a ⊆ b and b ⊆ a, and show that a = b. To prove this, we use the

Axiom of Extensionality. By that axiom, it su¬ces to prove that a

and b have the same members. But this follows from our assumption,

which tells us that every member of a is a member of b and vice versa.

Since a and b were arbitrary sets, our proof is complete. (You are

asked to formalize this proof in Exercise 15.13.)

Remember

Let a and b be sets.

1. a ⊆ b i¬ every element of a is an element of b.

2. a = b i¬ a ⊆ b and b ⊆ a.

Exercises

15.7 Which of the following are true?

1. The set of all US senators ⊆ the set of US citizens.

2. The set of all students at your school ⊆ the set of US citizens.

3. The set of all male students at your school ⊆ the set of all males.

4. The set of all John™s brothers ⊆ the set of all John™s relatives.

5. The set of all John™s relatives ⊆ the set of all John™s brothers.

6. {2, 3, 4} ⊆ {1 + 1, 1 + 2, 1 + 3, 1 + 4}

7. {“2”, “3”, “4”} ⊆ {“1 + 1”, “1 + 2”, “1 + 3”, “1 + 4”}

15.8 Suppose that a1 and a2 are sets, each of which has only the Washington Monument as a

member. Prove (informally) that a1 = a2 .

15.9 Give an informal proof that there is only one empty set. (Hint: Use the Axiom of Extensionality.)

15.10 Give an informal proof that the set of even primes greater than 10 is equal to the set of even

primes greater than 100.

15.11 Give an informal proof of the following simple theorem: For every set a, … ⊆ a.

Chapter 15

Intersection and union / 415

15.12 In the ¬le Exercise 15.12, you are asked to give a formal proof of Proposition 2 from the

‚ de¬nition of the subset relation. The proof is very easy, so you should not use any of the Con

rules. (You will ¬nd the symbol ⊆ if you scroll the predicate window in the Fitch toolbar.)

15.13 In the ¬le Exercise 15.13, you are asked to give a formal proof of Proposition 3 from the Axiom

‚ of Extensionality, the de¬nition of subset, and Proposition 2. The proof is a bit more complex,

so you may use Taut Con if you like.

Section 15.3

Intersection and union

There are two important operations on sets that you have probably seen

before: intersection and union. These operations take two sets and form a

third.

De¬nition Let a and b be sets.

1. The intersection of a and b is the set whose members are just those intersection (©)

objects in both a and b. This set is generally written a © b. (“a © b” is a

complex term built up using a binary function symbol © placed in in¬x

notation.2 ) In symbols:

∀a ∀b ∀z(z ∈ a © b ” (z ∈ a § z ∈ b))

2. The union of a and b is the set whose members are just those objects in union (∪)

either a or b or both. This set is generally written a ∪ b. In symbols:

∀a ∀b ∀z(z ∈ a ∪ b ” (z ∈ a ∨ z ∈ b))

At ¬rst sight, these de¬nitions seem no more problematic than the de¬ni-

tion of the subset relation. But if you think about it, you will see that there

is actually something a bit ¬shy about them as they stand. For how do we

know that there are sets of the kind described? For example, even if we know

that a and b are sets, how do we know that there is a set whose members

are the objects in both a and b? And how do we know that there is exactly

one such set? Remember the rules of the road. We have to prove everything

from explicitly given axioms. Can we prove, based on our axioms, that there

is such a unique set?

2 Function

symbols are discussed in the optional Section 1.5. You should read this section

now if you skipped over it.

Section 15.3

416 / First-order Set Theory

It turns out that we can, at least with the naive axioms. But later, we

will have to modify the Axiom of Comprehension to avoid inconsistencies.

The modi¬ed form of this axiom will allow us to justify only one of these two

operations. To justify the union operation, we will need a new axiom. But we

will get to that in good time.

Proposition 4. (Intersection) For any pair of sets a and b there is one and

existence and

uniqueness of a © b only one set c whose members are the objects in both a and b. In symbols:

∀a ∀b ∃!c ∀x(x ∈ c ” (x ∈ a § x ∈ b))

This proposition is actually just an instance of Proposition 1 on page 409.

Look back at the formula displayed for that proposition, and consider the

special case where z1 is a, z2 is b, and P (x) is the w¬ x ∈ a § x ∈ b. So

Proposition 4 is really just a corollary (that is, an immediate consequence) of

Proposition 1.

We can make this same point using our brace notation. Proposition 1

guarantees a unique set {x | P (x)} for any formula P (x), and we are simply

noting that the intersection of sets a and b is the set c = {x | x ∈ a § x ∈ b}.

Proposition 5. (Union) For any pair of sets a and b there is one and only

existence and

uniqueness of a ∪ b one set c whose members are the objects in either a or b or both. In symbols:

∀a ∀b ∃!c ∀x(x ∈ c ” (x ∈ a ∨ x ∈ b))

Again, this is a corollary of Proposition 1, since c = {x | x ∈ a ∨ x ∈ b}.

This set clearly has the desired members.

Here are several theorems we can prove using the above de¬nitions and

results.

Proposition 6. Let a, b, and c be any sets.

1. a © b = b © a

2. a ∪ b = b ∪ a

3. a © b = b if and only if b ⊆ a

4. a ∪ b = b if and only if a ⊆ b

5. a © (b ∪ c) = (a © b) ∪ (a © c)

6. a ∪ (b © c) = (a ∪ b) © (a ∪ c)

We prove two of these and leave the rest as problems.

Chapter 15

Intersection and union / 417

Proof of 1: This follows quite easily from the de¬nition of intersec-

tion and the Axiom of Extensionality. To show that a © b = b © a, we

need only show that a © b and b © a have the same members. By the

de¬nition of intersection, the members of a © b are the things that

are in both a and b, whereas the members of b© a are the things that

are in both b and a. These are clearly the same things. We will look

at a formal proof of this in the next You try it section.

Proof of 3: Since (3) is the most interesting, we prove it. Let a and

b be arbitrary sets. We need to prove a © b = b i¬ b ⊆ a. To prove

this, we give two conditional proofs. First, assume a ©b = b. We need

to prove that b ⊆ a. But this means ∀x(x ∈ b ’ x ∈ a), so we will

use the method of general conditional proof. Let x be an arbitrary

member of b. We need to show that x ∈ a. But since b = a© b, we see

that x ∈ a © b. Thus x ∈ a § x ∈ b by the de¬nition of intersection.

Then it follows, of course, that x ∈ a, as desired.

Now let™s prove the other half of the biconditional. Thus, assume that

b ⊆ a and let us prove that a © b = b. By Proposition 3, it su¬ces to

prove a © b ⊆ b and b ⊆ a © b. The ¬rst of these is easy, and does not

even use our assumption. So let™s prove the second, that b ⊆ a © b.

That is, we must prove that ∀x(x ∈ b ’ x ∈ (a © b)). This is proven

by general conditional proof. Thus, let x be an arbitrary member of

b. We need to prove that x ∈ a © b. But by our assumption, b ⊆ a,

so x ∈ a. Hence, x ∈ a © b, as desired.

You try it

................................................................

1. Open the Fitch ¬le Intersection 1. Here we have given a complete formal

proof of Proposition 6.1 from the de¬nition of intersection and the Axiom

of Extensionality. (We have written “int(x, y)” for “x © y.”) We haven™t

speci¬ed the rules or support steps in the proof, so this is what you need to

do. This is the ¬rst formal proof we™ve given using function symbols. The

appearance of complex terms makes it a little harder to spot the instances

of the quanti¬er rules.

2. Specify the rules and support steps for each step except the next to last

(i.e., step 22). The heart of the proof is really the steps in which c ∈ a§c ∈ b

is commuted to c ∈ b § c ∈ a, and vice versa.

Section 15.3

418 / First-order Set Theory

3. Although it doesn™t look like it, the formula in step 22 is actually an

instance of the Axiom of Extensionality. Cite the axiom, which is one of

your premises, and see that this sentence follows using ∀ Elim.

4. When you have a completed proof specifying all rules and supports, save

it as Proof Intersection 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

The following reminder shows us that © is the set-theoretic counterpart of

§ while ∪ is the counterpart of ∨.

Remember

Let b and c be sets.

1. x ∈ b © c if and only if x ∈ b § x ∈ c

2. x ∈ b ∪ c if and only if x ∈ b ∨ x ∈ c

Exercises

15.14 If you skipped the You try it section, go back and do it now. Submit the ¬le Proof Intersection 1.

‚

15.15 Let a = {2, 3, 4, 5}, b = {2, 4, 6, 8}, and c = {3, 5, 7, 9}. Compute the following and express your

answer in list notation.