A Quick Math Overview
(not the last one!)
•Section 1.4, you should it read carefully! (ignore the
equivalence relation stuff)
•Reading the corresponding material from the book is
strongly encouraged
Sets
• Sets are denoted by { <collection of elements> }
•Examples:
{} “the empty set”
{a,b} “the set consisting of the elements a and b”
{{}} “the set consisting of the empty set”
{1, 2, …, 100} “the set consisting of the first 100 natural
numbers”
{0, 1, 2, …} “the set consisting of all natural numbers”
Also denoted by .
{0,2,4, …} “the set of all natural pair numbers”
{2n | n } “the set of all natural pair numbers”
Set Inclusion and Set Equality
Definition: Given 2 sets, A and B, A is contained in B, denoted by
A B, if every element in A is also an element in B
True or false:
{e,i,t,c} {a, b, …, z} true
for any set A, A A true
for any set A, A {A} false
Definition: Given 2 sets A and B, A is equal to B, denoted by A = B,
if A B and B A
Cartesian Product
Definition: Given two sets, A and B, the Cartesian product of A
and B, denoted by A B, is the following set:
{(a,b) | a A and b B}
Examples:
•What is: {1, 2 , 3} {a,b} =
•True or false: {(1,a), (3,b)} {1, 2 , 3} {a,b} true
•True or false: {1,2,3} {1, 2 , 3} {a,b} false
Cartesian Product (2)
More examples:
•What is: {1, 2 , 3} {a,b} {,} =
•What is the form of the set A B C D
•What is the form of the set A B (C D)
•What is the form of the set (A B ) (C D)
Relations
Definition: Given two sets, A and B, A relation R is any subset
of A B. In other words, R A B
Motivation: We want to indicate which elements in A are
related to which elements in B
Question: what does the relation A B indicates?
Examples of relations in “real life”?
{(p,s) : p is a professor in Lehigh, s is an student in Lehigh
and s is taking a class with p}
Functions
Definition: A function f from a subset A to a set B, denoted by
f: A B, is a relation such that: for each a A’ there is one and
only one b B such that (a,b) f
Question: Is the following relation:
{(p,s) : p is a professor in Lehigh, s is an student in Lehigh
and s is taking a class with p}
a function from {p: professor in Lehigh} to {s: is an student
in Lehigh}?
No
Functions (2)
Example of other functions in real life?
SSN: People Social Security Number
The KEY Question: When should we use functions and when
should we use relations?
The KEY Answer:
•We use functions if each element in A has to be related to one
and only one element in B (think SSN)
•Otherwise, we use relations (think professor-student relation)
Homework (for next class)
•Book:
1.2 a) and c)
1.4 a) and c)
1.5
•True or false (explain your answers):
A B = B A
A (B C) = (A B) C
•Give an example of a “real-life” function (what is A? what is B?)
•Give an example of a related “real-life” relation (what is A? what
is B?)
Equivalence Relations
A relation R is an equivalence relations if R is reflexive, R is
symmetric and R is transitive
R is reflexive if (a,a) R for each a in the language
R is symmetric if the following property holds: if (a,b) R
holds then (b,a) R also holds
R is transitive if the following property holds: (a,b) R and
(b,c) R hold then (a,c) R also hold
Equivalence relations is a generalization of the equality
{(1,2),(1,3),…, (2,3),(2,4),…}
{(a,b) such that a and b are artificial lights of color red}