{"entities":{"Q1306795":{"pageid":1317545,"ns":120,"title":"Item:Q1306795","lastrevid":43016118,"modified":"2025-07-16T22:12:58Z","type":"item","id":"Q1306795","labels":{"en":{"language":"en","value":"Undecidability results on two-variable logics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1348047"}},"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":"Q1306795$965D6117-B4B2-4349-AD1B-9CCF5AD4D801","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"053192a794bc05e9059dcee7c1f7345944c6b40c","datavalue":{"value":{"text":"Undecidability results on two-variable logics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306795$A4096D3C-1C42-4A84-8ECB-E92B0401F195","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"05c6a7e416103b76f93bf1feb4bf706239956a5f","datavalue":{"value":"0927.03015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306795$3A6D3C30-A140-4304-8AC0-22DDC8D8351C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d92e5b50a477cfe238ac688c9a8eb0ddc7ad041e","datavalue":{"value":{"entity-type":"item","numeric-id":204638,"id":"Q204638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306795$CA63D87D-18F2-4868-9D53-C4E84C262AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3d44d2e806c94564ac8ed3016d0ed20fdb29f21","datavalue":{"value":{"entity-type":"item","numeric-id":490671,"id":"Q490671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306795$C48DB599-FFCE-47BE-BA01-1CBAAFAD0F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2477c4438484cc2d4b93c5ee2a14c06fcc0c2090","datavalue":{"value":{"entity-type":"item","numeric-id":948885,"id":"Q948885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306795$F29702AE-E2E6-4658-96DD-CA3C8D5A44DD","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":"Q1306795$4DF8192B-9E5E-44DB-859A-645319644171","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c2c35fb8a8597468e70992cceb470233a004c261","datavalue":{"value":{"time":"+1999-12-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306795$AA8FBDB6-7894-4A27-9B47-22C194490E83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"60f8694131b51e25fe4bb9d53054ab1787afc549","datavalue":{"value":"It is a classical result of Mortimer that \\(L^2\\), first-order logic with two variables, is decidable for satisfiability. We show that going beyond \\(L^2\\) by adding any one of the following, leads to an undecidable logic:    -- very weak forms of recursion, viz. (i) transitive closure operations, (ii) (restricted) monadic fixed-point operations,    -- weak access to cardinalities, through the H\u00e4rtig (or equicardinality) quantifier,    -- a choice construct known as Hilbert's \\(\\varepsilon\\)-operator.    In fact all these extensions of \\(L^2\\) prove to be undecidable both for satisfiability, and for satisfiability in finite models. Moreover most of them are hard for \\(\\Sigma^1_1\\), the first level of the analytical hierarchy, and thus have a much higher degree of undecidability than first-order logic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$213091E9-BE48-4179-9633-F5D5340BFD93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306795$BDA8D723-E0A2-4655-A978-CCBCE39E5719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306795$134F2C80-DA8B-4457-89DC-B1B8852A0380","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c6f640d57d86fba37c9b5839ec4968b0e984c005","datavalue":{"value":"1348047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306795$7C580CD7-2C7E-4D0F-B7C8-497561D3DE3F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a813fd0e4aef1fda5e8e7d4b77b02104337d96e6","datavalue":{"value":"undecidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$2619849D-E28C-410E-AECD-41AFF665DCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4be3f8ed1ec8e4a2e0023208c2b14dff77212d1f","datavalue":{"value":"first-order logic with two variables","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$FA5B25F7-A7DD-4A44-853F-28FA8BE4D066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d26e9375da72fdb0acfc15b2ae59e8fa34ad08d0","datavalue":{"value":"transitive closure operations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$0435FCE2-748C-4677-AA4E-8A139313F77A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d80514078aeedc68cd959c6074bf5c6aada4b139","datavalue":{"value":"monadic fixed-point operations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$90E1D001-A7E6-4B2D-B719-9EA2E54F8354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c9736d95481894c2a6955c354571ec4d5830080","datavalue":{"value":"weak access to cardinalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$4501B898-7E31-4104-B368-EABE1E09EFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9453fd7957b23d4ca916ac7fb3df9746f9cb8ad4","datavalue":{"value":"Hilbert's \\(\\varepsilon\\)-operator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$56B65940-465C-4B91-B37B-8B659467312A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$3EF18070-0595-40FC-A28F-A15C5573A8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1079eb7de954d5da29808649edc4628f1387ad4f","datavalue":{"value":"satisfiability in finite models","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306795$E363472B-456F-465D-A8B4-9E2ECEDC5EF7","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":"Q1306795$7D0DE7D8-E1CA-450B-B213-2DAC8D6ABEFF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5e1906b8fcc57771ec1840486e7041f434ff4626","datavalue":{"value":"https://doi.org/10.1007/s001530050130","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306795$2DE52D1E-5BD8-4014-AFD0-78C32522CB26","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"03ff7d101d4cf2ee8673822a0ff5dfa4fd892a60","datavalue":{"value":"W2047674711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306795$1B65C347-2253-48F6-8DB2-8F50049962F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"292f1c77b996e9bc84fc3f246aa554015aa1bdce","datavalue":{"value":"10.1007/S001530050130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306795$944BE508-2439-4A4B-B25B-E39F6B41265C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36710d3800ebad5721e0327d7ef51429ed5e8cf2","datavalue":{"value":{"entity-type":"item","numeric-id":5048929,"id":"Q5048929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$C3981D0D-B457-4949-8403-42F11DC1A265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1baf0e8b09720f765e34340f8ed24c658f1f3acf","datavalue":{"value":{"entity-type":"item","numeric-id":3370616,"id":"Q3370616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f65042adf022249ad9dc3690edafea275c287b5f","datavalue":{"value":{"amount":"+0.9433437","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$2199A2A3-A7E7-41DF-AEA0-5B19C14B2E87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aeb158dd7973414d14e61278870445c0f264b0c2","datavalue":{"value":{"entity-type":"item","numeric-id":4276022,"id":"Q4276022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d4bbe051981ac1be66638b7fbfe893818d6c632","datavalue":{"value":{"amount":"+0.9362416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$C68BDF05-9F3F-482D-83AC-673D5C68C632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7802a997bd979f5011a61696dec95d90d90ca35b","datavalue":{"value":{"entity-type":"item","numeric-id":2323638,"id":"Q2323638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"581eaac68775b7dbf3c6b5384a6ea67afbcf0bca","datavalue":{"value":{"amount":"+0.9124931","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$FCFAF838-EFA9-46C9-BDBE-E371F6BDCB62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e7a8383d2a68bea8281859b24922936482b9271","datavalue":{"value":{"entity-type":"item","numeric-id":3189649,"id":"Q3189649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87c20a31812942ccb59cf9cfcfdf0c1a94cef26d","datavalue":{"value":{"amount":"+0.9020795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$DAE26675-4383-4C66-9739-FC6662DEF354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd9efd4c5931241b71cc2371d2e3ceb5535ee6e2","datavalue":{"value":{"entity-type":"item","numeric-id":805607,"id":"Q805607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa0eaa0c10fc9291da04e34686ccaa2cd62dd1e7","datavalue":{"value":{"amount":"+0.9017535","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$7C106352-54D3-4A5C-8012-CFF875F03325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6d453e167d37e1e20fa09e1290daa189c05b307","datavalue":{"value":{"entity-type":"item","numeric-id":1917079,"id":"Q1917079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04a8fb84e72d7837edcb8f2393b01f7098f3305b","datavalue":{"value":{"amount":"+0.8986056","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$9F3C413A-A4CF-44B7-AD18-8A1A37A72C89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59af214b3734d41e08c59726b61b63e3f55a4bb8","datavalue":{"value":{"entity-type":"item","numeric-id":4376056,"id":"Q4376056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8489d816ee4fe6714939aa110976a8e171d4b57","datavalue":{"value":{"amount":"+0.8943131","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$90E0AFCC-F037-45CD-A0F1-DA3374AC02A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc3e79a6175c639ed75d8b0aa9af52759c22e853","datavalue":{"value":{"entity-type":"item","numeric-id":757339,"id":"Q757339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d28872bee36259f358a5332c6a82c6a2da1038c8","datavalue":{"value":{"amount":"+0.89261776","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$001F1C8C-A442-422A-BCE1-1A2C372A1CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c659bec14680488a0600fc4c8e6bd55236476eb9","datavalue":{"value":{"entity-type":"item","numeric-id":5015208,"id":"Q5015208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a99686fb019b9069c4188adc53e07da7ff38188","datavalue":{"value":{"amount":"+0.8916368","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306795$16F6AFE6-89EB-4BB1-A790-82DE1525D0B9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1306795","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1306795"}}}}}