{"entities":{"Q1361404":{"pageid":1372143,"ns":120,"title":"Item:Q1361404","lastrevid":46507377,"modified":"2025-12-24T22:39:04Z","type":"item","id":"Q1361404","labels":{"en":{"language":"en","value":"Unary quantifiers on finite models"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1038919"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361404$A0A9677F-14C2-4CC2-BFD1-C4FF25362CC1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eccfb31ef606fe87312501595990845c42ba5085","datavalue":{"value":{"text":"Unary quantifiers on finite models","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1361404$531C100B-F0F0-4147-964F-EBB162FCFF18","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2f70f93f628a2854e770bb9ec202b9f23e1b82dc","datavalue":{"value":"0880.03014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$6BE2FAEE-9EBC-48EA-82B7-EE7F512BBDA5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8ad6136ca72ec9b5a4a905ac20986a68b9f8a5b6","datavalue":{"value":"10.1023/A:1008209019899","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$13F7D142-20FE-4E4C-B9AA-C6CF46AEA514","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54e91bc5e0f61733bb6f4b607f8868935e632c0d","datavalue":{"value":{"entity-type":"item","numeric-id":278764,"id":"Q278764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361404$67598DCD-CF2C-4288-92EE-978E7ED710C9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"147edfc9dddd5bbefb3ef0a24d334c7da90bbf45","datavalue":{"value":{"entity-type":"item","numeric-id":195246,"id":"Q195246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361404$DC0395DA-F141-4082-9AC4-B6A4FBFA24F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2a0b49252c47513608a2024e704aeac58803f16a","datavalue":{"value":{"time":"+1998-01-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1361404$769C8006-0D15-4FC4-820F-CEAF3700C762","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bfacf0224031621f40dd0620dc8dd22fb09a6c8b","datavalue":{"value":"A simple unary or monadic quantifier is a class of certain structures closed under isomorphisms. All models under consideration are assumed to be finite. A quantifier \\(Q\\) is said to be definable in terms of a set \\textbf{Q} of quantifiers if \\(Q\\) is the class of models of a sentence of the extension \\(FO({\\mathbf Q})\\) of a first-order logic \\(FO\\) by the set \\({\\mathbf Q}\\).   The family of all logics of the form \\(FO({\\mathbf Q}\\)), where \\({\\mathbf Q}\\) is a set of monotone quantifiers, plays an important role and will be denoted by \\textbf{Mon}. The concept of a boundedly oscillated quantifier is a weakening of the concept of monotonicity. Then the following results are proved.    A quantifier is definable in terms of monotone quantifiers if and only if it is boundedly oscillating.    Let \\({\\mathbf Q}\\) be a finite set of bounded monotone quantifiers. Let \\(Q'\\) be a monotone quantifier. Then \\(Q'\\) is definable in \\(FO({\\mathbf Q})\\) if and only if \\(Q'\\) is bounded and the canonical coloring \\(\\beta_{\\mathbf Q}\\) of \\({\\mathbf N}\\) eventually refines \\(\\beta_{Q'}\\).   Let \\(Q_f\\) be a monotone quantifier satisfying  \\[ \\lim_{n \\to\\infty} f(n)= \\lim_{n\\to \\infty} \\bigl(n-f(n) \\bigr)= \\infty \\]  and  \\[ \\lim_{n \\to\\infty} \\bigl(f(n)- \\lfloor n/2 \\rfloor \\bigr)= \\infty \\quad \\text{or} \\quad \\lim_{n\\to \\infty} \\bigl(\\lfloor n/2 \\rfloor- f(n)\\bigr) =\\infty. \\]  Then a monotone quantifier \\(Q_g\\) is definable in \\(FO(Q_f)\\) iff \\(Q_g\\) is first-order definable or there is a constant \\(a\\in{\\mathbf Z}\\) and a number \\(m\\in{\\mathbf N}\\) fulfilling  \\[ \\forall n\\geq m\\bigl(g(n) =f(n) +a\\bigr) \\quad \\text{or} \\quad \\forall n\\geq m\\bigl(g(n) =n-f(n) +a\\bigr). \\]  In the last section a generalization of the preceding results to non-monotone and non-simple unary quantifiers is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$642770C4-17AC-4082-8123-7F16056490C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$EDB1B016-5F88-4E2D-8827-0EF04D93582E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"25e5a5f23d3e2e2c05864da16eda493011c33276","datavalue":{"value":"03C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$248DA156-4DAF-4A86-945B-040E262DE502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c1d2d83da0d870574277144fdd1db9abaae162ec","datavalue":{"value":"03C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$3A01CB39-0920-41FA-90ED-3C8DE2C2AC0D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"61243f7ae1662da5b647e0eca7c48c612f8b50bd","datavalue":{"value":"1038919","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$A93276DE-140B-4FE1-AB79-CAD30C292C59","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ac3f30d773ef1894fb2eb52711e135b17d0158","datavalue":{"value":"definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$2DA1B2A7-BB90-4AD6-BCE5-597221426BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb06b3c61aaaeefbd9a6ae48efc57ee7c0a288a5","datavalue":{"value":"Ehrenfeucht-Fra\u00efss\u00e9 game","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$85FE5DAB-BF12-4CDD-9E0F-EF5EDC5F293A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83798e1bbc00101714db436c991cc16b2064467d","datavalue":{"value":"finite model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$5985891F-BE8F-40A4-9155-9F7F84E25E7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1e29c1e69df0b6d1827b21cf5575217093f886f","datavalue":{"value":"generalized quantifier","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$7F90383E-224B-4637-961A-C0E6EA487339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64070e2d6f78adfffb61be87e7188e07305b7d93","datavalue":{"value":"monotone quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$C3A402F1-2568-40D1-A366-DBB1F203A1F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef2c27d3d54f0d7fb1d01f9aff0be722dd88a12b","datavalue":{"value":"boundedly oscillated quantifier","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$BF88D164-85E0-406A-AF55-D10E527EC7C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6a1d66955ab96b777680cfa2052b04194a2b968","datavalue":{"value":"unary quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361404$BAD46F2C-5663-4D4E-A96B-04554B3A4359","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6537e4dbc27d6024722d6db5255b901cc30f77dd","datavalue":{"value":{"entity-type":"item","numeric-id":1177860,"id":"Q1177860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361404$BFB8A251-E71A-4BE0-BB24-569D673A8812","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361404$5F0B63EF-E3E8-4CD7-A191-287FF11B9220","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9a4d9b81f3b78fd3b577c67c4932d804cf22823d","datavalue":{"value":"https://doi.org/10.1023/a:1008209019899","type":"string"},"datatype":"url"},"type":"statement","id":"Q1361404$1B70AF0B-49B3-4C0B-9D1D-064AB0109DE5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5692573f62064f35dd5249da8df04722435ccdbc","datavalue":{"value":"W1489148631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361404$D5F9357B-4926-4CC5-9EBF-2D485CA32542","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22fcf63977c3246128e4453d5b9d5d523662ca0d","datavalue":{"value":{"entity-type":"item","numeric-id":3985088,"id":"Q3985088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4316e13eb5e4d36dcb027137126902bb4f8aed60","datavalue":{"value":{"amount":"+0.8135680556297302","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361404$D3C33162-51FD-4AB1-8429-3C338D7003A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f98632613f597f44c3e846d752075a093b119add","datavalue":{"value":{"entity-type":"item","numeric-id":1361405,"id":"Q1361405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d47a1d00d022844c9516d280d570eb769806d0a","datavalue":{"value":{"amount":"+0.8129343390464783","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361404$72B59DA8-9904-4196-945E-7F4C07DBD29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca05b2af316d222afdf5d051088f088d5101fb1b","datavalue":{"value":{"entity-type":"item","numeric-id":1857361,"id":"Q1857361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e2b8f9555a1e948443cb890c539846137277b6a","datavalue":{"value":{"amount":"+0.7928594350814819","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361404$72F31A8F-90F4-4913-A4E1-C6F58A1FA0CF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1361404","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1361404"}}}}}