Introduction to
Set Theory
Why Study Set Theory?
Understanding set theory helps people to
• begin to understand logic
• organize things into groups
•see things in terms of systems
Key Mathematicians in
set theory and logic
• Georg Cantor
• John Venn
• George Boole
• Augustus DeMorgan
Georg Cantor 1845 -1918
German mathematician who
invented set theory
proved that real numbers
are more numerous than
Cantor's theorem states generally that, for
natural numbers
any set A, the power set of A (i.e. the set of
all subsets of A) has a strictly greater
cardinality than A itself.
His main legacy, though, is as perhaps
the first mathematician to really
understand the meaning of infinity and
to give it mathematical precision.
John Venn 1834-1923
- British Mathematician
- priest (1859)
-Books:
The Logic of Chance (1866),
Symbolic Logic’ (1881) and
The Principles of Empirical Logic (1889).
• studied and taught logic and probability theory
• Venn Diagrams (1881)
George Boole 1815-1864
- British mathematician ,
- self- taught
- featured the operators
and, or, not, nor (exclusive or)
His legacy was Boolean logic, a theory of
mathematics in which all variables are
either "true" or "false", or "on" or "off". The
theory preceded the digital age, with
American Claude Shannon applying
Boolean logic to build the electrical circuits
in the 1930s that led to modern computers.
Augustus De Morgan 1806-1871
• British mathematician
• De Morgan’s laws
• formally stated the
laws of set theory
•Introduced the term
mathematical induction
Sets : Review
•Definition of a Set
•Methods of naming a set
•Properties
•Relationships between two sets
•Operation on Sets
•Venn Diagram
Solve the problem using a Venn Diagram
In a school of 320 students: 85 students are in the band
200 students are on a sports teams 60 students
participate in both activities.
a) Create a Venn diagram to model the information.
b) How many students weren’t in either?
c) How many students were in band or sports?
d) How many were in band, but not sports?
105 adults were asked whether they had studied French, Spanish or Japanese in school. Here are the
results of the survey:
5 are taking all three
9 have studied both Japanese and French
11 have studied both Japanese and Spanish
24 have studied both Spanish and French
52 have studied French
63 have studied Spanish
25 have studied Japanese
a. Create a Venn diagram to model the information.
b. How many have studied Spanish but not French?
c. How many have studied Japanese but not French?
d. How many have studied both French and Spanish?
e. How many have studied French or Spanish?
f. How many have studied both French and Spanish but not Japanese?
Answer
French
24
4 19
Japanese 5
Spanish
10 33
6
Relation
- a correspondence between two things or quantities
- a set of ordered pairs such that the set of all first
coordinates of the ordered pairs is called Domain and the
set of all the second coordinates of the ordered pairs is
called Range.
- maybe expressed as a statement, arrow diagram, table,
equation, set-builder notation and graph.
Example: R= {(1, 2), (2, 4), (3, 6), (4, 8), (5, 10)}
Types of relations
1. one - to – one relation
2. one – to – many relation
3. many – to – one relation
Relations in Language of Math
Grammatical rules for the use of symbols :
To use < in a sentence, one should precede it by a noun and
follow it by a noun.
• Other examples of relations are “equals” and “ is an
element of”
• It is important (when specifying a relation) to be careful
about which objects are to be related.
Function
- a relation such that each element of the domain is paired with
exactly one element of the range.
To denote this relationship, we use the functional notation:
𝑦 = 𝑓(𝑥)
where 𝑓 indicates that a function exists between variables 𝑥
and 𝑦.
𝑓: 𝐴 → 𝐵 A- domain B - range
Function
Evaluating a function
Inverse of a function
Let's find what's wrong with each of these ?
1. 5 is a subset of N
should be, '5 is an element of N'
2. x > 2 or x < 1 is equivalent to 2 < x < 1
should be, 'x > 2 or x < 1 is not equivalent to 2 < x < 1'
x<1 x>2
Let's find what's wrong with each of these ?
1. 5 is a subset of N
should be, '5 is an element of N'
2. x > 2 or x < 1 is equivalent to 2 < x < 1
should be, 'x > 2 or x < 1 is equivalent to 2 < x < 1'
3. Given the function x + 10, find the value of f(4)
should be, 'Given the function f(x) =x + 10, find the value of f(4)'
4. 22/7 = 3.14
should be, '22/7 is approximately equal to 3.14', or
Binary Operations
A binary operation on a set A is a function that takes pairs of
elements of A and produces elements of A from them. We use
the symbol * to denote arbitrary binary operation on a set
Four Properties: For every x,y,z elements of A
1. Commutative x* y = y *x
2. Associative x* (y*z) = (x*y)* z
3. Identity e*x = x *e
4. Inverse x*y = y*x = e
Elementary Logic
•Logical connectives
•Quantifiers
•Negation
Logical connectives
- the mathematical equivalent of a conjunction
- examples : and
or
implies
Implication “p implies q”
Means :
• if p then q
• q if p
• p only if q
• whenever p is true, q is true
• q is necessary for p
• p is sufficient for q
Quantifiers
“all”, “some”, “any”, “every”, nothing”
Examples (see p. 7):
“Nothing is better than lifelong happiness.”
“Everybody likes at least one drink and that drink is water.”
