Wikipedia:Reference desk/Archives/Mathematics/2011 November 1

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.

November 1

Omega consistency

Is the standard model of Peano arithmetic the only omega-consistent one? I can't find a proof or counterexample (I'd think that if this were not true a counterexample would probably be known, but maybe not). 129.97.223.186 (talk) 04:21, 1 November 2011 (UTC)

Your question makes no sense: ω-consistency is a property of theories, not of models. Algebraist 10:08, 1 November 2011 (UTC)

I think what you can say is that if an extension of the Peano axioms is consistent and ω-consistent, then it contains the standard model of PA as a model. Right? --COVIZAPIBETEFOKY (talk) 14:16, 1 November 2011 (UTC)

Maybe I'm misunderstanding you, but the only way I manage to read that, no, that's wrong. That would mean that PA+"PA is omega-consistent" (formulated in a sufficiently rich language — you can't actually say that in the language of arithmetic) would decide all arithmetic statements, which is certainly not so. --Trovatore (talk) 22:58, 1 November 2011 (UTC)

To clarify, what I meant to ask is whether every ω-consistent extension of Peano arithmetic has the standard model as one of its models. Trovatore: That is only true if the ω-consistency of a theory were decidable, which I don't think is true. 129.97.215.59 (talk) 00:19, 2 November 2011 (UTC)

It does seem to be a little subtler than I thought at first glance. But I still think it's false. I'll think about it and get back to you if no one beats me to it. Note that what you're really asking is whether an omega-consistent extension of PA can contain a false arithmetic statement. I think almost certainly that it can, but I don't have as ready an example as I thought at first. --Trovatore (talk) 00:51, 2 November 2011 (UTC)

OK, here's a candidate. Let T be the theory ZFC+"for some n, the theory ZFC+'there exist at least n inaccessible cardinals' is inconsistent". Let T0 be the set of all arithmetic statements proved by T.

Clearly T0 is consistent and proves a false arithmetic statement, namely "for some n, the theory ZFC+'there exist at least n inaccessible cardinals' is inconsistent".

The question is whether T0 is omega-consistent. Of that I'm not sure. But at least the obvious attempt to find a counterexample to omega-consistency fails — you can't show that, for each n, T0 proves the claim "the theory ZFC+'there exist at least n inaccessible cardinals' is inconsistent consistent", because T0 doesn't even prove that for n equals zero. --Trovatore (talk) 01:02, 2 November 2011 (UTC)

The statement is false; the article ω-consistent theory explains the issue reasonably well. Basically a 1-consistent theory can contain false statements at higher quantifier depths (1-consistent is a more modern term for ω-consistent). For example, consider the twin prime conjecture (TPC), which has a $\Pi _{2}^{0}$ formula: for all n, there exists p>n such that p and p+2 are both prime. Suppose TPC is independent of Peano arithmetic (nobody knows if it is). Then either TPC or not-TPC can be added to PA without causing inconsistency or 1-inconsistency. But only one of them can be true in the standard model, so the other only holds in nonstandard models. 69.228.170.114 (talk) 09:22, 2 November 2011 (UTC)

I would quibble that it's not obvious to me that your claim follows just by assuming that TPC is independent of PA. Suppose for example that TPC is neither provable nor refutable from PA, but is provably equivalent in PA to some $\Pi _{1}^{0}$ statement (obviously, this statement that is, the hypothetical $\Pi _{1}^{0}$ statement in question would necessarily be true, because PA refutes all false $\Pi _{1}^{0}$ statements). If you know some reason that scenario can't happen, please do enlighten me.

Secondly, I would like to know a particular $\Pi _{2}^{0}$ statement such that both the statement and its negation are 1-consistent with PA, or at least an argument showing that such a statement exists. I completely believe you that it does, it seems like the natural hypothesis, but I don't know how to prove it. --Trovatore (talk) 20:09, 2 November 2011 (UTC)

I disagree with the claim that if TPC is independent of PA, then either can be added to PA without causing 1-inconsistency. Suppose TPC is true in the standard model. Then PA proves "there are twin primes bigger than n" for every n. So no 1-consistent extension can prove that there is an upper bound to the twin primes, and thus not-TPC + PA is 1-inconsistent. Alternatively, if TPC is false in the standard model, then for some m, PA proves "there are no twin primes between m and m+n" for every n. So no 1-consistent extension can prove that there are twin primes greater than m, and thus TPC + PA is 1-inconsistent.--121.74.125.249 (talk) 22:26, 2 November 2011 (UTC)

In fact, in general you can show that if a $\Sigma _{3}^{0}$ sentence is true in the standard model of PA, no 1-consistent extension can disprove it. So 2 quantifiers is insufficient. Edit: this is 121 from above. Just changed locations. I should really sign in.--130.195.2.100 (talk) 23:17, 2 November 2011 (UTC)

Tensors

I have been asked to show that the relativistic generalisation of Ohm's law ${\boldsymbol {j}}=\sigma {\boldsymbol {E}}$, which is in the rest of frame of the conducting medium, is given by $J^{\mu }+(J^{\nu }U_{\nu })U^{\mu }={\sigma }F^{\mu \nu }U_{\nu }$ where $J^{\mu }=(\rho ,{\boldsymbol {j}})$ and $U^{\mu }={\gamma }(1,{\boldsymbol {v}})$, which is in a frame where the medium moves with uniform velocity ${\boldsymbol {v}}$. I have already shown that the $F^{\mu \nu }U_{\nu }={\gamma }({\boldsymbol {E}}.{\boldsymbol {v}},{\boldsymbol {E}}+{\boldsymbol {v}}\times {\boldsymbol {B}})$.

Originally I asserted that, from the rest frame, we have $(0,{\boldsymbol {j}})=J^{\mu }={\sigma }F^{\mu \nu }U_{\nu }=(0,\sigma {\boldsymbol {E}})$. From this, I said that the generalisation must be of the form $J^{\mu }+X^{\mu }={\sigma }F^{\mu \nu }U_{\nu }$ and tried to find X via $X^{\mu }={\sigma }F^{\mu \nu }U_{\nu }-J^{\mu }$. But I am having big problems in simply verifying the given result never mind deriving it. [I am of the understanding that my approach is incorrect anyway but I'd like to work out where I'm going wrong with my tensor manipulation.]

So, we have $U^{\mu }={\gamma }(-1,{\boldsymbol {v}})$, so $J^{\nu }U_{\nu }=-\rho \gamma +\gamma {\boldsymbol {v}}.{\boldsymbol {j}}$ so $(J^{\nu }U_{\nu })U^{\mu }=(-\rho {\gamma }^{2}+{\gamma }^{2}{\boldsymbol {v}}.{\boldsymbol {j}})(1,{\boldsymbol {v}})$. Are these manipulations correct? I later have to derive a relation for ${\boldsymbol {j}}$, in which no $\rho {\gamma }^{2}{\boldsymbol {v}}$ features, merely a $\rho {\boldsymbol {v}}$.

Also, I think I need to apply a Lorentz boost to actually derive the given relation but I am unsure of the particular boost I want. Can someone please help? Thanks. asyndeton talk 15:47, 1 November 2011 (UTC)

Complex probability distibution

Here's a situation from a computer game I'm playing: You've got 16 objects. You randomly select three of them without replacement, put them back, and repeat. What's the average number of rounds of "select three" needed to select all 16, and what does the distribution look like? --Carnildo (talk) 20:16, 1 November 2011 (UTC)

"Select three" seems too hairy so let me try with "select one"; the method can probably be adapted to the more complex problem. For generality let n be the number of objects, so plug n=16 in the answer below. Let F(k,i) be the probability that, after round i, k objects have been picked. Let f(k, t) be the generating function ∑F(k,i)tⁱ. 0 objects have been picked at the start and more than 0 have been picked after that, so F(0,i)=1 if i=0, 0 otherwise, and so f(0,t)=1. After 1 round 1 object has been picked so F(1,1)=1, and with each additional round there is a 1/n chance that the same object will be picked again, so F(1,i)=1/n^i-1 and so

$f(1,t)={\frac {nt}{n-t}}$

For general F(k,i) you get (n-k+1)/n F(k-1,i-1) chance that a new object will selected, plus k/n F(k,i-1) chance that a previously picked object will be selected. So F can be computed by

$F(k,i)={\frac {n-k+1}{n}}F(k-1,i-1)+{\frac {k}{n}}F(k,i-1)$

Translating this to f gives

$f(k,t)={\frac {t(n-k+1)}{n}}f(k-1,t)+{\frac {tk}{n}}f(k,t)$

or

$f(k,t)={\frac {t(n-k+1)}{n-kt}}f(k-1,t)$

Expanding for k=n gives

$f(n,t)={\frac {t^{n}n!}{(n-t)(n-2t)\dots (n-nt)}}$

To get the generating function, g say, for the probability that the first time all n objects have been selected is round i, multiply this by 1-t. With a bit of cancellation this gives

$g(t)={\frac {t^{n}(n-1)!}{(n-t)(n-2t)\dots (n-(n-1)t)}}$

As a check g(1) does evaluate to 1 which is the probability that every object is selected eventually. The expected number of rounds will be g′(1) which can be found by logarithmic differentiation

$g'(t)=g(t)\{{\frac {n}{t}}+{\frac {1}{n-t}}+{\frac {2}{n-2t}}+\dots +{\frac {n-1}{n-(n-1)t}}\}$

so the expected number of rounds needed is

$n+{\frac {1}{n-1}}+{\frac {2}{n-2}}+\dots +{\frac {n-1}{1}}$

For n large enough (say >10) I'd guess that a reasonable estimate for the number of "pick three" rounds is this number divided by three.--RDBury (talk) 22:49, 1 November 2011 (UTC)

One of these days I'll learn about generating functions, but in the mean time I can provide some numerical backup. I made 10 runs of 10,000,000 random trials each of the draw 1 and draw 3 scheme for n=16. For each 10,000,000 trial run I calculated the average number of rounds necessary to choose all 16, and then compared those ten values.

draw 1 -- range: 54.086428 - 54.097903 average: 54.09038379

draw 3 -- range: 17.184745 - 17.188319 average: 17.18565233

so the actual expected values appear close to 54.09 and 17.18(5). RDBury's formula for n=16 yields 54.09166389 and 1/3 of that is 18.03055. As RDBury stated, the draw 3 value will approach 1/3 the draw 1 value as n grows, but at n=16 the actual value appears to be about 5% below that. -- 110.49.227.102 (talk) 08:33, 2 November 2011 (UTC)

Nice. It occurred to me that the "pick one" value as a random variable is the sum of independent variables with geometric distributions, which would make the analysis somewhat easier than the one I did above. It's possible that the "pick three" distribution could be computed using Markov chains. The transition matrix is easy to compute and is triangular so every state but one is transient.--RDBury (talk) 10:08, 2 November 2011 (UTC)

Selecting one item gives the Coupon collector's problem, with expectation 54.09... for 16 items. For the three-item problem, the minimum possible number of draws is 6 but there is no upper limit, so the distribution will have an infinite right tail. Simulation suggests that it is unimodal at 14.2, has a median of 15.6 and a mean of 17.2 as mentioned above, and that you'd be a bit surprised if you had to perform more than 30 draws to select all of the items, the probability of this being 3.1%.→86.155.185.195 (talk) 10:48, 2 November 2011 (UTC)

I would have been surprised if the one item version wasn't already known, but it's nice to know we have an article on it.--RDBury (talk) 02:03, 3 November 2011 (UTC)