Tag Archives: homomorphism

Elementary Math from an Advanced Standpoint

Education, Elementary Math, Modern Math, Uncategorized Leave a comment

Guesstimate Question  (no calculator allowed) –

[Hint]: use Abstract Math “Homomorphism”  {f * +}

What is 35823 x 23412 ?

A) 845203402
B) 838688076
C) 812343296

The mapping f defined by
\forall a_1, a_2, a_3 \in Z
f(a_1a_2a_3) = a_1+ a_2+ a_3
such that,

\forall a, b \in Z,
f (a * b) = f(a) * f(b)

=> f is an homomorphism.

Examples:

f (35823) = 3+5+8+2+3 = 21
f (21)= 2+1= 3

f (23412) = 2+3+4+1+2 =12
f (12) =1+2 = 3

f (35823 x 23412) = 3 x 3 = 9

Verification  (B):
f (838688076)= 8+3+8+6+8+8+0+7+6=54 ..5+4 =9 ☆

Wrong :
f(845203402)= 28…=10 = 1

f (812343296) = 38… =11 =2

Morphism Summary Chart

Modern Math 1 Comment

The more common morphisms are:

1. Homomorphism (Similarity between 2 different structures) 同态
Analogy: Similar triangles of 2 different triangles.

2. Isomorphism (Sameness between 2 different structures) 同构
Analogy: Congruence of 2 different triangles

Example: 2 objects are identical up to an isomorphism.

3. Endomorphism (Similar structure of self) = {Self + Homomorphism} 自同态
Analogy: A triangle and its image in a magnifying glass.

4. Automorphism (Sameness structure of self) = {Self + Isomorphism} 自同构
Analogy: A triangle and its image in a mirror; or
A triangle and its rotated (clock-wise or anti-clock-wise), or reflected (flip-over) self.

image

5. Monomorphism 单同态 = Injective + Homomorphism
image

6. Epimorphism 满同态 = Surjective + Homomorphism

Proofs of Isomorphism

Modern Math Leave a comment

Two ways to prove f is Isomorphism:

1) By definition:
f is Homomorphism + f bijective (= surjective + injective)

2) f is homomorphism + f has inverse map f^{-1}

Note: The kernel of a map (homomorphism) is the Ideal of a ring.

Two ways to construct an Ideal:
1) use Kernel of the map
2) by the generators of the map.

Two ways to prove Injective:

1) By definition of Injective Map:
f(x) = f(y)
prove x= y

2) By Kernel of homomorphism:
If f is homomorphism
f: A \mapsto B
Prove Ker f = {0}

Note: Lemma:
\text{f is injective} \iff Ker f = {0}

Proof Isomorphism 4 Steps:
1. Define function f：S -> T
Dom(f) = S
2. Show f is 1 to 1(injective)
3. Show f is onto (surjective)
4. Show f(a*b) = f(a). f(b)

Example:
Let T = even Z
Prove (Z,+) and (T,+) isomorphic
Proof:
1. Define f: Z -> T by
f(a) = 2a
2. f(a)=f(b)
2a=2b
a=b
=> f injective

3. Suppose b is any even Z
then a= b/2 ∈ Z and
f(a)=f(b/2)=2(b/2)=b
=> f onto

4. f(a+b) =2(a+b) =2a+2b =f(a)+f(b)
Hence (Z,+) ≌ (T,+)

Isomorphism (≌)
1. To prove G not isomorphic to H:
=> Prove |G| ≠ |H|

2. Isomorphism class = Equivalence Class
B’cos “≌” is an Equivalence relation.

3. Properties of Isomorphism (≌):
i) match e
\phi(e) = e'
ii) match inverse
\phi (g^{-1} )= (\phi (g))^{-1}

iii) match power
\phi(g^{k})= (\phi(g))^{k}

Ring Homomorphism

Elementary Math, Modern Math Leave a comment

Ring Homomorphism
Math Olympiad uses Elementary Math up to upper-secondary school level, for Number Theory questions students are forced to memorize complex tricks without knowing the essence of Math.

As the great 19th century German Math educator Felix Klein said we should look at Elementary Math in secondary schools from the angle of higher Math, below is an example applying Abstract Algebra of “Ring Homomorphism”:

Let integer N= a1a2…aj

Prove: N is divisible by 9 if
9 | (a1+ a2+ a3+…+ aj)

Proof
Let Φ: Z -> Z/9Z = {0,1,2,3…8}
Φ(z) = z mod 9

Φ is a Ring homomorphism from Ring Z to its Subring Z/9Z.

Note: Homomorphism in Math Structure (Group, Ring, etc) is like “Similarity” of triangles in Geometry.

WLOG (Without Loss of Generality)
Let j=4
N = a1a2a3a4
= a1.10³ + a2.10² + a3.10+ a4

Since in Z/9Z
Φ(aj) = aj for all j
Φ (10) = 1
Φ (10ⁿ) = Φ(10)ⁿ= 1ⁿ = 1

Φ(N)
= Φ(a1.10³ + a2.10² + a3.10+ a4)
= Φ(a1.10³ ) + Φ(a2.10² )
+ Φ(a3.10 ) + Φ(a4 )
= Φ(a1).Φ(10³ ) + Φ(a2).Φ(10² ) +
Φ(a3).Φ(10 ) + Φ(a4 )
= (a1).1 +(a2).1+ (a3).1 + (a4)
= a1+ a2+ a3+ a4

Hence,
Φ(a1a2a3a4) = a1+ a2+ a3+ a4
=> a1a2a3a4 is divisible by 9 if
9 | ( a1+ a2+ a3+ a4)

[QED]

Relationship-Mapping-Inverse (RMI)

Elementary Math, Modern Math 2 Comments

Relationship-Mapping-Inverse (RMI)
(invented by Prof Xu Lizhi 徐利治 中国数学家 http://baike.baidu.com/view/6383.htm)

Find Z = a*b

By RMI Technique:
Let f Homomorphism: f(a*b) = f(a)+f(b)

Let f = log
log: R+ –> R
=> log (a*b) = log a + log b

1. Calculate log a (=X), log b (=Y)
2. X+Y = log (a*b)
3. Find Inverse log (a*b)
4. ANSWER: Z = a*b

Prove:

\sqrt{2}^{\sqrt{2}^{\sqrt{2}}}= 2

1. Take f = log for Mapping:
\log\sqrt{2}^{\sqrt{2}^{\sqrt{2}}}
= \sqrt{2}\log\sqrt{2}^{\sqrt{2}}
= \sqrt{2}\sqrt{2}\log\sqrt{2}
= 2\log\sqrt{2}
= \log (\sqrt{2})^2
= \log 2

2. Inverse of log (bijective):
\log \sqrt{2}^{\sqrt{2}^{\sqrt{2}}}= \log 2
\sqrt{2}^{\sqrt{2}^{\sqrt{2}}}= 2