Mathematics desk
< December 14	<< Nov \| December \| Jan >>	December 16 >

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.

December 15[edit]

Berry paradox in second order logic[edit]

Why doesn't the Berry paradox apply to second order logic? I am familiar with self-referential arguments, but not with second-order logic, so I'm wondering why you can't state something like 'the first set of natural numbers not uniquely definable by a second-order statement with one free variable', given some well ordering of the set of sets of natural numbers. 129.97.215.245 (talk) 03:47, 15 December 2011 (UTC)[reply]

Once you talk about a wellordering of P(P(N)), you're already in third-order arithmetic, and it might well be that no such wellordering is definable in third-order arithmetic. So maybe what you want to do is throw in a predicate symbol for the wellordering, and work with definability with the wellordering as a parameter?

You could do that, I guess. I think what you'll find is that to define definability in this second-order language with the predicate for the wellordering, you'll need third-order logic, or some fragment of it, but in any case more than second-order. --Trovatore (talk) 09:45, 16 December 2011 (UTC)[reply]

I guess I should have mentioned this is my question, but according to http://plato.stanford.edu/entries/logic-higher-order/#4, any sentence in third (or higher) order logic is equivalent (constructively) to some sentence of second-order logic, so a wellordering should be translatable into second-order logic. Also, it isn't that hard to construct a wellordering of sets of naturals informally: there is a bijection from them to strings of binary digits where the ith digit represents whether the ith number is in the set. I'm not sure how to express this formally, but I would expect that it would be representable in third-order logic and then a corresponding second-order statement could be found. 129.97.215.57 (talk) 17:13, 16 December 2011 (UTC)[reply]

I haven't read your link carefully yet, but I think you have a misunderstanding here.

Here's what's true: In second-order logic, you can give a theory that completely characterizes the natural numbers up to isomorphism, which in some sense is as much as you could ever want them to be characterized. That is, any two models of this theory (models in the sense of full second-order logic) have all the same properties, first-order, second-order, third-order, and every higher order.

However that does not mean that third-order formulas are not more expressive than second-order formulas. They are more expressive. The second-order sentences have already fixed the objects of discourse; that doesn't mean they can say everything there is to be said about them. --Trovatore (talk) 19:49, 16 December 2011 (UTC)[reply]

It is true that there is a procedure to test logical validity of higher-order statements in terms of logical validity of a second-order statement. But this does not help with Berry's paradox. A sentence like "There is a least set which is not definable by any second-order formula" is not directly a second-order sentence; if we convert it into an equivalent second-order sentence, that sentence will simply be true or false the same as the original sentence. The converted sentence will not directly give us a second-order definition of any set, which is what we would need to make the argument in Berry's paradox go through.

You might think about trying to change the formula "x is the least set which is not definable by any second-order formula" into a second-order formula with a free variable x, but the theorem is only that sentences of higher-order logic can be changed into sentences of second-order logic in a way that preserves logical validity. The theorem does not give a way to change higher-order formulas with free variables into second-order formulas that are true of exactly the same objects. — Carl (CBM · talk) 20:41, 16 December 2011 (UTC)[reply]

I see. Thanks for your help. One more thing: does this mean that second-order logic can express arbitrary properties of a set, ie. it can express the truth of falsity of 'if x is the least set not definable by second-order logic, than P(x)', where P(x) is a general second-order expression involving x, not a predicate. 129.97.215.57 (talk) 03:48, 17 December 2011 (UTC)[reply]

Sieve of Atkin[edit]

There is an ambiguity in the lead of the article. It says "[it] marks off multiples of primes squared, rather than multiples of primes". It isn't clear whether it means the multiples of primes are squared, or is it the multiples of the squared primes that are marked. I don't understand it. Could someone please explain this? Thanks! -- WillNess (talk) 08:58, 15 December 2011 (UTC)[reply]

It means multiples of the squared prime, i.e. np² rather than (np)². This is so that non-squarefree integers are excluded before the quadratic forms tests are applied. I have changed the wording of the lead paragraph to try to make this clearer. Gandalf61 (talk) 09:38, 15 December 2011 (UTC)[reply]

Thanks! WillNess (talk) 17:21, 15 December 2011 (UTC)[reply]

Calculating average utilization of equipments[edit]

What is the correct method of calculating the average utilization of equipment over a period of time. I am just confused between the two methods that can be used for calculation:

Total number of hours available for: 17 (May-11), 9 (Jun-11)

Total number of hours actually used for: 13 (May-11), 6 (Jun-11)

Method 1:

Utilization calculated for each month and then averaged: 0.764705882(=13/17 for May-11), 0.666666667(=6/9 for Jun-11)

Average utilization: 72% (average of 0.764705882 & 0.666666667) and then %

Method 2:

Total number of hours available for (May+Jun): 26 (=17+9 for May-11 & Jun-11)

Total number of hours actually used for (May+Jun): 19 (=13+6 for May-11 & Jun-11)

Taken the sum of both numerator and denominator and then calculated the utilization: 73% (=19/26 and then %)

The second would be normal. If you worked like a dog for one day of the week and lazed the other five you wouldn't say you were working hard for half the time (well a person might but others wouldn't) Dmcq (talk) 15:00, 15 December 2011 (UTC)[reply]

I believe the first method is called an "average of averages" and it's a common statistical error. It seems like WP should have something on this but I don't see a good source when I Google the phrase.--RDBury (talk) 08:49, 16 December 2011 (UTC)[reply]

The first is sometimes done, the resulting figure doesn't mean an awful lot generally but its easy to calculate and for something like months like you say it should normally make little difference. Dmcq (talk) 02:05, 17 December 2011 (UTC)[reply]