709 reputation
411
bio website
location
age
visits member for 3 years, 6 months
seen Jul 22 at 5:10

Feb
25
comment Confusion of the decidability of $(N,s)$
@Chen: Take a look at en.wikipedia.org/wiki/Second-order_logic , and then you can read the following "old" survey by Gurevich projecteuclid.org/euclid.pl/1235417279
Feb
25
comment Confusion of the decidability of $(N,s)$
@Chao: Yes, PA axioms are complete for the $(\mathbb{N},s,+)$ fragment. To see this it is enough (because Pressburger arithmetic is complete) to check that the fragment of any PA-model satisfies the sentences in some axiomatization of Pressburger arithmetic (see for example en.wikipedia.org/wiki/Presburger_arithmetic )
Feb
25
answered Confusion of the decidability of $(N,s)$
Feb
18
comment Nonstandard models of Presburger Arithmetic
Where have you read the statement?
Jan
21
comment lattice-ordered group
Hint: In $a+\sup(b,c) \leq \sup((a+b),(a+c))$ you can move the $a$ to the right side (because you are in a group).
Jan
10
awarded  Yearling
Dec
16
comment Does quantifier elimination imply decidability?
Indeed, adding new symbols to the language any theory can be conservatively expanded into one which admits quantifier elimination. This conservative expansion is sometimes sknown as Morleyization. Hence, since not every first-order theory is decidiable it follows that the answer to your question is "No".
Dec
11
comment Example of decidable & undecidable in First Order Logic
The question is still nonsense. What is your definition of "decidable in first-order logic"?
Dec
9
comment First Order Logic Example of Halting Problem
www.math.psu.edu/simpson/courses/math457/trakh.ps
Dec
9
comment First Order Logic Example of Halting Problem
Take a look at the following file math.psu.edu/simpson/courses/math457/trakh.ps
Nov
26
comment Is there a decidable theory in propositional logic whose consequences are not decidable?
Hint: Let us consider for every $X \subseteq \mathbb{N}$ the theory $T_X$ which is the one generated by the set $\{p_n:n \in X\}$ of variables. Can you consider some X such that $\{p_n:n \in X\}$ is not decidable but $T_X$ is recursively enumerable?
Nov
22
comment Who first explicitly noted that second-order logic is unaxiomatizable?
Indeed, Henkin says "This follows from results of Godel concerning systems containing a theory of natural numbers, because a finite categorical set of axioms for the positive integers can be formulated within a second order calculus to which a functional constant has been added." So Henkin does does not give a reference, but he provides a proof (without the details, but it is quite clear this is a proof).
Sep
25
comment Difference between elementary logic and formal logic
@Peter: You are absolutely right that metalogic is in general in a much wider sense. I should have said "elementary logics refers to a part of metalogic" (the easiest part).
Sep
25
comment Difference between elementary logic and formal logic
I suspect that your answer to question 1 (that is, elementary logic refers to metalogic) is what Kelley had in mind. Concerning question 2 I suggest you look at en.wikipedia.org/wiki/Consequence_operator
Aug
21
comment Is the set of all definable subsets of the natural numbers recursively enumerable?
@Thomas: I do not follow your last edition, it has the same troubles. I can understand what you mean by a natural number which is well formed (although I dislike your terminology and proposal), but I do not understand your definition for subsets of natural numbers. Let me do some concrete questions: how do you codify the subset of odd numbers? how do you codify the subset of even numbers? how do you codify the subset of prime numbers? etc.
Aug
20
comment Is the set of all definable subsets of the natural numbers recursively enumerable?
As Carl Mummert says in his answer, your question is ambiguous (I disagree with his interpretation of the question, but what he says is completely fine). Problems about decidability (and recursive enumerability) must be presented in the form of a subset of natural numbers (another option is to consider a subset of the set $\{0,1\}^*$ of finite binary strings). Thus, your question must be rewritten saying which is the subset of natural numbers you are wondering whether is recursively enumerable. Notice for instance that in Carl's answer he has considered the subset $\{ n_{i,j}:i,j\in\omega\}$.
Aug
20
comment Is the set of all definable subsets of the natural numbers recursively enumerable?
Let me remember that the "Turing machine" model is a finitistic one; it only accepts finite inputs and it only produces finite outputs. How do you want to codify in a finitistic way a subset of natural numbers? The more natural way is to use a finitistic formula to describe the set, but then it is obvious which is the answer to your question (YES). If you do not want to use the natural way then you must add to the question what is the finitistic codification (for subsets of natural numbers) you want to use.
Aug
16
comment Totally ordered set with greater cardinality than the continuum
Although no Axiom of Choice [AC] is needed if you use the theory of transfinite ordinals, let me give a "simple" example (simple in the sense that you do not need to know ordinals) using Zorn's Lemma (which is known to be equivalent to [AC]). First consider the partial $( \mathcal{P}(\mathbb{R}), \subseteq )$, and then use Zorn's Lemma to prove that every partial order can be extended to a linear order (look at en.wikipedia.org/wiki/Linear_extension and en.wikipedia.org/wiki/Szpilrajn_extension_theorem )
Aug
9
answered Introductory text for lattice theory
Jul
30
comment Standard references for boolean algebra?
Another reference is the book "Countable Boolean Algebras and Decidability" by Goncharov books.google.es/books?id=BwroiP0IJcYC