Math 240 Archives - Page 7 of 9 - Shawn Zhong

2.3 Functions

$Functions • Definition ○ 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. ○ We write f(a)=b if b is the unique element of B assigned by the function f to the element a of A. ○ Functions are sometimes called mappings or transformations. • Example • Relation ○ A function f:A→B can also be defined as a subset of A×B (a relation). ○ This subset is restricted to be a relation where no two elements of the relation have the same first element. ○ Specifically, a function f from A to B contains one, and only one ordered pair (a,b) for every element a∈A. § ∀x[x∈A→∃y[y∈B∧(x,y)∈f]] § ∀x,y_1,y_2 [[(x,y_1 )∈f∧(x,y_2 )∈f]→y_1=y_2 ] • Terminology ○ Given a function f: A → B: ○ We say f maps A to B or 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, § then b is called the image of a under f. § 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). ○ 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. Representing Functions • Functions may be specified in different ways: • An explicit statement of the assignment. ○ Students and grades example. • A formula. ○ f(x)=x+1 • A computer program. ○ A Java program that when given an integer n, produces n! Example • f(a)=z • The image of d is z • The domain of f is A • The codomain of f is B • The preimage of y is b • f(a)={y,z} • The preimage of z is {a,c,d} • f{a,b,c}={y,z} • f{c,d}={z} 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. • A function is said to be an injection if it is one-to-one. 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. • A function f is called a surjection if it is onto. Bijections • A function f is a one-to-one correspondence, or a bijection, • if it is both one-to-one and onto (surjective and injective). Showing that f is one-to-one or onto • To show that f is injective ○ For x,y,∈A if x≠y then f(x)≠f(y) • To show that f is not injective ○ Find x,y∈A s.t. x≠y and f(x)=f(y) • Example 1 ○ Let f be the function from {a,b,c,d} to {1,2,3} defined by § f(a)=3 § f(b)=2 § f(c)=1 § f(d)=3 ○ Is f an onto function? § Yes, f is onto. § Since all elements of the codomain are images of elements in the domain. ○ If the codomain were changed to {1,2,3,4}, f would not be onto. • Example 2 ○ Is the function f(x) = x^2 from the set of integers to the set of integers onto? ○ No, f is not onto because there is no integer x with x^2 =−1, for example. • Example 3 ○ Let f be the function from the N to the even natural numbers defined by ○ f(n)=2n. Is f an onto function? One to one? ○ f is an onto function, and f is one to one • Example 4 ○ Is the function f(x)=x^3 from R to R onto? One to one? ○ f is an onto function, and f is one to one • Example 5 ○ Is the function f(x)=1/|x| fomr R∖{0} to R onto? One to one? ○ f is not injective, and f is not surjective. Inverse Functions • Let f be a bijection from A to B. • Then the inverse of f, denoted f^(−1) , is the function from B to A defined as • f^(−1) (y)=x iff f(x)=y • No inverse exists unless f is a bijection. Why? • Example Questions • Example 1 ○ Let f be the function from {a,b,c} to {1,2,3} such that § f(a)=2 § f(b)=3 § f(c)=1 ○ Is f invertible and if so what is its inverse? ○ The function f is invertible because it is a one-to-one correspondence. ○ The inverse function f^(−1) reverses the correspondence given by f, so § f^(−1) (1)=c § f^(−1) (2)=b § f^(−1) (3)=a • Example 2 ○ Let f:Z→Z be such that f(x)=x+1. ○ Is f invertible, and if so, what is its inverse? ○ The function f is invertible because it is a one-to-one correspondence. ○ The inverse function f^(−1) reverses the correspondence so f^(−1) (y)=y −1. • Example 3 ○ Let f:R→R be such that f(x)=x^2. ○ Is f invertible, and if so, what is its inverse? ○ The function f is not invertible because it is not one-to-one. Composition • Let f:B→C, g:A→B. • The composition of f with g, denoted f∘g is the function from A to C defined by • f∘g(x)=f(g(x)) • Example Composition Questions • Example 1 ○ If f(x)=x^2 and g(x)=2x+1 ○ Then f(g(x))=(2x+1)^2 ○ And g(f(x))=2x^2+1 • Example 2 ○ Let f and g be functions from the set of integers to the set of integers defined by § f(x)=2x+3 § g(x)=3x+2 ○ What is the composition of f and g, and also the composition of g and f ? § f∘g(x)=f(g(x))=f(3x+2)=2(3x+2)+3=6x+7 § g∘f(x)=g(f(x))=g(2x+3)=3(2x+3)+2=6x+11 Graphs of Functions • Let f be a function from the set A to the set B. • The graph of the function f is the set of ordered pairs {(a,b)┤|a∈A and f(a)=b}. • Example Some Important Functions • The floor function f(x)=⌊x⌋ is the largest integer less than or equal to x. • The ceiling function f(x)=⌈x⌉ is the smallest integer greater than or equal to x • Example ○ ⌈3.5⌉=4, ⌊3.5⌋=3 ○ ⌈−1.5⌉=−1, ⌊−1.5⌋=−2 Factorial Function • f:N→Z+, denoted by f(n) = n! is • the product of the first n positive integers when n is a nonnegative integer. ○ f(n)=1 ∙ 2 ∙∙∙ (n – 1) ∙ n, ○ f(0)=0! = 1 • Examples: ○ f(1)=1!=1 ○ f(2)=2!=1∙2=2 ○ f(6)=6!=1∙2∙3∙4∙5∙6=720 ○ f(20)=2,432,902,008,176,640,000 Partial Function • A partial function f from a set A to a set B is an assignment to each element a in a subset of A, of a unique element b in B. • The sets A and B are called the domain and codomain of f, respectively. • We day that f is undefined for elements in A that are not in the domain of definition of f. • When the domain of definition of f equals A, we say that f is a total function. • Example ○ f:N→Z where f(n)=√n is a partial function from Z to R ○ where the domain of definition is the set of nonnegative integers. ○ Note that f is undefined for negative integers.$

