2 - sets,relation and function Flashcards
collection of distinct object or elements
set
An object inside a set is called an element. For example, in the set
above, a is an element of V.
elements
a set having only one elements is called a _______
singleton
a set with no elements at all is called the ______ which is denoted
by { } or ∅.
empty set
A ________ is necessary to determine whether a particular element belongs to
a given set.
membership criterion
two common ways to indicate the members of a set:
a) List all the elements, e.g, {a, e, i, o, u}.
b) Provide some kind of an algorithm or a rule, such as a grammar.
A set is written using curly braces {}. For example, a set of vowels
in the alphabet can be written as: V = {a, e, i, o, u}
notation
To indicate that x is a member of the set S, we write ________
x ∈ S
every element of set A is also an element of set B, we say that A
is a ______ of B, and write ______
Example: A = {a, b}, B = {a, b, c} ⟹ ______
subset, A ⊆ B
If every element of set A is also an element of set B, but B also has
some elements not contained in A, we say that A is a _______
of B and write _____
proper subset, A ⊂ B
four types of operations
union
intersection
set difference
complement
The _____ of two sets A and B is the set of all elements that are
in A, in B, or in both
A ∪ B = {x ∣ x ∈ A or x ∈ B}
Example: A = {1, 2, 3}, B = {3, 4, 5} ⟹ A ∪ B = {1, 2, 3, 4, 5}
union
The intersection of two sets A and B is the set of elements
that are in both A and B
A ∩ B = {x ∣ x ∈ A and x ∈ B}
Example: A = {1, 2, 3}, B = {3, 4, 5} ⟹ A ∩ B = {3}
intersection
Written as A – B, is the set that contains everything
that is in A but not in B.
A − B = {x : x ∈ A and x ∉ B}
Example: A = {1, 3, 9}, B = {3, 5}
A − B = {1, 9}
set difference
Written as Ā or AC is the set containing everything that
is not in A but in the universal set U.
Example: If U = {1, 2, 3, 4, 5} and A = {1, 2}, then:
AC = {3, 4, 5}
complement
If A and B have no common element, that is, A ∩ B = ∅, then
the sets A and B are said to be _______.
Example: A = {1, 2, 3}, B = {4, 5, 6}
disjoint set
The ______ of a set A, written |A|, is the number of
elements in set A.
Example: Let: A = {w, x, y, z}; |A| = 4
cardinality
The _______ of a set A, written 2
A, is the set of all subsets of
A; i.e., a set containing ‘n’ elements has a ____________ containing 2
n
elements.
Example: Let: A = {1, 2}; P(A) = {∅, {1}, {2}, {1,2}}
powerset
Let A and B be two sets. Then the set of all ordered
pairs (x, y) where x ∈ A and y ∈ B is called the ________ ________ of the
sets A and B and is denoted by A × B, i.e.
A × B = {(x, y) : x ∈ A and y ∈ B}
Example: Let: A = {1, 2}, B = {x, y}
The Cartesian product A × B is:
A × B = {(1,x), (1,y), (2,x), (2,y)}
Let: X = {a}, Y = {1, 2}
The Cartesian product X × Y is:
X × Y = {(a,1), (a,2)}
cartesian product
A ______ is a connection or relationship between
elements of two sets
relation
A relation is made up of _______ _______, where the first element
is related to the second. If A and B are sets, a relation from A to B is a subset
of A × B (Cartesian product).
Example:
1. If A = {1, 2} and B = {x, y}, then the Cartesian product A × B
is: A × B = {(1,x), (1,y), (2,x), (2,y)}
A possible relation could be: R = {(1,x), (2,y)}
2. Suppose S is the set {a, b, c, d, e} and set T is {w, x, y, z}.
Then a relation on S and T is:
R = {(a, y), (c, w), (c, z), (d, y)}
order pair
three types of relation
reflexive relation
symmetric relation
transitive relation
A relation R on a set A is _________ if every element
is related to itself. For example, for all x ∈ A, (x, x) ∈ R.
Example: If A = {1, 2, 3}, then a reflexive relation is:
R = {(1,1), (2,2), (3,3)}
Let: B = {x, y}
The reflexive relation on B is:
R = {(x, x), (y, y)}
reflexive relation
A relation R on a set is _______if (a, b) ∈ R
implies (b, a) ∈ R.
Example: Let: A = {1, 2}
R = {(1, 2), (2, 1)}
Let: B = {x, y, z}
R = {(x, y), (y, x), (z, z)}
symmetric relation
A relation R is __________if (a, b) ∈ R and (b, c) ∈ R
implies (a, c) ∈ R.
Example: R = {(1,2), (2,3), (1,3)}
If (1, 2) ∈ R and (2, 3) ∈ R, then (1, 3) ∈ R.
Let: B = {x, y}
R = {(x,y), (y,y)}
transitive relation
A _________ is a specific type of relation
where each input is related to exactly
one output.
III. function
A function is otherwise known as _________.
mapping
A function f from set A to set B assigns each element in A exactly one element
in B. This is written as f : A→B
Example: If A = {1, 2, 3} and B = {a, b, c}, then a function f could be:
f(1) = a, f(2) = b, f(3) = c
three type of function
injective (one to one)
surjective (onto)
bijective
A function is ________ if different elements in A
map to different elements in B. No two inputs share the same output.
Example: f(1) = a, f(2) = b, f(3) = c
injective (one to one)
A function is ________ if each element of B is the image
of some element of A.
Example: f(1) = a, f(2) = b, f(3) =a
surjective (onto)
A function is ________ if it is both injective and surjective. Each
input has a unique output, and all outputs are used. Such a function maps
each and every element of A to exactly one element of B, with no elements
left over.
Example: f(1) = a, f(2) = b
bijective
