|
On May 01 2019 06:10 Acrofales wrote:Show nested quote +On May 01 2019 05:20 travis wrote:alright, im a bit behind in my abstract algebra class and now im lost as heck so here comes a wave of questions. please help me understand how to do this stuff first question says: let n >= 5. It can be shown that the only normal subgroups of S_n are {(1)}, A_n, and S_n a.) for each normal subgroup N of S_n above, describe what the quotient group S_n / N is isomorphic to.
So first, the extent of my understanding: A normal subgroup H of S_n is a subgroup of S_n in which gH = Hg (left cosets and right cosets are the same) for g in S_n A quotient group is a normal subgroup... but that's about as far as I understand it I see a rule (aN)(bN) = (abN) Is it the case here that a,b are cosets of G, and then the quotient group is abN which arises from the product of the group operation between a and b? So then back to the question of {(1)}, A_n, and S_n in S_n I don't really know how to solve what these quotient groups are isomorphic to What kind of steps do I take? I do have guesses though, I think for (1) the answer is S_n, for A_n the answer is Z_2, and for S_n the answer is the identity Not quite sure on the algebra, but any question of "prove that for all n > something..." invites a proof through induction, so prove it for n=5 and then assume for n and prove for n+1.
I don't think you need that here.
With regards to the original question:
Quotient groups are groups where you simply chuck all elements of a larger group which are equal (in some way) together as if they are one.
As an example, if you take a look at the quotient group Z/3Z. This is the same group as Z, if you consider all elements which are equal modulo 3 as equal. As such, the only things in there are the equivalence classes of 0; 1 and 2. All other elements of Z are equivalent to one of these. Or formulated in another way: Which different types of elements are there in Z with regards to the result of z + 3Z.
Luckily, the statement about the normal subgroups of S_n does not need to be proven here, but can instead be taken as a given.
And there is a very simple solution involving the amount of things in each of these groups, as there is a theorem which states that |G| = |N|*|G/N|
So the answer which was given by travis is indeed correct.
|
So then is the way this type of question would typically be solved (assuming you are a confused student and not a math god) to simply fill in the |G| = |N|*|G/N| and then base a conclusion on it?
Next two questions continued from that one:
suppose α: S_n --> H is a group homomorphism (i believe we are still dealing with n>=5). Describe the possibilities for what the image of α(S_n) could be isomorphic to.
Should this answer be formed from the theorem you just told me of |G| = |N|*|G/N| ?
Show that a homomorphism α : S_n ---> Z_5 must be the trivial one: α(j) = 0 for all j in S_n
I am very confused here Is it saying that this homomorphism exists for all n >= 5?
|
On May 01 2019 06:53 travis wrote: So then is the way this type of question would typically be solved (assuming you are a confused student and not a math god) to simply fill in the |G| = |N|*|G/N| and then base a conclusion on it?
It is one tool, but often not enough for a proof, though. If the answer is that |G/N| = 1;2 (maybe 3? unsure) or |G|, then your answer is clear. But if it is something like 4, then this alone doesn't prove what the group is isomorphic to.
Generally speaking, you should try to understand what exactly equivalence classes are. And then figure out which different ones of those you have. This can be as simple as calculating g*N for each member g of G, and looking at how many different results you have. If we go back to the Z/3Z example, we notice that 0 + 3Z is the same as 3 + 3Z or 6 + 3Z (+ instead of * because that is the operation of the Z group). The only fundamentally different results are 0 + 3Z, 1 + 3Z and 2 + 3Z. These are your equivalency classes, and that means that Z/3Z is isomorphic to the group {0;1;2} with the group operation (g+h (mod 3)), the group you call Z_3.
Here, the above calculation would not have helped either, because neither Z nor 3Z are finite.
Next two questions continued from that one: Show nested quote + suppose α: S_n --> H is a group homomorphism (i believe we are still dealing with n>=5). Describe the possibilities for what the image of α(S_n) could be isomorphic to.
Should this answer be formed from the theorem you just told me of |G| = |N|*|G/N| ? Show nested quote + Show that a homomorphism α : S_n ---> Z_5 must be the trivial one: α(j) = 0 for all j in S_n
I am very confused here
old useless thoughts: + Show Spoiler +Is H a normal subgroup? Or just any group? Anyways, because you are not talking about quotient groups, i don't think you need that equation. My first guess would be to take a look at the definition of homomorphism and try to see where that leads you. The whole A_n and sgn ideas might also help. (I am not leading you along here, i also don't immediately know the answer right now). {1} and S_n are definitively possible results, though, because they always are. And Z_2 due to the sgn homomorphism.
Nvm, thought about it a bit, and there was a theorem for this, the first isomorphism theorem links images of homomorphisms and quotient groups. This is clearly what you need to use here.
Second question is probably quickly answered using the result of the previous one. If you see that Z_5 and none of its subgroups except for the trivial one (of which there are none) can be isomorphic to the image of a homomorphism α: S_n ---> H, then the only possible homomorphism from S_n to Z_5 is the trivial one.
Edit: Your addition: The trivial homomorphism always exists between any two groups. It simply throws anything in group one onto unity in group two. What you need to show is not that this exists, but that no other exists. And that is true for all N >=5.
Unrelated edit 2: I will have to freshen up on my knowledge of algebra for a major exam in about half a year. I was thinking about doing this by explaining this stuff in a thread here on TL, possibly giving some worksheets to interested people, as i find that i learn very well by teaching stuff. Would people be interested in this? And what would be the best way to do this, probably a dedicated thread?
|
if its abstract algebra and it's before my final (about 2 weeks from now), i'd definitely be interested wil read the rest of the post later, am gonna go eat my chipotle
|
Okay, I read the first isomorphism theorem and it's the most confusing thing I have ever read.
I guess I need to remember what the kernel of a homomorphism is. The kernel describes the elements of G (in this case, S_n), which are mapped to the identity in H. That's confusing. Is that mapping ever not just a mapping between the identity in G and the identity in H?
So once I know the kernel, we can say the kernel is normal in G (S_n). ... not sure what that means. The kernel itself is a normal subgroup?
The theorem then says if we let q be a mapping from G--->G/K (where K is the kernel of G), then q is the canonical homomorphism. I have no idea what that means though.
It then says that there then exists a unique ismorphism G/K----> α(G) where α describes the original homomorphism?
I am a bit disheartened at my inability to understand this, lol
|
On May 01 2019 09:05 travis wrote: Okay, I read the first isomorphism theorem and it's the most confusing thing I have ever read.
I guess I need to remember what the kernel of a homomorphism is. The kernel describes the elements of G (in this case, S_n), which are mapped to the identity in H. That's confusing. Is that mapping ever not just a mapping between the identity in G and the identity in H?
Maybe it is a language problem, so just to avoid any confusion: The kernel of an homomorphism f: G -> H is the preimage of the identity element 1_H with respect to f. So it always contains 1_G, but it may also contain other elements.
So once I know the kernel, we can say the kernel is normal in G (S_n). ... not sure what that means. The kernel itself is a normal subgroup?
Yes. This is a really a key statement in algebra.
The theorem then says if we let q be a mapping from G--->G/K (where K is the kernel of G), then q is the canonical homomorphism. I have no idea what that means though.
You should check this again because right now, you are missing some assumptions of the theorem, or at least you have not stated them here explicitly. You can only speak of a kernel if there is a homomorphism to which this kernel belongs.
Also the way you say this isnt precise. There is the canonical homomorphism q: G -> G/K, by mapping g to its equivalence class. However, there could also be other homomorphisms G -> G/K (for example, the trivial homomorphism which maps everything to the identity element). So no, it is not true to say that "q is a mapping G -> G/K, then q is the canonical homomorphism".
It then says that there then exists a unique ismorphism G/K----> α(G) where α describes the original homomorphism?
I am a bit disheartened at my inability to understand this, lol
So basically you want K to be the kernel of α (?). And iirc no, while there is an isomorphism d: G/K -> α(G), the uniqueness is only guaranteed if you require that d q = α
|
There are different ways to formulate the first isomorphism theorem, i am going to use the one used on wikipedia here;
https://en.wikipedia.org/wiki/Isomorphism_theorems#First_isomorphism_theorem
Namely, in this case the interesting fact is that if α is a homomorphism from G to H (Or in this case S_n to H), this means that the image of α is isomorphic to the quotient group S_n/ker(α).
Furthermore, ker(α) is a normal subgroup.
With the answers to the first question, we know that there are not a lot of normal subgroups in S_n, and that there are thus not a lot of those quotient groups. Namely, the only possible quotient groups are {1}, S_n and Z/2Z. These are also the only possible images of alpha due to what the theorem says. (Obviously depending on alpha itself, and on the group it goes to)
If you want to go into more detail, depending on H, {1} is always possible, Z/2Z only possible if H has an element of order 2 (And thus a subgroup isomorphic to Z/2Z), and S_n is only possible if H has a subgroup isomorphic to S_n.
|
It looks as though you are being walked through a proof without being told you are proving something. I don't like that way of teaching maths. I prefer motivating things first.
Sometimes we want to move from one group G into another group G', so we want a map α:G-->G'. For this to be useful as groups we want the map α to preserve group structure; ie we want α(gh)=α(g)α(h) for all g,h in G. We call such maps homomorphisms.
The question is: What can we say about α(G) in terms of G?
Firstly, some elements of G may get mapped to the identity 1' in G'. We call the set of such elements the kernel of α. We denote it ker(α) and this is a subgroup of G. This follows directly from the definition of subgroup, together with the homomorphism property. Lets use K to denote the kernel for short.
Now we know that α(k)=1' in G' for all k in the kernel (by definition of kernel) so for any g in G, α(gK)=α(g) so to understand α(G) we only need to look at cosets of K.
So lets have a brief aside about cosets: Let U be a subgroup of G (I'm only using U because it is a new letter). We let G/U denote the set of left cosets of U in G, ie things of the form gU. There are two questions we could ask: 1) How many cosets are there? 2) When is G/U a group?
(1) The crucial fact about cosets is that they are either disjoint or the same, ie either gU=hU or they have no intersection at all. This is because if there is some intersection then gu=hv for some u,v in U and then gU = hvu^-1U = hU since vu^-1 is in U
Since different cosets cannot overlap we know |G| = Number of cosets x Size of a coset = |G/U| x |U|
(2) The most obvious way to make G/U a group is to say (gU)(hU)=(gh)U but this does not always give us a group. We would need (gU)(g^-1U)=U for inverses to work. So if U satisfies gUg^-1=U for all g in G then we call U a normal subgroup of G. It is equivalent to say left cosets are right cosets because gUg^-1=U if and only if gU=Ug and this condition is enough to make G/U a group, which we would then call the quotient group. This quotient group is not the same as U.
Now we can write down a homomorphism G-->G/U by sending g to its coset gU. We have to check that it is a homomorphism, ie that gUhU=(gh)U but this follows from U being a normal subgroup. This is what people meant by the canonical homomorphism.
Anyhoo, let's get back to our map α:G-->G' and its kernel K. We can quickly check that for all g in G we have gKg^-1 = K α(gkg^-1) = α(g)α(k)α(g^1) = α(g)α(g)^-1 = 1' in G'
so K is a normal subgroup of G and the set G/K of cosets is a group. We can actually write down a homomorphism A:G/K-->α(G) by saying gK goes to α(g). We need to check that this is well defined, by which I mean that if gK=hK then α(g)=α(h) and this follows from definitions; If gK = hK then gKh^-1 = K and so 1' = α(K) = α(gKh^-1) = α(g)α(K)α(h^-1) = α(g)α(h)^-1.
Finally, we can prove A is an isomorphism. It is injective because if A(gK) is the identity then α(g)=1' so g is in K and gK=K. It is surjective onto α(G) because if g' is in α(G) then there is some g in G such that α(g)=g' and then A(gK)=α(g)=g'.
This proves that isomorphism theorem; G / kernel(α) is isomorphic to α(G).
In summary, there are two important things to remember (besides definitions) (a) For any normal subgroup N of G |G| = |N| x |G/N| (b) For any homomorphism α:G-->G' kernel(α) is a normal subgroup of G and G/kernel(α) is isomorphic to α(G).
Onto the specifics about S_n We are told that it has only three normal subgroups {1}, S_n, and A_n. You say the quotients are S_n, {1}, and Z_2 respectively (which is correct and can be proven using fact (a) assuming you know the size or index of A_n in S_n).
So lets assume we have a homomorphism α: S_n ---> Z_5. There always is a homomorphism because I can send everything to the identity. Are there any other homomorphisms though? You know what the quotient groups of S_n are and using fact (b) you should be able to say what the image of α could be.
I hope this helps If not, please ask for more clarification/explanation.
|
just took a practice exam, there were a few questions I missed or just wanted some clarification on:
first was T/F question
T/F: every infinite cyclic group is isomorphic to Z
This question actually comes up again in a different way. I guessed True and got it, but I don't understand why. Why is Z cyclic, could someone explain? Is it because 1 is considered a generator of the infinite group Z?
Give an example of an abelian group with 12 elements that is not cyclic
The solution sheet said z2 x z4 I said A4
is A4 also a solution?
Give a reason why Z is not isomorphic Q
I didn't really know how to answer this. Their answer was that Z is cyclic and Q is not. See the question above I guess.
We have a function f: ZxZ ---> Q*, s.t. f(a,b) = 2^a3^b
What is the kernel of f?
The answer here is that the kernel is (0,0) I am still having trouble with the kernel of a homomorphism.
Is it because identity in Q is 1, and we get 1 by doing a=0,b=0?
Thanks for any help
|
On May 03 2019 08:26 travis wrote:Show nested quote + We have a function f: ZxZ ---> Q*, s.t. f(a,b) = 2^a3^b
What is the kernel of f?
The answer here is that the kernel is (0,0) I am still having trouble with the kernel of a homomorphism. Is it because identity in Q is 1, and we get 1 by doing a=0,b=0?
In an attempt to clear up your confusion with the kernel, the kernel of a homomorphism (α:G -> H) always contains the identity element of G (which can be derived from the definition of a homomorphism: α(ab) = α(a)α(b)). However, the kernel only contains a single element (the identity of G) when α is a monomorphism (a homomorphism that is injective.) Otherwise, the kernel will have multiple elements.
As for your question, that is correct. The proof is because 2 and 3 are coprime, so the product of a given number of 2's and 3's exists and is unique. Thus, α is injective and the only element of the kernel is the identity element of ZxZ, (0,0).
If we instead consider a function g: ZxZ --> Q*, where g(a,b) = 2^a4^b, then the kernel of f has infinite elements: all (a,b) that satisfy the equation a = -2b are in the kernel of g. We may readily observe this by substituting a = -2b into g(a,b) = 2^(-2b)4^b = 4^(-b)4^b = 1. We see that g is not injective so the kernel has multiple elements (the set of a and b given above.)
Sadly, I don't know enough about groups to help with your other questions.
|
On May 03 2019 08:26 travis wrote:just took a practice exam, there were a few questions I missed or just wanted some clarification on: first was T/F question This question actually comes up again in a different way. I guessed True and got it, but I don't understand why. Why is Z cyclic, could someone explain? Is it because 1 is considered a generator of the infinite group Z?
Cyclic groups have just one generator (an element that, along with it's inverse, can create every element of the group). You've found it for the infinite group Z.
But this true false question is asking a little bit more. Suppose I had another group Z' and all I told you about it was that it was infinite, and it was cyclic. The question wants us to show that my secret group Z' is actually isomorphic to Z. Isomorphic can be shown in a few ways, though they're basically equivalent to showing that there exists a pair of homomorphisms: f: Z->Z' g: Z'->Z
Where each is injective. Now, tbh I didn't have a great understanding of what a homomorphism was when I took algebra. It's a really general term for "function that preserves structure." If you like Computer Science, it may help to think of it as a compiler. A homorphism from A to B let's you simulate all of A in the "language" of B, and it's injective if that simulation never uses the same symbol for 2 different things. A and B are isomorphic if they can simulate each other without ambiguity, so that they're equivalent in power.
Anyway, in this case the homomorphisms are short and sweet, pick a generator g for Z' (we know one exists because cyclic), and map it to 1 in Z. If some element is n*g (ie, g+g+... repeated n times) then map that to n*1 in Z. Likewise for the other direction, map n=n*1 to n*g in Z'.
To show each of these is injective, note that these are both infinite cyclic groups, so that if n*g = m*g then n=m (otherwise, my secret group Z' would loop around after n-m additions, but that means it's actually finite).
Give an example of an abelian group with 12 elements that is not cyclic
The solution sheet said z2 x z4 I said A4
is A4 also a solution?
Forgive my bad memory, but is A4 abelian? I can't remember if A4 or A5 was the first bad one. A4 does have size 12, so you're good there.
Give a reason why Z is not isomorphic Q
I didn't really know how to answer this. Their answer was that Z is cyclic and Q is not. See the question above I guess.
So going back to our simulation analogy, how do we simulate Z using Q (Q with addition as the operation I'm guessing?) ? Well we can just use the inclusion, send n in Z to n in Q and everything works perfectly.
What about simulating Q with Z? Everything goes wrong pretty fast. If we pick some a/b in Q to send to 1 then we can't fit a/(2b), by which I mean that if our homomorphism is f then 1 = f(a/b) = f(a/(2b) + a/(2b)) = 2 f(a/(2b)) So f(a/2b) needs to equal 1/2... but 1/2 isn't in Z.
There are other problems. For example, Q needs infinitely many generators (as integer multiples of any fraction (not 0) will never include half itself, this is basically the problem above), while Z has only 1. This is the observation made in the answer key.
We have a function f: ZxZ ---> Q*, s.t. f(a,b) = 2^a3^b
What is the kernel of f?
The answer here is that the kernel is (0,0) I am still having trouble with the kernel of a homomorphism.
Is it because identity in Q is 1, and we get 1 by doing a=0,b=0?
Thanks for any help
Yet again mentioning the simulation analogy. if it helps you can think of the kernel as the details a simulation ignores. In this problem, we want to keep track of pairs of integers (Z x Z) with their additive structure (so, for example, (1,1) + (3,-2) =(4, -1) ). The problem proposes one way to do this inside of Q*, via (a,b) mapsto f(a,b)=2^a * 3^b.
To explicitly find the kernel, we just solve f(a,b) = 1 (the identity in the simulating group). Why does this work? Well if some (c,d) is in the kernel (gets mapped to 1) then f( (a,b) + (c,d) ) = f(a,b)*1 = f(a,b). So f always ignores copies of (c,d).
If there isn't anything besides the identity in the kernel then f is injective. As f(x,y) = f(a,b) -> f(x,y)f(a,b)^-1 = 1 -> f((x,y)-(a,b))=1 So that (x,y)-(a,b) is in the kernel, but that means (x,y)=(a,b).
|
Just to make sure that you understand what a kernel is:
The kernel of alpha(G--->H) is simply everything that ends up on unity in H.
For example, if i have the homomorphism Z ----> Z/3Z with f(z) = z (mod 3)
You can easily check that this is a homomorphism by using the homomorphism definition if you want to. The kernel of this homomophism is {...-6;-3;0;3;6;9;...}, because these are all of the elements in Z that end up on 0 in Z/Z3
|
Hey!
So I've decided I need to refresh my math knowledge. And I want to as well I'm a programmer, been working in web development (PHP, C#), but I'm making a switch to A.I./machine learning. Studying that + python, and working on Project Euler exercises for now. I studied some math in University (Masters degree in IT), but I have never had much application for it at work. And I've never considered myself good at math. So I feel really rusty.
Could anyone recommend some good books/resources? I really don't have more specific requirements for now. I just want another challenge for myself. I could use google, but I wonder if people from here have recommendations I'd really appreciate the help.
|
On May 04 2019 00:10 awerti wrote:Hey! So I've decided I need to refresh my math knowledge. And I want to as well I'm a programmer, been working in web development (PHP, C#), but I'm making a switch to A.I./machine learning. Studying that + python, and working on Project Euler exercises for now. I studied some math in University (Masters degree in IT), but I have never had much application for it at work. And I've never considered myself good at math. So I feel really rusty. Could anyone recommend some good books/resources? I really don't have more specific requirements for now. I just want another challenge for myself. I could use google, but I wonder if people from here have recommendations I'd really appreciate the help.
You're probably gonna want a good bit of stats and optimization for ML. The basics behind this are, at the end of the day, analysis (particularly calculus) and linear algebra. The Calculus texts by Michael Spivak or Tom Apostol are good here if you are okay to dive into a serious undergrad maths book. Apostol also seems to cover some of the algebra.
|
On May 03 2019 08:26 travis wrote:The solution sheet said z2 x z4 I said A4 is A4 also a solution? Since this part didn't get a good answer: A4 is not abelian. To show that I only need to find two elements a,b in A4 such that ab =/= ba
+ Show Spoiler [Hint] +Consider 3-cycles, ie the elements in A4 of the form ( i j k ) for i,j,k in { 1, ..., 4 }.
|
how do i calculate phi(242), that is to say the order of U(242), or some other U(x) ? thanks
|
You need to use the rules for calculating the euler phi function.
Namely
phi (m*n) = phi (m) * phi(n) (if m and n don't share any factors) phi (p^k) = p^k-p^(k-1) (for p prime)
so, you need to dissolve 242 into prime factors, and use the rules above.
|
OH RIGHT
god that makes sense
so 11^2 - 11^1
thank you so much
|
alright practicing for my final, going over old midterms
here is a question I had trouble with:
find the last 2 digits of 503^163
My method that I gave up on because it was taking too long to be feasible for a midterm:
[spoiler] 1.)Notice that the last two digits here are 03 and the 5 should never matter in regards to the last two digits 2.)use the repeated square method to find 3^2, 3^4, 3^etc all the way to 3^128 3.)take products of the squares such that they sum to 163 and look at last two digits [spoiler]
Actual intended method
+ Show Spoiler + 1.) notice that 503 is congruent to 3 mod 100 (i guess pretty much what I said for my step 1) 2.) compute phi(100) = phi(2^2)*phi(5^2) = (4-2)(25-5) = 40 3.) notice 163 is congruent to 3 (mod 40) ..... //they sure expect us to notice lots of stuff 4.) 503^163 congruent to 3^163 congruent to 3^3 congruent to 27 (mod 100)
How would you solve it if given this question also, if we are using the expected method, could anyone give me some intuition on why the second method works? What theorem is this tied to? Is this Euler's?
|
Here is another question. I don't mean to spam, I just think it's better in a separate post.
We have a 3d cube, each point(vertex) is labeled 1...8 G is the group of rotational symmetries of this cube
Is G cyclic? Give a brief justification
I say:
No, it is not. Any of these permutations are their own inverse in the group and thus the group is not cyclic.
Is my answer accurate? Would i get full credit for that?
|
|
|
|