bio | website | comp.nus.edu.sg/~a0078129 |
---|---|---|
location | Singapore | |
age | ||
visits | member for | 1 year, 11 months |
seen | 7 hours ago | |
stats | profile views | 309 |
I'm an undergraduate majoring in Mathematics and Computer Science in National University of Singapore.
Feb 15 |
answered | Can a Decidable Theory Have Non-recursive Models? |
Feb 10 |
comment |
Godel's Second Incompleteness theorem and Models
I'm not completely sure if I know what model-theoretic explanation you are looking for, but let me just say, assume $\Gamma$ is consistent, since $Con(\Gamma)$ is not provable from $\Gamma$, there is a model of $\Gamma$ such that $\neg Con(\Gamma)$ is true, namely, in this model you could even show that ``$\Gamma$ proves $\exists v (v\neq v)$'' |
Jan 26 |
comment |
Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$
@FrançoisG.Dorais: You are right. Obviously I left out some details thinking that some restriction could be relaxed. See my edit. |
Jan 26 |
revised |
Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$
added 444 characters in body |
Jan 25 |
asked | Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$ |
Dec 8 |
revised |
First order consequence of a combinatorial principle
deleted 255 characters in body |
Dec 8 |
revised |
First order consequence of a combinatorial principle
edited title |
Nov 13 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
@LawrenceWong: I feel pretty much the same way as you do. It may get very model dependent indeed. |
Nov 11 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
Exactly. If considering $M$-finite instead of $standard$ finite, a special class of r.e. sets, Turing functionals, would always have M-finite use. Since the elements are of the form $(x,y,P,N)$ and it only uses X on the segment of P and N. Obviously the same thing could not be said about any r.e. set. I'm wondering if there is some nice characterization of this. |
Nov 10 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
I doubt it is still not true even without bounded quantifiers in general. This may be the result of failure of $I\Sigma_1^{0,X}$ for some set $X$ and a $\Sigma_1^0$-formula without bounded quantifiers. For example, the set could be very complex, like $\emptyset^{(100)}$ for example. |
Nov 10 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
I was actually looking at the non-standard first-order universe and trying to see how much computability theory can be developed there. Therefore, different from second-order arithmetic, the induction schemes and comprehension schemes are totally first-order (no set parameters). I wasn't expecting normal form theorem to be true there either. I am wondering if there is any analog that we can say in the non-standard universe. |
Nov 10 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
My question is exactly your latter formulation. Actually, in the second-order arithmetic if the set is in the second-order part of the universe, it is considered M-finite already therefore, there is no issue about normal form theorem. In general, if we only look at the first-order universe and sets in the second-order universe are those that can be coded by a number (binary representation), a cut can not be M-finite (i.e. coded as a number in M), otherwise, it contradicts with the failure of some induction scheme (for example failure of $\Sigma_2^0$). |
Nov 10 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
@NoahS: Indeed my bad. Could think of $y,z$ as $k_0,k_1$. See my edits. $z(j)$ is not equal to $X(j)$ where $z$ is just some binary code in M for a M-finite set. |
Nov 10 |
revised |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
added 166 characters in body |
Nov 10 |
comment |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
@NoahS: Sorry it was a typo should be $\{X\in 2^\omega: \exists k \exists y,z<k \varphi(X|y,z)\}$. Yeah I mean $\Sigma_1^0$ in M. |
Nov 10 |
revised |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
added 4 characters in body |
Nov 10 |
revised |
Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA
added 4 characters in body |
Nov 10 |
asked | Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA |
Oct 28 |
comment |
Disobedience of some complete r.e. set to some additive cost function
I see the first method though it still sounds like a quite involved construction to get a MLR but not OWR Turing incomplete set. For your alternative method, are you saying there is a direct proof for: If $\beta$ is a left-c.e. Martin-Löf random real and $A$ obeys $c_\beta$, then $\beta$ is also Martin-Löf random relative to $A$? I can see that by the assumption, A is K-trivial so definitely it is low for randomness. However, the implication from K-triviality to lowness for randomness seems to require golden run. Is there any other direct way of showing this? |
Oct 28 |
asked | Disobedience of some complete r.e. set to some additive cost function |