Notes Archives - Page 14 of 84 - Shawn Zhong

9.6 Partial Orderings

$Partial Orderings • Definition 1 ○ A relation R on a set S is called a partial ordering, or partial order, if it is reflexive, antisymmetric, and transitive. ○ A set together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). ○ Members of S are called elements of the poset. • Example 1 ○ Show that the “greater than or equal” relation (≥) is a partial ordering on the set of integers. ○ Reflexivity: a≥a for every integer a. ○ Antisymmetry: If a≥b and b≥a , then a=b. ○ Transitivity: If a≥b and b≥c , then a≥c. • Example 2 ○ Show that the divisibility relation (∣) is a partial ordering on the set of integers. ○ Reflexivity § a∣a for all integers a. (see Example 9 in Section 9.1) ○ Antisymmetry § If a and b are positive integers with a | b and b | a, then a = b § (see Example 12 in Section 9.1) ○ Transitivity § Suppose that a divides b and b divides c. § Then there are positive integers k and l such that b = ak and c = bl § Hence, c=a(kl), so a divides c. § Therefore, the relation is transitive. ○ (Z^+, ∣) is a poset. • Example 3 ○ Show that the inclusion relation (⊆) is a partial ordering on the power set of a set S. ○ Reflexivity: A⊆A whenever A is a subset of S. ○ Antisymmetry: If A and B are positive integers with A⊆B and B⊆A, then A=B. ○ Transitivity: If A⊆B and B⊆C, then A⊆C. Comparability • Definition 2 ○ The elements a and b of a poset (S,≼) are comparable if either a ≼ b or b ≼ a. ○ a,b∈S so that neither a ≼ b nor b ≼ a, then a and b are called incomparable. • Definition 3 ○ If (S,≼) is a poset and every two elements of S are comparable ○ Then S is called a totally ordered or linearly ordered set ○ And ≼ is called a total order or a linear order. ○ A totally ordered set is also called a chain. • Definition 4 ○ (S,≼) is a well-ordered set if it is a poset such that § ≼ is a total ordering § every nonempty subset of S has a least element. Hasse Diagrams • A Hasse diagram is a visual representation of a partial ordering that leaves out edges that must be present because of the reflexive and transitive properties. • A partial ordering is shown in (a) of the figure above. • The loops due to the reflexive property are deleted in (b). • The edges that must be present due to the transitive property are deleted in (c). • The Hasse diagram for the partial ordering (a), is depicted in © Lexicographic Order • Definition ○ Given two posets (A_1,≼_1) and (A_2,≼_2) ○ The lexicographic ordering on A_1⨉A_2 is defined by specifying that ○ (a_1, a_2) is less than (b1,b2), that is, (a_1, a_2) ≺ (b_1,b_2), ○ either if a_1 ≺_1 b_1 or if a_1=b_1 and a_2 ≺_2 b_2. ○ This definition can be easily extended to a lexicographic ordering on strings (see text). • Example ○ Consider strings of lowercase English letters ○ A lexicographic ordering can be defined using the ordering of the letters in the alphabet ○ This is the same ordering as that used in dictionaries. ○ discreet ≺ discrete, because these strings differ in the seventh position and e ≺ t. ○ discreet ≺ discreetness, because the first eight letters agree, but the second string is longer. Well Ordered Induction • Theorem ○ If (S,≤) is a well ordered poset and P is a property s.t. ○ If P(y) is true for all y x, then P(x) is true ○ Then P is true for all elements in the poset • Example ○ Suppose that a_(m,n) is defined for (m,n)∈N×N § a_0,0=0 § a_(m,n)={■8(a_(m−1,n)+1&if n=0 and m 0@a_(m,n−1)+n&if n 0)┤ ○ Show that a_(m,n)=m+n(n+1)/2 is defined for all (m,n)∈N×N • Solution ○ Use induction ○ Basis Step § a_0,0=0+(0⋅1)/2 ○ Inductive Step § Assume that a_(m^′,n^′ )=m^′+(n^′ (n^′+1))/2 whenever § (m^′,n′) is less than (m,n) in the lexicographic ordering of N×N § If n=0, by the inductive hypothesis, we can conclude □ a_(m,n)=a_(m−1,n)+1=m−1+n(n+1)/2+1=m+n(n+1)/2 § If n 0, by the inductive hypothesis, we can conclude □ a_(m,n)=a_(m−1,n)+1=m+n(n−1)/2+n=m+n(n+1)/2 Maximal and Minimal Elements • Definition ○ If (S,≤) is a ordered poset then an element a is ○ Minimal if there is no element b s.t. b≤a, and b is not equal to a ○ Maximal if there is no element b s.t. a≤b, and b is not equal to a ○ Greatest if for every element b∈S, b≤a ○ Least if for every element b∈S, a≤b • Intuition ○ Minimal: No element is strictly smaller ○ Least: Every other element is bigger ○ Maximal: No element is strictly bigger ○ Greatest: Every other element is smaller • Example 1 ○ Let {2,4,5,10,12,20,25} ordered by divisibility relation ○ Which element of {2,4,5,10,12,20,25} are maximal and which are minimal? ○ Is there a least or greatest element? ○ Maximal: 12, 20, 25 ○ Minimal: 2,5 ○ No least or greatest element. • Example 2 ○ Given an example of a poset with no minimal element and two maximal elements? ○ {〖1,1〗^∗,0,−1,−2,−3,…} where 1≥0≥−1≥−2≥…, and 1^∗≥0≥−1≥−2≥… Topological Sorting • Definition ○ If (S,R) is a partial ordering and (S,R^∗ ) is a total ordering then we say that ○ The two are compatible if R is a subset of R^∗ • Theorem ○ Let S be a finite set ○ Every partial order R on S has a compatible total order R^∗ • Proof ○ Every nonempty finite partial order has a minimal element ○ This can be proved by induction on the size of S ○ We should build a total ordering of S be selecting § a_1 to be a minimal element of S § a_2 to be the minimal element of S−{a_1 } § a_i to be the minimal element of S−{a_1,a_2,…,a_(i−1) } § a_n to be the least available element of S ○ We set R^∗={(a_i,a_i )|j≥i}$

Math 541 – 5/2

$Prime Ideal • Definition ○ Suppose R is commutative ○ An ideal P⊊R is prime if ○ a,b∈R,ab∈P⇒a∈P or b∈P • Example ○ Take R=Z ○ The prime ideals are ideals of the form (n), where n is prime or n=0 ○ Proof (⟹) § Let (n)⊆Z be a prime ideal, and n≠0 § We want to show that n is prime § Choose a,b∈Z s.t. n=ab § Then ab∈(n), so either a∈(n) or b∈(n) § Without loss of generality, suppose a∈(n) § Then ├ n┤ |a┤ § Choose q∈Z s.t. nq=a § n=ab⇒n=nqb⇒1=qb⇒b∈{±1} § So n is a prime ○ Proof (⟸) § (0) is prime □ Let a,b∈Z, and ab∈(0) □ Then ab=0 □ ⇒a=0 or b=0 □ ⇒a∈(0) or b∈(0) □ Therefore (0) is prime § (p) is prime for p∈Z prime □ Let a,b∈Z, and say ab∈(p) □ Then p|ab □ Since p is prime, this means p|a or p|b □ ⇒a∈(p) or b∈(p) Proposition 73: Criterion for Prime Ideal • Statement ○ Let R be a commutative ring, P⊆R an ideal, then ○ P is prime ⇔ R\/P is a domain ○ In particular, R is a domain ⇔ 0 ideal is prime • Proof (⟹) ○ Let a+P,b+P∈(R/P)∖\{P} ○ Then (a+P)(b+P)=ab+P=0 ○ So, ab∈P ○ Since P is prime, a∈P or b∈P ○ Therefore a+P=0 or b+P=0 • Proof (⟸) ○ Let a,b∈R, and suppose ab∈P, then ○ 0=ab+P=(a+P)(b+P) ○ Since R\/P is a domain, a+P=0 or b+P=0 ○ So a∈P or b∈P • Example ○ (x^2−1)⊆R[x] is not prime ○ R[x]\/(x^2−1)≅R×R, which is not a domain ○ Also, x^2−1∈(x^2−1), but x−1,x+1∉(x^2−1) Corollary 74 • Statement ○ If R is a commutative ring, and M⊆R is maximal, then M is prime • Proof ○ M is maximal ⇒R\/M is a field ⇒R\/M is a domain ⇒ M is prime Euclidean Domain • Definition ○ Let R be a domain ○ A norm on R is a function N:R→Z(≥0) s.t. N(0)=0 ○ R is called a Euclidean domain if R is equipped with a norm N s.t. ○ ∀a,b∈R with b≠0, ∃q,r∈R s.t. § a=qb+r § Either r=0 or N(r) N(b) • Example 1 ○ Z is a Euclidean domain, N(a)=|a| • Example 2 ○ If F is a field, then F is trivially a Euclidean domain ○ Take N:F→Z(≥0) to be any function s.t. N(0)=0 ○ Then, if a,b∈F, where b≠0, take q=a/b,r=0 • Example 3 ○ If F is a field, then F[x] is a Euclidean domain, with N(p)=deg⁡p ○ The division algorithm have is just polynomial division ○ Note § deg⁡0=−∞∉Z(≥0), so this definition isn t quite right § To handle this problem, define a norm to take vales not in Z(≥0) § But any total ordered set in order-preserving bijection with Z(≥0) § (For instance, Z(≥0)∪{−∞}) Proposition 75 • Statement ○ Every ideal in a Euclidean domain R is principal ○ More precisely, if I⊆R is an ideal, then I=(d), where ○ d is an element of I with minimum norm • Proof ○ Let I⊆R be an ideal ○ If I=(0), then I is principal, so assume I≠(0) ○ {N(a)│a∈I∖{0} } has a minimal element, by well-ordering principal ○ Choose d∈I∖{0} s.t. N(d) is minimal ○ Certainly, (d)⊆I ○ Let a∈I, write a=qd+r, where q,r∈R and either r=0 or N(r) N(d) ○ Since r=a−qd∈I, N(r) can t be smaller than N(d) ○ So r=0⇒a=qd⇒a∈(d) • Example 1 ○ We haven t yet proven that F[x] is a Euclidean domain, when F is a field ○ Once we show this, we ll know F[x] has the property that ○ All of its ideals are principal • Definition ○ A domain in which every ideal is principal is called a principal ideal domain • Example 2 ○ Z[x] cannot be a Euclidean domain, since (2,x)⊆Z[x] is not principal Theorem 76 • Statement ○ Let F be a field ○ Then F[x] is a Euclidean domain ○ More specifically, if a,b∈F[x] where b≠0, then ○ ∃!q,r∈F[x] s.t. a=bq+r and deg⁡r deg⁡b • Proof (Existence) ○ We argue by induction on deg⁡a ○ If a=0, take q,r=0, so assume a≠0 ○ Set n≔deg⁡a, m≔deg⁡b ○ If n m, then take q=0,r=a ○ Assume n≥m ○ Write a=a_n x^n+…+a_1 x+a_0,b=b_m x^m+…+b_1 x+b_0 ○ Set a^′=a−a_n/b_m x^(n−m) b ○ Since a and a_n/b_m x^(n−m) b have the same leading coefficient, deg⁡a′ deg⁡a ○ By induction, ∃q^′,r∈F[x] with a^′=q^′ b+r with deg⁡r deg⁡b ○ Set q=q^′+a_n/b_m x^(n−m) b ○ Then a=a^′+a_n/b_m x^(n−m) b=q^′ b+r+a_n/b_m x^(n−m) b=(q^′+a_n/a_m x^(n−m) )b+r=qb+r • Proof (Uniqueness) ○ Suppose bq^′+r^′=a=bq+r where deg⁡r deg⁡b, and deg⁡r′ deg⁡b ○ Then deg⁡(a−bq) deg⁡b and deg⁡〖(a−bq′) deg⁡b 〗 ○ ⇒deg⁡((a−bq)−(a−bq^′ ))=deg⁡(bq^′−bq)=deg⁡b+deg⁡(q^′−q) deg⁡b ○ ⇒deg⁡(q^′−q) 0⇒q^′=q ○ It follows immediately that r^′=r$

Math 521 – 5/4

$Definition 7.1: Limit of Sequence of Functions • Suppose {f_n } is a sequence of functions defined on a set E • Suppose the sequence of numbers {f_n (x)} converges ∀x∈E • We can then defined f by f(x)=(lim)┬(n→∞)⁡〖f_n (x)〗,∀x∈E Example 7.2: Double Sequence • "Let" s_(m,n)=m/(m+n),(m,n∈N • Fix n∈N ○ lim┬(m→∞)⁡〖s_(m,n) 〗=1 ○ lim┬(n→∞)⁡lim┬(m→∞)⁡〖s_(m,n) 〗 =1 • Fix m∈N ○ lim┬(n→∞)⁡〖s_(m,n) 〗=0 ○ lim┬(m→∞)⁡lim┬(n→∞)⁡〖s_(m,n) 〗 =0 Example 7.3: Convergent Series of Continuous Functions • Let f_n (x)=x^2/(1+x^2 )^n ,(x∈Rn∈Z(≥0) ) • Let f(x)=∑_(n=0)^∞▒〖f_n (x) 〗=∑_(n=0)^∞▒x^2/(1+x^2 )^n • When x=0 ○ f_n (0)=0, so f(0)=0 • When x≠0 ○ f(x) is a convergent geometric series with sum ○ f(x)=∑_(n=0)^∞▒x^2/(1+x^2 )^n =x^2/(1−(1/(1+x^2 ))^n )=1+x^2 • Therefore, f(x)={■8(0&for x=0@1+x^2&for x≠0)┤ • So convergent series of continuous functions may be discontinuous Example 7.5: Changing the Order of Limit and Derivative • Let f_n (x)=sin⁡(nx)/√n, (x∈Rn∈N • Let f(x)=lim┬(n→∞)⁡〖f_n (x)〗=0 • Then f^′ (x)=0, but f_n^′ (x)=√n cos⁡(nx)→∞≠0 Example 7.6: Changing the Order of Limit and Integral • Let f_n (x)=nx(1−x^2 )^n, (x∈[0,1],n∈N, then • lim┬(n→∞)⁡(∫_0^1▒〖f_n (x)dx〗)=lim┬(n→∞)⁡(∫_0^1▒〖nx(1−x^2 )^n dx〗)=lim┬(n→∞)⁡〖n/(2n+2)〗=1/2 • ∫_0^1▒(lim┬(n→∞)⁡〖f_n (x)〗 ) dx=∫_0^1▒(lim┬(n→∞)⁡〖nx(1−x^2 )^n 〗 ) dx=∫_0^1▒〖0 dx〗=0 Definition 7.7: Uniform Convergence • A sequence of function {f_n }_(n∈N converges uniformly on E to a function f if • ∀ε 0, ∃N∈N s.t. if n≥N, then |f_n (x)−f(x)| ε,∀x∈E Theorem 7.11: Interchange of Limits • Suppose f_n→f on a set E uniformly on a metric space • Let x be a limit point of E and suppose that lim┬(t→x)⁡〖f_n (t)〗=A_n,(n∈N • Then {A_n } converges and lim┬(t→x)⁡f(t)=lim┬(n→∞)⁡〖A_n 〗 • i.e. (lim)┬(t→x)⁡(lim)┬(n→∞)⁡〖f_n (t)〗 =(lim)┬(n→∞)⁡(lim)┬(t→x)⁡〖f_n (t)〗 Theorem 7.12: Uniform Convergence Implies Continuity • If {f_n } is a sequence of continuous functions on E, and f_n→f uniformly on E • Then f is continuous on E Definition 7.14: Space of Bounded Continuous Functions • Let X be a metric space • Let C(X) be the set of all continuous bounded functions f:X→ℂ • If f∈C(X), define the supremum norm ‖f‖≔(sup)┬(x∈X)⁡|f(x)| • ‖f−g‖ is a distance function that makes C(X) a metric space Example 2.44: Cantor Set • Define a sequence of compact sets E_n ○ E_0=[0,1] ○ E_1=[0, 1/3]∪[2/3,1] ○ E_2=[0, 1/9]∪[2/9,3/9]∪[6/9,7/9]∪[8/9,1] ○ ⋮ • The set P≔⋂24_(n=1)^∞▒E_n is called the Cantor Set • P is compact, nonempty, uncountable, perfect, measure zero Example 4.27: Discontinuous Function • Let f(x)≔{■8(1&if x∈Q0&if x∉Q┤ • Then f(x) is discontinuous at all x∈R • Let g(x)≔{■8(x&if x∈Q0&if x∉Q┤ • Then g(x) is discontinuous everywhere except x=0$

Math 521 – 5/2

$Theorem 6.20: Fundamental Theorem of Calculus (Part I) • Statement ○ Let f∈R on [a,b] ○ Define F(x)=∫_a^x▒f(t)dt for x∈[a,b], then § F is continuous on [a,b] ○ Furthermore, if f is continuous at x_0∈[a,b], then § F is differentiable at x_0, and § F^′ (x_0 )=f(x_0 ) • Proof: F is continuous on [a,b] ○ Since f∈R, f is bounded, so ∃M∈R s.t. § |f(t)|≤M,∀a≤t≤b ○ If a≤x y≤b § |F(y)−F(x)|=|∫_y^x▒f(t)dt|≤M(x−y) ○ Given ε 0 § |F(y)−F(x)| ε provided |y−x| ε/M ○ So this shows uniform continuity of F • Proof: F^′ (x_0 )=f(x_0 ) ○ Suppose f is continuous at x_0 ○ Given ε 0,∃δ 0 s.t. § |f(x)−f(x_0 )| ε whenever |x−x_0 | δ for a≤x≤b ○ If x_0−δ s≤x_0≤t x_0+δ where a≤s t≤b § |(F(t)−F(s))/(t−s)−f(x_0 )| § =|(1/(t−s) ∫_s^t▒f(x)dx)−f(x_0 )| § =|(1/(t−s) ∫_s^t▒f(x)dx)−(1/(t−s) ∫_s^t▒f(x_0 )dx)| § =|1/(t−s) ∫_s^t▒(f(x)−f(x_0 ))dx| § |1/(t−s) (t−s)ε|=ε ○ Consequently, F^′ (x_0 )=f(x_0 ) Theorem 6.21: Fundamental Theorem of Calculus (Part II) • Statement ○ Let f∈R on [a,b] ○ If there exists a differentiable function F on [a,b] s.t. F^′=f ○ Then ∫_a^b▒f(x)dx=F(b)−F(a) • Proof ○ Let ε 0 be given ○ Choose a partition P={x_0,x_1,…,x_n } of [a,b] s.t. § U(P,f)−L(P,f) ε ○ Apply the Meal Value Theorem, ∃t_i∈[x_(i−1),x_i ] s.t. § F(x_i )−F(x_(i−1) )=f(t_i )Δx_i where 1≤i≤n ○ Thus,∑_(i=1)^n▒〖f(t_i )Δx_i 〗 forms a telescoping series § ∑_(i=1)^n▒〖f(t_i )Δx_i 〗=F(x_n )−F(x_(n−1) )+F(x_(n−1) )+…−F(x_0 ) § =F(b)+(F(x_(n−1) )−F(x_(n−1) ))+…+(F(x_1 )−F(x_1 ))−F(a) § =F(b)−F(a) ○ Combining the obvious inequalities below § L(P,f)≤∑_(i=1)^n▒〖f(t_i )Δx_i 〗≤U(P,f) § L(P,f)≤∫_a^b▒fdx≤U(P,f) ○ We get § |∑_(i=1)^n▒〖f(t_i )Δx_i 〗−∫_a^b▒fdx| ε § ⇒|F(b)−F(a)−∫_a^b▒fdx| ε ○ Therefore, ∫_a^b▒f(x)dx=F(b)−F(a)$

Math 521 – 4/30

$Definition 6.1: Riemann Integral • Partition ○ A partition P of a closed interval [a,b] is a finite set of points ○ {x_0,x_1,…,x_n } where a=x_0≤x_1≤…≤x_(n−1)≤x_n=b • Let f be a bounded real function on [a,b], for each partition P of [a,b] ○ Define M_i and m_i to be § M_i=sup┬(x∈[x_(i−1),x_i ] )⁡f(x) § m_i=inf┬(x∈[x_(i−1),x_i ] )⁡f(x) ○ Define the upper sum and lower sum to be § U(P,f)=∑_(i=1)^n▒〖M_i Δx_i 〗 § L(P,f)=∑_(i=1)^n▒〖m_i Δx_i 〗 § where Δx_i=x_i−x_(i−1) ○ Define the upper and lower Reimann integral to be § (∫_a^b▒ ) ̅fdx=inf┬(All P)⁡U(P,f) § ▁(∫_a^b▒ ) fdx=sup┬(All P)⁡L(P,f) • If (∫_a^b▒ ) ̅fdx=▁(∫_a^b▒ ) fdx, then ○ We say that f is Riemann\-integrable on [a,b], and write f∈R ○ Their common value is denoted by∫_a^b▒fdx or ∫_a^b▒f(x)dx • Well-definedness of upper and lower Riemann integral ○ Since f is bounded, ∃m,M∈R s.t. § m≤f(x)≤M (a≤x≤b) ○ Therefore for every partition P of [a,b] § m(b−a)≤L(P,f)≤U(P,f)≤M(b−a) ○ So (∫_a^b▒ ) ̅fdx and ▁(∫_a^b▒ ) fdx are always defined Definition 6.2: Riemann-Stieltjes Integral • Let α be a monotonically increasing function on [a,b] • Let f be a real-valued function bouned on [a,b] • For each partition P of [a,b], define ○ M_i=sup┬(x∈[x_(i−1),x_i ] )⁡f(x) ○ m_i=inf┬(x∈[x_(i−1),x_i ] )⁡f(x) ○ Δα_i=α(x_i )−α(x_(i−1) ) ○ U(P,f,α)=∑_(i=1)^n▒〖M_i Δα_i 〗 ○ L(P,f,α)=∑_(i=1)^n▒〖m_i Δα_i 〗 ○ (∫_a^b▒ ) ̅fdx=inf┬(All P)⁡U(P,f,α) ○ ▁(∫_a^b▒ ) fdx=sup┬(All P)⁡L(P,f,α) • If(∫_a^b▒ ) ̅fdx=▁(∫_a^b▒ ) fdx ○ We denote the common value by∫_a^b▒fdα or ∫_a^b▒f(x)dα(x) ○ This is the Riemann-Stieltjes integral of f with respect to α over [a,b] ○ We say f is integrable with respect to α with on [a,b], and write f∈R(α) • Note ○ When α(x)=x, this is just Riemann integral Definition 6.3: Refinement and Common Refinement • We say that the partition P^∗ is a refinement of P if P^∗⊃P • Given two partitions P_1 and P_2, their common refinement is P_1∪P_2 Theorem 6.4: Properties of Refinement • If P^∗ is a refinement of P, then ○ L(P,f,α)≤L(P^∗,f,α) ○ U(P^∗,f,α)≤U(P,f,α) Theorem 6.5: Properties of Common Refinement • Statement ○ (∫_a^b▒ ) ̅fdx≤▁(∫_a^b▒ ) fdx • Proof Outline ○ Given 2 partitions P_1 and P_2 ○ Let P^∗ be the common refinement ○ Then L(P_1,f,α)≤L(P^∗,f,α)≤U(P^∗,f,α)≤U(P_2,f,α) Theorem 6.6 • Statement ○ f∈R(α) on [a,b] if and only if ○ ∀ε 0, there exists a partition P s.t. U(P,f,α)−L(P,f,α) ε • Proof Outline ○ ∀P,L(P,f,α)≤▁(∫_a^b▒ ) fdx≤(∫_a^b▒ ) ̅fdx≤U(P,f,α) ○ (⟸) If U(P,f,α)−L(P,f,α) ε § Then 0≤(∫_a^b▒ ) ̅fdx−▁(∫_a^b▒ ) fdx ε ○ (⟹) If f∈R(α) § Then ∃P_1,P_2 s.t. □ U(P_1,f,α)−∫_a^b▒fdα ε/2 □ ∫_a^b▒fdα−L(P_1,f,α) ε/2 § Consider their common refinement P § By Theorem 6.4, U(P,f,α)−L(P,f,α) ε Theorem 6.8 • If f is continuous on [a,b], then f∈R(α) on [a,b] Theorem 6.9 • If f is monotonic on [a,b], and α is continuous on [a,b] • Then f∈R(α) on [a,b] Theorem 6.10 • If f is bounded on [a,b] with finitely many points of discontiunity • And α is continuous on these points, then f∈R(α)$

Shawn Zhong

Shawn Zhong

Notes

9.6 Partial Orderings

Math 541 – 5/2

Math 521 – 5/4

Math 521 – 5/2

Math 521 – 4/30

Search

WeChat Account