{"entities":{"Q2372682":{"pageid":2383425,"ns":120,"title":"Item:Q2372682","lastrevid":43971087,"modified":"2025-11-18T15:40:11Z","type":"item","id":"Q2372682","labels":{"en":{"language":"en","value":"Filters on computable posets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5176389"}},"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":"Q2372682$6678D2DF-E21E-4C9D-B2C8-A423A0E67785","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e6584df2702913ff411c9397359345c1a8e9a7c","datavalue":{"value":{"text":"Filters on computable posets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2372682$8E13F71D-218A-49D0-8204-FDC57E7A79DB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c07ad13c2f19eec0a296e9a3f07b85854c45ad28","datavalue":{"value":"1128.03037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$9C84554D-45C1-4D54-9C7F-F961A851059A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e46a0b2f77af8f2df77d28314d19ad410add2b91","datavalue":{"value":{"entity-type":"item","numeric-id":218972,"id":"Q218972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372682$B9B1BF83-D918-48A0-94D5-B94B0583A72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa6fe6778469ced17e25612a269bf91190d4e60c","datavalue":{"value":{"entity-type":"item","numeric-id":375888,"id":"Q375888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372682$3C8A2F0D-F3CC-49FF-A0B5-A85D705DA18E","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":"Q2372682$62828DF0-9F90-4D43-9CA2-CC3F9F1DA73A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"37c844feca35da75671978fc1effde9476fb11ba","datavalue":{"value":{"time":"+2007-08-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2372682$4957C85A-D2B0-4E17-A7B2-4F0ACDF69E84","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b777ea488ce9370184e802fdea0ce67545004bee","datavalue":{"value":"This paper studies filters in posets from the viewpoint of computable mathematics. A filter in a poset \\((P, {\\preceq})\\) is an upward closed set \\(F \\subseteq P\\) such that \\(\\forall p,q \\in F\\, \\exists r \\in F (r \\preceq p \\land r \\preceq q)\\). A filter which is not properly included in another filter is \\textsl{maximal}. The filter \\(F\\) is unbounded if \\(\\forall p \\notin F\\, \\exists q \\in F\\, p \\npreceq q\\). Obviously every maximal filter is unbounded.   It turns out that every computable poset has a \\(\\Delta^0_2\\) maximal filter. On the other hand the authors construct a computable poset with no \\(\\Sigma^0_1\\) or \\(\\Pi^0_1\\) maximal filters, and a computable poset \\((P, {\\preceq})\\) such that if \\(F \\subseteq P\\) is a maximal filter then \\(F\\) computes the halting problem. It is also shown that every computable poset has a \\(\\Sigma^0_1\\) unbounded filter, and that there exist computable filters without \\(\\Pi^0_1\\) unbounded filters and such that every unbounded filter computes the halting problem.   From the reverse mathematics viewpoint (\\textit{S. G. Simpson}'s book [Subsystems of second order arithmetic. Berlin: Springer (1999; Zbl 0909.03048)] is the main reference), these results imply that each of the statements ``every poset has a maximal filter'' and ``every poset has an unbounded filter'' is equivalent to \\textbf{ACA}\\(_0\\) over the base theory \\textbf{RCA}\\(_0\\).   The paper includes a few more results of the same kind.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372682$9B97A6BE-5480-4BA7-8D47-D221EECB522F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"714ba9e68918c0335f6540ff55b340d5c87112cd","datavalue":{"value":{"entity-type":"item","numeric-id":238867,"id":"Q238867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2372682$DD905604-2F88-4D96-8E82-376D4747A225","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"758b4d196a1f97708f26591fee42c00739e26cc0","datavalue":{"value":"03D80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$06659488-B9E9-4AED-A449-BD6D3FA28014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"13841f0b96793f178ce9a7dcac9f232220625aee","datavalue":{"value":"03B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$E418A2F4-A44A-4FCF-B821-01D611A926FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4cb4544bfd0397cd4a315ee326499c372f013de5","datavalue":{"value":"03F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$2104B1FF-BE95-4B35-95EE-1E0902D914BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$EFD786C5-21D8-4E68-80D6-E556FA60FA12","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2855b772c02ca6b4171e502ed5d73de05bed944a","datavalue":{"value":"5176389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$D6670A39-92F8-4400-B1F1-884186DA4AC0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40d93df6e1a6a685e2abcc70361971901e798aab","datavalue":{"value":"computable mathematics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372682$147BE0D1-E04E-4C55-9301-441835F5CD82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e325a72f0e26ab98b1e996e2e86ac8d7891b9a92","datavalue":{"value":"reverse mathematics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372682$329EF23A-43D4-49FE-99A5-AA99A6EA4FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0234c8bd1d434410bb3bde3b417bbef742348b70","datavalue":{"value":"maximal filters","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372682$C60D8D64-E7CE-4118-83AC-B316A9FF25A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"470c68cb189fc0f6e957406de4ea59c65f4cd1af","datavalue":{"value":"unbounded filters","type":"string"},"datatype":"string"},"type":"statement","id":"Q2372682$580C5C5A-E015-4510-8992-10EC7EF42267","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":"Q2372682$2D20833A-EA48-4EB5-8C7D-A8418B4695AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1b604710ca24d4d41c9e10eb6115defe62a4e072","datavalue":{"value":"https://doi.org/10.1305/ndjfl/1168352662","type":"string"},"datatype":"url"},"type":"statement","id":"Q2372682$C0F702D4-70DD-4C74-A068-C4AB69F6B9C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1f75694899f32f65b6a0d2a65a420f1e108e4ae0","datavalue":{"value":"W2016627349","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$5BCB9EB2-33AC-4490-B64D-017909760984","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ee374189ffdb5faf214ca56505b81c2cb472768","datavalue":{"value":"10.1305/NDJFL/1168352662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2372682$0B9C2D08-5E05-4CD9-A16E-8AE0675CAF59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be47797fb99ac80a69f65645d65c807b5cf83a00","datavalue":{"value":{"entity-type":"item","numeric-id":3807196,"id":"Q3807196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d691d8634568dd16400046f70ff809d7a4abf27d","datavalue":{"value":{"amount":"+0.70917904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$A69AEE7B-CCF6-468C-B517-8329E017D5F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25039b6171b2485eba382bcb26f5369f48506ee7","datavalue":{"value":{"entity-type":"item","numeric-id":3699664,"id":"Q3699664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c237f427d7a3137f303a9aa009d5985e25239d4","datavalue":{"value":{"amount":"+0.6989099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$329CC024-4810-4D57-9806-F21B63467299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37bc3bfcd11f8a21f0e9b45e52857c41b55de2ef","datavalue":{"value":{"entity-type":"item","numeric-id":5713163,"id":"Q5713163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d3f97c532a04dbab23027bd0c31b00bed31c26b","datavalue":{"value":{"amount":"+0.69883287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$DA25A638-8F8E-444F-BF9F-A0638B1FD1E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a37891e23c649d536522fc4eb3a7d84afa97ee28","datavalue":{"value":{"entity-type":"item","numeric-id":3464661,"id":"Q3464661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"400afca9ace05e2dbf51a9c389cfacac940d7481","datavalue":{"value":{"amount":"+0.69179314","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$95968B46-282A-4AF3-B7A6-5CF23FE31F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd991d405400e2d892bc58b725db06349854edba","datavalue":{"value":{"entity-type":"item","numeric-id":5472644,"id":"Q5472644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b501733d34485069e43468e45064ae213460dc8e","datavalue":{"value":{"amount":"+0.69125295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$721931AB-BDC6-4490-99E4-1AA6B99E1C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"837b8e30ee7a9d72cc4becd9ac98e6122a000825","datavalue":{"value":{"entity-type":"item","numeric-id":1063593,"id":"Q1063593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4b49f1f5df8130e1ce8fdf6cac9dc0e55d2dd75","datavalue":{"value":{"amount":"+0.68574154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$94090E6A-1CF7-4D69-9748-429CA4E79BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"698285bedd1468c15cafd61e35c38928259b85e0","datavalue":{"value":{"entity-type":"item","numeric-id":5293192,"id":"Q5293192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5097c1bedb8b8c5eca91dd7e92da87020d3a5cfe","datavalue":{"value":{"amount":"+0.67823434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$C41192AE-539B-44CE-83EE-FC8331396B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a86889ee0c20c78a66e155efac08460a54d006af","datavalue":{"value":{"entity-type":"item","numeric-id":894259,"id":"Q894259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69c93b4e998d868528eec1b0ce5e4b693ee60cb0","datavalue":{"value":{"amount":"+0.6766672","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$4A18391E-2074-405A-9C98-51CEEFC01509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f370a8f81fdfc413706a3975e31749f543527788","datavalue":{"value":{"entity-type":"item","numeric-id":3163663,"id":"Q3163663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbab68a1f727f0c25a8749467d6e1bc0a098bc6b","datavalue":{"value":{"amount":"+0.67503434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2372682$C111D6E7-B1EB-4BC6-A8AF-6606D3D404AC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2372682","badges":[]}}}}}