February 2018 - Page 5 of 7 - 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.$

Math 541 – 2/9

$Examples of Orders • Example 1 ○ A≔(■8(0&−1@1&−1))∈GL_2 (R ○ A^3=(■8(0&−1@1&−1))^3=(■8(−1&1@−1&0))(■8(0&−1@1&−1))=(■8(1&0@0&1))=I ○ Thus, |A|=3 • Example 2 ○ In Z,Q,R,ℂ, every nonzero element has infinite order • Example 3 ○ In Q∗ and R∗, the elements of finite order are § |1|=1 § |−1|=2 ○ In ℂ^∗, there are lots more § elements of order n in ℂ are called n^th roots of unity § i is the fourth root of unity § i.e. i^1=i, i^2=−1, i^3=−i, i^4=1 • Example 4 ○ What are the orders of the elements in Z\/6Z? Elements Order Note 0 ̅ 1 0 ̅ is the identity 1 ̅ 6 1 ̅⋅6=6 ̅=0 ̅ 2 ̅ 3 2 ̅⋅3=6 ̅=0 ̅ 3 ̅ 2 3 ̅⋅2=6 ̅=0 ̅ 4 ̅ 3 4 ̅⋅3=(12) ̅=0 ̅ 5 ̅ 6 5 ̅⋅6=(30) ̅=0 ̅ ○ In general, if a ̅∈Z\/nZ, then the "n^th power" of a ̅ is (na) ̅ ○ Note that all the orders are divisors of 6 (Lagrange Theorem) • Example 5 ○ What are the orders of the elements in Z\/5Z×? § Z\/5Z×={1 ̅,2 ̅,3 ̅,4 ̅ } § (0,5)=0≠1, so 0 ̅∉Z\/5Z× Elements Order Note 1 ̅ 1 1 ̅ is the identity 2 ̅ 4 2 ̅^4=(16) ̅=1 ̅ 3 ̅ 4 3 ̅^4=81 ̅=1 ̅ 4 ̅ 2 4 ̅^2=(16) ̅=1 ̅ Symmetric Groups (Section 1.3) • Symmetric Group of Degree n ○ n∈Z(0) ○ S_n≔{bijective functions {1,…,n}→{1,…,n}} ○ S_n is a group with operation given by composition of functions ○ Composition of functions is an operation on S_n § S_n×S_n→S_n § (σ,τ)↦σ∘τ § σ∘τ is again bijictive, so this makes sense ○ Associativity § Suppose f:X→Y, g:Y→Z,h:Z→W § ((hg)∘f)(x)=(hg)(f(x))=h(g(f(x))) § (h(g∘f))(x)=h((g∘f)(x))=h(g(f(x))) § Thus (hg)∘f=h∘(g∘f) ○ Identity § Identity map ○ Inverses § Bijective functions have inverses Proposition 15 • Statement ○ |S_n |=n! • Proof ○ First, we prove that if X and Y are sets of order n, then ○ There are n! injective functions from X to Y ○ We argue by induction on n ○ n=1 § Clear ○ n1 § Suppose f:X→Y is injective § Let x∈X. § There are n possibilities for f(x) § f restricts to an injective function X∖{x}→Y∖{f(x)} § There are (n−1)! such functions, by induction § Thus, there are n(n−1)!=n! injective functions X→Y ○ (To be continued)$

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)}$

Math 521 – 2/7

$Complex Numbers ℂ • Definition ○ If z∈ℂ, then z=a+bi where a,b∈R and i^2=−1 • Real part and imaginary part ○ For z=a+bi ○ Re(z)=a is the real part of z ○ Im(z)=b is the imaginary part of z • Complex conjugate ○ z ̅=a−bi is the complex conjugate of z ○ zz ̅=(a+bi)(a−bi)=a^2+b^2 • Absolute value ○ |z|=√(zz ̅ )=√(a^2+b^2 ) is the absolute value of z ○ Note § For a real number x § |x|=√(x^2+0^2 )=√(x^2 )≥0 § |x|={■8(x&if x≥0@−x&if x0)┤ • Complex division ○ If z=a+bi, w=c+di∈ℂ, then ○ z/w=(zw ̅)/(ww ̅ )=(a+bi)(c−di)/(c+di)(c−di) =(ac+bd)/(c^2+d^2 )+(bc−ad)/(c^2+d^2 ) i Theorem 1.31 • If z and w are complex numbers, then ○ (z+w) ̅=z ̅+w ̅ ○ (zw) ̅=z ̅⋅w ̅ ○ z+z ̅=2Re(z), z−z ̅=2i Im(z) ○ zz ̅ is real and positive (except when z=0) Theorem 1.33 • If z and w are complex numbers, then (1) |z|0 unless z=0 in which case |z|=0 (2) |z ̅ |=|z| (3) |zw|=|z||w| § Let z=a+bi, w=c+di § Then zw=(ac−bd)+(ad+bc)i § |zw|=√((ac−bd)^2+(ad+bc)^2 ) § =√(a^2 c^2+b^2 d^2+a^2 d^2+b^2 c^2 ) § =√((a^2+b^2 )(c^2+d^2 ) ) § =√(a^2+b^2 ) √(c^2+d^2 ) § =|z||w| (4) |Re(z)|≤|z| (5) |z+w|≤|z|+|w| (Triangle Inequality) § |z+w|^2=(z+w)((z+w) ̅ ) § =(z+w)(z ̅+w ̅ ) § =zz ̅+zw ̅+z ̅w+ww ̅ § =|z|^2+|w|^2+zw ̅+z ̅w § =|z|^2+|w|^2+2Re(zw ̅ ) § ≤|z|^2+|w|^2+2|zw ̅ | by (4) § =|z|^2+|w|^2+2|z||w ̅ | by (3) § =|z|^2+|w|^2+2|z||w| by (2) § =(|z|+|w|)^2 § So |z+w|^2≤(|z|+|w|)^2 § Thus, |z+w|≤|z|+|w|∎ Euclidean Spaces • Inner product ○ If x ⃗,y ⃗∈Rn with § x ⃗=(x_1,x_2,…,x_n ) § y ⃗=(y_1,y_2,…,y_n ) ○ Then the inner product of x ⃗ and y ⃗ is § x ⃗⋅y ⃗=∑_(i=1)^n▒〖x_i y_i 〗 • Norm ○ If x ⃗∈Rn, we define the norm of x ⃗ to be ○ |x ⃗ |=√(x ⃗⋅x ⃗ ) • Euclidean spaces ○ The vector space Rn with inner product and norm ○ is called Euclidean n-space Theorem 1.37 • Suppose x ⃗,y ⃗,z ⃗∈Rn,α∈R, then (1) |x ⃗ |≥0 (2) |x ⃗ |=0 if and only if x ⃗=0 ⃗ (3) |αx ⃗ |=|α|⋅|x ⃗ | (4) |x ⃗⋅y ⃗ |≤|x ⃗ |⋅|y ⃗ | (Schwarz$

Shawn Zhong

Shawn Zhong

2.3 Functions

Math 541 – 2/9

2.2 Set Operations

2.1 Sets

Math 521 – 2/7

Search

WeChat Account