Sets, Relations and Functions

set

is a collection of distinct objects or

elements.

element.

An object inside a set is called an

singleton

A set having only one element is called a

empty set

A set with no element at all is called the

membership criterion

A criterion is necessary to determine whether a particular element belongs to

a given set. This is known as the

Union

the set of all elements that are

in A, in B, or in both:

intersection

sets A and B is the set of elements

that are in both A and B:

Set Difference

is the set that contains everything

that is in A but not in B.

Complement

is the set containing everything that

is not in A but in the universal set U.

Disjoint Sets

If A and B have no common element, that is, A ∩ B = ∅, then

the sets A and B are said to be

Cardinality

set A, written |A|, is the number of

elements in set A.

Powerset

a set A, written 2

A, is the set of all subsets of

A; i.e., a set containing ‘n’ elements has a powerset containing 2

n

elements.

Cartesian Product

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

relation

is a connection or relationship between

elements of two sets.

Ordered Pair

A relation is made up of ___________, where the first element

is related to the second.

Reflexive Relation

A relation R on a set A is reflexive if every element

is related to itself.

Symmetric Relation

A relation R on a set is symmetric if (a, b) ∈ R

implies (b, a) ∈ R.

Transitive Relation

A relation R is transitive if (a, b) ∈ R and (b, c) ∈ R

implies (a, c) ∈ R.

function

is a specific type of relation

where each input is related to exactly

one output.

Mapping

A function is otherwise known as “________”. A function is said to map an

element in its domain to an element in its range.

Injective

A function is ________ if different elements in A

map to different elements in B. No two inputs share the same output.

Surjective

A function is ________ if each element of B is the image

of some element of A.

Bijective

A function is ________ if it is both injective and surjective. Each

input has a unique output, and all outputs are used.