<<

. 75
( 107 .)



>>


∀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.

<<

. 75
( 107 .)



>>