{"entities":{"Q2563982":{"pageid":2574725,"ns":120,"title":"Item:Q2563982","lastrevid":73797366,"modified":"2026-04-14T17:17:28Z","type":"item","id":"Q2563982","labels":{"en":{"language":"en","value":"Arity hierarchies"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 961100"}},"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":"Q2563982$1DB1632D-C9CA-427B-99A6-5E921E53209E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d262feddcec6db7e4bd553a8bae4d9c060a0219","datavalue":{"value":{"text":"Arity hierarchies","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2563982$BC9E43AC-F518-4C4C-BE34-7A0588D05911","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a75cf4e467bea1b399ac032c9df56a11605f9aa","datavalue":{"value":"0860.03033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$56193557-3D8D-4F82-8994-FC733DF478A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f613bc8d7dfe4c0553ce78dd312213f335ae7b8d","datavalue":{"value":"10.1016/0168-0072(95)00072-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$0C311401-4A31-48E7-909A-CAFE43F7888D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e472eff586da807ef811f77707a93e380b6a974","datavalue":{"value":{"entity-type":"item","numeric-id":414932,"id":"Q414932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$D64F98E9-4CE5-44AB-B248-A93BF9387FCC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$AB2ACCF6-B016-40A1-846E-DD578F8065DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5bc48ff7272712d3abc20a4d87040a18a4c3fff9","datavalue":{"value":{"time":"+1997-04-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2563982$F4E4549F-8CA1-4807-B27A-8BC17E4E028A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5a314f1581199014d436ea9d209c18bae5e3bf7b","datavalue":{"value":"For many extensions \\(L\\) of first-order logic considered for finite structures there is a natural notion of arity of a formula (e.g., the maximal arity of a bounded second-order variable in a formula of fixed-point logic). Denote by \\(L^k\\) the fragment of \\(L\\) consisting of the sentences of \\(L\\) of arity \\(\\leq k\\). The main lemma shows that there is a quantifier-free formula \\(\\varphi (x_1, \\dots, x_k,y_1, \\dots, y_k)\\) in the language of graphs such that the transitive closure of \\(\\varphi\\) is not expressible in \\(s\\text{-PFP}^{k-1}\\), where \\(s\\text{-PFP}\\) denotes simultaneous partial fixed-point logic. This result implies that the arity hierarchy (even on the class of graphs) is strict for all ``natural'' logics between transitive closure logic and \\(s\\text{-PFP}\\) and it can be used to obtain the strictness of the corresponding hierarchies of pure DATALOG and several of its extensions and of the class of implicitly definable queries. The proof of the main lemma is based on an ingenious construction of structures ``homogeneous in the \\((k-1)\\)-tuples''. An iteration of this construction is needed to show the hierarchy result for deterministic transitive closure logic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$2E4A613A-D06A-4A29-94AE-9300A18EF2FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25e5a5f23d3e2e2c05864da16eda493011c33276","datavalue":{"value":"03C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$D94A7922-59F4-4A06-93AA-7315F81B63D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$45F2A73A-8955-43E7-BBB4-B6B6D00A744D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa69c13f73ae57309db5e91fd7e4d5aaf111f98e","datavalue":{"value":"03C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$AECF5ACF-3F0B-47C0-87F4-26412CA0CCD9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7342e1cf4bec8577cc48287b2d6155556dc4bba9","datavalue":{"value":"961100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$0A3BD6E3-DF45-4D5B-8342-F08F8B0589C2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac77b73a419028a99e62a78661cb450ff531af3a","datavalue":{"value":"extensions of first-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$DD8FFB0E-C4C6-4E97-8826-BA20D0B405FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75ecc202525c2ae53874acb5b42301faf8be2064","datavalue":{"value":"strictness of hierarchies","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$2542782E-5C01-49B2-A716-95328C409E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa1f9cffd18fe4bc8fecd35eb209e3dd8c324b86","datavalue":{"value":"finite structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$DCAC282C-9620-4D6F-A996-0A06AF7CC779","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b25be8231427d2a5059b9cb905f81b381aeac6ba","datavalue":{"value":"simultaneous partial fixed-point logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$E8B7B5F3-1234-431F-9910-D0489593507C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"095c937150e9b4665c74fc657c1eb9fc75f702c9","datavalue":{"value":"arity hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$D884FD4B-C813-43C0-B7B0-D44BE9DCC901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55118d9d1bbc13007a4b8d4da1af3e6fb042ce73","datavalue":{"value":"transitive closure logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$A1A1C4D6-309A-4C05-8829-0CBDC785E11F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a7e552a8313c994f36cc69f034a5002ca83626a","datavalue":{"value":"DATALOG","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563982$561E8EF2-7387-4094-943F-9AB7947AF7BA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73a1643e41698b2031364550f847827b09b1ce33","datavalue":{"value":{"entity-type":"item","numeric-id":490658,"id":"Q490658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$E252BD14-9AF3-4DF2-91C7-6BB93BBF3859","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":"Q2563982$27EA5908-3811-43D8-B443-B41A9C2614AF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4f766e7a5758aa054794901aed1f896f79cf9be9","datavalue":{"value":"https://doi.org/10.1016/0168-0072(95)00072-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q2563982$A8BFEF10-7F97-4701-8382-75A241C65FAD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3aaa0417e0254ebee7c9cba3ce862ff669009973","datavalue":{"value":"W4213231691","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563982$067B910C-1A38-4610-9B4F-4764895ED6F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b061c74acfe7ed299eeb2c95c750dc4bed6741a4","datavalue":{"value":{"entity-type":"item","numeric-id":1176285,"id":"Q1176285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$7F66EFE3-F28C-470F-8F9D-26273903B6A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$B513F881-B38C-4EB2-AF4C-1C5F4340CAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$56A7B611-687A-431B-A049-E6BD055876BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95c4224fcf08a75cee96ba2e66707b2ecb8b0d04","datavalue":{"value":{"entity-type":"item","numeric-id":2757822,"id":"Q2757822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$FDC6AA52-060A-4329-8C7C-605B7F730F0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04199e03d1d3ec0d2b5fbfff526a164b91654871","datavalue":{"value":{"entity-type":"item","numeric-id":1838840,"id":"Q1838840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$2BC27A25-9D44-4F27-AF12-90D4CC3580FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e1e825f83b50e8e1130715dfc474cbbe8c43bb5","datavalue":{"value":{"entity-type":"item","numeric-id":3706528,"id":"Q3706528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$7B0EAFDE-42AC-46F5-8A2B-56531BFBA5EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d7e6768b22bc08e9e065fa04ec4a9f1dc4b3ccf","datavalue":{"value":{"entity-type":"item","numeric-id":1271559,"id":"Q1271559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$35642EB5-7F12-4515-82B1-4AD023C57F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c32b298b09103f7cc9eabedf752dc67f406d3","datavalue":{"value":{"entity-type":"item","numeric-id":4850061,"id":"Q4850061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$58E0C1BC-F269-4A65-B899-EC538C807937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb1630ee5af00db53c3291f37c8e390b1646e4fc","datavalue":{"value":{"entity-type":"item","numeric-id":4298571,"id":"Q4298571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$B5C17B75-097F-4D99-AA24-99285EDC3A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$9CF3CD4F-3FBA-4147-9763-4EA05AC9058B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98625ed8a97eb6d2931df92b273a7f7a72b6d12c","datavalue":{"value":{"entity-type":"item","numeric-id":4202939,"id":"Q4202939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$A8102681-EFC5-44CF-8136-1971BDE49667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2678e50ef7873cd9064904e8a56db590f072f08","datavalue":{"value":{"entity-type":"item","numeric-id":4525283,"id":"Q4525283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$DD2BA867-6601-49B9-AA07-8419D3BA057D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d1b0ad6d8ca8b89a968c790988f8cc0c64dfc12","datavalue":{"value":{"entity-type":"item","numeric-id":1913297,"id":"Q1913297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$7FAD3C12-1183-447E-8FD0-285C2EAD38C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ed5cf1250814a5e584c109ec7d15def62f14cf","datavalue":{"value":{"entity-type":"item","numeric-id":1090327,"id":"Q1090327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$28E3DB70-87AE-47D1-A146-A96335CB6072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38b2df16e0721643b5780540c289c533ac16c1ff","datavalue":{"value":{"entity-type":"item","numeric-id":1817218,"id":"Q1817218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$5C81FB6F-D8D9-4524-A1F0-B26694DB3E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb8967f24f91589a2ac118758e3da6ec1600e526","datavalue":{"value":{"entity-type":"item","numeric-id":1900185,"id":"Q1900185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$0293718D-573A-48F2-A14E-3224ED5B008D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a96d70159cc7d872387a06ef5ad78fc8f0ad9bd","datavalue":{"value":{"entity-type":"item","numeric-id":1204527,"id":"Q1204527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$61955A8C-981A-4ED6-B90A-06D14BAE6D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$947B210A-752F-409F-953C-A54799678327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b97aae996047866e201e0764a961d1290615bba0","datavalue":{"value":{"entity-type":"item","numeric-id":4385543,"id":"Q4385543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$4CF90B95-A129-4717-BF25-11EB4CFC10DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"580c5daf14013a177e0f096c54b598446f9ef52c","datavalue":{"value":{"entity-type":"item","numeric-id":4501155,"id":"Q4501155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563982$491878B8-F89D-4450-8B4C-5071DF419239","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29f7c2c478a63f7aa22879f201e8759a4b151103","datavalue":{"value":{"entity-type":"item","numeric-id":1913297,"id":"Q1913297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a391234f186b4b0798204184c2c7972360151b74","datavalue":{"value":{"amount":"+0.8830613493919373","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":"Q2563982$CF232402-FE37-4AD5-B634-F2041E38F3BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ca50459bc99e82a6914701c8792ff21fa2d190f","datavalue":{"value":{"entity-type":"item","numeric-id":4525283,"id":"Q4525283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"602ffafd14620451bc91323f7f49f2df84548b77","datavalue":{"value":{"amount":"+0.848259449005127","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":"Q2563982$B6573C03-1247-4938-89F7-E06A7F4E093E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a027f29b3a1e20aa7f2ad66f89128ad7aa90236d","datavalue":{"value":{"entity-type":"item","numeric-id":5898540,"id":"Q5898540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46d0a3ba2ff820d65b221631b53933703065f7dd","datavalue":{"value":{"amount":"+0.8151288628578186","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":"Q2563982$5F9A9295-C3AE-4864-8558-499029EB6B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00c25e03c60bae296ad08a8a04e944c772534ea7","datavalue":{"value":{"entity-type":"item","numeric-id":2385450,"id":"Q2385450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00622b754ddd4ee47508bc8373a6502d1ecf8e39","datavalue":{"value":{"amount":"+0.8139145374298096","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":"Q2563982$6D7E228E-BD23-4779-B1E4-B6945CED9EE8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Arity hierarchies","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Arity_hierarchies"}}}}}