428 reputation
126
bio website comp.nus.edu.sg/~a0078129
location Singapore
age
visits member for 1 year, 11 months
seen 7 hours ago

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