{"entities":{"Q1091820":{"pageid":1102572,"ns":120,"title":"Item:Q1091820","lastrevid":49081606,"modified":"2026-01-06T13:54:46Z","type":"item","id":"Q1091820","labels":{"en":{"language":"en","value":"How to prove representation-independent independence results"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4011941"}},"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":"Q1091820$1F4A105F-4A5B-4142-ADA7-1DD0A3D5860A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"850b154b47d7fa18842371140eeb028fa8fba31f","datavalue":{"value":{"text":"How to prove representation-independent independence results","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1091820$9EB9EF64-6DF1-4FFE-BEFD-3EC2F987E52D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22c0817c9c37baf3ccb3cc466c4e5eb60e7747c4","datavalue":{"value":"0623.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$4B0B4A7E-144F-4AD7-81EF-10E3930FB0B5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bbc7165839ba0aa70bd3b0f8edbb72d3cbaab624","datavalue":{"value":"10.1016/0020-0190(87)90191-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$3F8D6ED4-F9FF-4ED3-B6EF-9D3533EACF7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c50a503249816ae6bfc9a4fea05a1fa1163cd7c","datavalue":{"value":{"entity-type":"item","numeric-id":913488,"id":"Q913488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$51D5E6E2-9A23-4853-A7A9-1CD69B7AEA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5198e45a9951dbc1e7a97e827f0544724d7b5c3","datavalue":{"value":{"entity-type":"item","numeric-id":1091819,"id":"Q1091819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$ED75BD4D-158E-4FF9-B98B-D93E9293F9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bdb4109ac59d3ca813b07e527a14abf4f26a17c1","datavalue":{"value":{"entity-type":"item","numeric-id":579919,"id":"Q579919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$4412B80B-0557-4EDA-AD3B-DF7026F2BE47","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$504E0E7F-621C-4B1C-BD15-A79F0573A0F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1091820$D535F103-48A3-4A35-BE57-EBE4566EFAF6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f6eafc346d441f7a71693442883002f4ca6c4a05","datavalue":{"value":"A true assertion about the input-output behavior of a Turing machine M may be independent of (i.e., impossible to prove in) a theory \\({\\mathbb{T}}\\) because the computational behavior of M is particularly opaque, or because the function or set computed by M is inherently subtle. The latter sorts of representation-independent independence results are more satisfying. For \\(\\Pi_ 2\\) assertions, the best-known techniques for proving independence yield representation-independent results as a matter of course. This paper illustrates current understanding of unprovability for \\(\\Pi_ 2\\) assertions by demonstrating that very weak conditions on classes of sets S and R guarantee that there exists a set \\(L_ 0\\in R-S\\) such that \\(L_ 0\\) is not provably infinite (hence, not provably nonregular, nondeterministic, noncontext-free, not in P, etc.). Under slightly stronger conditions, such \\(L_ 0's\\) may be found within every \\(L\\in R-S\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091820$9849013F-CFE5-4DD0-A254-41DE8E289151","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$E2D7DB91-DBE7-4B03-B834-204660E112E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$70C04FCA-5FF9-40AC-B137-86CE858989BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$B7931080-56B7-40A2-9DCC-FBBA7EB7095C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$467C66B0-C426-4E4A-BDDF-FCF0743D6640","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"af7827db64840be2ec2f302455404ea5d3e567d3","datavalue":{"value":"4011941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$205DE812-B07D-476C-9D42-422860B25B2E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce412c7a06594f2f6585ca819af9d86d861a10f6","datavalue":{"value":"subrecursive complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091820$8DFD09AB-C5BA-45F9-9FA8-105508742978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cfb2a5c19c805e2e9dc613c91643e5e79e8bf4f","datavalue":{"value":"input-output behavior of a Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091820$8E85C991-A9E1-431E-8755-A8BA076BDB6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7f2309fb294dd29493c00e48da0975657f3e433","datavalue":{"value":"representation-independent independence results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1091820$BD86D4F9-AB33-425B-B4D2-4BC3CDC17B9E","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":"Q1091820$EDAD01B8-A1B9-43C1-AD51-75EB7C7D92C3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"74e321cd2ad7eb659bb64d4019fce70861d82b5a","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90191-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1091820$1160FD20-B8EC-464D-BCB0-5B70168A5073","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1a711a03d7220b9f7f741b3daf222d483543652f","datavalue":{"value":"W2030070824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1091820$994E0121-241B-4912-9ADD-842394005089","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"53bcfabc22212d3db2a4fa41c3566844e5ecdda6","datavalue":{"value":{"entity-type":"item","numeric-id":3668859,"id":"Q3668859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$588954AC-2096-4BD4-9534-E12975EEA8B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"862ea219c4a9b44f1c3bb448b0cf228839a066cb","datavalue":{"value":{"entity-type":"item","numeric-id":1071500,"id":"Q1071500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$AE08B89B-8599-4E80-B20D-956C7A59A955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82fe1700ff97e6850bd8ab19a07be4ba1db7a677","datavalue":{"value":{"entity-type":"item","numeric-id":1158957,"id":"Q1158957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$9486EFBD-A826-4142-877A-660691A9E94E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c695379422b7047c66b9db17e8a4509aa87bc9ee","datavalue":{"value":{"entity-type":"item","numeric-id":1162506,"id":"Q1162506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$5085565D-9306-43DB-80CD-E5B18E8BFEF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"704b67c0c7a5a44ff323d18e1363803acffd4565","datavalue":{"value":{"entity-type":"item","numeric-id":4071737,"id":"Q4071737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$9E39061D-378C-40A3-8C38-D2D8277E59F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917800fa52c098f2382f946c4094dc39e957bfbe","datavalue":{"value":{"entity-type":"item","numeric-id":4153600,"id":"Q4153600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$2E0E26F7-A501-4B39-B6BE-A1F2CDD90EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4323f719ce556aa0fffe2f662ce5bbcc2b42b051","datavalue":{"value":{"entity-type":"item","numeric-id":4194958,"id":"Q4194958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$186AA615-0748-4CB7-ACBC-567F40199CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1091820$7882BE02-63D2-4086-8A90-2F91DE25AC3D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e123ede04bdb363f0ac061ee5d37bc32061f7f1b","datavalue":{"value":{"entity-type":"item","numeric-id":3220573,"id":"Q3220573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b11dac743ffefa310f146cf69154486901936cb6","datavalue":{"value":{"amount":"+0.8079708218574524","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":"Q1091820$2C7A20CF-C1AC-491B-A9D5-6911DC2DC576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41614f3236ca0a9a6d25944d5d6a0090b3b5199c","datavalue":{"value":{"entity-type":"item","numeric-id":3703885,"id":"Q3703885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e604f56b113ed06b24e28897499ecd91c7ae86ac","datavalue":{"value":{"amount":"+0.7737600803375244","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":"Q1091820$7D51876F-0258-4DD9-A645-994C5DA4B039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a04f573e7da81bc482a21dfff05e83779d43987","datavalue":{"value":{"entity-type":"item","numeric-id":2988824,"id":"Q2988824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7e32ac5d8c6dab585d1c07a4e9bdea4f81140bb","datavalue":{"value":{"amount":"+0.7423762083053589","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":"Q1091820$A4B2D528-1C43-4247-97B0-CE68646BA079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e047350193f4e6f1d8464c4f8d3fec396fbf7e7d","datavalue":{"value":{"entity-type":"item","numeric-id":5384126,"id":"Q5384126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d1cbcd0acb7a7919b3d9cc9a32359618532ac9c","datavalue":{"value":{"amount":"+0.7402080297470093","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":"Q1091820$BFE494FC-BE0E-4DF3-9193-9624265C763F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646da1ed462b70087d1f7d1496ee8f3efe60e7bd","datavalue":{"value":{"entity-type":"item","numeric-id":1071500,"id":"Q1071500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f0e0e5c301b45655aa1361d4e07cae173cafd09","datavalue":{"value":{"amount":"+0.7362006902694702","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":"Q1091820$3E318B7A-6023-42BF-B7E1-CE6F2F7C4422","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1091820","badges":[]}}}}}