433 reputation
138
bio website comp.nus.edu.sg/~a0078129
location Singapore
age
visits member for 2 years, 7 months
seen 6 hours ago

I'm an undergraduate majoring in Mathematics and Computer Science in National University of Singapore.


Nov
10
comment Cohesive set with degree below non-high Martin-Löf random reals
So the question is really for MLR which neither low or high.
Sep
24
awarded  Autobiographer
Jul
2
awarded  Curious
May
20
awarded  Yearling
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