{"entities":{"Q412061":{"pageid":413828,"ns":120,"title":"Item:Q412061","lastrevid":51457076,"modified":"2026-01-18T08:13:15Z","type":"item","id":"Q412061","labels":{"en":{"language":"en","value":"Menger's theorem in \\(\\Pi^1_1 \\mathrm {-CA}_0\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6029798"}},"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":"Q412061$7323C3EE-EDB4-4C32-A4FB-0C1C5D5A52EF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9a03a52803b805ed1180129e90ae33ec06f8f9c4","datavalue":{"value":{"text":"Menger's theorem in \\(\\Pi^1_1 \\mathrm {-CA}_0\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q412061$FF521FDD-BB69-4D77-82E3-7C9602E98A86","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"23eb946d91b9c5ae851adab2c83077938520c5c7","datavalue":{"value":"1245.03018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$AEFC236C-78D5-449A-BFD8-A16D9ECEDF83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e534880849b93db09a5c4bf78c5b4ca1b817f6f","datavalue":{"value":{"entity-type":"item","numeric-id":283111,"id":"Q283111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$A1CD6C65-9D82-472C-A4AD-FCA0C4EADFA5","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":"Q412061$8B987CEE-A21B-4446-8C39-4E7A13B908C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"97df402d3a91ac31bfea85893aa349af566173be","datavalue":{"value":{"time":"+2012-05-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q412061$27B7F46F-0BE1-4DB1-913E-C13EAF879369","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7988d1640f0f36164c1460e537e51c05ae00af9a","datavalue":{"value":"The author studies the reverse mathematics of infinitary extensions of Menger's theorem from graph theory. The extension of finite Menger's theorem to countable graphs was proved in 1987 by \\textit{R. Aharoni} [J. Comb. Theory, Ser. B 43, 303--313 (1987; Zbl 0631.05032)], but the extension to arbitrary graphs was only recently obtained by \\textit{R. Aharoni} and \\textit{E. Berger} [Invent. Math. 176, No. 1, 1--62 (2009; Zbl 1216.05092)]. The difficulty of the proof of the general result makes the theorem a natural candidate for reverse mathematics analysis. Previous work established only the lower bound that Menger's theorem for countable graphs implies the subsystem \\(\\text{ATR}_0\\) of second-order arithmetic over the base system \\(\\text{RCA}_0\\).  This paper establishes an upper bound by showing that Menger's theorem for countable graphs is provable in the subsystem \\(\\Pi^1_1\\text{-CA}_0\\). The author poses the exact strength of Menger's theorem as an open question, but proves that a strengthened version, which the author calls extended Menger's theorem, is equivalent to \\(\\Pi^1_1\\text{-CA}_0\\) over \\(\\text{RCA}_0\\). The proofs in \\(\\Pi^1_1\\text{-CA}_0\\) proceed via countable coded \\(\\beta\\)-models and countable coded models of \\(\\Sigma^1_1\\text{-DC}_0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q412061$C8E42371-E3C1-41DE-89CB-F681A16EE09F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1ffd6458cf29ace8b9f78898cc3cc1cfe8fed9fa","datavalue":{"value":{"entity-type":"item","numeric-id":375888,"id":"Q375888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$AC9C4DD5-1271-471E-947B-1D15446DBF41","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"13841f0b96793f178ce9a7dcac9f232220625aee","datavalue":{"value":"03B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$3DDD650D-B32A-4C32-8994-416380C19F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4cb4544bfd0397cd4a315ee326499c372f013de5","datavalue":{"value":"03F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$491FCDF3-73EC-4793-8A40-687CE95CEB6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$FF3C0D0C-860A-4B66-ADB5-BEB9C28FF29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$149B402A-7DC1-4F9D-9ECA-2F7BC231DB89","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"29257f03c5a22594ca8731085970c439561f7fbe","datavalue":{"value":"6029798","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$EED2F843-48A1-4F4B-B682-24901DECC52A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e325a72f0e26ab98b1e996e2e86ac8d7891b9a92","datavalue":{"value":"reverse mathematics","type":"string"},"datatype":"string"},"type":"statement","id":"Q412061$1D1ABE2F-0776-4B73-B7F6-3E4D60E9FF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q412061$0E284BE8-FA68-46BE-ACFA-E27A8BDC62AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"933f96092e7a74ebb2f811e63c6e198c9bb9a8dd","datavalue":{"value":"matching theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q412061$BA314D81-507A-4259-9948-AEC260A3F7DE","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":"Q412061$56B00CCA-FBCE-455D-9FB3-A0338DD23A41","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1b6d6b5cacab7c1e1013be6b5b62c0671420d0bc","datavalue":{"value":"https://doi.org/10.1007/s00153-012-0269-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q412061$3A1696C2-516C-4EE8-8E60-38262752665B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e5e65387384f6046c39ed4235e21d09f2816e304","datavalue":{"value":"W1968578038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$0FF84BF2-52BA-4316-8437-3DDE63993766","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"95e76945924615d1fd982f2685806e8aba6ff215","datavalue":{"value":{"entity-type":"item","numeric-id":1094433,"id":"Q1094433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$A3E1A72D-987E-47F1-AE70-D54FB7257B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e5cdfd38c969eec78220d1ab74695b624b6333e","datavalue":{"value":{"entity-type":"item","numeric-id":1016232,"id":"Q1016232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$9DFE713C-702D-497B-8584-B9D05F6B120C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ced782eb6e7be2df0dbcea28ce1bb103b301bc0","datavalue":{"value":{"entity-type":"item","numeric-id":1193566,"id":"Q1193566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$6DA7F13C-F967-46AB-B5CA-0F6DB75717A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca9945d56e04cd274a3e2533b7d542fac3be86fd","datavalue":{"value":{"entity-type":"item","numeric-id":3374865,"id":"Q3374865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$45F071BF-7A2A-4538-962C-16813DAA0EC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0842236f0f9c6282c7fbe6f5512cae3e61d9ccae","datavalue":{"value":{"entity-type":"item","numeric-id":4111536,"id":"Q4111536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$784E3688-6D1E-4BC4-92B0-A56EE90A4CF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8da5dd0807d4d75222dc76b353aa0a5b1cc7d241","datavalue":{"value":{"entity-type":"item","numeric-id":1237732,"id":"Q1237732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$8953C937-5543-4077-B545-EBE3EE432B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d209d940a77a138aef5d545c237e80cee14d7f2","datavalue":{"value":{"entity-type":"item","numeric-id":4292597,"id":"Q4292597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$73FC5E3E-20FC-4604-9B9E-5240906FEA6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0430e4a9fe16a78c945c278746cad2959afea463","datavalue":{"value":{"entity-type":"item","numeric-id":3395521,"id":"Q3395521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q412061$F1A5C8B3-4411-435B-8F63-4FC7F8AAEE20","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"91ef9586310bc1776417b53e9dd1c435ad25142a","datavalue":{"value":"10.1007/S00153-012-0269-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q412061$FB4F858C-777C-46CC-A373-857262395959","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84862d9edef528111a06cf6d1cd1949c2c8e4b5e","datavalue":{"value":{"entity-type":"item","numeric-id":1016232,"id":"Q1016232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7b06563c449cd51a286f153b31d323b026d5685","datavalue":{"value":{"amount":"+0.7751116156578064","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":"Q412061$C32D864D-DB6A-4857-9476-7BC4D355A811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70d521428387f250bc82c2bbc09ffdad7bfb2176","datavalue":{"value":{"entity-type":"item","numeric-id":1065025,"id":"Q1065025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"363398d393a1d401eafab85d1e008ae5c9e18857","datavalue":{"value":{"amount":"+0.7629238963127136","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":"Q412061$874833F9-FB3F-4677-9F16-408D9391BDB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f504a00c62e8975936115564b5838de96710c8b8","datavalue":{"value":{"entity-type":"item","numeric-id":4305312,"id":"Q4305312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbbd55dd8b7531266c315a2fdc31b7b2cdcc3010","datavalue":{"value":{"amount":"+0.7625229358673096","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":"Q412061$67F94A4F-B6E6-453C-8D25-92F1C64260F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4437bce6528d0976f0ab0aa3d21fa73e16d7a3d","datavalue":{"value":{"entity-type":"item","numeric-id":5057117,"id":"Q5057117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ace7d18bbf0b6d61eec40fd4e80c45e8c54d0730","datavalue":{"value":{"amount":"+0.7545636892318726","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":"Q412061$E8163C4A-18FB-44AE-8B9D-ABDA36B62AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05a45b5ffbe96decf65240375a9b13e801afb790","datavalue":{"value":{"entity-type":"item","numeric-id":1094433,"id":"Q1094433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d28471fa4a512d1353f17dac73ebed58571ab37","datavalue":{"value":{"amount":"+0.7504804134368896","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":"Q412061$6D385002-99A6-4BF6-9FB2-E98E595C8621","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:412061","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:412061"}}}}}