{"id":206,"date":"2015-04-23T12:21:16","date_gmt":"2015-04-23T10:21:16","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=206"},"modified":"2015-06-22T16:16:15","modified_gmt":"2015-06-22T14:16:15","slug":"from-first-order-definable-to-aperiodic","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/3-the-schutzenberger-theorem\/from-first-order-definable-to-aperiodic","title":{"rendered":"From first-order definable to aperiodic"},"content":{"rendered":"

In this page we prove the implication from 2 to 3 in the Sch\u00fctzenberger theorem. This implication says that if a language is definable in first-order logic, then its syntactic monoid is aperiodic. The key lemma is given below.<\/p>\n

Lemma 0.\u00a0<\/strong>If \"L \subseteq A^*\" is definable in first-order logic, then it is recognised by a morphism into a finite and aperiodic monoid.<\/p>\n

From the above lemma it follows that if \"L\" is definable in first-order logic, then its syntactic monoid is aperiodic. This is because, by Theorem 2 on syntactic monoids<\/a>, the syntactic monoid is a homomorphic image of a submonoid of any monoid recognising \"L\". Since taking submonoids and homomorphic images preserves aperiodicity, Lemma 0 implies that the syntactic monoid of \"L\" is aperiodic.<\/p>\n

\n

Types.\u00a0<\/strong>Define the\u00a0quantifier rank\u00a0<\/em>of a formula of first-order logic to be the nesting depth of quantifiers. Formulas of quantifier rank at most \"k\" are closed under Boolean combinations, while applying a quantifier causes the rank to increase. For a natural number \"k\", define the \"k\"-type of a word \"w \in A^*\" to be the set of sentences (i.e. formulas without free variables) of quantifier rank at most \"k\" that are true in \"w\". By convention, we assume that all words have the same \"0\"-type.<\/p>\n

Theorem.\u00a0<\/strong>For\u00a0every\u00a0alphabet \"A\" and natural number\u00a0\"k\", \u00a0the function that maps a word to its \"k\"-type is compositional.<\/p>\n

Proof hint.\u00a0<\/strong>\u00a0One way to prove this would be using\u00a0the Ehrenfeucht-Fraisse method, which can be found in Phokion Kolatis’ slides here<\/a>, beginning with page 16.\u00a0 <\/strong>\"\Box\"<\/p>\n

Corollary. \u00a0<\/strong>For every \"k\", there are finitely many different \"k\"-types, and\u00a0\"w^{2^k}\" and \"w^{2^k+1}\" have the same \"k\"-type for every word \"w\".<\/p>\n

Proof. \u00a0<\/strong>Define the \"k\"-profile<\/em> of a word \"w \in A^*\" to be\u00a0 the set\u00a0of triples \"(\tau,a,\sigma)\" such that there exists a decomposition \"w=vau\" where the \"(k-1)\"-types of \"v\" and \"u\" are \"\tau\" and \"\sigma\", respectively. From compositionality of \"k\"-types it follows that for every\u00a0\"k \ge 1\", the \"k\"-type is determined by the \"k\"-profile. The two statements in the corollary can then be proved by induction on \"k\". \"\Box\".<\/p>\n

We can now prove\u00a0Lemma 0. Suppose that \"L \subseteq A^*\" is definable in first-order logic, by a formula of quantifier rank \"k\". Let \"M\" be the set of \"k\"-types. By the Theorem on compositionality above, and by the lemma on compositional mappings here<\/a>, it follows that there is a monoid operation on \"M\" such that the \u00a0function which maps a word to its \"k\"-type is a monoid morphism. Furthermore, by the corollary above, the monoid \"M\" is finite and aperiodic.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

In this page we prove the implication from 2 to 3 in the Sch\u00fctzenberger theorem. This implication says that if a language is definable in first-order logic, then its syntactic monoid is aperiodic. The key lemma is given below. Lemma 0.\u00a0If is definable in first-order logic, then it is recognised by a morphism into a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":202,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-206","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/206"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=206"}],"version-history":[{"count":3,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/206\/revisions"}],"predecessor-version":[{"id":462,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/206\/revisions\/462"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/202"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=206"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}