For unlimited access to Class Notes, a Class+ subscription is required.

Review Summary for the Tutorial and Written Quizzes of Lab 4

Part I.Mathematical Proofs in Set Theory and the Underlying Logical Arguments

Each step of a proof in set theory is either an interpretation of a deﬁnition, an application of a rule in propositional

logic, or a consequence/example of a known theorem. Learners of mathematical proofs should be careful and patient

while writing a proof, keeping a clear mind about what they are doing in each step. Very often the proof is led

astray by a simple error in one step, and becomes invalid.

Example 1. Let Aand Bbe subsets of the universal set U. Denote by Acand Bcthe complements of Aand B

in Urespectively. Prove that, as subsets of the product set U×U,

(A×Ac)∩(Bc×B) = (A×B)∩(Bc×Ac).

Analyze the deﬁnitions and the rules in logic that are used in each step of the proof.

Proof. Let (x, y)∈U×U. Because

(x, y)∈(A×Ac)∩(Bc×B) (consider A×Acand Bc×Bas subsets of U×U)

iﬀ (x, y)∈A×Acand (x, y)∈(Bc×B) (follow the deﬁnition of intersection of sets in U×U)

iﬀ (x∈Aand y∈Ac) and (x∈Bcand y∈B) (follow the deﬁnition of product sets)

iﬀ (x∈Aand y∈B) and (x∈Bcand y∈Ac) (apply the rule (p∧q)∧(r∧s)⇔(p∧s)∧(r∧q) in logic)

iﬀ (x, y)∈A×Band (x, y)∈Bc×Ac(follow the deﬁnition of product sets)

iﬀ (x, y)∈(A×B)∩(Bc×Ac), (follow the deﬁnition of intersection of sets in U×U)

It follows that (A×Ac)∩(Bc×B) = (A×B)∩(Bc×Ac).

A typical, silly mistake in writing a proof for product sets is to write x∈A×Bor y∈A×Binstead of (x, y)∈A×B.

Similarly, one should not conclude that the assumption that a∈Aand b∈Bimplies (a, b)∈A∩Bbecause A∩B

is not a subset of U×V.

Another warning is that the symbol “⇔”cannot be repalced by the symbol “=”, as the former denotes “iﬀ”

that links two statements while the latter indicates the two sides of it are equal sets in set theory, or equal

quantities in algebra.

Proofs of identities in set theory may also be written using the set-builder notation that deﬁnes a set by specifying

the property, or the condition, that a typical element of this set posseses, or satisﬁes. Here is an alternative proof

of the equality of two sets in Example 1.

An alternative Proof.

(A×Ac)∩(Bc×B)

={(x, y)∈U×U|(x, y)∈A×Acand (x, y)∈Bc×B}

={(x, y)∈U×U|(x∈A and y ∈Ac)and (x∈Bcand y ∈B)}

={(x, y)∈U×U|(x∈A and y ∈B)and (x∈Bcand y ∈Ac)}

={(x, y)∈U×U|(x, y)∈A×B and (x, y)∈Bc×Ac}

= (A×B)∩(Bc×Ac).

Part II.Combinatorial Counting Principles for Finite Sets

We have studied the following three counting principles for ﬁnite sets that lay the foundation of enumerative

combinatorics. They are the basic tools for us to formulate relations among numbers of elements in sets concerned

and/or to establish formulas for practical computations. We denote by |A|the number of elements in a ﬁnite set

A.

1.Addition Counting Principle

Let A,Bbe ﬁnite disjoint sets; that is, A∩B=∅. Then A∪Bis ﬁnite and |A∪B|=|A|+|B|.

More generally, we may consider the situation in which more than two sets are pairwise disjoint (also called

mutually disjoint).

Generalized Addition Counting Principle Let A1, A2, . . . , Anbe ﬁnite sets with the property that Ai∩Aj=∅

for i6=j. Then

|A1∪A2∪ · · · ∪ An|=|A1|+|A2|+· · · +|An|.

It can be proved using mathematical induction on n, the number of mutually disjoint sets involved. (This will be

a discussion problem in the tutorial session.)