tag:blogger.com,1999:blog-3722233.post9081742640314081958..comments2021-04-17T21:45:43.290-05:00Comments on Computational Complexity: A Second Order Statement true in (R,+) but not (Q,+)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-19065788279851710092016-10-09T01:07:41.327-05:002016-10-09T01:07:41.327-05:00To the last anonymous: the point is that when you ...To the last anonymous: the point is that when you blow up (Q, +) to have cardinality |R| it will still be a vector space over Q (because it will still be a torsion-free divisible abelian group) and so it is *isomorphic* to (R, +) and elementary equivalent to (Q, +) because it was chosen as such (using the Lowenheim-Skolem theorem). Of course, as vector spaces Q and R are not isomorphic, but nobody claimed they were.Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28347601898152861202016-10-06T08:03:29.940-05:002016-10-06T08:03:29.940-05:00In the argument using the Lowenheim-Skolem theorem...In the argument using the Lowenheim-Skolem theorem one probably needs more care to argue that the blown up structure (M,+) is indeed elementary equivalent to (R,+). As vector spaces over Q they are not elementary equivalent as (Q,+) is of dimension 1 and (R,+) of infinite dimension. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16109337522171246312016-10-06T05:14:01.498-05:002016-10-06T05:14:01.498-05:00A thought: Isn't it the case that a formula F(...A thought: Isn't it the case that a formula F(x_1,..,x_n) is true in (R,+) iff F(-x_1,..,-x_n) is true in (R,+)? And that holds for first and second order. But then there can be no F(x,y) which is true iff x is less than y (iff -x is greater than -y).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65765441209156945182016-10-05T05:04:11.776-05:002016-10-05T05:04:11.776-05:00... I mean it's more appropriate to use the te...... I mean it's more appropriate to use the term "monadic second order" (instead of "second order") in the note to define your problemMarzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4972489911820540942016-10-05T03:14:27.964-05:002016-10-05T03:14:27.964-05:00"...Some readers thought that second order me..."...Some readers thought that second order meant you could quantify over functions. My intent was just to be able to quantify over sets..." ---> I suspected it, but in this case there is the *widely* used "monadic second order logic" ( only quantification over unary relations :-)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63355531974610629612016-10-04T21:41:22.389-05:002016-10-04T21:41:22.389-05:00Regarding the Löwenheim–Skolem theorem solution: b...Regarding the Löwenheim–Skolem theorem solution: by the LS theorem, there exists a structure (M, +) of cardinality continuum that is elementary equivalent to (Q, +). Note that (M, +) and (R, +) are linear spaces. Since |M| = |R|, (M, +) and (R, +) are isomorphic as linear spaces over Q; thus, (M, +) and (R, +) are isomorphic structures. By transitivity, (Q, +) and (R, +) are elementary equivalent.Yurynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10917378023231970422016-10-04T14:28:49.433-05:002016-10-04T14:28:49.433-05:00stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83013714900087801222016-10-04T13:40:26.268-05:002016-10-04T13:40:26.268-05:00I think you can define < in second-order (R,+)....I think you can define < in second-order (R,+). Sort of. The idea is to consider the second order predicate Pos(X) = X is closed under + and 0 \not\in X and forall x \not= 0, exactly one of x and (-x) are in X. Note here that the maximality condition in the definition of Pos implies that it is closed under multiplication with positive rationals.<br /><br />Clearly this predicate is true of R^+, but it is also true of other subsets of R too. We can understand their structure. Let B be a basis for R over Q. The elements of B come with "natural" positive or negative assignments, but any predicate X satisfying Pos imposes its own assignment of positive or negative to the basis elements, and moreover, any assignment of positive or negative to the basis elements uniquely determines a set X that satisfies Pos(X).<br /><br />We can now convert any closed formula \phi in second-order (R,+,<) to an equivalent formula in (R,+) via<br /><br />forall (X : R -> Prop) (< : R -> R -> Prop), Pos(X) and (x < y iff exists z \in Pos, x+z = y), \phi.<br /><br />Rod Downey and I had a paper on recursive ordered groups that relied being able to play this sort of game with the order relation, although it wasn't at all framed in this language.<br /><br />Thoughts?<br />stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47351261794417274082016-10-04T11:34:10.065-05:002016-10-04T11:34:10.065-05:00Clever! I didn't think of using subgroups at a...Clever! I didn't think of using subgroups at all... Shawhttps://www.blogger.com/profile/01154442090080258299noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29678671656733650312016-10-04T11:15:45.339-05:002016-10-04T11:15:45.339-05:00The first order equivalence of (Q, +) and (R, +) f...The first order equivalence of (Q, +) and (R, +) follows from the Lowenheim-Skolem theorem for the following reason: (Q, +) and (R, +) are both torsion-free divisible abelian groups-- i.e. essentially vector spaces over Q. Thus when you use Lowenheim Skolem to blow (Q, +) up to a model of cardinality |R|, it will be a vector space over Q of the same dimension as (R, +).Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.com