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

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 _{1}^{0}$. 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 _{1}^{0}$ is the best possible for a true unprovable sentence, since all true $\Sigma _{1}^{0}$-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)³. 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— Fly by Night (talk) 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)

What was the need for that reply, and this edit summary? It's obvious I was trying to help someone in good faith. Making suggestions. As my first message begain: "I think the convention is..." and my second one "You ought to...". What sort of an anti-social jerk wades in with a reply and edit summary like the one you gave? And you didn't even have the guts to sign in to your normal account! (Or was that your first edit to RD/MATH?) I hope Warwick university know what good use you put their network computers to. For the record: I know that A⊕B and A×B are the same; I've said so! The direct sum is used with abelian groups to emphasise their addative structure (as I already mentioned, and linked to in the past). Please ABSTAIN from telling people what to do. Oh, and make sure you log in to your account next time. — Fly by Night (talk) 18:39, 16 January 2011 (UTC)

Earth vs. human vs. rhinovirus

How many average-sized humans would fit into the Earth? And how many rhinoviruses would fit into an average-sized human? I could figure it out but my cold is so bad I can't even remember how standard notation works. —Preceding unsigned comment added by 93.96.113.87 (talk) 20:41, 10 January 2011 (UTC)

Before attempting to answer, you must state what condition the humans must be in. If you allow them to be puréed first, you can get a lot more in. Not only will the liquid remains fill in nicer, it will also remove the empty air cavities. -- kainaw™ 20:44, 10 January 2011 (UTC)

http://www.wolframalpha.com/input/?i=(earth+volume)%2F(human+volume) gives 10^22 humans in the earth, while http://www.wolframalpha.com/input/?i=(human+volume)%2F((100+nm)^3) gives 10^20 rhinoviruses in a human. The diameter of a rhinovirus is about 100 nm. Bo Jacoby (talk) 13:57, 14 January 2011 (UTC).