{"entities":{"Q793716":{"pageid":795564,"ns":120,"title":"Item:Q793716","lastrevid":42696155,"modified":"2025-07-08T13:59:51Z","type":"item","id":"Q793716","labels":{"en":{"language":"en","value":"\\(\\Sigma^ n_ 0\\)-equivalence relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3857083"}},"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":"Q793716$980625E6-B55C-44C0-B5FF-5AC9B3F57E8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4c7b14d89a03c3eddb5714cf6a09fe017a2b39fe","datavalue":{"value":{"text":"\\(\\Sigma^ n_ 0\\)-equivalence relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793716$0ACD2908-601F-4CF4-BBD1-63C67BA0F926","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b123b9b1e60498761efda74e5fa715d498d42f6e","datavalue":{"value":"0539.03023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793716$C027DD0B-50FD-479D-BADB-7E398B98BDE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8214ce32398a4ca538d15460cd52cea1bd37c48a","datavalue":{"value":"10.1007/BF00403335","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793716$9788370F-EA3F-4CD1-83F7-C0E56F0C5AC3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cb78a179ab7f7671775d8afe3c2e6cdc5cf26c4","datavalue":{"value":{"entity-type":"item","numeric-id":242615,"id":"Q242615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$88B2DBAE-6299-4887-A4C3-A55F1340FFC0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e34236ca73b92c6ee0bc17431d03c3537a7f0792","datavalue":{"value":{"entity-type":"item","numeric-id":195358,"id":"Q195358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$10C2499C-3F46-4953-A9BA-5C0A1F406D8E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47f57cd36df9e30d446df3867dc3917e4ea74654","datavalue":{"value":{"time":"+1982-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q793716$17C18709-50DC-4B0B-A24A-D8BBFA6B50D4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"800b00da09054e0d188751542f12c725521151d9","datavalue":{"value":"This paper deals with the reducibility pre-order \\(\\leq_ m\\) ranging over equivalence relations on the set of natural numbers, where \\({\\mathcal R}\\leq_ m{\\mathcal S}\\) if there exists a recursive function f such that, for all x, y: x \\({\\mathcal R} y\\) if and only if f(x) \\({\\mathcal S} f(y)\\). For \\(n\\geq 1\\), \\(\\Sigma^ 0_ n\\)-precomplete equivalence relations are introduced (generalizing a notion due to Ershov). It is shown that every \\(\\Sigma^ 0_ n\\)-precomplete \\(\\Sigma^ 0_ n\\)-equivalence relation is complete with respect of \\(\\leq_ m\\) restricted to \\(\\Sigma^ 0_ n\\)-equivalence relations. Several additional features of \\(\\Sigma^ 0_ n\\)-precomplete equivalence relations are discussed. A representation theorem is also proved: Let T be an r.e. consistent theory which satisfies specific requirements (e.g. T is Peano arithmetic) and for \\(n\\geq 1\\) let \\(T^ n\\) denote the theory obtained by adding as axioms all \\(\\Pi_{n-1}\\) true sentences; then for every \\(\\Sigma^ 0_ n\\)-equivalence relation \\({\\mathcal R}\\) there is a \\(\\Sigma_ n\\) formula F of T such that for all x, y: x \\({\\mathcal R} y\\) iff \\(T^ n\\vdash F(\\bar x)\\leftrightarrow F(\\bar y).\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q793716$3BBBF4C0-1D1C-487C-8E70-FD5370D1F1B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793716$96D868EF-5A90-4C56-A4F3-5B2BD125E308","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10c86b4dd725fabb672b36b0f75fe48f8a19031b","datavalue":{"value":"3857083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793716$501AAD46-233A-4ED8-B4BB-50EF2BE46594","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29c0c712eee057c483b0cc3de24c72a3bd7d85db","datavalue":{"value":"reducibility pre-order","type":"string"},"datatype":"string"},"type":"statement","id":"Q793716$18C8C8DF-F1B2-4004-82B4-CAAF31072119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"203f490cb26d63ca4e4b11aa6cd491fce1d6cf12","datavalue":{"value":"precomplete equivalence relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q793716$95B108C3-DDD7-4D07-A48B-697C1D2C2692","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":"Q793716$9BC78DF6-3662-4816-8A13-5F33535916D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ea0c6a74e5ef0db48f2e3e6adb0974a2fd4f7a1","datavalue":{"value":{"entity-type":"item","numeric-id":1156125,"id":"Q1156125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$06F0FA46-4FFD-4015-B2B1-F39DC6F96F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a06a77350a0e89c679d1b1a4beb086f99b213ebf","datavalue":{"value":{"entity-type":"item","numeric-id":3309827,"id":"Q3309827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$44A33E3E-54C4-479F-9EE7-752C9C6647A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c59fa5a6862e05df7ee16ddb2d8bba3daa3988","datavalue":{"value":{"entity-type":"item","numeric-id":1393225,"id":"Q1393225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$C528EB79-AB55-4575-A517-5E79BD273155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"287785aa8651b26f912f2bcca2b2a743939d591e","datavalue":{"value":{"entity-type":"item","numeric-id":4146722,"id":"Q4146722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$6D5544FB-4807-4A40-BA64-38BD648DDB03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3e871ec06eee6b4c87c027fb64dde5aee6cd144","datavalue":{"value":{"entity-type":"item","numeric-id":5183473,"id":"Q5183473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$956F725B-EBDA-4731-B4CA-34ACB95E8BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$89F2DE7D-91AD-4EAE-81BA-6DA16D9812CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc4a07ec1205acfce88858f5d9b517525042cc83","datavalue":{"value":{"entity-type":"item","numeric-id":3967526,"id":"Q3967526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793716$CD4A8523-CB35-4183-8BBE-3E958AA445DD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc81f40c65a73218138cd31313abfde289290de0","datavalue":{"value":{"entity-type":"item","numeric-id":3576042,"id":"Q3576042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bfe285dab81a3dd44fdc1a2da95879531a2e023","datavalue":{"value":{"amount":"+0.9074146","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":"Q793716$7E9E91B1-9C8A-400B-8864-2C78E3280894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3876cd1fdfa012c186e5107a5193332d94799c69","datavalue":{"value":{"entity-type":"item","numeric-id":639658,"id":"Q639658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e41f4e6cf6a65c65d4d16062556a0e7ad89b36f","datavalue":{"value":{"amount":"+0.90456045","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":"Q793716$35476FCC-79E5-4A98-A8EF-1051C663CA5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b56a628f58b2f373163e90c763edc9c44e450dab","datavalue":{"value":{"entity-type":"item","numeric-id":3390678,"id":"Q3390678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"273c1e3028d0e1729726ce77f0e389a2f2014d24","datavalue":{"value":{"amount":"+0.8893081","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":"Q793716$97DEB3FC-98A9-4CBF-BC8B-5BA61815F9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa7045c55dbec74e93207d3e97d363ca9b186b42","datavalue":{"value":{"entity-type":"item","numeric-id":3117786,"id":"Q3117786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac55ce2bf5b7e864e259ce04fb24d6193208433d","datavalue":{"value":{"amount":"+0.88601303","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":"Q793716$8605A760-618D-4F41-AC7C-00F79250E3C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c693d79c0a9a409f7de3782b2c4018788da211f9","datavalue":{"value":{"entity-type":"item","numeric-id":1106203,"id":"Q1106203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0ba999c399507d2807febb5d22b70d9edf2685d","datavalue":{"value":{"amount":"+0.8787682","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":"Q793716$03191E2E-CB88-4AE5-A8D3-E69BFBD58854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dac78d1db25dabbb74f4f400c60a72c9e8873dfc","datavalue":{"value":{"entity-type":"item","numeric-id":2922491,"id":"Q2922491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a26336305f2b4d63ca693d1c41d5ae0a450e5267","datavalue":{"value":{"amount":"+0.87763447","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":"Q793716$0469F332-F6E8-4248-873B-227D12437022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c28a280f8576cb36527bde97d6a44cc3f02a15d1","datavalue":{"value":{"entity-type":"item","numeric-id":4683538,"id":"Q4683538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c5c968976d2361c00de84a0f332f02ac9acd506","datavalue":{"value":{"amount":"+0.8753798","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":"Q793716$88788925-DEE7-44C5-AB66-5FEA64D0C551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24d71dec92a52f1fc58a572a3051eae2d07e7bc1","datavalue":{"value":{"entity-type":"item","numeric-id":1047478,"id":"Q1047478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"739379ffc58768e625dd300b74e5aa206ba47d9b","datavalue":{"value":{"amount":"+0.869704","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":"Q793716$3EDA994E-D46C-4904-8497-016820DC0207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87ad3ec450186d9b4523a8e122e5f2b88af30b9d","datavalue":{"value":{"entity-type":"item","numeric-id":1198637,"id":"Q1198637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f0f1fa3677ab6af6d99caff33d7fd104d578536","datavalue":{"value":{"amount":"+0.8678129","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":"Q793716$BD399EF7-1C24-4217-AE23-6104A093DFFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ccc2d80be5930b12aec1b05a95f36c4d5abccdd","datavalue":{"value":{"entity-type":"item","numeric-id":2921014,"id":"Q2921014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17af717e6f4f68858bcaf747a80af886416061c2","datavalue":{"value":{"amount":"+0.8628258","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":"Q793716$0BCCB855-0A89-4540-854D-203DB5B9FD6D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:793716","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:793716"}}}}}