2.2 Set Operations

$Union • Definition ○ 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} • Example: What is {1,2,3}∪{3, 4, 5}? ○ {1,2,3,4,5} • Venn Diagram Intersection • Definition ○ The intersection of sets A and B, denoted by A ∩ B, is ○ {x|x∈A∧x∈B} • Note ○ If the intersection is empty, then ○ A and B are said to be disjoint. • Example: What is {1,2,3} ∩ {3,4,5} ? ○ {3} • Example: What is {1,2,3} ∩ {4,5,6} ? ○ ∅ • Venn Diagram Complement • Definition ○ If A is a set, then the complement of the A (with respect to U), denoted by Ā is the set U−A ○ Ā={x∈U|x∉A} ○ (The complement of A is sometimes denoted by A^c.) • Example ○ If U is the positive integers less than 100, ○ what is the complement of {x | x 70} ○ {x│x≤70} • Venn Diagram Difference • Definition ○ 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. ○ The difference of A and B is also called the complement of B with respect to A. ○ A–B={x|x∈A∧x∉B}=A∩B ̅ • Venn Diagram Set Identities • Identity laws ○ A∪∅=A ○ A∩U=A • Domination laws ○ A∪U=U ○ A∩∅=∅ • Idempotent laws ○ A∪A=A ○ A∩A=A • Complementation law ○ ((A ̅ ) ) ̅=A ̅ • Communtative laws ○ A∪B=B∪A ○ A∩B=B∩A • Associative laws ○ A∪(B∪C)=(A∪B)∪C ○ A∩(B∩C)=(A∩B)∩C • Distributive laws ○ A∩(B∪C)=(A∩B)∪(A∩C) ○ A∪(B∩C)=(A∪B)∩(A∪C) • De Morgan$

2.1 Sets

