N}
1,2,3 are all clearly one of the elements in set B as they satisfy the property that characterizes
the elements of set B. (they all are positive integers)
Basic Mathematical Objects Homepage
The following are the contents of this introductory chapter.
What
is a set?
Set
is a group of elements, having a property that characterizes those elements.
How
to specify a Set?
One
way is to enumerate the elements completely ( all the elements belonging
to set are explicitly
given)
and give a property that characterizes the elements of the Set.
Example: A = {1,2,3,4,5}
Alternate way, is to enumerate the elements in a way that makes clear what
the remaining
elements are and to give a property that characterizes the elements of
the Set.
Example: B = {x | x is a positive integer less than or equal to 5}
C = {1,2,3,4,5,6,……..} ( this is a infinite set)
Simpler
Representation
Consider
the following example
Example:
A = {1,2,3}
B = {x | x is a positive integer}
Here
we can think of some better way of specifying the set B just by replacing
the English
like
sentence “x is a positive integer less than 100” in a more mathematically
simpler way.
We
can achieve it by assuming ‘N’ as all positive integers.
Now we can specify set B as, B = {x | x
N}
1,2,3
are all clearly one of the elements in set B as they satisfy the property
that characterizes
the elements of set B. (they all are positive integers)
Set terminology
Belongs
To
x B implies that
x is an element of set B. Using this notation we can specify the
set {1,2,3,4,5}
by writing
Z = {x A | x <= 5}
which is read as “ the set of elements ‘x’ in ‘A’such that ‘x’<5”.
Subset
If A and B are two sets,
A is a subset of B, if every element of A is an element of B.
A
is
a subset of B is represented as
A 
B.
Note: If A is a subset of B and B is a
subset of A then A=B. Also, A is subset and equal to B
represented as A 
B
and B A.
Compliment
If A is a set, then the compliment of A is the set A', consisting of all
elements contained in the
universal set and not in A..To understand compliment, it is necessary
for us to know about
Universal Set.
Universal
Set
A set U that contains all the elements we might ever consider.
Then A’ can be represented as
A’= { x U | x 
A }
Where "is not an
element of"..
Example:: if U = { 1,2,3….}
If A = { 1,2,3 } then A’ = { 4,5,6….}
Set Operations
The operations that can be performed on sets are:
1. Union
If A and B are two sets, then A union B is a set that contains all the
elements only in
A, only in B and in both A and B which can be represented as A 
B.
Example: A={1,2,3} B={3,4,5}
then A B={1,2,3,4,5}
2. Difference
If A and B are two sets, then A Difference B is a set that contains the
elements only in A
and the elements only in B but not the elements that are in both A and
B which can be
represented as A - B.
Example: A={1,2,3} B={3,4,5}
then A - B={1,2,4,5}
3. Intersection
If A and B are two sets, then A intersection B is a set that contains only
the elements in
both A and B which can be represented as A 
B.
Example: A = {1,2,3,8}
B = {3,4,5,8}
then A B = { 3,8 }.
Disjoint
sets
A
and B are said to be disjoint sets if they contain no elements in
common
i.e.
A B = ø,
where
ø
is the Empty set that is the set with no elements.
Example:
A = { 1,2,3,4,5 } B = { 6,8,9
}
then A
B = ø.
Here is a list of some standard
Set
Identities
A, B, C
represent arbitrary sets and ø is the empty
set and U is the Universal Set.
The Commutative
laws:
A B = B
A
A B = B
A
The Associative
laws:
A (B
C) = (A B)
C
A (B
C) = (A B)
C
The Distributive
laws:
A (B
C) = (A B)
(A C)
A (B
C) = (A B)
(A C)
The Idempotent
laws:
A A = A
A A = A
The Absorptive
laws:
A (A
B) = A
A (A
B) = A
The De
Morgan laws:
(A B)’=A’
B’
(A B)’=A’
B’
Other laws
involving Complements:
( A’ )’ = A
A A’ = ø
A A’ = U
Other laws involving
the empty set
A ø
= A
A ø
= ø
Other laws involving
the Universal Set:
A U = U
A U = A
Venn
Diagrams
A common technique in working
with Set Operations is to illustrate them by drawing Venn
Diagrams.
The
idea is to draw a large region representing the universe and within that
to draw schematic diagrams
of each of primitive sets
we are starting with, overlapping in such a way that the illusstration
includes a
region corresponding to every
membership combination.
( This
illustration is very clear and easy when we have three sets or less. Three
sets are enough to
illustrate those laws)
A basic venn diagram for a case of two sets
is illustrated below.
A = { 1,2,3,4 } B = { 6,8,2,4 }
Sets A and B can be represented as shown in the
below figure using Venn Diagrams
Set A
Set B
U represents the Universal set in which A is one of the Set.
The following Venn Diagram is used to illustrate A
B
A B
The following Venn Diagram is used to illustrate A U B
A B
A
B is the set consisting of all the different elements in A and B.
Before going on to the illustration of one of the
laws using Venn Diagrams, its better
to know a little more about Venn Diagrams.
(A
B)' is the yellow shaded region in the below venn diagram.
'.jpg)
For example:
U = { 1,2,3,4,5,6,7,8 } A = { 1,2,3,4 }
B = { 2,4,6,8 }
A B = { 1,2,3,4,6,8 }
(A B)' =
U - (A B)
= { 5, 7 }
A - B is the yellow shaded region &
B - A is the blue shaded region in the below
shown Venn Diagram
A simple illustration of the use of Venn Diagrams
in reasoning about the set
operations is given explaining one of the Demorgan's
Identity.
(A B)’ = A’
B’
Let us first draw the Venn Diagram for the Left Hand side of the above identity.
(A
B)’
'.JPG)
Fig: 1
Yellow shaded region is the
one representing the (A
B)’ part of the identity.
Now let us draw the venn diagram
for the Right Hand Side of the Identity.
A’
B’
We shall solve it in
parts by first showing a Venn diagram for A' part and then for B'.
Then a combined Venn
Diagram for the Intersection of those two diagrams.
A'
Fig: 2
Yellow shaded region is the one corresponding
to the A' part.
B'
Fig: 3
Blue shaded region is the one representing
the B' part.
Now the intersection of the above two i:e A’
B’ is the common shaded area in
above two Venn Diagrams.
It is represented as shown below
Fig: 4
Green shaded region in the above Venn Diagram is
common for both A' and B'
and so represents the Intersection A' and
B'.
From Fig: 1 and Fig: 4 it is
clear that (A
B)’ = A’ B’.
In the same way one can prove
all the identities.
To make your concepts strong, go through some of the review excercises.
Click here for Review Excercises
Logic
Proposition and Logical Connections
“Proposition”
can be defined as a declarative statement with sufficient meaning, objective
and having a
precise truth-value, true or false.
Example:
The following statements are propositions
as they have a precise truth values. Their truth values are false,
true.
The following are the logical connectives used commonly:
a. Conjunction
The logical conjunction is understood in the same
way as commonly used “and”. The compound proposition
truth-value is true iff all the propositions hold
true. It is represented as “ ^ ”.
Truth table for two individual propositions p and
q with conjunction is given below
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b. Disjunction
This is logical “or” read as either true value of
the individual propositions.
Truth table is given below
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c. Negation
This is the logical “Negation” read as for 
p “not p”.
Truth table is given below
|
|
p |
|
|
|
|
|
|
d. Conditional
This is used to define as “a proposition holds true”
if another
proposition is true i.e. p
q
is read as “if p, then q”.
Truth table is given below
|
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
e. Biconditional
A proposition (p
q) ^ (q p) can be abbreviated
using biconditional conjunction <->
as p 
q and is read as “p only if q” and “p if q”..
f. Tautology
A compound proposition, which is true in every case.
E.g.: p V
q
g. Contradiction
This is the opposite of tautology, which is false
in every case.
E.g.: p ^ q
Logical implication and equivalence
If the value of Q is true in every case in, which
p is true then p is said to logically imply q,
which is represented as p 
q. If p and q have same truth-value in each case then both are
said to be logically Equivalent represented as p
q.
Implication
The " 
" symbol is used to symbolize a relationship called material implication;
a compound
statement formed with this connective is true unless
the component on the left (the antecedent)
is true and the component on the right (the consequent)
is false, as shown in the truth-table below.
|
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Equivalence
Finally, the " 
" is used to symbolize material equivalence, in which the compound statement
is true only when its component statements have
the same truth-value- either both are true or
both are false. Truth table is given below
|
|
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This corresponds to a minimal interpretation of the
biconditional statements commonly
expressed in English with the connective phrase
" . . . if and only if . . . ."
Logical quantifiers and quantified statements
Quantifiers are used to make a proposition about a domain.
The proposition variable is
bound to a particular domain and not a free variable.
Such statements with quantifiers is
called a “quantified statement”.
E.g.: Existential quantifiers 
Universal
quantifier 
Functions
If f is a function and x is an
element of its domain, the element of the co-domain associated
with x is written as f(x). A
function associates with, or assigns to each element of one set to
a single element in the other set. The former set
is called the “domain” and the later is called
“Co-domain”.It is represented as follows:
f : A
B where f is the function, A is the domain and B
is the co-domain
Types of functions
1. One-to-One Function
If A and B are two sets, such that f:A
B and if no single element of B is associated
with
more than one element in A, then the function f is said to
be One-to-One or injective
or
an injection.
Example:
2. Onto functions
If A and B are two sets, such that f:A
B and every element in B is associated with
an element in A then
f
is said to be an Onto, Surjective or Surjection
i.e. f(A) = B.
Example:
3. Bijection
A bijection is a function
that is both one to one and Onto..
Example:
Composition of functions
If f: A
B and g: B C
then, for any element xA, the
function h: A C
defined by h(x) = g(f(x))
is called the composition of g and f and is written
as h = g o f.
Inverse of a function
If f: A
B is a bijection, then for any yB
and xA such that y = f(x),
the inverse of f is denoted
by f-1 is defined as x = f-1(y).