bio | website | |
---|---|---|
location | Seattle WA USA | |
age | ||
visits | member for | 2 years, 1 month |
seen | Oct 7 at 1:25 | |
stats | profile views | 189 |
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? |