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

May
21
comment What do linearly ordered abelian groups look like?
Mi mistake for not reading the details. I answered just using the information in the title ("linearly ordered abelian groups").
May
21
comment What do linearly ordered abelian groups look like?
With the term "copy" you mean a "subgroup" or a "isomorphic copy"? In the first case the answer is yes (by Hahn's embedding theorem) and in the second case the answer is no (a trivial counterexample is the rationals).
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.