{"entities":{"Q790105":{"pageid":791953,"ns":120,"title":"Item:Q790105","lastrevid":64493634,"modified":"2026-04-11T20:14:58Z","type":"item","id":"Q790105","labels":{"en":{"language":"en","value":"Density of a final segment of the truth-table degrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3847372"}},"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":"Q790105$E7533143-372A-44B4-A926-D9B4A16DBA15","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b916c0fa70c7862361c9e849ab20dda282311176","datavalue":{"value":{"text":"Density of a final segment of the truth-table degrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790105$F7677F9B-7DBE-474D-A614-0E5A9B7321AB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9ed5dc1dec88d3a7ac0a37fd8ba9738208274ec0","datavalue":{"value":"0534.03018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790105$D1520E78-55D0-46DB-9735-BDF5746FE8B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c4579f149912dc7243c91a33ef8c18792f251af","datavalue":{"value":{"entity-type":"item","numeric-id":790104,"id":"Q790104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790105$C6957BC1-7207-452D-AC9F-1686B184F59A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"edf18db5439a683e98eaf3205ba65f05cfd68a4d","datavalue":{"value":{"entity-type":"item","numeric-id":161301,"id":"Q161301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790105$DC72EB3F-74FE-4E5D-B0EE-78A7289E17AF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q790105$CD1A9568-8E18-42F2-A836-171949B7FE2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"76a81f8f30dd5d80c99ea62d4c9dbb721e690448","datavalue":{"value":"This paper gives a proof that the truth-table degrees above the truth- table degree of the halting problem are dense. This is in contrast to the well known property of Turing degrees that every Turing degree has a minimal cover. Richard Shore had already constructed a first order sentence that is true in the Turing degrees and false in the truth-table degrees, but the main result of this paper gives a simple and explicit example of elementary inequivalence. An essential part of the proof is showing that every truth-table degree above that of the halting problem is the jump of another truth-table degree. Whether the full Friedberg completeness theorem (including cupping) holds for the truth-table degrees is open. Some other results and open questions, concerning truth- table degrees, are stated in the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790105$C1F67457-DBA9-44C7-AE49-176E0721D2D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790105$698B8A57-9576-4A33-BFF4-0B407119E0E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba73ea83361b93e2cdac9044ec7d1a3da54a4f6c","datavalue":{"value":"3847372","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790105$597AEBD5-EBC2-47D9-9CA3-8ACF8F6F3700","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efb4ff95f3a621b349e1899903c754474a9a9bb4","datavalue":{"value":"truth table degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q790105$94C6E1EA-AC8A-4C3E-AA91-0C82C7E7E8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"358a0a99873ef9c213ed5e1201c829b384d52b77","datavalue":{"value":"minimal cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q790105$AB98B2A7-1694-44D6-9A91-EDEE38C3E127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f18945668010cf0db80b78f0d4f602a506e66dbb","datavalue":{"value":"jump theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q790105$93FC0198-02A9-4B1E-A8FC-6C0E6A6CDC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b38447a3ea959cbe95310edeeb21e7ef6903f8","datavalue":{"value":"halting problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q790105$C7D17510-9BEC-4E4C-B7E4-7AC73F132F91","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":"Q790105$30581FC8-86BD-4F76-A7A7-693863440807","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6dc0110fc032b97423044c884444e468f23ae8ca","datavalue":{"value":"https://doi.org/10.2140/pjm.1984.115.409","type":"string"},"datatype":"url"},"type":"statement","id":"Q790105$B2BEC92B-CFB3-4883-AB3B-5172DC23B9CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ffb9782d4bdddcfa1eebcbe6148e9ef06038722e","datavalue":{"value":"W2091909693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790105$44D1BF42-1891-4DE7-A6E2-1F3280E14C96","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7e46d17a77660a85dd2d1de8a4c76e4ea8560bd","datavalue":{"value":"10.2140/PJM.1984.115.409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790105$9C212EDE-4010-4607-9CFF-9EEE170976B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90df087a7b39de847ba15fe9c9377faf7442c5e0","datavalue":{"value":{"entity-type":"item","numeric-id":2747717,"id":"Q2747717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dbe88e4470aeeec4640c4d367d481fcb3ae8d2b","datavalue":{"value":{"amount":"+0.8139482140541077","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":"Q790105$4F84CF06-FDFE-425B-B78A-AE4AA3D959DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faa3e006ab699f14b1ddd283797017cf45015b30","datavalue":{"value":{"entity-type":"item","numeric-id":5931217,"id":"Q5931217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da40b674a3c16d9e15a17560fa8bfe25ff2d8eb","datavalue":{"value":{"amount":"+0.7833923697471619","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":"Q790105$5DC4382B-8483-441C-BC88-C4011E3783FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8740d2d25ea871dc74d0e35dfb2c1830fdc3362b","datavalue":{"value":{"entity-type":"item","numeric-id":1092896,"id":"Q1092896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"020cd0466a6c50c9ddd4be3ce2aac5cb5894bbcd","datavalue":{"value":{"amount":"+0.7767270803451538","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":"Q790105$8DF2CFF8-4E2C-4683-87A0-53453ED488C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d65ebf8eaf389dea1a58a438c84c4a4ed79a4d75","datavalue":{"value":{"entity-type":"item","numeric-id":3798648,"id":"Q3798648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c67799d1ea006d91d33d3c91c0dd61842ef2e2ce","datavalue":{"value":{"amount":"+0.7760199904441833","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":"Q790105$A8BA99DE-F655-4703-8491-E5B6E133E265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"690fbb9bd8bebad535f2d442e86f826a696be3a9","datavalue":{"value":{"entity-type":"item","numeric-id":1081599,"id":"Q1081599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6b6ddd3a8cde635e05646e01abe18e477ed2296","datavalue":{"value":{"amount":"+0.7748482823371887","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":"Q790105$5D80E44D-7444-4C27-A6FF-2060BED96876","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Density of a final segment of the truth-table degrees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Density_of_a_final_segment_of_the_truth-table_degrees"}}}}}