bio  website  

location  Seattle WA USA  
age  
visits  member for  2 years, 6 months 
seen  yesterday  
stats  profile views  200 
2d

awarded  Yearling 
2d

revised 
Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?
fix typo 
Mar 24 
answered  Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$? 
May 25 
awarded  Good Question 
Feb 23 
comment 
Can a Decidable Theory Have Nonrecursive Models?
This is what I thought, too. We can encode a set of ordered triples proving addition and multiplication are total over a finite field. I don't see the significance of the algorithm being "nonstandard". All algorithms are nonstandard in a nonstandard model. 
Feb 21 
comment 
Can a Decidable Theory Have Nonrecursive Models?
Assume there is an algorithm that can prove if a finite field is recursive. It would prove all standard finite fields are recursive. Using overspill we could then prove there must exist a recursive nonstandard finite field violating Tennenbaum's theorem. I don't see how we could prove all finite fields are recursive. 
Feb 15 
comment 
Can a Decidable Theory Have Nonrecursive Models?
OK. Could a finite field be an input to an algorithm? 
Feb 15 
comment 
Can a Decidable Theory Have Nonrecursive Models?
Tao's blog talks about decidable subsets of nonstandard finite fields. It seems reasonable to ask if such a subset can encode a recursively inseparable set. It makes sense this might require defining noncomputable constants. I hadn't thought about nonrecursive models of Presburger arithmetic. Does this mean there is no algorithm to tell which models of Presburger arithmetic are recursive? 
Feb 15 
accepted  Can a Decidable Theory Have Nonrecursive Models? 
Feb 15 
revised 
Can a Decidable Theory Have Nonrecursive Models?
fix a mistake 
Feb 15 
comment 
Can a Decidable Theory Have Nonrecursive Models?
Thanks. I will correct the question. 
Feb 15 
comment 
Can a Decidable Theory Have Nonrecursive Models?
Does this mean Terence Tao's description of "almost quantifier elimination" can't be implemented recursively? 
Feb 15 
asked  Can a Decidable Theory Have Nonrecursive Models? 
Jan 26 
comment 
Constructing Useful SAT Instances
Each $k$CNF clause removes exactly one $k$bit assignment. The example you give has six $3$bit assignments that must be removed: $000, 001, 010, 011, 100,$ and $111$. For example, $(\neg x1 \lor \neg x2 \lor \neg x3)$ removes $111$. 
Dec 19 
comment 
Recursive Nonstandard Models of Modular Arithmetic?
I want an injection that preserves successor: $(a=b+1) \rightarrow (a=0 \lor f(a)=f(b)+f(1))$. 
Dec 19 
comment 
Recursive Nonstandard Models of Modular Arithmetic?
I apologize for using terms I don't understand. What I meant is can I map the elements of an ACF to the elements of a ring $\mathbb{Z}^* /n^* \mathbb{Z}^*$? 
Dec 18 
comment 
Recursive Nonstandard Models of Modular Arithmetic?
Thanks for taking the time to answer my question. I assume MA would not be "the theory of $\mathbb{Z}^* /n^* \mathbb{Z}^*$". Would you say something about what axioms such a theory would have? I will repost the question as "Are there theories where $\mathbb{Z}^* /n^* \mathbb{Z}^*$? is a recursive model" if you want. 
Dec 18 
accepted  Recursive Nonstandard Models of Modular Arithmetic? 
Dec 17 
comment 
Recursive Nonstandard Models of Modular Arithmetic?
@Joel: The usual definition $a \leq b \leftrightarrow \exists x(b = a+x)$ is meaningless in MA. We can impose an order if we assume the MA model can be embedded into some model of PA. I don't know if every model of MA can be embedded into a model of PA. How would I embed an ACF into PA? This is why I asked if an ACF can be homomorphic to some $\mathbb{Z}^* /n^* \mathbb{Z}^*$? 
Dec 15 
revised 
Recursive Nonstandard Models of Modular Arithmetic?
repond to questions 