2.12 Lesson: Applying set identity laws

• De Morgan’s laws for sets: A ∪ B = A∩B and A ∩ B = A∪B
• To prove a set identity, work with one side of the equation and manipulate it by using the identity laws until it matches the other side of the equation.
• To prove a set identity, you can translate the set notation into propositional logic and use those identities.

2.13 Module 7: Higher Set Operations

This page marks the beginning of Module 7. This module contains three lessons:

• Cartesian products
• Applying Cartesian product to strings
• Set partitions

2.14 Lesson: Cartesian products

An ordered pair of items is written (x, y). 

• The first entry of the ordered pair (x, y) is x and the second entry is y.
• For two sets, A and B, the Cartesian product of A and B, denoted A x B, is the set of all ordered pairs in which the first entry is in A and the second entry is in B.
• An ordered list of three items is called an ordered triple and is denoted (x, y, z). 
• For n ≥ 4, an ordered list of n items is called an ordered n-tuple. 
• An ordered pair, denoted (a,b) is pair of elements listed in a way that the order matters. For example: (x,y)≠(y,x)when x≠y
• The Cartesian product of sets A and B is the set of ordered pairs whose first coordinate comes from set A and the second from set B. It is denoted A×B = {(a,b)|a∈A, b∈B}.
• The number of elements in A×Bis the number of elements in A multiplied by the number of elements in B. That is, |A×B| = |A|×|B|
• The product A×B×C= {(a,b,c)|a∈A b∈B, c∈C}. The elements in this set are called ordered triples.
• The product A₁×A₂… ×A_n = {a₁∈A₁, a₂∈A₂, …, a_n∈A_n}. The elements in this set are called n-tuples.
• The product A^k = A×A … ×A (k times).

2.15 Lesson: Applying Cartesian products to strings

• A sequence of characters is called a string.
• The set of characters used in a set of strings is called the alphabet for the set of strings. 
• The length of a string is the number of characters in the string. 
• A binary string is a string whose alphabet is {0, 1}. 
• A bit is a character in a binary string.
• A string of length n is also called an n-bit string.
• The empty string is the unique string whose length is 0 and is usually denoted by the symbol λ.
• If s and t are two strings, then the concatenation of s and t (denoted st) is a longer string obtained by putting s and t together. If s = 010 and t = 11, then st = 01011
• A string is a sequence of characters where order matters. The set of characters used in a string are called the alphabet and the number of characters in a string is called the length of the string.
• A binary string consists of two characters: zeros and ones. That is, the alphabet is {0,1}. Each character in a binary string is called a bit. Binary strings can be different lengths and are called n- bit strings if they are of length n.
• The empty string, denoted λ, is a string of length 0.
• Joining strings together to make a new string is called concatenation.

2.16 Lesson: Set partitions

• Two sets, A and B, are said to be disjoint if their intersection is empty (A ∩ B = ∅). 
• A sequence of sets, A₁, A₂, …, A_n, is pairwise disjoint if every pair of distinct sets in the sequence is disjoint (i.e., A_i ∩ A_j = ∅ for any i and j in the range from 1 through n where i ≠ j).
• A partition of a non-empty set A is a collection of non-empty subsets of A such that each element of A is in exactly one of the subsets. 
• Two sets are disjoint if their intersection is empty. (A ∩ B = ∅)
• If every pair of distinct sets in a sequence of sets is disjoint, the sequence of sets is considered pairwise disjoint.
• A partition of a non-empty set A is a collection of nonempty sets whose union is all of A and each pair in the collection is pairwise disjoint. Hint: Think of a partition as chopping the set up into disjoint pieces.

2.17 Module 8: Overview of Functions

• Introduction to functions
• Function equality
• Floor and ceiling functions
• Function properties
• Inverse of a function
• Inverse functions with finite and infinite domains

2.18 Lesson: Introduction to functions

• A function f that maps elements of a set X to elements of a set Y, is a subset of X × Y such that for every x ∈ X, there is exactly one y ∈ Y for which (x, y) ∈ f.
• f: X → Y is the notation to express the fact that f is a function from X to Y. The set X is called the domain of f, and the set Y is the target of f. The fact that f maps x to y (or (x, y) ∈ f) can also be denoted as f(x) = y.
•  In an arrow diagram for a function f, the elements of the domain X are listed on the left and the elements of the target Y are listed on the right. 
• A function is a set of ordered pairs whose first coordinate has only one second coordinate. In set notation it can be expressed as: {(x,y)|x∈X, y∈Y such that for each there is only one y∈Y}. The following is an example of a set of ordered pairs of a function: {(1, 2), (3, 3), (4, 3)}. The following is an example of a set of ordered pairs that does not model a function: {(1, 2), (1, 3)}. The second example is not a function because 1 is paired with two different values, 2 and 3.
• Function notation is expressed as: X → Y, where X is called the domain and Y is called the target set. The function is read: f maps x to y or f(x) = y. Note: the term “target set” may also be referred to as the codomain.
• The domain is the set of all possible inputs. The target set (or codomain) is the set a function maps into. The range is the subset of the target set (codomain) and consists of all of the mapped points.
• If the domain and target set are finite, you can illustrate the function with an arrow diagram that maps each element of the domain to an element in a target set. For example:

• The elements in the target set that are paired with an element from the domain make up the range of the function. This relationship is denoted: range of f = {y|(x,y)∈f}.
• Algebraic functions are functions whose pairing relationship is defined by an algebraic set of operations. For example, f : R → R where f(x) = x² -2x + 3.

2.19 Lesson: Function equality

