Timeline for Complete mathematics
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 20, 2021 at 20:44 | comment | added | Erik Walsberg | Another example worth mentioning is the monadic second order theory of $(\mathbb{N},<)$. This is decidable and interesting, in large part because a lot of structures can be coded in it. For example it interprets the theory of $(\mathbb{N},+,V_k)$ where $k \ge 2$ is an integer and $V_k(m,n,i)$ holds when $i \in \{1,\ldots,k - 1\}$ is the $n$th $k$-ary digit of $m$. So this theory is decidable. There are also interesting connections to automata theory. | |
| Jun 6, 2011 at 22:46 | comment | added | George Lowther | @Bubba88: The standard model of ZFC has a countable set of axioms. There's only a countable set of possible sentences. But, it is definitely not effectively axiomatizable. | |
| Jul 11, 2010 at 11:00 | comment | added | Carl Mummert | They're not the same. A theory is effectively axiomatizable if the theory is generated by some computable set of axioms. A stronger condition, mentioned by Dave Marker, is decidability: there is a computable function that correctly determines whether an arbitrary formula is a logical consequence of the axioms. | |
| Jul 11, 2010 at 6:31 | vote | accept | Bubba88 | ||
| Jul 11, 2010 at 6:30 | comment | added | Bubba88 | Hi! Great answer :) Is effective axiomatization equivalent to countable axiomatization? | |
| Jul 10, 2010 at 16:39 | comment | added | Dave Marker | Other important basic examples of complete decidable theories are the theory of the integers as an additive ordered group and the theory of the $p$-adic numbers as a valued field. | |
| Jul 10, 2010 at 13:29 | comment | added | François G. Dorais | (The algebraically closed field example also works for characteristic 0.) | |
| Jul 10, 2010 at 12:02 | history | answered | Carl Mummert | CC BY-SA 2.5 |