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

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

Precise definition of Σ₀⁰

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

• All first-order arithmetic formulas that have no unbounded quantifiers.
• All first-order arithmetic formulas describing functions that can be recursively defined (sometimes the definition includes only primitive recursive functions, thus excluding functions such as Ackermann's function; I believe Goodstein sequence, while computable, is excluded in both cases).

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 $\varphi (n)$ of the following form:

$\forall k<n:\varphi _{0}(a_{k})$

where $\varphi _{0}$ is some first-order formula and $a_{k}$ is primitive recursively defined by:

$a_{0}=C$

$a_{n+1}=F(a_{n},n)$

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 $\varphi (n)$ in the following way (as in this article):

$\exists b:\exists c<b:\forall k<n:\varphi _{0}(\beta (b,c,k))\land (\beta (b,c,0)=C)\land \forall i<n:(\beta (b,c,i+1)=F(\beta (b,c,i),i))$

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

So $\varphi (n)$ is in Σ₁⁰ but not in Σ₀⁰ according to the first definition given above, while it is in Σ₀⁰ 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)

An answer can be found hereDan Gluck (talk) 22:07, 18 June 2016 (UTC)

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. Σ¹₀ is not something we usually bother to define; the first level we care about is Σ¹₁. 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, Σ¹₁ 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)

Semantics of recursive definitions

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)

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)

System of linear equations with a sum and ratios

What is the general form of solutions of a system of linear equations based on a sum of b_n numbers and n-1 distinct ratios between these numbers of the form b_i/b_j, 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)

There may be no solutions - for example

${\frac {b_{1}}{b_{2}}}+{\frac {b_{2}}{b_{1}}}=1$

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 b_i. Gandalf61 (talk) 15:42, 17 June 2016 (UTC)

...or, even simpler,

${\frac {b_{1}}{b_{2}}}=1$

$b_{1}-b_{2}={\frac {b_{1}}{b_{2}}}$

has no solutions at all. Gandalf61 (talk) 15:54, 17 June 2016 (UTC)

What is the form of the solution for the following type of system having n equations (a sum of bi numbers and (n-1) b_i/b_j 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 n² - n possible distinct ratios discussed above.

$b_{1}+b_{2}+b_{3}=b,{\frac {b_{1}}{b_{2}}}=r_{1},{\frac {b_{2}}{b_{3}}}=r_{2},$

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)

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

Ok, for that specific system of n equations, if we can assume that the n-1 ratio equations all follow the pattern

${\frac {b_{k}}{b_{k+1}}}=r_{k}$

the solution is:

$b_{n}={\frac {b}{s}}$

$b_{n-1}={\frac {r_{n-1}b}{s}}=r_{n-1}b_{n}$

$b_{n-2}={\frac {r_{n-2}r_{n-1}b}{s}}=r_{n-2}b_{n-1}$

...

$b_{1}={\frac {r_{1}r_{2}\dots r_{n-2}r_{n-1}b}{s}}=r_{1}b_{2}$

where

$s=1+r_{n-1}+r_{n-2}r_{n-1}+\quad \dots \quad +r_{1}r_{2}\dots r_{n-2}r_{n-1}$

Method - express $b_{1}\dots b_{n-1}$ as multiples of $b_{n}$, then substitute in the first equation and you get $sb_{n}=b$. Gandalf61 (talk) 13:55, 20 June 2016 (UTC)