344 reputation
29
bio website
location Seattle WA USA
age
visits member for 1 year, 10 months
seen Jul 12 at 5:02

May
25
awarded  Good Question
Feb
23
comment Can a Decidable Theory Have Non-recursive 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 Non-recursive 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 Non-recursive Models?
OK. Could a finite field be an input to an algorithm?
Feb
15
comment Can a Decidable Theory Have Non-recursive 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 non-computable constants. I hadn't thought about non-recursive 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 Non-recursive Models?
Feb
15
revised Can a Decidable Theory Have Non-recursive Models?
fix a mistake
Feb
15
comment Can a Decidable Theory Have Non-recursive Models?
Thanks. I will correct the question.
Feb
15
comment Can a Decidable Theory Have Non-recursive 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 Non-recursive 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 Non-standard 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 Non-standard 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 Non-standard 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 Non-standard Models of Modular Arithmetic?
Dec
17
comment Recursive Non-standard 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 Non-standard Models of Modular Arithmetic?
repond to questions
Dec
14
revised Recursive Non-standard Models of Modular Arithmetic?
added tag
Dec
14
comment Recursive Non-standard Models of Modular Arithmetic?
I would accept this as an answer. Let $PA^{-Inf}$ be PA with out the axiom $\forall x(Sx \neq 0)$. Would Tennenbaum's theorem apply to $PA^{-Inf}$? Does Tennenbaum's theorem require the axiom $\forall x(Sx \neq 0)$?
Dec
14
comment Recursive Non-standard Models of Modular Arithmetic?
Why doesn't Tennenbaum's theorem apply to MA? What prevents me from encoding a recursively inseparable set as a non-standard number?