MA121 Lecture 2: Lab 2 Notes

60 views4 pages
11 Feb 2019
School
Department
Course
Professor

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 definition, 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 definitions 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)
iff (x, y)A×Acand (x, y)(Bc×B) (follow the definition of intersection of sets in U×U)
iff (xAand yAc) and (xBcand yB) (follow the definition of product sets)
iff (xAand yB) and (xBcand yAc) (apply the rule (pq)(rs)(ps)(rq) in logic)
iff (x, y)A×Band (x, y)Bc×Ac(follow the definition of product sets)
iff (x, y)(A×B)(Bc×Ac), (follow the definition 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 “iff
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 defines a set by specifying
the property, or the condition, that a typical element of this set posseses, or satisfies. 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 finite 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 finite set
A.
1.Addition Counting Principle
Let A,Bbe finite disjoint sets; that is, AB=. Then ABis finite 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 finite 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.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class