{"entities":{"Q1049747":{"pageid":1051595,"ns":120,"title":"Item:Q1049747","lastrevid":66037617,"modified":"2026-04-12T07:06:36Z","type":"item","id":"Q1049747","labels":{"en":{"language":"en","value":"Self-embeddings of computable trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5657679"}},"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":"Q1049747$6B158F8B-537D-41CF-BF93-9F605A3F06A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd0fbd9a54540d4228a9e68a9c92334d39bd5f98","datavalue":{"value":{"text":"Self-embeddings of computable trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1049747$C1178E8D-118A-4EAE-8292-661FA853D5FA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bab7cb4482c3469704baea8b89bb2f71a2b20980","datavalue":{"value":"1204.03044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1049747$BB8682C6-31D5-463B-94F7-9E7340983A9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e438a3ea270ba97a50d7fa5899ead3a579962391","datavalue":{"value":{"entity-type":"item","numeric-id":701735,"id":"Q701735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$2F6B70E8-A3AD-499A-BAE2-8E4168D468D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"713c2f755459cde585837394c4916f4792e504e4","datavalue":{"value":{"entity-type":"item","numeric-id":490406,"id":"Q490406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$99318424-3F4E-4568-B236-6232D58197E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d2bcabba238ebd3703bf94360bc556df90e8632","datavalue":{"value":{"entity-type":"item","numeric-id":1049746,"id":"Q1049746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$FD3E51E4-DE00-4BFD-979E-938823A52EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"80620c2b4df8756e658fe199f1a89d0f51d86188","datavalue":{"value":{"entity-type":"item","numeric-id":190265,"id":"Q190265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$2EAB8250-47C5-455E-B2DF-780363CCCDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"22619fa0bcfede8dabe102ce78dd2250f3353f67","datavalue":{"value":{"entity-type":"item","numeric-id":218974,"id":"Q218974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$57BFA1D6-F4E4-4534-84EA-C6E481AED319","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$1C93DFE8-366F-4558-8D3A-E7990DF2457E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"881d7755ed56ad45091e513ac6c64caeecaa15ad","datavalue":{"value":{"time":"+2010-01-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":"Q1049747$C94071F1-C637-4B43-A3B8-D0CFD2D4BC05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74c2a27e8e54a45ab7b9ce9124a847116f456c2f","datavalue":{"value":"https://arxiv.org/abs/1408.2286","type":"string"},"datatype":"url"},"type":"statement","id":"Q1049747$9D1C35DB-59D7-4FB9-A2E6-6D0107455953","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f7eef4ccaf267a7f3fc8c4fb912f47a2797b4537","datavalue":{"value":"The authors study the problem of how complex it is to find a non-trivial self-embedding of an infinite computable tree. They represent trees as partial orderings, and define self-embeddings to be non-trivial if they are not onto. The answer is that \\(0^{\\prime\\prime}\\) is sufficient and necessary to compute non-trivial self-embedding. They also consider some sub-classes of trees where \\(0^{\\prime}\\) is sufficient and necessary. When proving the necessity of these oracles, they ask the interesting question of whether one can build a single tree where every non-trivial self-embedding of any computable copy of the tree computes \\(0^{\\prime\\prime}\\) (or \\(0'\\) in the restricted class), rather than just every non-trivial self-embedding of a single presentation. They obtain partial results in this regard.  In the last section they prove that every infinite computable tree has either an infinite computable chain, or an infinite \\(\\Pi^0_1\\) antichain, and that these bounds are optimal. This contrasts with a previous result of Herrmann which says that every infinite computable partial ordering has either an infinite \\(\\Delta^0_2\\) chain, or an infinite \\(\\Pi^0_2\\) antichain.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1049747$CE6641F6-1E77-48F4-95A3-7F3A3559187B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0a67f77b8c1da6e34278d8eb54be6e5a28a3dcd4","datavalue":{"value":{"entity-type":"item","numeric-id":453199,"id":"Q453199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1049747$2CAC6B77-E6BA-4D6A-B2F5-6BDEF8EA535B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1267197712a0b8481bdd51a65bbac0428b08dd13","datavalue":{"value":"03D45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1049747$9A561073-9365-4BAC-BA12-00AB8EC3A0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1049747$39C0B47A-B869-4C1B-AF79-AB4C5235133C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"30e7302abcc969d540378eb7af13e124082e0a26","datavalue":{"value":"5657679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1049747$4EE51D82-F1EB-4F62-A68F-3A77772E4B7E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c618e2ea4d4d1f00b1e05e2a8219e4f127168312","datavalue":{"value":"self-embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1049747$A5284F3B-7175-4002-AF09-FE53D1A9FBE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f86213a2f26816131d92f2d88460dda345ad743","datavalue":{"value":"computable tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1049747$F91BD321-FEE1-4900-94D2-708D08C59456","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":"Q1049747$240B9B06-99A4-4910-B289-A8D3F2EB6FAD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"379865fab7cd88f515c71a6cf6efdaa16eacbb56","datavalue":{"value":{"entity-type":"item","numeric-id":2576940,"id":"Q2576940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"639b0eb4690ced60429384c1097daab12337de0b","datavalue":{"value":{"amount":"+0.8118877410888672","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":"Q1049747$7A09D29F-447D-427E-B04B-B0AEF33DD4B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88404c522150094adf2318e41b94806cf16ee111","datavalue":{"value":{"entity-type":"item","numeric-id":3655260,"id":"Q3655260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"989a9a7e76a0c077c8f57dcf7bec53f9daee5a2e","datavalue":{"value":{"amount":"+0.780543327331543","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":"Q1049747$82BC07DE-1D13-477A-9474-D53CBCAD2EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75f06f9bec540674bf89230a627a0a410669aef1","datavalue":{"value":{"entity-type":"item","numeric-id":3370758,"id":"Q3370758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b10d9ae0c37abfdb877eb1a03e92c39ca78261fc","datavalue":{"value":{"amount":"+0.7735345363616943","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":"Q1049747$BB8471D3-CD27-48DD-99FC-AFB1B9ADE2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"deea6e7cfae17caefa18e955bba00569ee6ccc65","datavalue":{"value":{"entity-type":"item","numeric-id":3033763,"id":"Q3033763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24495c3f0bd67f1771c97f8610b8a5f2490d1ef7","datavalue":{"value":{"amount":"+0.7645102143287659","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":"Q1049747$D0B8216C-7693-4502-948A-C8CDA243EE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57f44ce99e17e70eef09d582c2b22d96d46ad61e","datavalue":{"value":{"entity-type":"item","numeric-id":2329170,"id":"Q2329170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a86a3cc22caf985f04c66ed5a509dfeab35d8924","datavalue":{"value":{"amount":"+0.7504470944404602","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":"Q1049747$552D3256-67C4-4825-A4AC-C38499584356","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Self-embeddings of computable trees","badges":[]}}}}}