• Two functions, f and g, are equal if f and g have the same domain and target, and f(x) = g(x) for every element x in the domain.

• Two functions f,g are equivalent if f(x)=g(x) for every x in their shared domain.
• Functions that are equal have the same domain and target. For example, functions f(x)=x2−2x+1 and g(x)=(x−1)2,x≥0 are not the same function because they do not share the same domains.
• It is possible that two functions have the same domain and the same range, yet the functions are not equal. Functions that are equal will have the same domain and range, but more importantly they have to map the same elements of the domain to the same

2.20 Lesson: Floor and ceiling functions

• The floor function maps a real number to the nearest integer in the downward direction.
• The ceiling function rounds a real number to the nearest integer in the upward direction.

• The floor function f(x)=⌊x⌋ assigns real numbers to the largest integer at or below it. For example, f(4.01)=4 since 4 is the largest integer below 4.1. In fact, f(4.99)=4 and f(4)=4 because the floor function rounds down to the largest integer at or below it. For negative numbers, f(−4.5)=−5 as -5 is the largest integer below -4.5. Even though the magnitude (the value of the number taken without the sign) of -5 is larger than the magnitude of -4.5, the number -5 < -4.5 as it sits to the left of -4.5 on the number line.
• The ceiling function f(x)=⌈x⌉ assigns real numbers to the smallest integer at or above it. For example, f(4.5)=5 since 5 is the smallest integer above 4.5 and f(−4.5)=−4.

2.21 Lesson: Function properties

• A function f: X → A is injective or one-to-one if x₁ ≠ x₂ implies that f(x₁) ≠ f(x₂). That is, f maps different elements in X to different elements in A.
• A function f: X → A is surjective or onto if the range of f is equal to the target A. That is, for every a ∈ A, there is an x ∈ X such that f(x) = a.
• A function is bijective if it is both injective and surjective. A bijective function is called a bijection. A bijection is also called a one-to-one correspondence.
• A function f:X →Y is injective (one-to- one) if f(x) = f(y) is true only if x = y
• A function f:X →Y is surjective (onto) Y if for every y∈Y there exists x∈X such that f(x)=y
• If a function is both injective and surjective, it is a bijective function. A bijection is sometimes called a one-to- one “correspondence.”
• The following table summarizes the properties:

2.22 Lesson: The inverse of a function

• A function f: X → Y is invertible if there exists a function g with domain Y and range X with the property f(x) = y ⇔ g(y) = x.
• If a function f: X → Y is a bijection, then the inverse of f is obtained by exchanging the first and second entries in each pair in f. The inverse of f is denoted by f^-1

• Only bijective functions have inverses.
• The inverse of f is obtained by exchanging the first and second entries in each pair in f.
• The inverse of f is denoted by f−1.
• The inverse of a bijective function f:X→Y is a function f−1:Y→X that maps y back to the x such that f(x)=y. That is, if (x,y)∈f then (y,x)∈f−1.
• The domain of f is the range of f−1 and the range of f is the domain of f−1.

2.23 Lesson: Inverse functions: finite and infinite domains

• If a function with an inverse has a finite domain, you can find the inverse by swapping the order in all the ordered pairs. For example if f(x)=(a,1),(b,2),(c,3) then f−1(x)=(1,a),(2,b),(3,c)
• Inverses for functions on infinite domains can be solved algebraically.
• To algebraically solve for an inverse, use the following algorithm:
  1. Replace f(x) with y
  2. Interchange x and y
  3. Solve for y.
  4. Replace y with f−1(x)

2.24 Module 9: Functions – Composition and Applications

• Composition of functions
• Exponential functions
• Logarithmic functions

2.25 Lesson: Composition of functions

• The process of applying a function to the result of another function is called composition

• Composition is the process of applying a function to the result of another function.
• To compose two functions, for example f and g, first find the output of f(x) and then find g(f(x)).
• The composition of g with f is denoted g∘f.
• If f:X→Y,g:Y→Z, then (g∘f):X→Z is the composition of f and g where (g∘f)(x)=g(f(x))
  • Generally, (g∘f)(x)≠(f∘g)(x)
  • The identity function f:X→X maps x values to themselves. That is, f(x)=x for all x∈X
  • Composition is associative, so the order in which one composes the functions does not matter.
• The expression to compose three functions is: (f∘g∘h)(x)=f(g(h(x))).

2.26 Lesson: Exponential functions

• The exponential function exp_b:R → R⁺ is defined as: expb(x)=bx
• where b is a positive real number and b ≠ 1. The parameter b is called the base of the exponent in the expression b^x. The input x to the function b^x is called the exponent

• The exponential function, denoted expb:R→R+ is defined as expbx=bx. More commonly, it is written as f(x)=bx or y=bx. The base is b and the exponent is bx
• The following is a summary of properties of exponents:

2.27 Lesson: Logarithmic functions

• The exponential function is one-to-one and onto, and therefore has an inverse. The logarithm function is the inverse of the exponential function. 
• The parameter b is called the base of the logarithm in the expression log_b y.

• The inverse function to the exponential is the logarithmic function.
• The log function is denoted logb:R+→R expressed as logbx=y where b>0,b≠1
• The relationship between the exponential function and the logarithmic function can be expressed: y=bx⇔logby=x. For example, if 32=9⇔log39=2.
• The following is a summary of the logarithm properties:

• A function is strictly increasing on an interval if f(x)>f(y) whenever x>y for all x,y in the interval.
• A function is strictly decreasing on an interval if f(x)<f(y) whenever x>y for all x,y in the interval.
• The exponential and the logarithmic function are both strictly increasing functions.