February 14, 2018 - Shawn Zhong

$Schwarz Inequality • See Theorem 1.35 in Rudin for a proof of Schwarz Inequality for ℂ ○ For intuition, try proving (x_1 y_2+x_2 y_2 )^2≤(x_1^2+x_2^2 )(y_1^2+y_2^2 ) • Triangle Inequality ○ In a Euclidean Space, |x ⃗⋅y ⃗ |≥|x ⃗ |⋅|y ⃗ | ○ |x ⃗+y ⃗^2 |=|x ⃗ |^2+2x ⃗⋅y ⃗+|y ⃗ |^2≤|x ⃗ |^2+2|x ⃗ ||y ⃗ |+|y ⃗ |^2=(|x ⃗ |+|y ⃗ |)^2 ○ Thus |x ⃗+y ⃗ ||x ⃗ |+|y ⃗ | ○ Let x ⃗≔x ⃗−y ⃗, y ⃗≔y ⃗−z ⃗, we have |x ⃗−z ⃗ ||x ⃗−y ⃗ |+|y ⃗−z ⃗ | Function • Given two sets A and B • A function (or mapping) is a rule that assigns elements in A to elements in B • Notationally, if f is a function from A to B, we write f:A→B • Set A is called the domain of f • Set B is called the codomain of f • For E⊂A, f(E)={b∈B│b=f(e) for some e∈E} is the image of E under f • f(A) is called the range of f • If f(A)=B, then we say that f is onto or surjective • If f(a_1 )=f(a_2 ) implies a_1=a_2, then f is one-to-one or injective • A function that is both one-to-one and onto is said to be bijective • For E⊂B, f^(−1) (E)={a∈A│f(a)∈E} is the inverse image of E under f • Notationally, if y∈B, f^(−1) (y)=f^(−1) ({y}) ○ f^(−1) is at most a single element set for all y∈B if and only if f is injective ○ In this case, f^(−1) can be thought of as a function maps to the single element • Example ○ f:R→R defined by f(x)=x^2 ○ f^(−1) ({1})={1,−1} ○ f^(−1) ({x∈Rx0})=∅ ○ f^(−1) ({0})={0}, we can also write f^(−1) (0)=0 Cardinality • If there exists a one-to-one, onto mapping from set A to set B • We say that A and B can be put in one-to-one correspondence • And that A and B have the same cardinality (or cardinal number) • In this case, we write A~B Equivalence Relation • One-to-one correspondence is an example of an equivalence relation • An equivalence relation satisfies 3 properties ○ Reflexive: A~A ○ Symmetric: If A~B, then B~A ○ Transitivity: If A~B, B~C, then A~C Finite and Countable • Let J_n={1,2,3,…,n} and N={1,2,3,…} • For any set A, we say ○ A is finite if A~J_n for some n (∅~J_0 so ∅ is finite) ○ A is infinite if A≁J_n for all n ○ (To be continued)$

$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 ○ n 1 § Suppose f:X→Y is injective § Let x∈X, then 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 ○ Now, take X={1,…,n}=Y ○ Then every injection between finite sets of the same order is a bijection ○ Notice that the sets must be finite (Counterexample: f:Z→Z, n↦2n) Cycle • Definition ○ Fix n∈Z( 0). Let a_1,…,a_t∈{1,…,n} ○ The element of S_n given by § a_i↦a_(i+1) for 1≤i≤t−1 § a_t↦a_1 § j↦j if j∉{a_1,…a_t } ○ is denoted by (a_1,a_2,…,a_t ) and is called a cycle of length t • Example ○ Let σ=(1 3 2)∈S_4, then ○ (■8(i&1&2&3&4@↓&↓&↓&↓&↓@σ(i)&3&1&2&4)) ○ Notice: (1 3 2)=(3 2 1)=(2 1 3) Disjoint Cycles • Definition ○ Two cycles (a_1,…a_t ) and (b_1,…,b_k ) are disjoint if ○ {a_1,…a_t }∩{b_1,…,b_k }=∅ • Example ○ (1 2), (3 4)∈S_4 are disjoint • Fact ○ Every element of S_n can be written as a product of disjoint cycles ○ S_1={(1)} ○ S_2={(1),(1 2)} ○ S_3={(1), (1 2), (1 3), (2 3),(1 2 3), (1 3 2)} ○ S_4 = {(1), (1 2), (1 3), (1 4), (2 3), (2 4), (3 4), (1 2 3), (1 2 4), (1 3 2), (1 4 2), (1 3 4), (1 4 3), (2 3 4), (2 4 3), (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2)(3 4), (1 4)(2 3), (1 3)(2 4s)} ○ Note: We write the identity of S_n as (1) Cycle Decomposition for Permutations • Algorithm Method Example a≔min⁡{x∈Nx not appeared in previous cycles} (1 Begin the new cycle: (a b≔σ(a) σ(1)=12=b If b=a 12≠1 • close the cycle with a right parenthesis So write (1 12 • return to step 1 If b≠a • write b next to a in this cycle: (a b c≔σ(b) σ(12)=8 If c=a 8≠1 • close the cycle with a right parenthesis So continue the cycle as: • return to step 1 (1 12 8 If c≠a • write c next to in this cycle: (a b c b≔c and repeat this step until the cycle closes Naturally this process stops when all the numbers from {1,2, …,n} have appeared in some cycle. σ = (1 1 2 8 10 4)(2 1 3)(3)(5 1 1 7)(6 9) Remove all cycles of length 1 σ = (1 1 2 8 10 4)(2 1 3)(5 1 1 7)(6 9) • Example ○ Take σ∈S_13 to be the following ○ (■8(i&1&2&3&4&5&6&7&8&9&10&11&12&13@↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓&↓@σ(i)&12&13&3&1&11&9&5&10&6&4&7&8&3)) ○ Start with 1, σ(1)=12, so write 12 after 1. ○ Keep going until you cycle back to 1 ○ Start with the smallest number which hasn t yet appeared, and repeat. ○ Repeat this step until 1,…,13 have all appeared. Product of Cycles • Reminder: Read from right to left • Example ○ Write σ=(1 2 3)(1 2)(3 4) as a product of disjoint cycles ○ What is σ(1)? § (3 4) maps 1 to 1 § (1 2) maps 1 to 2 § (1 2 3) maps 2 to 3 § Thus σ(1)=3 ○ Similarly σ(3)=4, σ(4)=1 ○ Thus we close the cycle (1 3 4) ○ We won t write down (2), since it is the identity ○ Thus σ=(1 3 4)(2)=(1 3 4) ○ Note: σ∈S_4, but it make sense to think of σ∈S_n for n 4 • Commutativity of S_n ○ (1 2)(1 2 3)=(2 3) ○ (1 2 3)(1 2)=(3 1) ○ In particular S_3 is not abelian ○ Therefore S_n is not abelian for n≥3$

Shawn Zhong

Shawn Zhong

Math 521 - 2/12

Math 541 - 2/12

Search

WeChat Account