meta user
network profile
| bio | website | |
|---|---|---|
| location | ||
| age | ||
| visits | member for | 2 years, 4 months |
| seen | 1 hour ago | |
| stats | profile views | 76 |
|
May 10 |
answered | Good (Auto)Biographies of von Neumann and other physicists/mathematicians |
|
May 6 |
comment |
Non-standard models of arithmetic for Dummies It is worth saying that if you consider Presburger arithmetic (just forget about multiplication, and take the corresponding fragment of Peano arithmetic) then you can have non-standard models of the following kind: a copy of $\mathbb{N}$ followed by a discretely-ordered infinite sequence of copies of $\mathbb{Z}$. |
|
Apr 8 |
comment |
Undecidability in ZFC Thanks for your example. By the way, now I believe there was some mistake in my first proof. Could you take a look at my addendum? |
|
Apr 8 |
revised |
Undecidability in ZFC added 703 characters in body |
|
Apr 8 |
asked | Undecidability in ZFC |
|
Mar 31 |
revised |
First-order Indistinguishibility of “the continuum” added 5 characters in body |
|
Mar 31 |
asked | First-order Indistinguishibility of “the continuum” |
|
Feb 26 |
comment |
First-Order Logic vs. Second-Order Logic Let us consider some domain interpretation for your formula (for example, sets, human beings, ...). Then, the first-order variables (like x,y,z, etc.) must be interpreted as members of your domain (for example, x is a set, x is a human being, etc), while the second-order variables (like P, Q, etc) must be interpreted as subsets of your domain (for example, P is a family of sets, P is a family of human beings, etc). This is the difference. |
|
Feb 10 |
comment |
Lukasiewicz Logic Tautology This question is quite badly formulated. What is T? What is U? Do you mean first-order or just propositional? |
|
Feb 5 |
accepted | Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? |
|
Jan 31 |
comment |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? Although it is not clear to me whether that $T_2$ is recursively enumerable, it can be easily replaced by another $T_2$ with this requirement: take as axioms the ones from discrete linear orders plus the information of membership in $A$ given by numerals. |
|
Jan 31 |
comment |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? What it is not so obvious above is whether this $T_2$ is recursively enumerable or not. |
|
Jan 31 |
comment |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? Following one of @JDH previous comments (the 2nd above) now I see how to give a counterexample. Let us consider $T_1$ the theory, in the signature $(\leq, P)$, given by the structures with domain the natural numbers and where $\leq$ corresponds to the standard order. By the famous Buchi's Theorem this is decidable. And $T_1$ is finitely axiomatizable (by talking about discrete linear orders with minimum and without maximum). On the other hand, take $T_2$ to be the theory of $(\mathbb{N}, \leq , A)$ where $A$ is some c.e. set, but not decidable. Then, $T_2$ is easily seen to be non decidable. |
|
Jan 31 |
revised |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? added 245 characters in body |
|
Jan 30 |
comment |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? There is another trouble: Presburger arithmetic is not finitely axiomatizable. |
|
Jan 30 |
comment |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? Thanks for the detailed answer. Do you know any natural example? For example, what happens if we require a finite number of symbols in the language (i.e., a finite signature)? This assumption would avoid the trick based on constants. |
|
Jan 30 |
awarded | Supporter |
|
Jan 30 |
awarded | Commentator |
|
Jan 30 |
comment |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? Yes, you are right (Craig's trick). |
|
Jan 30 |
revised |
Example of an UnDecidable Logical Theory which is an extension of a Logical Decidable Theory? added 37 characters in body |
