Wikipedia:Reference desk/Archives/Mathematics/2016 June 17

Mathematics desk
< June 16 << May | June | Jul >> June 18 >
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.


June 17

edit

Precise definition of Σ00

edit

I encountered several different definitions for Σ00 = Π00 = Δ00 of the arithmetical hierarchy. Following are two definitions which seem to me different but I'm not sure:

While every recursively-defined function can be formalized on bounded variables in first-order Peano arithmetic using Gödel's β function (though usually one only uses it for primitive recursive functions), it seems that this formalization necessitates the use of unbounded quantifiers as well.

Why? suppose we want to write formally a formula   of the following form:

 

where   is some first-order formula and   is primitive recursively defined by:

 
 

with C a constant and F some already defined function (could be just multiplication, for the sake of the argument).

Then we should actually write   in the following way (as in this article):

 

Crucially, b cannot be bounded in arithmetic (without using yet other primitive recursive functions, and so on ad infinitum).

So   is in Σ10 but not in Σ00 according to the first definition given above, while it is in Σ00 according to the second definition.

Note that this will not affect the rest of the arithmetical hierarchy since we can always bound b by a variable given in an "external" unbounded quantifier.

To conclude, my question is: Are these two definitions really different?Dan Gluck (talk) 09:38, 17 June 2016 (UTC)[reply]

An answer can be found hereDan Gluck (talk) 22:07, 18 June 2016 (UTC)[reply]
My take, no references, just what I've inferred from being around the field and seeing how people talk about these things:
I think that basically people don't worry too much about the exact definition of the bottom of the hierarchy. Any differences get smeared out by the time you add one quantifier, so you can take the base to be whatever is convenient, either all primitive recursive predicates or only bounded quantifiers, as you like. Those may be the same or not, depending on exactly what's in the language, which mostly people don't want to worry about in too much detail.
There are similar phenomena at the bottom of the type-1 and type-2 hierarchies. Σ10 is not something we usually bother to define; the first level we care about is Σ11. That says you have one exists-a-real quantifier, but quantifying over what matrix? What are we allowed to do with real numbers inside the quantified formula? Usually we don't want to take the trouble to specify that precisely; instead, Σ11 is taken by convention to contain any set that's obtained by looking at all paths through a tree on ω×ω and projecting along one coordinate. --Trovatore (talk) 07:50, 19 June 2016 (UTC)[reply]

Semantics of recursive definitions

edit

Ackermann's function can be recursivey defined in arithmetic, while Goodstein sequence cannot (had it been such, it would have been provably computable, which is not). Both are totally computable (and thus "recursive") and both are not primitive recursive. Is there a name for functions that can be recursivey defined that includes Ackermann's function but not Goodstein sequence? (perhaps just "recursivey definable?") Dan Gluck (talk) 09:44, 17 June 2016 (UTC)[reply]

You can define it (a function from m to the length of G(m), for example) in Peano arithmetic. You can't prove in PA that the definition is total, but it is (in the standard model). I think "provably total" is the term you're looking for. -- BenRG (talk) 23:12, 17 June 2016 (UTC)[reply]

System of linear equations with a sum and ratios

edit

What is the general form of solutions of a system of linear equations based on a sum of bn numbers and n-1 distinct ratios between these numbers of the form bi/bj, i different from j (in connection to a related previously discussed topic here regarding distinct ratios)?

How is the form of solutions influenced by the increase of the number n?--82.137.10.243 (talk) 15:20, 17 June 2016 (UTC)[reply]

There may be no solutions - for example
 
has no solutions in real numbers. It is probably not helpful to think of your equations as being linear equations - they are certainly not linear in the bi. Gandalf61 (talk) 15:42, 17 June 2016 (UTC)[reply]
...or, even simpler,
 
 
has no solutions at all. Gandalf61 (talk) 15:54, 17 June 2016 (UTC)[reply]

What is the form of the solution for the following type of system having n equations (a sum of bi numbers and (n-1) bi/bj ratios) when the number of terms bi in the sum increases from 4 to 5 to 6 ..to n and the remaining n-1 equations as ratios chosen from n2 - n possible distinct ratios discussed above.

 

as tried on Talk:System_of_linear_equations#Type_of_a_system_-_general_solution?--82.137.10.68 (talk) 17:22, 17 June 2016 (UTC)[reply]

Could the general form solution be obtained through a mathematical induction analysis?--82.137.11.19 (talk) 10:09, 20 June 2016 (UTC)[reply]

Ok, for that specific system of n equations, if we can assume that the n-1 ratio equations all follow the pattern
 
the solution is:
 
 
 
...
 
where
 
Method - express   as multiples of  , then substitute in the first equation and you get  . Gandalf61 (talk) 13:55, 20 June 2016 (UTC)[reply]