Impact
~9k
people reached
- 0 posts edited
- 0 helpful flags
- 4 votes cast
May
2 |
awarded | Curious |
Mar
25 |
awarded | Yearling |
Mar
25 |
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 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}^*$? |