Reputation
759
Top tag
Next privilege 1,000 Rep.
Create new tags
Badges
4 11
Newest
 Curious
Impact
~31k people reached

  • 0 posts edited
  • 0 helpful flags
  • 91 votes cast
Apr
14
comment First Order Logic: Formula for $y$ is the sum of non-negative powers of $2$
It is well known that the exponential formula is first order definable in the (standard) natural numbers (with the language you have stated in the question), you can find this on any book about Peano arithmetic or Gödel incompletenes theorem. However, for your particular question you do not need this (at least if you are thinking in the standard model), because all natural numbers are the sum of non-negative powers of 2.
Apr
8
comment Decidability of a Turing machine always halting in at most ten steps
@Alex: Using which input? [One has to realize that there are infinite inputs]
Apr
8
comment Decidability of a Turing machine always halting in at most ten steps
@Fischer: You are completely right about my misinterpretation of Rice's Theorem. However, I still do not see how you want to deal with all inputs: cannot be the case that a particular Turing machine halts in 10 steps for all inputs of length smaller or equal than 10, while it does not halt in 10 steps for an input of larger length?
Apr
8
comment Decidability of a Turing machine always halting in at most ten steps
It seems to me that you are suggesting that the problem is decidable. However , I am afraid that this problem is not decidable (the trouble of your naive approach is "on every input"). The undecidability is a trivial consequence of Rice's Theorem en.wikipedia.org/wiki/Rice%27s_theorem (since the property "halts in at most ten steps on every input" is a non trivial one).
Apr
2
revised Best Fake Proofs? (A M.SE April Fools Day collection)
added 45 characters in body
Apr
2
answered Best Fake Proofs? (A M.SE April Fools Day collection)
Mar
26
comment Why is quantified propositional logic not part of first-order logic?
@Thomas: The two-element Boolean algebra means the set $\{0, 1\}$ endowed with the Boolean operations (negation, conjunction and disjunction are enough) and two constants 0,1 (one for each element). Notice that in this structure (indeed an algebra) the sentences $0 \neq 1$ and $\forall x ( x =0 \lor x=1)$ that you have just remarked are obviously true. My claim is simply the fact that the set $QBF$ (i.e., the true quantified Boolean formulas) coincides exactly with the first-order theory of the previous structure.
Mar
25
comment Why is quantified propositional logic not part of first-order logic?
I would rather say you can avoid the extra predicate by considering the adequate signature for Boolean algebras (for sure you have functional symbols for join, meet, negation, etc.). From the set perspective the $\lor$ is an extra functional symbol, but from the perspective of a Boolean algebra this function (the join) is already given.
Mar
25
comment Why is quantified propositional logic not part of first-order logic?
@Mummert: I believe it is more convenient to think the truth value of $(\exists Q)(\forall R)[R \lor Q]$ as the truth value the first-order sentence $(\exists q)(\forall r)[ (r \lor q) = 1]$ in the two-elements Boolean algebra. It is not necessary to consider any extra predicate.
Mar
25
comment Why is quantified propositional logic not part of first-order logic?
Sorry for the misprint "first-sentences". In my last comment I meant "first-order sentences".
Mar
25
comment Why is quantified propositional logic not part of first-order logic?
In my opinion the best way to understand quantified propositional logic is to realize that this is exactly the true first-sentences (sometimes it is only the prenex ones) in a particular first-order structure, which is the two-elements Boolean algebra.
Mar
14
comment Definition of Spectrum in Logic
Some time ago I read a short note written by Burris about this spectrum (and available at math.uwaterloo.ca/~snburris/htdocs/WWW/PDF/spectra.pdf ). This remark is only to tell you that I found these three pages very helpful to understand the notion, and perhaps you can take a look.
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"?