{"entities":{"Q964457":{"pageid":966305,"ns":120,"title":"Item:Q964457","lastrevid":65682909,"modified":"2026-04-12T04:18:28Z","type":"item","id":"Q964457","labels":{"en":{"language":"en","value":"Definability of second order generalized quantifiers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5693393"}},"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":"Q964457$B303F2D4-34A9-4D91-BCDE-C679C63B89AF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c92ec6acc1159d67c48a76c39da6c6ce454454d","datavalue":{"value":{"text":"Definability of second order generalized quantifiers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q964457$D235FAFD-A0CE-43D6-A847-FF82D000F255","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72d17afb47a5d7d5591c76dd991a6f109538e6df","datavalue":{"value":"1206.03040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$58FE7D2D-F8B5-47CC-9DF2-0EFF426C9AF0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d6c92a6d1e244ef6727f00b02d0236f9547dd35","datavalue":{"value":{"entity-type":"item","numeric-id":269505,"id":"Q269505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964457$4EA17AAE-AD8C-47A8-BC42-672F6C55E2AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a0a7cd28a9f85b9c6ad57bd5bb1ae477bfe37846","datavalue":{"value":{"entity-type":"item","numeric-id":114337,"id":"Q114337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964457$2A135F12-04AA-478D-996D-4ACFCF8E4C54","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35759f2c57e380463f3872b667008da8bd531cd4","datavalue":{"value":{"time":"+2010-04-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q964457$33E0F10E-3143-4D0C-83DA-6862870659A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"37f4d18f3cae5085bc7ab72566ec12790e7f8c1b","datavalue":{"value":"http://hdl.handle.net/10138/21232","type":"string"},"datatype":"url"},"type":"statement","id":"Q964457$BFCE55F9-8E5E-4610-BDCF-A8A28FCE0820","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c39d354e61f72515dd8be10b72c587abff5716fa","datavalue":{"value":"The article introduces a notion of when a second-order generalized quantifier \\(Q\\) is definable in a logic \\(L\\). The structures considered are always finite and the logics are always extensions of first-order logic, \\text{FO}, by generalized (first or second-order) quantifiers. First it is shown that if \\(Q\\) is definable in \\(\\text{FO}(B)\\), where \\(B\\) is a collection of Lindstr\u00f6m quantifiers, then \\(\\text{FO}(Q,B)\\equiv\\text{FO}(B)\\), i.e. the logics \\(\\text{FO}(Q,B)\\) and \\(\\text{FO}(B)\\) have the same expressive power on finite structures.  Then the paper focuses mostly on second-order generalized quantifiers of `type ((1))'; such a quantifier \\(Q\\) corresponds to a class of finite second-order structures of the form \\((M,G)\\) where \\(G\\) is a subset of \\(P(M)\\), the powerset of \\(M\\), which is closed under isomorphism. The author proves that if \\(B\\) is the collection of all Lindstr\u00f6m quantifiers and \\(Q\\) a second-order generalized quantifier of type ((1)), then \\(Q\\) is definable in \\(\\text{FO}(B)\\) \\textit{by a flat formula} if and only if, for some positive integer \\(n\\), membership of \\((M,G)\\) in \\(Q\\) depends only on whether \\((M,G(n))\\) belongs to \\(Q\\), where \\(G(n)\\) is the set of all \\(X\\) in \\(G\\) such that \\(|X| < n\\) or \\(|M - X| < n\\). Roughly speaking, a formula in \\(\\text{FO}(B)\\) is \\textit{flat} if no nesting occurs of an auxiliary first-order quantifier symbol which plays a role in the definition of \\(Q\\) being definable in \\(\\text{FO}(B)\\).  The author proves that if \\(B\\) is the collection of all Lindstr\u00f6m quantifiers, then there are several generalized second-order quantifiers which are not definable in \\(\\text{FO}(B)\\); examples include \\(n\\)-ary second-order existential quantification, for every \\(n\\). Furthermore, for every countable collection \\(B\\) of Lindstr\u00f6m quantifiers, there is a second-order generalized quantifier \\(Q\\) of type ((1)) such that \\(\\text{FO}(Q,B)\\equiv\\text{FO}(B)\\) and \\(Q\\) is not definable in \\(\\text{FO}(B)\\). Hence, the converse of the first result mentioned above does not hold. Finally, it is proved that if \\(B\\) is the collection of all Lindstr\u00f6m quantifiers, then there is a generalized second order quantifier \\(Q\\) of type ((1)) such that \\(\\text{FO}(Q)\\equiv \\text{FO}\\) and \\(Q\\) is not definable in \\(\\text{FO}(B)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q964457$04D0C2E6-756D-41B3-B3A3-6E09B2D87D3A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"63d582552c02fffafb280152e2d5e020473417a2","datavalue":{"value":{"entity-type":"item","numeric-id":494646,"id":"Q494646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964457$74EAD0F5-B8F7-4A18-9602-9275A0F4ED65","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25e5a5f23d3e2e2c05864da16eda493011c33276","datavalue":{"value":"03C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$5D20541B-156D-464F-851B-227439456718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$2736FC52-8D23-43D9-A89D-40FA442F86FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd1ebd9dd665e7350d17a40eafa30f7b99b8c1e0","datavalue":{"value":"03C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$3E8E00EF-F9C5-47AF-8A0A-F5076A6A9A10","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2fc49f842a858819fca15b5d10fc6c644df67387","datavalue":{"value":"5693393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$FFFEAAAE-92BA-4597-B044-0DC9C5A15615","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b3238d708fa27afe6aaff9336301f4526f8f6a3","datavalue":{"value":"second-order generalized quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q964457$C9B4CD9F-B896-4201-857D-2D2025515F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc61a025d23805ef0c762c087d3f9ea45989791f","datavalue":{"value":"Lindstr\u00f6m quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q964457$C2139106-1581-4565-BAB8-43FC4F0E6369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ac3f30d773ef1894fb2eb52711e135b17d0158","datavalue":{"value":"definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q964457$17A369AD-AF73-4C1D-A8FB-992AF163F6B2","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":"Q964457$FB0385F0-BA0D-441C-9B7E-110C7BD58055","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"494e278320a7e7b76b8c08874b8022b96eeadf66","datavalue":{"value":"W2169453869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$AF5B0681-264C-48AC-817C-4EBBE96CFDAB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff070a8a6dcb7930b036bbd984618da88e27b705","datavalue":{"value":{"entity-type":"item","numeric-id":1612478,"id":"Q1612478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964457$33DF2EBF-990F-4F74-9486-12079E37AFC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ba3e1652a6eaa58e29b32f36c0eef3d0ef93603","datavalue":{"value":{"entity-type":"item","numeric-id":5687317,"id":"Q5687317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964457$1E383522-611A-435C-90F5-7196E585AF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d03344fb3809ac2d00cb9b60c5a358c8728ef000","datavalue":{"value":{"entity-type":"item","numeric-id":3113046,"id":"Q3113046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964457$1414FFF5-549B-48E7-B5C9-707F55D73077","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"684c08822c4317cf83e31143acd5b7f7d5cc41df","datavalue":{"value":"10.1007/S00153-010-0177-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964457$4C69649B-2C95-46A0-8380-85B8718A13B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adfc73262ff06e28f762db6f5c2e565dc867c5c5","datavalue":{"value":{"entity-type":"item","numeric-id":5477629,"id":"Q5477629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e9676c545b2893b197a71eb83c6c32606a6a82a","datavalue":{"value":{"amount":"+0.854561448097229","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":"Q964457$B33ED8C0-2B3F-4DDF-BCA9-4A84C89EA7CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"726bea4e76da4cfbeeaa75a8d918ec17e8168a8e","datavalue":{"value":{"entity-type":"item","numeric-id":3003360,"id":"Q3003360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0503ac923d935b360c48aff4767c597fd78129d6","datavalue":{"value":{"amount":"+0.8511865735054016","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":"Q964457$7A6AA15F-B585-4FD4-A23E-0679EE78F522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e5f4a80d80bf96df74fc5bfbb09adddbbc03b37","datavalue":{"value":{"entity-type":"item","numeric-id":2453584,"id":"Q2453584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"171e07de39dfcc7c2e3d50d11efc4d0c3c8090a9","datavalue":{"value":{"amount":"+0.8378596305847168","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":"Q964457$A56AE45E-842A-4B01-B0C5-5F145CE0A84C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14d0f66dd459ee91871a105336c2ef77830b0a9","datavalue":{"value":{"entity-type":"item","numeric-id":1612478,"id":"Q1612478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce65aa5a653c03efd689d6804eb22659b66acc39","datavalue":{"value":{"amount":"+0.8207409381866455","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":"Q964457$7FC56B4D-1436-496E-819E-5BAD44BF39CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf77d23485cbe5175a288164559c1e2e583f992","datavalue":{"value":{"entity-type":"item","numeric-id":4355676,"id":"Q4355676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"493d2a86a63ea4d1cea31f2d06f5668a9bd90c51","datavalue":{"value":{"amount":"+0.8012117147445679","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":"Q964457$F102DBB6-74E9-4C3B-801C-05D740107C35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Definability of second order generalized quantifiers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Definability_of_second_order_generalized_quantifiers"}}}}}