# MA121 Lecture 2: Lab 2 Notes

60 views4 pages
School
Department
Course
Professor

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ﬀ (xAand yAc) and (xBcand yB) (follow the deﬁnition of product sets)
iﬀ (xAand yB) and (xBcand yAc) (apply the rule (pq)(rs)(ps)(rq) 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 xA×Bor yA×Binstead of (x, y)A×B.
Similarly, one should not conclude that the assumption that aAand bBimplies (a, b)ABbecause AB
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|(xA and y Ac)and (xBcand y B)}
={(x, y)U×U|(xA and y B)and (xBcand 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.
Let A,Bbe ﬁnite disjoint sets; that is, AB=. Then ABis ﬁnite and |AB|=|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 AiAj=
for i6=j. Then
|A1A2 · · · 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.)
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

# Get access

\$10 USD/m
Billed \$120 USD annually
Homework Help
Class Notes
Textbook Notes