{"entities":{"Q958489":{"pageid":960337,"ns":120,"title":"Item:Q958489","lastrevid":65665059,"modified":"2026-04-12T04:08:36Z","type":"item","id":"Q958489","labels":{"en":{"language":"en","value":"Computable categoricity and the Ershov hierarchy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5378329"}},"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":"Q958489$640CA5F1-21DD-42B9-B993-B8CC8079F7B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9cd3d52e5290de90f93c9139ea13eaa14abcba4b","datavalue":{"value":{"text":"Computable categoricity and the Ershov hierarchy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q958489$3DF6514A-D56B-4A68-95A7-709B755D2045","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6432131fabb13507920845fb878e152d9cf3811e","datavalue":{"value":"1165.03012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$994BBD68-30A7-4D43-804A-742EAF73004A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"908230505203eccb837b53bb6b9c33b396a9a16d","datavalue":{"value":{"entity-type":"item","numeric-id":188054,"id":"Q188054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$031CA8E3-5E3C-47D9-8F90-A8853E1A8DB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a56bc7b07f95b5885e3133c205b9456af5cfa030","datavalue":{"value":{"entity-type":"item","numeric-id":324251,"id":"Q324251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$817D4EF4-EB02-4A80-B2FD-77D48F40862D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4103685926a903a30f8c32ed60fa8061b1add04","datavalue":{"value":{"entity-type":"item","numeric-id":189918,"id":"Q189918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$797CA0E0-5EE9-4DE4-808B-E641DDC23407","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":"Q958489$341693F4-7B86-4ACB-8CCD-C8BD00F5CD74","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"85c956bb62834fd3366db6abe30b39dc8a24e17e","datavalue":{"value":{"time":"+2008-12-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q958489$3DD027EA-6C3D-44B0-B303-51E720395092","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e3a807a8d1bcf25144023578ff1495b5b7754095","datavalue":{"value":"A structure is \\(F_{\\alpha}\\)- (accordingly \\(G_{\\alpha}\\)-) categorical, if it has computable presentations and any two computable presentations are isomorphic via a function which belongs (accordingly, its graph belongs) to the \\(\\alpha\\)-th level of the Ershov hierarchy.  It is proved that for every ordinal notation \\(\\alpha\\) there is a graph which is \\(F_{\\alpha}\\)-categorical but not \\(G_{\\alpha}\\)-categorical. A graph \\(G\\) is constructed which is not \\(G_{\\alpha}\\)-categorical for any ordinal notation \\(\\alpha\\). It is also proved that there is a graph which is \\(G_2\\)-categorical but not \\(F_{\\alpha}\\)-categorical for any notation \\(\\alpha\\). Examples of \\(D_3\\)-categorical but not \\(G_2\\)-categorical graphs are given.  Considering linear orderings, the authors prove that a linear order \\((L,<)\\) is \\(F_{\\alpha}\\)-categorical for some \\(\\alpha\\) if and only if it is countable and has only finitely many successive pairs. (By definition, for \\(x,y\\in L\\), \\(\\langle x,y\\rangle\\) is a successive pair if \\(x<y\\) and there are no elements in \\(L\\) between \\(x\\) and \\(y\\).) It follows from this result and some other known facts that every \\(F_{\\alpha}\\)-categorical linear order is also computable-categorical. At last, an example of a linear order which is \\(\\Delta^0_2\\)-categorical but not \\(G_{\\alpha}\\)-categorical for any \\(\\alpha\\), is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q958489$A733836B-F4A2-41BA-90D4-53585502F9E4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7c0f9a5de2afd25d103c132e1617d4201a3c58e4","datavalue":{"value":{"entity-type":"item","numeric-id":591972,"id":"Q591972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$06504C71-2444-4481-8E76-0A105CC2D711","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$0CE8F08B-5B1B-49C2-B944-5F41ADA97BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d40823595f671f8f347825fd0adc1e31ebeb184f","datavalue":{"value":"03C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$0276A86A-0CA8-4ED5-BDEA-DA215CE0E280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$AB4D2E69-2266-49D5-A05B-FC7000DBD338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"758b4d196a1f97708f26591fee42c00739e26cc0","datavalue":{"value":"03D80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$026C184C-6120-4E01-BCF2-056B4A1F13D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"12fabc944d2d49d6b406e61ffb31d9d5d5e58c87","datavalue":{"value":"5378329","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$29CC3D9A-DE4C-4892-BA8B-66D0A26C0275","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bcac6e7742ed502d62642f0ae3ba05e0b03177a","datavalue":{"value":"Ershov hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q958489$BD19DC03-43DA-4AB0-BBA2-DBD916899FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a3b417213f1366c965da801b8e017a31000b8ab","datavalue":{"value":"categoricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q958489$5603E78E-9C7B-4B26-9DDC-9984D2ADFA8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q958489$C1F134F5-CAD7-41C0-9D5A-7774E413E67D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a95117eca4562916655982de035b721507a45dcd","datavalue":{"value":"linear orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q958489$7AD49554-6B08-4D87-BB66-2E374B8A421F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6384c9a3e443bfb7ba0f294a1c40a15678e59e33","datavalue":{"value":"recursive ordinal","type":"string"},"datatype":"string"},"type":"statement","id":"Q958489$DE2FFF0C-DCD3-46EB-86C8-037B0A79C290","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":"Q958489$0A244440-5D7F-4E67-B0A4-99B1C4B60A1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"95425e915b8d057589f01912eea5f21b2785a258","datavalue":{"value":"https://doi.org/10.1016/j.apal.2008.06.010","type":"string"},"datatype":"url"},"type":"statement","id":"Q958489$C2CBBAE3-757C-4AE9-BAF7-EE94E33ED753","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6c82b9f69a11d61797d06975430b29810941520c","datavalue":{"value":"W1976898576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$322AF261-64D1-4DC4-88D7-19EAC3A44AE2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a8c417e53bc2fb015830043606802d00e685525","datavalue":{"value":{"entity-type":"item","numeric-id":4943318,"id":"Q4943318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$CF737A3B-5FAF-4B12-B31F-19E4EB779877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5735a66cbd4e659d8879162430b8e938c5631b9b","datavalue":{"value":{"entity-type":"item","numeric-id":3630578,"id":"Q3630578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$40304C63-8FD9-4ABF-A064-50B005C59A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59bb3753d4078b0e252803e0d68417e93825dc53","datavalue":{"value":{"entity-type":"item","numeric-id":5619076,"id":"Q5619076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$BF582023-636B-4A7F-800F-3A4E29BE44BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f30fa5cb203dfa828e9c57936177288f1a5c5f64","datavalue":{"value":{"entity-type":"item","numeric-id":5619077,"id":"Q5619077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$19DA4CC2-8EA3-4BA3-8ED2-C04EF7E47324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9782e225de477bb610f3f41969be529a695d5964","datavalue":{"value":{"entity-type":"item","numeric-id":1317427,"id":"Q1317427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$A5C6DE79-0FBB-4E79-9929-DB1AE4CB7242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ad62835a55923ec861c71dbb6edfd53ffd42573","datavalue":{"value":{"entity-type":"item","numeric-id":5601468,"id":"Q5601468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$7692F39C-8161-4549-91E5-AEA862FB3749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e05d7132d40513b67e6d35d3751926616ce7ff3","datavalue":{"value":{"entity-type":"item","numeric-id":1156127,"id":"Q1156127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$758DF1CC-889A-4277-B636-6EFC926F635B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422fbd49375a71f2cc53112f23d932495b3647b6","datavalue":{"value":{"entity-type":"item","numeric-id":4513969,"id":"Q4513969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$AAADF3D9-5346-475F-A820-779DFD091516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c4a6cea1ab137e7df5384c5d2a4e11ba43dd0b","datavalue":{"value":{"entity-type":"item","numeric-id":4032650,"id":"Q4032650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$1EA05A65-92A4-483C-B41D-88CE41D8AFD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3c12e6ddea2bce7a12bf80c9c36f8b3f2f8139c","datavalue":{"value":{"entity-type":"item","numeric-id":1861536,"id":"Q1861536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$84054CF2-8F60-4A04-A13C-E75C3C29E047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e3e792b035a99c55a65db7b58af0b1512602e6","datavalue":{"value":{"entity-type":"item","numeric-id":2558217,"id":"Q2558217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$8F318BE6-D43B-410F-B4EB-F7FA7CD1A33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46e6ec8bf53a403cc5a32600f6b7dd2946260e87","datavalue":{"value":{"entity-type":"item","numeric-id":5588612,"id":"Q5588612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$82DF2F08-5225-452C-907A-955A878F2783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca8d31b9fc87b89ee3effdeb240daa3f1a04408e","datavalue":{"value":{"entity-type":"item","numeric-id":3955343,"id":"Q3955343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q958489$0EC196EA-9730-4E2F-B52D-12C3C2A7AADE","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":"Q958489$7382B353-0C5A-4D85-8A48-BDBE0B0D4F1A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f725884e8013e443b65d3549ee13648ea4036b85","datavalue":{"value":"10.1016/J.APAL.2008.06.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q958489$EC596E5E-9AF9-477D-BBD2-0B1F77D5F27B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7457dffbf46c04ad8c38271e4815b7e8f1623758","datavalue":{"value":{"entity-type":"item","numeric-id":887636,"id":"Q887636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32fd0f580a061cd3fcf4ca05fbb90c39c156b01a","datavalue":{"value":{"amount":"+0.8617419600486755","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":"Q958489$AEE1AA36-A5FE-4739-8BBE-9ABB704DF2E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dcbf56f370bd9bf7b4efdeba4318aba213ef30f","datavalue":{"value":{"entity-type":"item","numeric-id":3630578,"id":"Q3630578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"040bd858d2e20098670e3aca8c3bb2d867537f40","datavalue":{"value":{"amount":"+0.8061556816101074","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":"Q958489$81C7992F-80B8-4FAD-849D-55103DB6FA67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56b1efeb0264c931483480d3307c25d2a952358f","datavalue":{"value":{"entity-type":"item","numeric-id":1740457,"id":"Q1740457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b41347897aee433778465d61b6942d75c143d3c","datavalue":{"value":{"amount":"+0.8021392822265625","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":"Q958489$354A0C57-BFB0-4BA8-9FA7-75E663E8483B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6235334719a1b58e3d2f9a680d85440a04e9277","datavalue":{"value":{"entity-type":"item","numeric-id":471691,"id":"Q471691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81067c9b5212fda26aea57d5c78f83507e6adeef","datavalue":{"value":{"amount":"+0.7909183502197266","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":"Q958489$07E3F958-FE0F-4C77-999B-91E3ABAC4D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7452e81dd137438b6e484e6775a22a17c2f0df1","datavalue":{"value":{"entity-type":"item","numeric-id":1949167,"id":"Q1949167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd42d430319a57d2c2150365f341fb7d011dc10","datavalue":{"value":{"amount":"+0.7905163168907166","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":"Q958489$9FE9720A-9EFE-4E8A-9B67-C155C1CCFD27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computable categoricity and the Ershov hierarchy","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computable_categoricity_and_the_Ershov_hierarchy"}}}}}