# MA121 Lecture Notes - Lecture 4: Subset, Empty Set, Contraposition

50 views2 pages

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

MA121 1 - Tutorial Fall 2018

I. Recall the truth tables of the following most basic logical operations on “simple” statements pand qwith connectives

∼,∧,∨and →, respectively.

Negation

p∼p

T F

FT

Conjunction

p q p∧q

T T T

T F F

F T F

F F F

Disjunction

p q p∨q

T T T

T F T

F T T

F F F

Conditional

p q p→q

T T T

T F F

F T T

F F T

Truth tables of all other compound statements involving two or more “simple” statements may be constructed using

the above basic ones.

II. Recall the following most frequently used nontrivial equivalence relationships:

Contrapositive

p→q⇔ ∼ q→∼ p

Distributive Laws

p∧(q∨r)⇔(p∧q)∨(p∧r)

p∨(q∧r)⇔(p∨q)∧(p∨r)

De Morgan′s Laws

∼(p∨q)⇔(∼p)∧(∼q)

∼(p∧q)⇔(∼p)∨(∼q)

These equivalences, together with other more trivial equivalences such as p⇔∼ (∼p), may be used to verify other

equivalence relationships.

III. Let A,Band Cbe sets containing elements of the same non-empty universal set U. Recall the following deﬁnitions

and theorems from set theory.

Deﬁnition 1. The sets Aand Bare equal, denoted A=B, if Aand Bcontain exactly the same elements. Otherwise,

A6=B.

Deﬁnition 2. The set Ais a subset of B, denoted A⊆B, if every element of Ais also an element of B; that is, if

x∈A, then x∈B. If A⊆Bbut A6=B, we say Ais a proper subset of B, denoted A⊂B.

Deﬁnition 3. The union of Aand Bis the set

A∪B={x∈U:x∈Aor x∈B}.

Deﬁnition 4. The intersection of Aand Bis the set

A∩B={x∈U:x∈Aand x∈B}.

Deﬁnition 5. The set diﬀerence Aminus Bis the set

A−B={x∈U:x∈Aand x /∈B}.

In particular, U−B, denoted Bc, is called the complement of B(in U).

Theorem 1. (a) ∅ ⊆ A⊆U, where ∅is the empty set and Ais any subset of the universal set U.

(b) If A⊆Band B⊆C, then A⊆C.

(c) A=Bif and only if A⊆Band B⊆A.

Examples. Determine if each of the following statements is true or false, and try to understand the given justiﬁcations

by the deﬁnitions and theorems listed above.

(a) ∅ ⊆ {∅}. ( T rue /False)

Justiﬁcation:By Theorem 1(a), ∅is a subset of any set A. Thus, ∅ ⊆ {∅} if we take Aas the set {∅}.

Remark. Here ∅ ∈ {∅} is also true because the set contains ∅as its element.