Week 2: Sets, Functions and Relations

Set

an unordered collection of distinct objects, called
elements or members of the seta ∈ A

a ∈ A

a is an element of the set A

a ∉ A

a is not an element of the set A

set N

natural numbers = {0,1,2,3....}

set Z

integers = {...,-3,-2,-1,0,1,2,3,...}

set Z⁺

positive integers = {1,2,3,.....}

set R

set of real numbers

set R+

set of positive real numbers

set Q

set of rational numbers

set C

set of complex numbers

[a,b]

{x | a ≤ x ≤ b}

[a,b)

{x | a ≤ x < b}

(a,b]

{x | a < x ≤ b}

(a,b)

{x | a < x < b}

Set equality

Two sets are equal if and only if they have the

same elements.

set U

the set containing everything currently under consideration.

∅ or {}

the empty set

A ⊆ B

The set A is a subset of B, if and only if every element of A is also an element of B.

A ⊂ B

If A ⊆ B, but A ≠ B, then we say A is a proper subset of B

Finite set

A set A is finite if there are n distinct elements in A, where n is a
non-negative integer.

Set cardinality

The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A.

P(A)

The power set of A is the set of all subsets of a set A. If a set A has n elements, then the cardinality of its power set P(A) is 2ⁿ.

Cartesian product

The Cartesian Product of two sets A and B, denoted as A x B, is the set of ordered pairs (a,b) where a ∈ A and b ∈ B. A x B = {(a, b) | a ∈ A ∧ b ∈ B}.

Union

Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set:

{x | x ∈ A ∨ x ∈ B}.

Intersection

The intersection of sets A and B, denoted by A ∩ B, is the set: {x | x ∈ A ∧ x ∈ B}. If the intersection is empty, then A and B are said to be disjoint.

Compliment

If A is a set, then the complement of the A (with respect to U), denoted by Ā or Ac , is the set U - A. A^c = Ā = {x ∈ U | x ∉ A}

Difference

Let A and B be sets. The difference of A and B, denoted by A – B, is the set containing the elements of A that are not in B. A – B = {x | x ∈ A x ∧∉ B} = A ∩ B̅.

Principle of Inclusion-Exclusion

|A ∪ B| = |A| + | B| - |A ∩ B|

Function

Let A and B be nonempty sets. A function f from A to B, denoted f: A → B is an assignment of each element of A to exactly one element of B.

Function f: A → B

• f is a mapping from A to B.

• A is called the domain of f.

• B is called the codomain of f.

• If f(a) = b, b is called the image of a under f and a is called the preimage of b.

• The range of f is the set of all images of points in A under f. We denote it

by f(A).

Function equality

Two functions are equal when they have

• the same domain,

• the same codomain, and

• map each element of the domain to the same element of the codomain.

Injections

A function f is said to be one-to-one, or injective, if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f.

Surjections

A function f from A to B is called onto or surjective, if and only if for every element b∈B there is an element a∈A with f(a) = b.

Bijections

A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto (i.e., it is injective and surjective).

⌊x⌋

Floor function. Greatest integer less than or equal to x.

⌈x⌉

Ceiling function. Least integer greater than or equal to x.

Inverse function

Only exists if f is a bijection.

Composition of functions

Let g be a function from the set A to the set B

• Let f be a function from the set B to the set C .

• The composition of the functions f and g , denoted for all

a ∈ A by 𝑓 ∘ 𝑔 , is the function from A to C defined by: 𝑓 ∘ 𝑔 (𝑎) = 𝑓(𝑔(𝑎))

Relations

an association of objects of one set with objects of another set

Binary relations

A binary relation R from a set A to a set B is a subset R ⊆ A × B.

Reflexive relations

R is reflexive if and only if (a,a) ∊ R for every element a ∊ A.

Symmetric relations

R is symmetric iff (b,a) ∊ R whenever (a,b) ∊ R for all a, b ∊ A

Transitive relations

A relation R on a set A is called transitive if (a,b) ∊ R and (b,c) ∊ R implies (a,c) ∊ R, for all a,b,c ∊ A.

Equivalence relations

A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. Two elements a, and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation.

Equivalence classes

Let R be an equivalence relation on a set A.

• The set of all elements in A that are related to an element x of A is called

the equivalence class of x.

• The equivalence class of x with respect to R is denoted by [x]R;

• [x]R = {s | (x,s) ∈ R}

Partition of a Set

A partition of a set 𝑆 is a collection of disjoint non-empty subsets of 𝑆 that have 𝑆 as their union

Composition of relations

Definition: Suppose

• R1 is a relation from a set A to a set B.

• R2 is a relation from the set B to a set C.

T hen the composition of R1∘ R2, is a relation from A to C where

• if (x,y) is a member of R1 and (y,z) is a member of R2, then (x,z) is a

member of R1∘ R2.