$Sets • A set is an unordered collection of objects. ○ the students in this class ○ the chairs in this room • The objects in a set are called the elements, or members of the set. • A set is said to contain its elements. • The notation a∈A denotes that a is an element of the set A. • If a is not a member of A, write a∉A Describing a Set: Roster Method • S={a,b,c,d} • Order not important ○ S={a,b,c,d}={b,c,a,d} • Each distinct object is either a member or not; listing more than once does not change the set. ○ S={a,b,c,d}={a,b,c,b,c,d} • Dots (…) may be used to describe a set without listing all of the members when the pattern is clear. ○ S={a,b,c,d, …,z} Example of Roster Method • Set of all vowels in the English alphabet: ○ V={a,e,i,o,u} • Set of all odd positive integers less than 10: ○ O={1,3,5,7,9} • Set of all positive integers less than 100: ○ S={1,2,3,…,99} • Set of all integers less than 0: ○ S={…, −3,−2,−1} Some Important Sets • N = natural numbers = {0,1,2,3…} • Z = integers = {…,−3,−2,−1,0,1,2,3,…} • Z+= positive integers = {1,2,3,…} • R = set of real numbers • R+= set of positive real numbers • ℂ = set of complex numbers. • Q = set of rational numbers Set-Builder Notation • Specify the property or properties that all members must satisfy: ○ S = {x|x is a positive integer less than 100} ○ O = {x┤|x is an odd positive integer less than 10} ○ O = {x∈Z+ | x is odd and x10} • A predicate may be used: ○ S={x|P(x)} • All prime numbers ○ S={x│Prime(x) } • Positive rational numbers: ○ Q+={x∈R │x=p/q, for some positive integers p,q} Universal Set and Empty Set • The universal set U is the set containing everything currently under consideration. ○ Sometimes implicit ○ Sometimes explicitly stated. ○ Contents depend on the context. • The empty set is the set with no elements. • Symbolized ∅, but {} also used. • Venn Diagram Russell’s Paradox • Let S be the set of all sets which are not members of themselves. • A paradox results from trying to answer the question • “Is S a member of itself?” • Related Paradox: ○ Henry is a barber who shaves all people who do not shave themselves. ○ A paradox results from trying to answer the question ○ “Does Henry shave himself?” Some things to remember • Sets can be elements of sets. ○ {{1,2,3},a, {b,c}} ○ {NZQR • The empty set is different from a set containing the empty set. ○ ∅≠{∅} Set Equality • Two sets are equal if and only if they have the same elements. • Therefore if A and B are sets, then • A and B are equal if and only if ∀x(x∈A⟷x∈B) . • We write A = B if A and B are equal sets. ○ {1,3,5}={3,5,1} ○ {1,5,5,5,3,3,1}={1,3,5} Subsets • The set A is a subset of B, if and only if • every element of A is also an element of B. • The notation A⊆B is used to indicate that A is a subset of the set B. • A⊆B holds if and only if ∀x(x∈A→x∈B) is true. • Special Subsets ○ Because a∈∅ is always false, ∅⊆S, for every set S. ○ Because a∈S→a∈S,S⊆S, for every set S. Showing a Set is or is not a Subset of Another Set • Showing that A is a Subset of B ○ show that if x belongs to A, then x also belongs to B. • Showing that A is not a Subset of B ○ find an element x∈A with x∉B. ○ (Such an x is a counterexample to the claim that x∈A implies x ∈ B.) • Examples: ○ The set of all computer science majors at your school is a subset of all students at your school. ○ The set of integers with squares less than 100 is not a subset of the set of nonnegative integers. Another look at Equality of Sets • Recall that two sets A and B are equal, denoted by A=B, iff ○ ∀x(x∈A⟷x∈B) • Using logical equivalences we have that A=B iff ○ ∀x((x∈A→x∈B)∧(x∈B→x∈A)) • This is equivalent to ○ A⊆B and B⊆A Proper Subsets • If A⊆B, but A≠B, then we say A is a proper subset of B, denoted by A⊂B. • If A⊂B, then ∀x(x∈A→x∈B)∧∃(x∈B∧x∉A) is true. • Venn Diagram Set Cardinality • Finite and infinite ○ If there are exactly n distinct elements in S ○ where n is a nonnegative integer, we say that S is finite. ○ Otherwise it is infinite. • Definition ○ The cardinality of a finite set A, denoted by |A|, ○ is the number of (distinct) elements of A. • Examples: ○ |ø| = 0 ○ Let S be the letters of the English alphabet. Then |S|=26 ○ |{1,2,3}| = 3 ○ |{ø}| = 1 ○ The set of integers is infinite. Power Sets • The set of all subsets of a set A, denoted P(A), is called the power set of A. • Example ○ If A={a,b} then P(A)= {ø, {a},{b},{a,b}} • If a set has n elements, then the cardinality of the power set is 2^n. • (In Chapters 5 and 6, we will discuss different ways to show this.) Tuples • The ordered n-tuple (a_1,a_2,…,a_n) is the ordered collection that ○ has a_1 as its first element ○ and a_2 as its second element ○ and so on until an as its last element. • Two n-tuples are equal if and only if their corresponding elements are equal. • 2-tuples are called ordered pairs. • The ordered pairs (a,b) and (c,d) are equal if and only if a=c and b=d. • Note: (a,b)={a,{a,b}} Cartesian Product • Cartesian Product of two sets ○ The Cartesian Product of two sets A and B, denoted by A×B is ○ the set of ordered pairs (a,b) where a∈A and b∈B . ○ A×B={(a,b)│a∈A∧b∈B} • Example: ○ A={a,b} ○ B={1,2,3} ○ A×B={(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)} • Cartesian Product of more sets ○ The cartesian products of the sets A_1,A_2,…,A_n ○ denoted by A_1×A_2×…×A_n ○ is the set of ordered n-tuples (a_1,a_2,…,a_n ) ○ where a_i belongs to A_i for i=1,2, …,n ○ A_1×A_2×…×A_n={(a_1,a_2,…,a_n )│a_i∈A_i for i=1,2,…,n} • Example ○ What is A × B × C where A = {0,1}, B = {1,2} and C = {0,1,2} ○ A×B×C= {(0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)}$

1.8 Proof Methods and Strategy

$Proof by Cases • To prove a conditional statement of the form: ○ \(p_1∨p_2∨…∨p_n)→q • Use the tautology ○ \(p_1∨p_2∨…∨p_n)→q ↕ ○ (p_2→q)∧(p_2→q)∧…∧(p_n→q) • Each of the implications p_i→q is a case. • Example ○ Let a@b=max{a, b}=a if a≥b, ○ otherwise a@b=max{a, b}=b. ○ Show that for all real numbers a, b, c § (a@b)@c=a@(b@c) ○ (This means the operation @ is associative.) ○ Let a, b, and c be arbitrary real numbers. ○ Then one of the following 6 cases must hold. § a≥b≥c § a≥c≥b § b≥a≥c § b≥c≥a § c≥a≥b § c≥b≥a Without Loss of Generality • Show that if x and y are integers and both x∙y and x+y are even, • then both x and y are even. • Use a proof by contraposition. • Suppose x and y are not both even. • Then, one or both are odd. • Without loss of generality, assume that x is odd. • Then x=2m+1 for some integer m. • Case 1: y is even. ○ Then y=2n for some integer n, so ○ x+y=(2m+1)+2n=2(m+n)+1 is odd. • Case 2: y is odd. ○ Then y=2n+1 for some integer n, so ○ x∙y=(2m+1)(2n+1)=2(2m∙n+m+n)+1 is odd. • We only cover the case where x is odd • because the case where y is odd is similar. • The use phrase without loss of generality (WLOG) indicates this. Existence Proofs • Proof of theorems of the for ∃x P(x). • Constructive existence proof: ○ Find an explicit value of c, for which P(c) is true. ○ Then ∃x P(x) is true by Existential Generalization (EG). • Example: ○ Show that there is a positive integer that can be written as ○ the sum of cubes of positive integers in two different ways: ○ 1729=〖10〗^3+9^3=〖12〗^3+1^3 • Nonconstructive existence proof ○ In a nonconstructive existence proof, ○ we assume no c exists which makes P(c) true ○ and derive a contradiction. • Example ○ Show that there exist irrational numbers x,y such that x^y is rational. ○ We know that √2 is irrational. ○ Consider the number 〖√2〗^√2. ○ If 〖√2〗^√2 is rational § we have two irrational numbers x and y with x^y rational § namely x=√2 and y=√2. ○ If 〖√2〗^√2 is irrational § then we can let x=〖√2〗^√2 and y=√2 so that § x^y= (〖√2〗^√2 )^√2=〖√2〗^(√2×√2)=〖√2〗^2=2. Uniqueness Proofs • Some theorems asset the existence of • a unique element with a particular property, ∃!x P(x). • The two parts of a uniqueness proof are ○ Existence § We show that an element x with the property exists. ○ Uniqueness § We show that if y≠x, then y does not have the property. • Example ○ Show that if a and b are real numbers and a≠0, then ○ there is a unique real number r such that ar+b=0. ○ Existence § The real number r =−b/a is a solution of ar+b=0 § because a(−b/a)+b=−b+b=0. ○ Uniqueness § Suppose that s is a real number such that as+b=0. § Then ar+b=as+b, where r=−b/a. § Subtracting b from both sides § and dividing by a shows that r = s. Additional Proof Methods • Later we will see many other proof methods: • Mathematical induction ○ which is a useful method for proving statements of the form ∀n P(n), ○ where the domain consists of all positive integers. • Structural induction ○ which can be used to prove such results about recursively defined sets. • Cantor diagonalization ○ used to prove results about the size of infinite sets. • Combinatorial proofs use counting arguments.$

1.7 Introduction to Proofs

Proofs of Mathematical Statements • A proof is a valid argument that establishes the truth of a statement. • In math, CS, and other disciplines, informal proofs which are generally shorter, are generally used. ○ More than one rule of inference are often used in a step. ○ Steps may be skipped. ○ The rules of inference used are not explicitly stated. ○ Easier for to understand and to explain to people. ○ But it is also easier to introduce errors. Definitions • A theorem is a statement that can be shown to be true using: ○ definitions ○ other theorems ○ axioms (statements which are given as true) ○ rules of inference • A lemma is a ‘helping theorem’ or a result which is needed to prove a theorem. • A corollary is a result which follows directly from a theorem. • Less important theorems are sometimes called propositions. • A conjecture is a statement that is being proposed to be true. • Once a proof of a conjecture is found, it becomes a theorem, it may turn out to be false. Forms of Theorems • Many theorems assert that a property holds for all elements in a domain, such as the integers, the real numbers, or some of the discrete structures that we will study in this class. • Often the universal quantifier (needed for a precise statement of a theorem) is omitted by standard mathematical convention. • For example, the statement: ○ “If xy, where x and y are positive real numbers, then x^2y^2” ○ really means ○ “For all positive real numbers x and y, if xy, then x^2y^2.” Proving Theorems • Many theorems have the form: ∀x(P(x)→Q(x)) • To prove them, we show that P(c)→Q(c) where c is an arbitrary element of the domain, • By universal generalization the truth of the original formula follows. • So, we must prove something of the form: p→q Proving Conditional Statements: p→q • Trivial Proof ○ If we know q is true, then p→q is true as well. ○ “If it is raining then 1=1. • Vacuous Proof ○ If we know p is false then p→q is true as well. ○ “If I am both rich and poor then 2 + 2 = 5.” • Even though these examples seem silly, both trivial and vacuous proofs are often used in mathematical induction, as we will see in Chapter 5 • Direct Proof Assume that p is true. Use rules of inference, axioms, and logical equivalences to show that q must also be true. • Example 1 of Direct Proof ○ Give a direct proof of the theorem “If n is an odd integer, then n^2 is odd.” ○ Assume that n is odd. Then n=2k+1 for an integer k. ○ Squaring both sides of the equation, we get: § n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1=2r+1, § where r=2k^2+2k , an integer. ○ We have proved that if n is an odd integer, then n^2 is an odd integer. • Example 2 of Direct Proof ○ Prove that the sum of two rational numbers is rational. ○ Assume x and y are two rational numbers. ○ Then there must be integers p,q,r,s such that x=p/q, y=r/s and s≠0, p≠0 ○ x+y=p/q+r/s=(ps+qr)/qs, where q,s≠0, and (ps+qr),qs are integers ○ Hence, x+y is rational • Proof by Contraposition ○ Assume ¬q and show ¬p is true also. ○ This is sometimes called an indirect proof method. ○ If we give a direct proof of ¬q→¬p then we have a proof of p→q. • Example of Proof by Contraposition ○ Prove that for an integer n, if n^2 is odd, then n is odd. ○ Use proof by contraposition. ○ Assume n is even (i.e., not odd). ○ Therefore, there exists an integer k such that n=2k. ○ Hence, n^2=4k^2=2(2k^2), and n^2 is even(i.e., not odd). ○ We have shown that if n is an even integer, then n^2 is even. ○ Therefore by contraposition, for an integer n, if n^2 is odd, then n is odd. • Proof by Contradiction: (AKA reductio ad absurdum). ○ To prove p, assume ¬p and derive a contradiction such as p∧¬p. (an indirect form of proof). ○ Since we have shown that ¬p→F is true, ○ it follows that the contrapositive T→p also holds. • Example of Proof by Contradiction ○ Use a proof by contradiction to give a proof that √2 is irrational. ○ Towards a contradiction assume that √2 is rational ○ Let a,b be such that √2=a/b, b≠0, and a,b have no common factors ○ 2=a^2/b^2 ⇒2b^2=a^2, so a^2 is even and a is even ○ Let a≔2k for some k∈Z, then a^2=4k^2 ○ Then 2b^2=4k^2⇒b^2=2k, so b^2 is even, and b is also even ○ So 2 divides a and b, which makes a contradiction ∎ Theorems that are Biconditional Statements • To prove a theorem that is a biconditional statement, that is, a statement of the form p↔q, we show that p→q and q→p are both true. • Example ○ Prove the theorem: “If n is an integer, then n is odd if and only if n^2 is odd.” ○ We have already shown (previous slides) that both p→q and q→p. ○ Therefore we can conclude p ↔ q. • Note ○ Sometimes iff is used as an abbreviation for “if an only if,” as in “If n is an integer, then n is odd iif n^2 is odd.” Looking Ahead • If direct methods of proof do not work: • We may need a clever use of a proof by contraposition. • Or a proof by contradiction. • In the next section, we will see strategies that can be used when straightforward approaches do not work. • In Chapter 5, we will see mathematical induction and related techniques. • In Chapter 6, we will see combinatorial proofs

Shawn Zhong

Shawn Zhong

Math 240

2.3 Functions

2.2 Set Operations

2.1 Sets

1.8 Proof Methods and Strategy

1.7 Introduction to Proofs

Search

WeChat Account