boumol
Reputation
773
Top tag
Next privilege 1,000 Rep.
Create new tags
 Apr 29 comment Is there a sentence in the language of $\mathrm{PA}$ asserting that $\mathrm{PA}$ is sound? Can you tell us what is the sentence "Sou(PA)"? I can see how to write down a sentence which expresses "there is no (finite) proof ...", i.e., expresses "PA is consistent". On the other hand I do not see how to write down a sentence (in the Peano language) that expresses "there is a (infinite) first-order structure ...". This trouble would not appear if one wants to write a sentence in the ZFC language saying that "PA is sound", this can be clearly done. Apr 22 comment mathematical logic and valid ways of reasoning @Lays: Godel's theorem says what it says, so if you cannot follow wikipedia link I am afraid you need to improve your background. I suggest you take a deep look at plato.stanford.edu/entries/logic-classical to digest what completeness is. This entry is addressed to philosophers, so I suspect it will be easier to understand. Apr 22 comment mathematical logic and valid ways of reasoning @Lays: Have you read the section "Statement of the theorem" in the wikipedia link? Apr 22 comment mathematical logic and valid ways of reasoning Take a look at en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem I suspect this is what you are interested on. It is worth saying that the completeness theorem fails in second-order logic. Apr 16 comment What is the formal definition of a translation between theories? Take a look at Caicedo's answer in math.stackexchange.com/questions/315399/… Apr 14 comment First Order Logic: Formula for $y$ is the sum of non-negative powers of $2$ @Food4Thought: I think you are not getting the point of Carl's remark. When you say "$\exists n (2^n = x)$", how do you pretend to write this formula (and so with a fixed number of symbols) just using the vocabulary $+,\cdot,0,s$ ? Is this a formula? 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 )