{"entities":{"Q1360313":{"pageid":1371052,"ns":120,"title":"Item:Q1360313","lastrevid":43058366,"modified":"2025-07-17T07:58:08Z","type":"item","id":"Q1360313","labels":{"en":{"language":"en","value":"Count\\((q)\\) versus the pigeon-hole principle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1036279"}},"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":"Q1360313$7E1ADD41-3761-4EDA-B1CB-0F250F327E92","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"32e6a78bc3b9ea15319ee6a8aa4b750f94464e10","datavalue":{"value":{"text":"Count\\((q)\\) versus the pigeon-hole principle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1360313$A77C0817-9A39-482C-B74F-B37EC42530C8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"afcab62ab5ceee7f4284f5d7ccf6a9f1b3e1eabc","datavalue":{"value":"0884.03055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$90B663AD-1801-4960-814A-6AF7EBCEC051","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b988aafc908ad0705db140a886cbabb24b606a94","datavalue":{"value":{"entity-type":"item","numeric-id":195146,"id":"Q195146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1360313$62E09C5A-E1D4-428D-9E6F-3ABE65F7CAEA","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":"Q1360313$B0EC389C-9DE0-413B-B821-ED95E1486C13","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"363664994bd3f98264ff6fc78db2cfbbaf8e3fbc","datavalue":{"value":{"time":"+1998-04-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":"Q1360313$7910B3A2-6D43-427A-9087-E3913407E2CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb8ae57a4caaa19d11f8ed7d3bd207fd8b6555ec","datavalue":{"value":"The paper contributes to the area which studies the status of elementary counting principles (like pigeon-hole principle) in Bounded Arithmetic. Such questions are in a nontrivial way connected to some questions (like the well-known P-NP problem) in complexity theory.   The author continues his previous work on solving the so-called \\(\\text{Count}(q)\\) versus \\(\\text{Count}(p)\\) problem; the main onstruction is here simplified. A complete classification of the mentioned \\(\\text{Count}(q)\\) versus \\(\\text{Count}(p)\\) problem is obtained as a corollary of the main technical theorem (which shows the existence of a certain model satisfying the \\(\\text{Count}(p)\\) principle).   Another corollary shows that the pigeon-hole principle for injective maps does not follow from any of the \\(\\text{Count}(q)\\) principles; this solves an open question.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360313$731E7C6F-52FB-4B58-9945-D1770D016934","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$83ECDB4C-E13D-48F9-A0A8-E02BA959D441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$411B4C06-16F2-4CC1-BADA-56AEC145AEC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$EAB12E78-A9FA-4E7C-A938-B53D463FDEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7ac70285252cd92545adbf950f35d5f38d449784","datavalue":{"value":"03C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$C47CA9B5-76F0-4B5C-B538-F042C8554271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$FD4BF86E-A72F-4875-B4C2-5D732937AD91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e67e197a631e39e178063b50ed8706c20bb706dd","datavalue":{"value":"1036279","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$0D4A47E4-179F-41A9-A473-3FE8D5E138F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa50f60e01d4b4fdf90a3281cefafcf6e4b065a3","datavalue":{"value":"counting principles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360313$2DCC35D1-77A4-4FE0-B916-7BD7F88E4C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01aa176836d243db97ef26f6e5ac337d9251b982","datavalue":{"value":"Bounded Arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360313$1861A7B2-9922-47E3-9FEA-FC04442B63FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b8e7d033342c99b72c744e65e5d3e8084428c65","datavalue":{"value":"pigeonhole principle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1360313$73F20024-50EA-4B7E-8C03-57EA3B9596F1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aa98ea30b6abca7b476f74745e2df6c0f45b70be","datavalue":{"value":{"entity-type":"item","numeric-id":672325,"id":"Q672325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1360313$3A8D2BB1-2F98-45BA-B438-73A224EA3EFB","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":"Q1360313$CF00E7AB-A7C9-4895-B6FB-91B9574EF790","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d444f352c7828b740f8e9115098bf834153c637","datavalue":{"value":"https://doi.org/10.1007/s001530050060","type":"string"},"datatype":"url"},"type":"statement","id":"Q1360313$C01139C3-C9E4-44D0-A493-593175891A3F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eeceef32cedde735dd2e4b6ba86caa7b236d72d5","datavalue":{"value":"W2728095097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$3E9DCD62-7945-4D25-B69C-45FCF874FFF4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b13270e277cc2cf97808f6a389f824723c4d40da","datavalue":{"value":"10.1007/S001530050060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1360313$62A31E26-CA31-491C-AA81-E867E26430B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b5feaa0117062ce092d3881ae7d3f76de9ba3f0","datavalue":{"value":{"entity-type":"item","numeric-id":2225400,"id":"Q2225400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbcf2e66434aeb8c4909ae26e21c16b9fa3367a3","datavalue":{"value":{"amount":"+0.8370161","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$5A24AFA9-7837-4D76-95BA-872C6BE2E2C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"217ca188c28e2635cf5bccb238de4f5c96411b6b","datavalue":{"value":{"entity-type":"item","numeric-id":1343166,"id":"Q1343166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"189e1934a81bb0c7335a061dd845e696fa2db0ca","datavalue":{"value":{"amount":"+0.826448","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$6E58DEF6-2BD0-4B85-A5D6-BC4AD0237960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"578cd776d48d10dab91f5be7d3277c1ff953b403","datavalue":{"value":{"entity-type":"item","numeric-id":2344736,"id":"Q2344736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"580ce532c3f71c2bf158a1985ec735a75e3a26d8","datavalue":{"value":{"amount":"+0.8205893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$BD6304BF-E63D-4750-B2CC-D60804E0A489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81d478ac6a9d318401b706fb64dc7d74fb19248e","datavalue":{"value":{"entity-type":"item","numeric-id":687506,"id":"Q687506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39ee2501008855a9cb121dc71f780aa6d3d2ec53","datavalue":{"value":{"amount":"+0.8186143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$2A71CA55-E289-4A9E-9F58-E7EF3CFEECD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29c3b508bbd46323bd542168fae4542209951028","datavalue":{"value":{"entity-type":"item","numeric-id":2773242,"id":"Q2773242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"873c58f698820d6acf5f0546e66021623045b748","datavalue":{"value":{"amount":"+0.8183086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$A4332298-C687-4588-96BF-A37158CD88ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7b52be97a4d7dfc870341fc8291c1d06a8c6e47","datavalue":{"value":{"entity-type":"item","numeric-id":4035300,"id":"Q4035300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"584001d3c3fb1a1ce2ddd70864079d9dd196664b","datavalue":{"value":{"amount":"+0.81544375","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$FA56651A-33FC-4968-BB9B-B55895A9ACC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72f763a0acf25eff5f5bdcb014f33351f972157c","datavalue":{"value":{"entity-type":"item","numeric-id":2928653,"id":"Q2928653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d968048a7b3d4cd4f0119a756d402a3d9741d83","datavalue":{"value":{"amount":"+0.8142933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$A4AC2475-FAEF-4BF2-86E6-3BAEAB99A68E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45bfbd0453cf7b48d9491b4811ec739ec60088f2","datavalue":{"value":{"entity-type":"item","numeric-id":1199550,"id":"Q1199550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7999de9001fbe0716b664e8ffa1c8055857c859","datavalue":{"value":{"amount":"+0.8110578","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$C3C111ED-EEA7-4DE0-A251-3CB9CCFEB927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c29ce1159944571be95ea53132a610a98bf9eaa7","datavalue":{"value":{"entity-type":"item","numeric-id":4511546,"id":"Q4511546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f51e1ff6332cd1876fdcde97d251fa2dccd1df8e","datavalue":{"value":{"amount":"+0.8101101","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1360313$5FED19BA-7610-429C-A690-4622642350F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1360313","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1360313"}}}}}