{"entities":{"Q1081599":{"pageid":1092351,"ns":120,"title":"Item:Q1081599","lastrevid":69594288,"modified":"2026-04-13T08:04:53Z","type":"item","id":"Q1081599","labels":{"en":{"language":"en","value":"Semilattices of disjunctive and linear degrees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3970738"}},"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":"Q1081599$FF2A13D5-725B-42C9-A808-1E0144DA25BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2bacd2a4a16601563a7a440703b506815a1f09d1","datavalue":{"value":{"text":"Semilattices of disjunctive and linear degrees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1081599$2944B298-3308-4952-B39A-1705E81016DF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"35bed2290f470c333a736c7f58fab50634745380","datavalue":{"value":"0602.03009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081599$49EDF21D-5098-47AA-B0E6-ACD91AD2E510","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84d0ed032d215d83cfb9864ee1fce12a75a5628a","datavalue":{"value":"10.1007/BF01156253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081599$BB60701B-874C-4161-B18D-6D013E351355","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081599$795C4D68-1A09-413F-AE22-7FCC487380C5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1081599$8D513073-923C-4030-890E-7B21659918E0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"786e68addd85f88a9cd6b54d257c3b91923fbda5","datavalue":{"value":"It is known that there are essentially only seven intermediary reducibilities between truth table (tt-) and many-one (m-)reducibilities. These are truth table (tt-), many-one (m-), linear (l-), positive (p-), disjunctive (d-), conjunctive (c-), and bounded truth table with norm 1 \\((btt_ 1\\)-). If r is a reducibility, R the collection of r-degrees, and \\(\\oplus\\) is the join operation for r-degrees, then let \\(L_ r\\) denote the upper semi-lattice (R,\\(\\oplus,0)\\), and let \\(Th(L_ r)\\) denote the complete first-order theory of \\(L_ r\\). The author shows: (1) \\(Th(L_ 1)\\neq Th(L_ r)\\) for r in \\(\\{\\) tt-,p-\\(\\}\\) ; (2) \\(Th(L_ d)\\neq Th(L_ r)\\) for r in \\(\\{\\) tt-,l-,p-\\(\\}\\).    The proof that \\(Th(L_ l)\\neq Th(L_{tt-})\\) consists in constructing a set B, given any arbitrary non-recursive set A, such that if one sets \\(C=A\\cap B\\) then \\(A\\nleq_{tt}B\\oplus C\\) and \\(C\\nleq_{tt}B\\). Thus the proposition  \\[  \\exists a\\neq 0\\quad \\forall b \\forall c\\quad (c\\leq a\\oplus b\\to (a\\leq b\\oplus c\\quad or\\quad c\\leq b))  \\]  is true in \\(L_{l-}\\) but false in \\(L_{tt-}\\). The proofs of the other results involve similar constructions of a set B in stages, where B satisfies certain simple conditions involving \\(\\leq\\) and \\(\\oplus\\). The arguments are non-priority finite extension constructions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081599$73475BFA-8569-4B94-B10C-8B8E14F31A54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081599$F7F20891-C916-42B5-ACCC-F43A37453132","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24404546cf843a18a503cbda7ca719d6e69898e4","datavalue":{"value":"3970738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081599$037F7B7C-A3D6-4F57-A878-E93E581D8E22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"214cfd74473bc6d0eae3b8ca28189646d43fd7f1","datavalue":{"value":"many-one reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081599$310DC77E-A72B-4D73-9668-2EDA385F7F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d4e15085277c77e1f6537f1355f78224cb0f64","datavalue":{"value":"truth-table reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081599$D0377AAF-F258-4809-95B4-2349C3E3F39F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4331f1d56595446bb12729153275332691268eb0","datavalue":{"value":"theory of degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1081599$6A5AA1C4-149C-4565-8DC5-5E9D5A4C3664","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"587d11483618646ab2f82c15bc64ced23d8304ad","datavalue":{"value":{"entity-type":"item","numeric-id":178406,"id":"Q178406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081599$70FBE573-B4C4-4D38-B86E-626199D5CA4C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af7a6817238379ba945f4c57a8ee8caebc5f2605","datavalue":{"value":{"entity-type":"item","numeric-id":455764,"id":"Q455764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081599$324C4166-CE66-4290-8E21-DAAB7B915BC5","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":"Q1081599$6A8913F0-BA6C-4D72-BE8F-F9FAFB82805D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d56d6d3e2b86ce2896b018481efbd35f39a15ed2","datavalue":{"value":{"entity-type":"item","numeric-id":3884099,"id":"Q3884099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1081599$4AF3B9E2-ACB9-4726-B048-D181AACA6BD0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"359c52795caf4b55d7406ba5f46dc0cd1fe8235b","datavalue":{"value":"https://doi.org/10.1007/bf01156253","type":"string"},"datatype":"url"},"type":"statement","id":"Q1081599$137786B5-B157-4321-8FFD-8958FAE722EC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e2e1aa1b055b22c104ee49c54de3e98fedb7afc4","datavalue":{"value":"W2001941650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1081599$6CB26CFD-3E4C-4B9F-B996-955DF96CA11D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"008f161617e76912149e856320e13d9231b7a32b","datavalue":{"value":{"entity-type":"item","numeric-id":790106,"id":"Q790106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad369338ac0eef247c57e8483a18438fec96bad0","datavalue":{"value":{"amount":"+0.8852199912071228","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":"Q1081599$E181C690-97C0-4A61-9EBF-D5204AB37B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cae98ccbab44085115a02f526f71228ae283d8e","datavalue":{"value":{"entity-type":"item","numeric-id":1062049,"id":"Q1062049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16e6224f54b99e8b196829d8c4cd3257aa95e102","datavalue":{"value":{"amount":"+0.8718547821044922","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":"Q1081599$357902F2-137C-4F7F-A523-4A62450FF7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ea4fb6aab73f47dda50cc9d0b6adfa316e04201","datavalue":{"value":{"entity-type":"item","numeric-id":1902712,"id":"Q1902712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0060c798aa8c87294b48fc3caa55d21d622752f6","datavalue":{"value":{"amount":"+0.8409609198570251","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":"Q1081599$EDDE956E-32DF-405E-ACE0-B58225CB357B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a6aff6ada44a7e7a7873f07cda8f1320c47c450","datavalue":{"value":{"entity-type":"item","numeric-id":4285797,"id":"Q4285797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef7a4074dd2225b6ccc812255acba10e34e91c9d","datavalue":{"value":{"amount":"+0.840960681438446","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":"Q1081599$8AA1FB0E-6E5F-4B7D-8CD4-DFABF3821C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"753a6d05bb0bf449df6ee280d6b7c5082d41a42a","datavalue":{"value":{"entity-type":"item","numeric-id":1095898,"id":"Q1095898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f47f777008f107661051863de2f5aa966eb2877","datavalue":{"value":{"amount":"+0.8402475714683533","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":"Q1081599$BEBDBB87-A159-4542-91F6-E2D10F6B0EDC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Semilattices of disjunctive and linear degrees","badges":[]}}}}}