Haven't commented in this channel before. Just wanted to pass by and tell you that your efforts don't go unnoticed. I'm a software dev from Argentina that always wanted to live from mathematics but never could. Couldn't even go to uni. So i've had to study on my free time from the very basics of algebra and real analysis, to group theory and topology. Online material is many times unhelpful because it assumes you've gone through the formal training college gives you. And even though i'm able to prove, for example, Cauchy's theorem for Abelian groups on my own I still have gaps in my knowledge that this videos help me notice. So, long story short, your videos have been an amazing help! Thank you, from the bottom of my heart! I may never get a degree in mathematics, but these type of channel means I can get closer to it than I imagined.
My favorite part is "[40:57] when he casually says "...because 3 times 5 is 8 which is seven mod 8..." 😂 (Just kidding, Michael is great; I love these videos!)
The fact that _m_ and _n_ are coprime is not needed at 26:50, so even if _m_ and _n_ aren't coprime we still get a homomorphism from U_ _mn_ to U_ _m_ × U_ _n_ ; it just won't be injective or surjective. If you package well-definedness and injectivity together then you have " _a_ mod _mn_ = _b_ mod _mn_ ⇔ _mn_ | _a_ - _b_ ⇔ _m_ | _a_ - _b_ and _n_ | _a_ - _b_ ⇔ _a_ ≡ _b_ (mod _m_ ) and _a_ ≡ _b_ (mod _n_ ) ⇔ ( _a_ mod _m_ , _a_ mod _n_ ) = ( _b_ mod _m_ , _b_ mod _n_ )", where the left direction of the second equivalence holds because _a_ - _b_ being a multiple of _m_ and _n_ implies it is a multiple of lcm( _m_ , _n_ ) = _mn_ / gcd( _m_ , _n_ ) = _mn_ , and therefore we can use the coprimality condition neatly as "phi( _a_ mod _mn_ ) = phi( _b_ mod _mn_ ) ⇔ ( _a_ mod _m_ , _a_ mod _n_ ) = ( _b_ mod _m_ , _b_ mod _n_ ) ⇔ _a_ ≡ _b_ (mod _m_ ) and _a_ ≡ _b_ (mod _n_ ) ⇔ _m_ | _a_ - _b_ and _n_ | _a_ - _b_ ⇔ *_mn_** = lcm( **_m_** , **_n_** )* | _a_ - _b_ ⇔ _a_ mod _mn_ = _b_ mod _mn_ "
Good catch, that's a mistake (the inequality is true but not for the reason michael says). The correct argument is that ord(a) divides m and ord(b) divides n so lcm(ord(a), ord(b)) divides lcm(m, n), and therefore lcm(ord(a), ord(b)) ≤ lcm(m, n) since they are both positive integers. The "least" and "greatest" in "least common multiple" and "greatest common divisor" do not actually refer to ≤ and ≥; they refer to least and greatest with respect to _divisibility_ - to be more exact one could write "|-least common multiple" and "|-greatest common divisor". This is why lcm and gcd have nice properties with respect to divisibility but not with respect to ≤ and ≥ (e.g. you just showed that lcm is not increasing with respect to ≤). When restricted to positive integers the gcd and lcm are actually the ≤-greatest and ≤-least (just because if 0 < x | y then x ≤ y), but this is not the case for all integers: - For gcd(0, 0), every integer is a common divisor of 0 and 0, so the ≤-greatest common divisor does not exist/is "infinity", but the gcd -- the |-greatest common divisor -- is 0 - Similarly for lcm(1, 1), every integer is a common multiple of 1 and 1 so the ≤-least common multiple doesn't exist/is "negative infinity", but the lcm -- the |-least common multiple -- is 1. (1 is the least element of the divisibility order for *Z* while 0 is the greatest element)
@@tesafilm8447 I think we can prove equality with a couple extra steps, but it simply isn't needed for the proof - we can conclude that d=1 from the inequality mn ≤ mn/d, so there's no need for the equality mn = mn/d.
At 27:40 your presentation of the well-definedness argument makes the mistake of already using the definition just before having reached the conclusion that is well defined.
... is it a mistake though? He uses psi(a)=(a,a) and psi(b)=(b,b)... which is true in "formally" (it is true because we just Ctrl+F instances of x in psi(x)=(x,x) which is the definition of the map). What he proves was that a=b implies psi(a)=psi(b).... so even if you choose different "representatives" of the same value in U(n*m), you will get the same values in Un x Um
... I mean, if it doesn't satisfy you, let's consider a relation(not a function) psi between U_{n*m} and U_{n} x U_{m} relating "a" relates to "(a,a)"... I will denote with "a ~ (a,a)" A function is a relation which is total(for every element x ∈ U_{n*m} there is at least one element y ∈ U_{n} x U_{m} such that x ~ y....in function notation we would say ψ(x)=y) and well defined(for all elements x ∈ U_{n*m}, y₀, y₁ ∈ U_{n*m} x ~ y₀ and x ~ y₁ ⇒ y₀ = y₁... in function notation ψ(x)=y₀ and ψ(x)=y₁ ⇒y₀=y₁... but the notation would assume that ψ(x) is a single fixed value... which is kinda what you don't want) That statement for well defined is kinda hard to work with, so we use another for all elements x₀,x₁ ∈ U_{n*m}, y₀, y₁ ∈ U_{n*m} (x₀=x₁ and x₀ ~ y₀ and x₁ ~ y₁) ⇒ y₀ = y₁... in function notation psi(x)=y₀ and ψ(x)=y₁ ⇒ y₀=y₁) Here... we can do ψ(x₀)=y₀ and ψ(x₁) = y₁ as a "syntactic sugar" for x₀ ~ y₀ and x₁ ~ y₁(just like you sometimes people do f(x,y) instead of f((x,y))... that double parenthesis) then prove y₀=y₁ as long we don't make y₀=ψ(x₀)=ψ(x₁)=y₁. In particular, he made so a ~ (a,a) = (b,b) ~ b when a=b Also... showing the relation is total is like showing the inverse relation is surjective; while showing the relation is well defined is like showing the inverse relation is injective.
Haven't commented in this channel before. Just wanted to pass by and tell you that your efforts don't go unnoticed. I'm a software dev from Argentina that always wanted to live from mathematics but never could. Couldn't even go to uni. So i've had to study on my free time from the very basics of algebra and real analysis, to group theory and topology. Online material is many times unhelpful because it assumes you've gone through the formal training college gives you. And even though i'm able to prove, for example, Cauchy's theorem for Abelian groups on my own I still have gaps in my knowledge that this videos help me notice. So, long story short, your videos have been an amazing help! Thank you, from the bottom of my heart! I may never get a degree in mathematics, but these type of channel means I can get closer to it than I imagined.
If you think a mathematics degree would be useful for your future perhaps you should look into the Open University
My favorite part is "[40:57] when he casually says "...because 3 times 5 is 8 which is seven mod 8..." 😂
(Just kidding, Michael is great; I love these videos!)
good explanation 😃
The fact that _m_ and _n_ are coprime is not needed at 26:50, so even if _m_ and _n_ aren't coprime we still get a homomorphism from U_ _mn_ to U_ _m_ × U_ _n_ ; it just won't be injective or surjective. If you package well-definedness and injectivity together then you have
" _a_ mod _mn_ = _b_ mod _mn_ ⇔ _mn_ | _a_ - _b_ ⇔ _m_ | _a_ - _b_ and _n_ | _a_ - _b_ ⇔ _a_ ≡ _b_ (mod _m_ ) and _a_ ≡ _b_ (mod _n_ ) ⇔ ( _a_ mod _m_ , _a_ mod _n_ ) = ( _b_ mod _m_ , _b_ mod _n_ )",
where the left direction of the second equivalence holds because _a_ - _b_ being a multiple of _m_ and _n_ implies it is a multiple of lcm( _m_ , _n_ ) = _mn_ / gcd( _m_ , _n_ ) = _mn_ , and therefore we can use the coprimality condition neatly as
"phi( _a_ mod _mn_ ) = phi( _b_ mod _mn_ ) ⇔ ( _a_ mod _m_ , _a_ mod _n_ ) = ( _b_ mod _m_ , _b_ mod _n_ ) ⇔ _a_ ≡ _b_ (mod _m_ ) and _a_ ≡ _b_ (mod _n_ ) ⇔ _m_ | _a_ - _b_ and _n_ | _a_ - _b_ ⇔ *_mn_** = lcm( **_m_** , **_n_** )* | _a_ - _b_ ⇔ _a_ mod _mn_ = _b_ mod _mn_ "
Is the lcm inequality at 20:38 valid? For example, 34=lcm(2,4).
Good catch, that's a mistake (the inequality is true but not for the reason michael says). The correct argument is that ord(a) divides m and ord(b) divides n so lcm(ord(a), ord(b)) divides lcm(m, n), and therefore lcm(ord(a), ord(b)) ≤ lcm(m, n) since they are both positive integers.
The "least" and "greatest" in "least common multiple" and "greatest common divisor" do not actually refer to ≤ and ≥; they refer to least and greatest with respect to _divisibility_ - to be more exact one could write "|-least common multiple" and "|-greatest common divisor". This is why lcm and gcd have nice properties with respect to divisibility but not with respect to ≤ and ≥ (e.g. you just showed that lcm is not increasing with respect to ≤). When restricted to positive integers the gcd and lcm are actually the ≤-greatest and ≤-least (just because if 0 < x | y then x ≤ y), but this is not the case for all integers:
- For gcd(0, 0), every integer is a common divisor of 0 and 0, so the ≤-greatest common divisor does not exist/is "infinity", but the gcd -- the |-greatest common divisor -- is 0
- Similarly for lcm(1, 1), every integer is a common multiple of 1 and 1 so the ≤-least common multiple doesn't exist/is "negative infinity", but the lcm -- the |-least common multiple -- is 1. (1 is the least element of the divisibility order for *Z* while 0 is the greatest element)
@@schweinmachtbree1013 Why can't we write equality?
@@tesafilm8447 I think we can prove equality with a couple extra steps, but it simply isn't needed for the proof - we can conclude that d=1 from the inequality mn ≤ mn/d, so there's no need for the equality mn = mn/d.
In the last step in the proof that the homomorphism U_mn -> U_n × U_m is injective, one could simply argue with the Chinese Remainder Theorem.
How do you prove that talking non-stop for 40 minutes is exhausting? 40:57🤯
What do you mean? Of course 3 times 5 is 8, which is 7 mod 8. Sheesh, please try to keep up! 🤣🤣
At 27:40 your presentation of the well-definedness argument makes the mistake of already using the definition just before having reached the conclusion that is well defined.
... is it a mistake though?
He uses psi(a)=(a,a) and psi(b)=(b,b)... which is true in "formally" (it is true because we just Ctrl+F instances of x in psi(x)=(x,x) which is the definition of the map).
What he proves was that a=b implies psi(a)=psi(b).... so even if you choose different "representatives" of the same value in U(n*m), you will get the same values in Un x Um
... I mean, if it doesn't satisfy you, let's consider a relation(not a function) psi between U_{n*m} and U_{n} x U_{m} relating
"a" relates to "(a,a)"... I will denote with "a ~ (a,a)"
A function is a relation which is total(for every element x ∈ U_{n*m} there is at least one element y ∈ U_{n} x U_{m} such that x ~ y....in function notation we would say ψ(x)=y) and well defined(for all elements x ∈ U_{n*m}, y₀, y₁ ∈ U_{n*m} x ~ y₀ and x ~ y₁ ⇒ y₀ = y₁... in function notation ψ(x)=y₀ and ψ(x)=y₁ ⇒y₀=y₁... but the notation would assume that ψ(x) is a single fixed value... which is kinda what you don't want)
That statement for well defined is kinda hard to work with, so we use another
for all elements x₀,x₁ ∈ U_{n*m}, y₀, y₁ ∈ U_{n*m} (x₀=x₁ and x₀ ~ y₀ and x₁ ~ y₁) ⇒ y₀ = y₁... in function notation psi(x)=y₀ and ψ(x)=y₁ ⇒ y₀=y₁)
Here... we can do ψ(x₀)=y₀ and ψ(x₁) = y₁ as a "syntactic sugar" for x₀ ~ y₀ and x₁ ~ y₁(just like you sometimes people do f(x,y) instead of f((x,y))... that double parenthesis) then prove y₀=y₁ as long we don't make y₀=ψ(x₀)=ψ(x₁)=y₁.
In particular, he made so
a ~ (a,a) = (b,b) ~ b when a=b
Also... showing the relation is total is like showing the inverse relation is surjective; while showing the relation is well defined is like showing the inverse relation is injective.