Subject: Re: Help in understanding set theory problems |
Author: Lynn
| [ Next Thread |
Previous Thread |
Next Message |
Previous Message
]
Date Posted: 14:37:34 07/16/03 Wed
In reply to:
Pete Snyder
's message, "Help in understanding set theory problems" on 04:38:25 05/05/03 Mon
I assume that since you posted a couple of months ago, that if I'm answering assignment questions, it's too late. So, just so you can actually see how this is done, here we go:
(Incidentally, Shawm's is not too good at showing worked out solutions to problems that need proofs rather than numbers.)
>1. Let y and z be non-zero integers.
>Show mathematical proof that if (3y, 10z) = 9, then
>x|(y,z). I need a proof and not just a numerical
>answer.
Verbally: "If the greatest common divisor of 3y and 10z is nine, then find a factor of the greatest common divisor of y and z? (I'm paraphrasing a bit since as you typed it, it makes no sense.)
x = 3.
Proof (in words, sort of):
The fact that 9 is the greatest common divisor of 3y and 10z means two things: 1) that 9 divides both 3y and 10z.
and 2) that nothing bigger than 9 (no multiple of 9) also divides them.
So, let's see what we get out of consequence 1:
If 9|3y then it's clear that 3|y.
If 9|10z then 9 must divide z since 9 and 10 share no common factors.
Since 3|y and 3|9|z, we have that 3|(y,z).
In point of fact, using consequence 2 and the same sort of logic, it's possible to prove that 3 = (y,z)
Now, that's not how I would hand it in (although if marking it, I would sigh and give full marks).
What I would hand in:
Claim: 3|(y,z).
Proof:
9 | 3y (by hypothesis)
Thus, 3 | y (by dividing both sides by 9)
9 | 10z
(9,10) = 1
Thus, 9 | z (using the unique factorization theorem)
(This step may require more work, depending on how many consequences of the UFT you've seen in class.)
3 | 9
Thus 3 | z (transitivity)
Since 3|y and 3|z, then 3|(y,z).
QED
>
>2. Let G be the following group of permutations.
>G = {(3), (1234), (13)(24), (1432), (24), (12)(34),
>(13), (14)(23)}.
>Let H = {(1), (1234), (13)(24), (1432)}.
>Prove H is cyclic and find all the cosets of H in G.
(First, I assume that the first permutation in G is (1). Otherwise, it's not a group and nothing makes sense.)
The first part is fairly simple. To prove that a group is cyclic, all you need is to find a generator and then prove that that generator works. Since H has only 4 elements, trial and error should be quite quick.
So my solution would go as follows:
Claim: g:=(1234) is a generator of H.
Proof: Let this group act on the "word" abcd.
g(abcd) = dabc
g^2(abcd) = g(dabc) = cdab = [(13)(24)](abcd)
(ie, g^2 = (13)(24) )
g^3(abcd) = g(cdab) = bcda = [(1432)](abcd)
(ie, g^3 = (1432) )
g^4(abcd) = g(bcda) = abcd = [(1)](abcd)
(ie, g^4 = (1))
QED
The second part is also comparatively straight forward. A subgroup always divides the big group into equal parts when you take cosets. Furthermore, these equal parts are the same size as the subgroup. So, since H has 4 elements, it divides the 8-element group G into 2 parts:
{(1),(1234),(13)(24),(1432)} = H and
{(24), (12)(34),(13), (14)(23)} (the rest).
If I were grading this, I would accept what I've written here as a decent proof although I might like references to theorems for each of the sentences which I just stated.
Hope that helps.
Lynn
[
Next Thread |
Previous Thread |
Next Message |
Previous Message
] |
|