Properties Example

\rho = \{ \frac{p}{q}, \frac{q}{p} \}

• Is symmetric, is not reflexive or transitive

Functions (Mappings)

Let S and T be sets. S = \{ (1,2) \} \qquad T = \{ a,b,c \}

A function f from S to T (f:S \to T) is a subset of S \times T (f \subseteq S \times T)

• Each member of S can appear only once as the first component of an ordered pair.
  • Suppose (s,t) belongs to the function, then t can be denoted by f(s)
    • Preimage: s (“preimage of t under f”)
    • Image: t (“image of s under f”)
• Domain: S
• Codomain: T
• Range: f(s) \subseteq T
  • Set of images smaller than the codomain

For A \subseteq S, f(A) denotes \{ f(a) | a \in A \}

Summary: Three Parts of a Function

1. A set of starting values
2. A set from which associated values come
3. The association itself

These rules for a function mean that functions can’t have a binary relation that is one-to-many or many-to-many.

Floor Function and Ceiling Function

Floor Function: floor(x)$

• Associates with each real number x the greatest integer less than or equal to x

Ceiling Function: ceil(x)

• Associates with each real number x the smallest integer greater than or equal to x.

Note: Both floor and ceil domains’ are all real numbers.

Equal Functions

Equal Functions: Two functions are equal if they have the same:

1. Domain,
2. Codomain, and
3. Association of values

Onto (Surjective) Functions

Onto Function: Function where the range of f equals the codomain of f

• “Every node has an association”

To prove that a given function is onto:

1. Show that T \text{(domain)} \subseteq R \text{(range)} (this proves that R = T)
2. Show that an arbitrary member of the codomain is a member of the range.

One-to-One (Injective) Functions

One-to-one Function: Function (f:S \to T) where no member of T is the image under f of two distinct elements of S.

To prove that a function is one-to-one, we assume that there are elements s_1 and s_2 of S with f(s_1) = f(s_2) and then show that s_1 = s_2

Bijective Functions

Bijective Function: Function (f: S \to T) that’s both one-to-one and onto.

Composition of Functions

Suppose f: S \to T and g: T \to U

Composition Function: Function (g \circ f) from S to U defined by (g \circ f)(s) = g(f(s))

• Applied right-to-left (f applied, then g)
• Preserves properties of being onto and one-to-one.

Theorem on Composing Two Bijections: The composition of two bijections is a bijection.

• Ergo, suppose f: S \to T and g: T \to U are onto, then g \circ f is also onto.

Next Lecture

Next lecture (Tuesdau) will be a review section.

Each student can choose one of the four homework and make it up.

• A new list of questions will be given and answers will be turned in via paper on next Thursday.

Finals will probably be graded within a day because Prof. has to travel lol.

Composition of Functions Cont.

Suppose f: S \to T and g: T \to U

Composition Function: Function (g \circ f) from S to U defined by (g \circ f)(s) = g(f(s))

• Applied right-to-left (f applied, then g)
• Preserves properties of being onto and one-to-one.

Theorem on Composing Two Bijections: The composition of two bijections is a bijection.

• Ergo, suppose f: S \to T and g: T \to U are onto, then g \circ f is also onto.

Example: R \to R, f(x)=x^2 \qquad R \to R, g(x) = x-1 f \circ g(x) = (x-1)^2 \qquad g \circ f(x) = x^2 - 1

Inverse Functions

Identity Function: Function that maps each element of a set S to itself, leaving each element of S unchanged (i_s).

• Suppose f: S \to S is a bijection.
  • Because f is onto, every t \in T has a preimage in S.
    • Because f is one-to-one, each preimage is unique

Inverse Function:

• Suppose f: S \to T and g: T \to S such that g \circ f = i_s and f \circ g = i_p; then g is the inverse function of f, denoted for f^{-1}

Theorem on Bijections and Inverse Functions:

• If f:S \to T, then f is a bijection if and only if f^{-1} exists