tag:blogger.com,1999:blog-3722233.post3307527963474745327..comments2019-10-18T11:05:28.649-04:00Comments on Computational Complexity: Give a second order statement true in (R,+) but false in (Q,+) or show there isn't oneLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-72523986319034548342016-10-03T17:15:17.866-04:002016-10-03T17:15:17.866-04:00Even easier: Any two non-trivial additive groups i...Even easier: Any two non-trivial additive groups in Q have a non-trivial intersection. Not true in R.CHelfgotthttps://www.blogger.com/profile/06692804010993576741noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13029534115773546562016-10-02T19:17:36.973-04:002016-10-02T19:17:36.973-04:00For second-order you can express the distance usin...For second-order you can express the distance using addition and then express the sentence that a Cauchy sequence has a limit.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77439556742690991372016-10-02T19:15:28.243-04:002016-10-02T19:15:28.243-04:00The first-order theory of addition over rational n...The first-order theory of addition over rational numbers is complete so the answer is negative.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12914990522787355132016-10-02T12:29:27.191-04:002016-10-02T12:29:27.191-04:00In the rationals there is a bounded set which does...In the rationals there is a bounded set which doesn't have a least upper bound. This should be expressible in second-order logic.Yuval Filmushttps://www.blogger.com/profile/08450062297306341505noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71682700131885589792016-10-02T04:37:53.671-04:002016-10-02T04:37:53.671-04:00... in the above "1" is not a member of ...... in the above "1" is not a member of the signature, but we can replace it with any non-zero element: <br />forall P . (exists d . ((!d=0) and P(0) and (P(x)->P(x+d)))) => ...<br /><br />Another alternative simpler approach could be to use irrationals: i.e. define x^2 and use:<br /><br />forall x,y . exists z . z^2 = x^2 + y^2<br /><br /><br /><br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75400452787804407792016-10-01T18:00:06.823-04:002016-10-01T18:00:06.823-04:00Quickly: the domain is uncountable
** Countabilit...Quickly: the domain is uncountable<br /><br />** Countability can be defined in SO with the + funciton in this way:<br /><br />forall P . (P(0) and (P(x)->P(x+1))) // grab at least one infinite countable set ...<br /><br />=> exists F . // ... which is a bijection ...<br />(forall x,y,z . F(x,y) and F(x,z) => y=z) and<br />(forall x,y,z . F(x,y) and F(z,y) => x=z) and<br /><br />// ... from the domain to the countable set ...<br />(forall x exists y . F(x,y)) and<br />(forall x,y . F(x,y) -> P(y))<br /><br />The negation of the above is in the SO of (R,+) but not in the SO of (Q,+)<br />Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47995544966936648102016-10-01T09:02:39.527-04:002016-10-01T09:02:39.527-04:00There is a purely logical second order sentence P ...There is a purely logical second order sentence P such that M |= P iff M is uncountable. The second-order theory of (R, +) contains P, but that of (Q, +) does not.Aatu Koskensiltahttps://www.blogger.com/profile/10999226899475411504noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65135346237080695162016-09-30T18:13:03.862-04:002016-09-30T18:13:03.862-04:00Ah, I'm not allowed that kind of quantificatio...Ah, I'm not allowed that kind of quantification. Hmm...Ashley Yakeleyhttps://www.blogger.com/profile/00449875179637133204noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41690556919061689822016-09-30T16:48:39.839-04:002016-09-30T16:48:39.839-04:00I think this works?
forall P Q, (forall a b, P(a)...I think this works?<br /><br />forall P Q, (forall a b, P(a) + P(b) = P(a + b) AND forall a b, Q(a) + Q(b) = Q(a + b) AND P(1) = Q(1)) IMPLIES forall a, P(a) = Q(a)Ashley Yakeleyhttps://www.blogger.com/profile/00449875179637133204noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83262581352094551862016-09-30T15:24:05.479-04:002016-09-30T15:24:05.479-04:00I thought forall and exists written out were clear...I thought forall and exists written out were clear enough but better to use the real notation, so I have changed it. Thanks for motivating me to do so.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61774779008584487772016-09-30T11:53:04.326-04:002016-09-30T11:53:04.326-04:001) No (in particular, this follows from the Löwenh...1) No (in particular, this follows from the Löwenheim–Skolem theorem).<br /><br />2) Yes. Here is the sentence: For every x and y, there is z such that every subgroup (S, +) that contains z also contains x and y. This sentence can be written in the second-order language.Yurynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72839941122483669712016-09-29T21:27:45.765-04:002016-09-29T21:27:45.765-04:00I think I have such a sentence. Rather than writin...I think I have such a sentence. Rather than writing it out in LATeX I'm describing it in words. (Interesting how hard it was to come up with this - I study model theory but I so rarely think about second order quantification that it almost feels like magic.) <br /><br />My sentence: you can write in the second order language, "there exists a binary relation P so that P satisfies all the finitely many first order axioms of a group-compatible linear order (think P(x,y) iff x, so they would behave as expected. Then the second sentence is true in R but not in Q. <br /><br />So essentially we create < out of thin air and rely on the fact that there are no unexpected linear orderings possible on the divisible groups to show that in R, but not in Q, every bounded set has a least upper bound. Shawhttps://www.blogger.com/profile/01154442090080258299noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1009184680947963362016-09-29T20:30:02.787-04:002016-09-29T20:30:02.787-04:00Bill, do you have a problem with using ∀ and ∃?!Bill, do you have a problem with using ∀ and ∃?!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53424420593712729732016-09-29T16:39:59.553-04:002016-09-29T16:39:59.553-04:00All typos fixed (I hope).
Thanks for corrections.All typos fixed (I hope).<br />Thanks for corrections.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50540331482427326062016-09-29T14:43:34.742-04:002016-09-29T14:43:34.742-04:00The {1,2,3,...} refers to his second example, the ...The {1,2,3,...} refers to his second example, the nonabelian group thing was just a place where the first example sentence (which I believe has an extra "+y" in it) fails. Shawhttps://www.blogger.com/profile/01154442090080258299noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52853585805233391402016-09-29T14:43:26.395-04:002016-09-29T14:43:26.395-04:00You have an extra y+ in the first sentenceYou have an extra y+ in the first sentenceAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70981101637003532712016-09-29T14:17:45.973-04:002016-09-29T14:17:45.973-04:00typo?
(forall x)(forall y)[ x+y=y+x+y]
shouldnt it...typo?<br />(forall x)(forall y)[ x+y=y+x+y]<br />shouldnt it be:<br />(forall x)(forall y)[ x+y=y+x]<br /><br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24477580903357364992016-09-29T14:16:35.960-04:002016-09-29T14:16:35.960-04:00How is {1,2,3,...} a nonabelian group?How is {1,2,3,...} a nonabelian group?domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com