{"entities":{"Q917545":{"pageid":919393,"ns":120,"title":"Item:Q917545","lastrevid":65365842,"modified":"2026-04-12T02:05:24Z","type":"item","id":"Q917545","labels":{"en":{"language":"en","value":"Parametrization over inductive relations of a bounded number of variables"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4156421"}},"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":"Q917545$48C12A5B-26D6-486B-8F72-DF3FCA34EAF2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8aaaee4cdc1e9d8aae6208cdf1305308f998db04","datavalue":{"value":{"text":"Parametrization over inductive relations of a bounded number of variables","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q917545$67624478-AFAE-418B-A085-4BCCDCF35587","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e6eb633b34b779811ae579338b56c3557a9dcb0","datavalue":{"value":"0705.03019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$19C6D29C-0990-4D89-A172-26A435EB9E94","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4eaa87531b7cc80406015fa3ae7da5cd45bd3250","datavalue":{"value":"10.1016/0168-0072(90)90043-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$2EBFD141-1D3C-4B25-8A0E-4071D51F60AA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$A9D29EA3-7B9E-4CF6-B380-293FE0321165","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q917545$02BA7A39-E5B1-45F3-A05C-DBAE2FA92360","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c87c6b68c9f8e14108d11bfe4d9353c18ca99dbd","datavalue":{"value":"This paper introduces and applies a version of the Parametrization Theorem for (positive) fixedpoint inductions - of a bounded number of variables. First, the ``number of variables'' measure of complexity is proved nontrivial, on classes of finite structures admitting unbounded inductions, and a conjecture on such classes is proposed. The closure ordinals and saturation of models are examined, and the paper concludes with a glance at the Spector-Gandy Theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$37DA7E76-4AC0-4693-A062-136D36F13B28","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$F8641427-997A-4A5D-99AC-A1E76158AE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51c3dc27e13e59ca92a9af5f9c02c332a8b9421a","datavalue":{"value":"03C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$C3056399-F6C1-4467-A4DC-8643CB5C0728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bacc42d4ab28169bcab125a394e2c486e425337a","datavalue":{"value":"03D75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$39C36272-E0BB-4A31-A569-F160A5F2B98E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e4acb947bbb93aef022d2652e8dc30ed364d53d7","datavalue":{"value":"03C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$BEB97E7B-8251-4EF0-94D4-5AF272754ADB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"55282e92626124600b9b262b9ee5836c2e89ebc4","datavalue":{"value":"4156421","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$28CC6735-F3D1-4DCE-9F8E-C10E851E45AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e774b8bf24e7be34caa533f509bd9dbb608adb0","datavalue":{"value":"monotone induction","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$EC93708C-6896-46A6-855E-0F480ED30E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec171027d1650ccf5b7f14821b846bd5dc75680","datavalue":{"value":"complexity measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$B30BFA9C-5D65-45F9-9C05-DACB9824ED51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0f6c0de098bccb57ef078b4ff17ca18814ed8a3","datavalue":{"value":"halting problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$FAE0B6DD-A923-4F42-A083-02A12C857026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$17C33362-4ACB-4862-AEEA-014CF6A690E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eddc51435f624d124729425ffaa7d56002b7a4d","datavalue":{"value":"logic of positive elementary induction","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$96A9AC08-AF07-468F-BCF9-102C47D799A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4993d4bbd5881021d1637488284327d9c5a8d406","datavalue":{"value":"parametrization theorem for fixed point inductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$9A8A0C87-C332-48CD-8C50-3EA5E6FD2339","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5b33acf4f0dcbd57010753ae55579e1e8602345a","datavalue":{"value":"number of variables","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$4A1BF8E3-EDDE-45D6-89E2-C83930E41FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"837aa95d4b26f24d3f89f06d9308a55807506f2d","datavalue":{"value":"classes of finite structures admitting unbounded inductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$59FD07BB-836F-4276-9A25-FCF937E1729A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbf11bdd967a69b9925ac1782416d9cd8edb27ab","datavalue":{"value":"closure ordinals","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$A3BCE068-58D8-4596-B893-4D6D56016A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32d08421ec56b95e902f7bb55c5be2f80ed6703b","datavalue":{"value":"saturation of models","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$EBE8716C-9676-4F51-B027-E62E327B1B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e00933497d8d921b05485f7fe7fd12a819aadd7e","datavalue":{"value":"Spector-Gandy Theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q917545$E11E7FAF-26D0-44AC-94D0-F4123609E9A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9eaa89ddc8f1c02cec0a1d0e7fe6b6f15f5a7ca9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$C2E9712A-39F3-4D1B-928C-9FF539368B93","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$A28C06AA-06A0-496B-BCBF-188B0435C894","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":"Q917545$73A6D992-E16F-429D-8F21-C40F9DBD0578","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3bcab62da7243b675d6ce41d150c543de3b949b9","datavalue":{"value":"https://doi.org/10.1016/0168-0072(90)90043-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q917545$5CC7448C-D009-49DD-8FD5-A5455C945EF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6556ffca5bcf37348bb82cb6622400fd5326de03","datavalue":{"value":"W2059596002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q917545$AF4549FD-ADA9-4FCB-8021-35CA43521B4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b2d77f0fb06acf637b8ebc8f180812244ae66e5","datavalue":{"value":{"entity-type":"item","numeric-id":3252702,"id":"Q3252702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$59DC16C2-29B8-408A-AE2A-53EF3AA85301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bccc04170b12cdfbc782f77a5d15185542badb7","datavalue":{"value":{"entity-type":"item","numeric-id":4143287,"id":"Q4143287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$CCE23CF4-42D1-4C21-8CC0-4E304234D1ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea45854da7df1d421d45b7aeb6b91b2908960cc1","datavalue":{"value":{"entity-type":"item","numeric-id":5537605,"id":"Q5537605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$C41C9308-77B6-49DE-ADE1-ECCA039EC144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51860ac0d6d1da9f805ee1ccc37a8c3c419b812","datavalue":{"value":{"entity-type":"item","numeric-id":5677071,"id":"Q5677071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$0EF05166-E070-4F77-8F9A-C84C281E5BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbd46e00e025849b54a0892b5e385ef0d563478f","datavalue":{"value":{"entity-type":"item","numeric-id":1393228,"id":"Q1393228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$2D87F5A2-CD25-468F-B6A9-440B4AF5BD8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b41ed073aa8154ef82f4568e281d9fa0e323670","datavalue":{"value":{"entity-type":"item","numeric-id":3220545,"id":"Q3220545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$E42A5B71-109A-4687-89B3-6F1160534BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668a8637c081f79751e1e57f52557e1f7bc7f98a","datavalue":{"value":{"entity-type":"item","numeric-id":3274971,"id":"Q3274971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$6BB9E3AC-5E62-4FDF-B721-9290ACE294C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27e4af5b5876ff51622383a273f2390072da4ec7","datavalue":{"value":{"entity-type":"item","numeric-id":5338333,"id":"Q5338333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$948D5AB0-A538-45B5-B167-690F0AF5A7E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39639c4eb400ecf30117195f6618d519cd21ecbb","datavalue":{"value":{"entity-type":"item","numeric-id":5537368,"id":"Q5537368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$57CE7C55-6709-42D7-8D4B-1998563E5563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ed8c1c9b5cf85c3067f46e271b605235d5e997","datavalue":{"value":{"entity-type":"item","numeric-id":5339741,"id":"Q5339741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$F54D8877-ED39-4DCE-81BA-E0D477DB0637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d639fb9d03ad258814bab0f3f43d6d28e28a1e","datavalue":{"value":{"entity-type":"item","numeric-id":1173404,"id":"Q1173404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$44826A03-10C4-4C8B-8217-587F3F72675B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a675fab4321817783597d6a1b8160efcb24c4ec","datavalue":{"value":{"entity-type":"item","numeric-id":3753525,"id":"Q3753525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$5091FCB7-3F17-4926-82E1-A7BC196250F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78020da47e0eece67216713da75789cba236d83","datavalue":{"value":{"entity-type":"item","numeric-id":3228608,"id":"Q3228608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$97F1CB97-8548-4759-95BD-F5E3F267047B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"365fc3a8c1ea4fdd14d92715e8b6b254641238e4","datavalue":{"value":{"entity-type":"item","numeric-id":3226751,"id":"Q3226751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$5543D8A4-35F4-4A43-9084-AA1CCF829031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c167042c712732ecd80bb14fcdcc61d49dde7bbb","datavalue":{"value":{"entity-type":"item","numeric-id":5607980,"id":"Q5607980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$8462A15A-6ABC-4F3E-A155-E0B8382904EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bab358c92256243f420d7acaf3d76a80fa6e7b63","datavalue":{"value":{"entity-type":"item","numeric-id":5622175,"id":"Q5622175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$1846B315-A493-4DA1-8147-64A63C5B30DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fa762974e3cb0286b2a40e5214b429aa00cb948","datavalue":{"value":{"entity-type":"item","numeric-id":1217684,"id":"Q1217684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$88CE3F8D-7AC8-4387-9A23-DCB90CEB842D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb5b813f7d8a3c2627f5c661a61c9efa024187d9","datavalue":{"value":{"entity-type":"item","numeric-id":3734395,"id":"Q3734395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$AB901FD9-E193-442A-BBB1-922317E930D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c1c8f61c568d0a490d1355d16af10568f782fd2","datavalue":{"value":{"entity-type":"item","numeric-id":3278335,"id":"Q3278335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q917545$2D6B55F8-D65D-4823-A9DB-EAB193E7F02B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"613b69ad76c8fc3ea3d99ec97a8669a0e4d62269","datavalue":{"value":{"entity-type":"item","numeric-id":3834043,"id":"Q3834043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee1f9881b8af40edee91177bbf530c1a205f9cd9","datavalue":{"value":{"amount":"+0.7291176915168762","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":"Q917545$4A72726A-1E86-4532-833F-49F73F79F11B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50cdd5b25d5e3a3507064a7e1ab08de447a552ad","datavalue":{"value":{"entity-type":"item","numeric-id":2639057,"id":"Q2639057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9750c23d60b417873427b379ad1284c79d0dcc1f","datavalue":{"value":{"amount":"+0.7081461548805237","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":"Q917545$69E2C56B-7316-44A7-BE33-FD9EA2F5E292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b8418eb488784c1b0e16f07168709005617b11b","datavalue":{"value":{"entity-type":"item","numeric-id":3807194,"id":"Q3807194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bc7b824696ed6803c40264b881c27c9e1055422","datavalue":{"value":{"amount":"+0.7072235941886902","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":"Q917545$34837A92-3D26-4CB2-A69F-2A5841C42E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9679a00204c8036f6094ae780d967a4f89cd0c8a","datavalue":{"value":{"entity-type":"item","numeric-id":3809800,"id":"Q3809800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43518a1ca99890053981db7e5f960feec8933b28","datavalue":{"value":{"amount":"+0.7005055546760559","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":"Q917545$7DDACFD1-9414-4FE2-9C1F-DC10ADDF5E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51a9d41e496ac807447307ac401854d076ed6956","datavalue":{"value":{"entity-type":"item","numeric-id":4364507,"id":"Q4364507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf2267b6bab9bcbb40a9c2a95f5bcc0e52c325d9","datavalue":{"value":{"amount":"+0.6995496153831482","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":"Q917545$8BFF8D02-7801-4C94-A62E-D44D4A4B15A8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parametrization over inductive relations of a bounded number of variables","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parametrization_over_inductive_relations_of_a_bounded_number_of_variables"}}}}}