Discrete 2.3 Functions

function f from set A to B

an assignment of exactly one element of B to each element of A.

Domain

if f:A→B, the domain is A

Codomain

if f:A→B, the codomain is B

Image

if f(a)=b, the image is b

Preimage

if f(a)=b, the preimage is a

Range of f

{b∈B | ∃a∈A(f(a)=b)}

Equal functions

they have the same domain and codomain

Image of the set

if f: A→B is a function, and S⊆A, then the image of the set S is the subset of B consisting of the images of the elements of S.

f(S) = {b∈B | ∃s∈S (f(s)=b)}

Injective

a function f:A→B is injective iff ∀a₁,a₂∈A (f(a₁)=f(a₂) → a₁=a₂)

Surjective

a function f:A→B is surjective iff ∀b∈B ∃a∈A (f(a) = b)

Bijective

a function f:A→B is bijective iff f is both injective and surjective

Inverse function

If a function f:A→B is a bijection, the inverse function, f^-1:B→A, assigns to each b∈B the unique a∈A such that f(a)=b.

Thus f^-1(b)=a when f(a)=b.

Invertible

If the inverse of a function exists, we say the function is invertible.

Composition

If g:A→B and f:B→C, then the composition of f and g, is a function from A to C, defined by (f∘g)(a) = f(g(a))

Identity function

i_A:A→A is defined by i_A(a)=a for all a∈A.

The identity function is a bijection.

Graph

The graph of a function f:A→B is {(a,b): a∈A and f(a) = b∈B} and a subset of A×B

Floor function

⌊x⌋ : ℝ → ℤ rounds the real number x down to the greatest integer that is less than or equal to x.

Ceiling function

⌈x⌉ : ℝ → ℤ rounds the real number x up to the smallest integer that is greater than or equal to x.