{"entities":{"Q377460":{"pageid":379227,"ns":120,"title":"Item:Q377460","lastrevid":77847881,"modified":"2026-05-06T10:11:25Z","type":"item","id":"Q377460","labels":{"en":{"language":"en","value":"Traces, traceability, and lattices of traces under the set theoretic inclusion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6223047"}},"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":"Q377460$2B732C29-682D-4633-9617-5D13BCD5F5E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b0c5e252516cb94cc730f2283e3e11e58890fc0b","datavalue":{"value":{"text":"Traces, traceability, and lattices of traces under the set theoretic inclusion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q377460$30F1D06B-11AB-46C2-8A9C-63F52D8B49D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c03a0a3d7fd4e3bfbbc923da5bb5079d5acecae1","datavalue":{"value":"1287.03091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377460$E638E246-7B52-48E3-9D2C-4D2FC89FE63B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c41eb04e81dad9841fae38d29fd8f434ff3ef01","datavalue":{"value":{"entity-type":"item","numeric-id":377459,"id":"Q377459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377460$3ECF3182-1D6E-4698-8CD7-340B8C8C24AE","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":"Q377460$B57916D7-A817-40A7-AB09-C0E97F3D1A78","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"102ef688e1f1ee42ad21d8460f0995ebefcc5ee1","datavalue":{"value":{"time":"+2013-11-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q377460$08789A80-DA71-4FA7-B03D-F258D17441E4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d2c92005b754365c152b7b93a4f7bc40780e5ac5","datavalue":{"value":"The paper is concerned with traces; a trace is a computably enumerable set \\(V\\) of natural numbers such that every \\(V^{[m]}:=\\{n \\mid \\langle n,m\\rangle\\in V\\}\\) is finite, where \\(\\langle , \\rangle\\) is the pairing function -- i.e., an r.e. system of indexed finite sets. Thinking of functions \\(f:\\mathbb{N}\\rightarrow\\mathbb{N}\\), one can imagine a trace as `guessing' finitely many values for \\(f(n)\\); if the correct value is always among these `guesses', the function is `traceable'. Expressing \\(A\\subseteq\\mathbb{N}\\) via a function mapping \\(n\\) to a binary string representing the characteristic function of \\(A^{\\leq n}\\), traces can also be used to `guess' sets. Traces show up at various places in recursion theory, among them algorithmic randomness.   Section \\(2\\) gives basic facts about traces; in particular, it is shown that the set of programs computing traces is not r.e. and in fact \\(\\Pi_{3}\\)-complete.   Section \\(3\\) then looks at traceable functions and sets. Clearly, if a function \\(f\\) is traceable by a trace \\(V\\) with \\(|V^{[m]}|=1\\) for cofinitely many \\(m\\), then \\(f\\) is computable; otherwise, functions of arbitrary Turing degree are traceable via \\(V\\). This suggests investigating the number \\(|V^{[m]}|\\) of `guesses' a trace \\(V\\) tracing a function \\(f\\) or a set \\(A\\) makes for each \\(m\\), which is done in a series of results showing e.g. that exactly the computable sets are traceable by a \\(V\\) with \\(|V^{[m]}|\\) bounded by a constant, but that already below \\(\\mathbf{0}^{\\prime\\prime}\\), there are sets that can only be traced by a \\(V\\) for which \\(|V^{[m]}|>2^{m-j}\\) for some \\(j\\); this bound can be considerably improved when \\(A\\) contains an infinite computable subset. Concerning functions, it is shown that there are \\(f\\leq\\mathbf{0}^{\\prime}\\) that cannot be traced by any \\(V\\) for which \\(|V^{[m]}|\\) is bounded by a recursive function and that this continues to hold even if the finiteness condition in the definition of a trace is relaxed to the demand that \\(V^{[m]}\\neq\\mathbb{N}\\) for infinitely many \\(m\\).   Section \\(4\\) exhibits structural properties of the lattices \\(L_{\\mathrm{tr}}(V)\\) of traces \\(W\\supseteq V\\) with \\(V\\) a trace ordered by \\(\\subseteq\\). \\(L_{\\mathrm{tr}}(\\emptyset)\\) is shown to allow a set of continuum many automorphisms that are far apart from each other in the sense that, for each two \\(\\Phi_{1},\\Phi_{2}\\) of them, \\(\\Phi_{1}(V)\\setminus\\Phi_{2}(V)\\) will be infinite for some \\(V\\). Some information is given about the relation to \\(\\mathcal{E}\\), the lattice of r.e. sets ordered by \\(\\subseteq\\); finally, it is shown that \\(L_{\\mathrm{tr}}(V)\\) is isomorphic to \\(L_{\\mathrm{tr}}(\\emptyset)\\) for computable \\(V\\), but not in general.  The paper is reasonably self-contained and good to read. It is a bit unfortunate that the connection to algorithmic randomness, which appears among the keywords, is not explained, but the paper contains many results and methods that give a good picture of the behaviour of traces and are likely to come in handy when working with them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q377460$561D2019-79B1-4F1A-83F1-A1DE48682043","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"18bdc3e9791879423538829d590ed2da8e1e9db6","datavalue":{"value":"03D25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377460$0D98068D-390E-44FB-B1BE-550FB8E8A0C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"90a2b3788a51799b35fe5176688de98b7aa4306b","datavalue":{"value":"6223047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377460$216A972E-A3F3-40BA-9BDB-EC51C61EDB19","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4489f3ccbdc3f3cda22d0d7be1ac0bcfba19459","datavalue":{"value":"computably enumerable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q377460$80CF90F2-A584-46AE-B256-39C68BF64FE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6ce889a8a92a5adf9884f2ba6068fac0f7d64b3","datavalue":{"value":"traces","type":"string"},"datatype":"string"},"type":"statement","id":"Q377460$5EA416DB-8910-4EC3-9DA5-8783A211C051","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":"Q377460$1A23940C-923A-4E99-9B54-A1F6EFEC9C9E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b870debf78dd2a97c1c25edc705d56acad4f443","datavalue":{"value":"https://doi.org/10.1007/s00153-013-0348-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q377460$E9B33798-2C52-46E8-B904-D72CF869D513","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8bf1a8c5eaae8be75511e49d530c2dc3109c17fa","datavalue":{"value":"W1964021480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377460$44EA85AF-E488-4B5F-9F81-D4554A79AA1F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45131a38ff53f12b9952d52e2962c28740fef2f7","datavalue":{"value":{"entity-type":"item","numeric-id":3161424,"id":"Q3161424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377460$D68C88E8-67C7-4848-882F-1B32668BAB2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4a2271affae034ba55185dfaa746a67ca832e7d","datavalue":{"value":{"entity-type":"item","numeric-id":5389159,"id":"Q5389159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377460$76A54699-D5E0-4F6B-8610-3C9D688A2279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5cf8fa535605290547950c58b065116b31c50c3","datavalue":{"value":{"entity-type":"item","numeric-id":1188502,"id":"Q1188502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377460$DC2B4C9F-A23A-4A48-AB80-913DD00C88A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba17c610b66d156b76e62a37325c965ffedff718","datavalue":{"value":{"entity-type":"item","numeric-id":4184825,"id":"Q4184825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q377460$35AF463B-2EE1-4489-8A78-888D6FFAD649","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e3ae23f237a66e0890686d6d75249d137ccb136","datavalue":{"value":"10.1007/S00153-013-0348-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q377460$54DB34EA-BA01-49B6-9760-29CD0DEEFC4F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0454b36e46b61212a0dc36b83eaef9956f36d170","datavalue":{"value":{"entity-type":"item","numeric-id":3163891,"id":"Q3163891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0d169ffd57d54580471ec18f39a03f764a6384d","datavalue":{"value":{"amount":"+0.7826887965202332","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":"Q377460$DF285CD6-22A3-4106-91F4-978FBBABAF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5ed8e6acc12ba08f2a6e0ebbb9928786e41a299","datavalue":{"value":{"entity-type":"item","numeric-id":5496646,"id":"Q5496646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23fcfe81c0ff24078c2a7d45c9e771e937763271","datavalue":{"value":{"amount":"+0.7295752167701721","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":"Q377460$50BD169E-1EAB-4628-8A56-16449D4A61AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eb571c01cc322d7e83c2ee6e8e658b3eeda71ee","datavalue":{"value":{"entity-type":"item","numeric-id":912844,"id":"Q912844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41430a56fd8532d807da589d8160a929378e2488","datavalue":{"value":{"amount":"+0.7295131683349609","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":"Q377460$5B33E699-4A43-4846-9047-49BFED9451A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee4d99d46d9c3ca336c616da878f62244a10c109","datavalue":{"value":{"entity-type":"item","numeric-id":3011127,"id":"Q3011127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d951cb7400b48a5cd43f93b64f52b7a1e752953","datavalue":{"value":{"amount":"+0.7285740971565247","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":"Q377460$84E62C8A-8AC4-4D04-B168-D5857E0202C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8763c41ac974c788c411bce3a2a6d8a04d794cac","datavalue":{"value":{"entity-type":"item","numeric-id":764269,"id":"Q764269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5503ab4eaa28eb5c11ac13f9611580690fb7b78","datavalue":{"value":{"amount":"+0.7257218360900879","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":"Q377460$E3FA1F65-2D11-4510-AE1F-FFE459C40465","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Traces, traceability, and lattices of traces under the set theoretic inclusion","badges":[]}}}}}