# Wikipedia:Reference desk/Archives/Mathematics/2011 January 10

Mathematics desk
< January 9 << Dec | January | Feb >> January 11 >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

# January 10

## Godel sentences and the arithmetic hierarchy

Where was Godel's original Godel sentence on the arithmetic hierarchy? In general, what is the lowest level of the arithmetic hierarchy where a Godel sentence for Peano arithmetic can be constructed? 76.67.79.61 (talk) 01:28, 10 January 2011 (UTC)

The Goedel sentence for any c.e. theory in first-order logic is $\Pi^0_1$. At least I'm pretty sure it is. It essentially says "for every n, n is not the Goedel number of a proof of me". Of course you can't literally say "me"; you have to use the recursion theorem, and I'd have a bit of work to do to be sure that doesn't increase the complexity, but I don't think it does. --Trovatore (talk) 01:34, 10 January 2011 (UTC)
Isn't the idea of "is a proof of" nontrivial enough to raise its position? 74.14.110.15 (talk) 07:12, 10 January 2011 (UTC)
No. To say that n is the Goedel number of a proof of proposition σ is primitive recursive. --Trovatore (talk) 07:14, 10 January 2011 (UTC)
Oh yeah. Thanks for your help. 74.14.110.15 (talk) 08:40, 10 January 2011 (UTC)
And to answer the second part of the question, $\Pi^0_1$ is the best possible for a true unprovable sentence, since all true $\Sigma^0_1$-sentences are provable already in Robinson's Q.—Emil J. 13:45, 10 January 2011 (UTC)

## Groups

Let a,b be linearly independent in Z^2. Is there an automorphism on Z^2 so that a,b gets turned into the form (x,0),(y,0)? i.e. their first and second coordinates vanish resp. Is it possible to do this for one element as well? Money is tight (talk) 14:13, 10 January 2011 (UTC)

No -- consider a=(1,1), b=(-1,1). Since neither a nor b is a proper multiple of any element, x and y must both be units. But then there is no possible image of (0,1), which must be halfway between the images of a and b. –Henning Makholm (talk) 14:41, 10 January 2011 (UTC)
Damn. I noticed I made a mistake: (x,0),(y,0) should be (x,0),(0,y) but nevertheless your example still works (I have to say it's pretty clever). My real problem was this: let A be a group have order the power of a prime and be generated by 2 torsion elements, is there only two factors in A's primary decomposition into cyclic groups (the structure theorem for finitely generated abelian groups)? Also, if A is generated by a torsion free element and a torsion element is A of the form Z x Z/nZ for some n? Thanks. Money is tight (talk) 15:06, 10 January 2011 (UTC)
I assume you're talking only about Abelian groups. For the second question, it should be easy to prove that the subgroups generated by your two elements form a direct sum. For the first, write your group as a product of cyclic groups of order a power of the prime number p, and assume there are at least three factors. Then there is some quotient of it that is isomorphic to (Z/pZ)3. This quotient must be generated by the projections of your two generators. But now this is a vector space question! 82.120.58.206 (talk) 16:41, 10 January 2011 (UTC)
As I mentioned before, you ought to use the direct sum ⊕ for abelian groups instead of the more general direct product ×. Using ⊕ emphasises the additive structure of an abelian group. So you want Z ⊕ Z/nZ instead of Z × Z/nZ 19:17, 10 January 2011 (UTC)
No, that's not the purpose of the direct sum. The direct sum symbol here represents a coproduct in the corresponding category, whereas the product represents a product.
For instance, the category of abelian groups is an abelian category, so that finite products are finite coproducts are the same thing: $A \times B = A \oplus B$ (and yes I do mean equal, and not just isomorphic). There is no difference. For infinitely many factors, however, there is a difference: the direct sum corresponds to elements being the identity in all but finitely many factors, whereas the direct product consists of all sequences.
Finally, the two notations differ when talking in other categories. The product of groups is the product of abelian groups (this is clear, but it otherwise follows from the forgetful functor preserving limits by adjointness properties), but the coproduct is not (it is instead the free product). Usually people tend to avoid $\oplus$ for the coproduct of groups, by fear of confusion with the coproduct of abelian groups.
TLDR: Please ABSTAIN telling people to use the direct sum notation instead. They are both equivalent for finitely many factors and are both equally valid.
Thanks in advance. --137.205.233.146 (talk) 20:14, 11 January 2011 (UTC)