{"entities":{"Q1361250":{"pageid":1371989,"ns":120,"title":"Item:Q1361250","lastrevid":46500969,"modified":"2025-12-24T22:23:21Z","type":"item","id":"Q1361250","labels":{"en":{"language":"en","value":"Induction rules, reflection principles, and provably recursive functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1038665"}},"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":"Q1361250$73408E3D-AADA-41A8-BB58-6C1724D7E56F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ada3492d46282034cd62b5cda78cfdf796d2ef3","datavalue":{"value":{"text":"Induction rules, reflection principles, and provably recursive functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1361250$6605E64E-2AA2-4C66-BB94-32D0B02E4F19","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"226cc3db601963eb2d0c4c9395f4f34d209f6565","datavalue":{"value":"0882.03055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361250$B800842E-C3E3-4998-87DE-C1F04998D08D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"339c78d33ff06f8c1181091be5492393d9661779","datavalue":{"value":"10.1016/S0168-0072(96)00045-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361250$AE20D345-E3BB-44D6-9D24-D7221C1CA2F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5270766f22c7ad4a781677af5d45e6943b2a3573","datavalue":{"value":{"entity-type":"item","numeric-id":636315,"id":"Q636315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$CDF9E027-1508-4149-9B37-97A749403D22","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":"Q1361250$AABCE40A-E5AF-4047-A4B4-A335C3930E7C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f90b4e4f8d3c91bc0cb00b95b47a240b3f524981","datavalue":{"value":{"time":"+1998-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1361250$01493443-AB8F-4D4F-92B7-096F71C42001","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"411d8ed1091a919ab2629297b5decbf6bbe383b1","datavalue":{"value":"The author characterizes \\(\\Pi_n\\)- and \\(\\Sigma_n\\)-induction rules, \\(\\Pi_n\\)-IR and \\(\\Sigma_n\\)-IR, respectively. With a rule, in contrast to an axiom, one can take into account how many times it is applied nestedly. Thus, for instance, \\([T,\\Sigma_n\\text{-IR}]_k\\) is the theory obtained from the given \\(T\\) by using \\(\\Sigma_n\\)-IR at most \\(k\\) times. \\(\\Pi\\)- and \\(\\Sigma\\)-IR are related. He shows, for example, that \\([T,\\Pi_{n+2}\\text{-IR}]_k\\) is included in \\([T,\\Sigma_{n+1}\\text{-IR}]_{k+1}\\), where \\(T\\) is any \\(\\Pi_{n+2}\\)-theory extending Kalmar elementary arithmetic, EA. The main result is the relation with the reflection principle, \\(\\text{RFN}_\\Gamma(T)\\), for formulas in \\(\\Gamma\\). For \\(T\\) extending EA, \\([T,\\Sigma_{n+1}\\text{-IR}]_1\\) is equivalent to \\(T+\\{\\text{RFN}_{\\Sigma_{n+1}}(T_0)/T_0\\) is finite \\(\\Pi_{n+2}\\)-axiomatized subtheory of \\(T\\}\\).   Similar characterization of \\(\\Pi_n\\)-IR is given with respect to \\(\\Pi_n\\)-RFN. Results of different nature pertain to characterizations of various classes of functions. For example, for a theory \\(T\\) axiomatized by one \\(\\Pi_2\\) sentence, a function is shown to be total in \\([T,\\Sigma_1\\text{-IR}]_1\\) exactly when it is obtained from the standard witness function of \\(T\\) by composition and one application of primitive recursion.   Since the results are of a positive nature, namely a formula proved in a theory is also obtained in another way, etc., what the author does is a careful analysis of the situation at hand, using familiar tools like Herbrand theorem. This paper is self-contained, as the author provides abundant information and explanations. Indeed, he ``did not try to be overly laconic''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361250$53C668B2-1EAF-4A31-81C7-F60CA3D7A00E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361250$622C8E3D-3DB0-4523-8059-B99B37221B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6ee9f5484d11a01fb95552e5bea2154ebac0877","datavalue":{"value":"03D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361250$B9E4A715-5E28-4280-8752-AF1E127086E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f1e7643f2c8450e128e5ee02bd355497d785df2","datavalue":{"value":"1038665","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361250$5888833A-B8ED-44B7-A981-6DF52C7322CC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1896ab682ea8e3d89f06222a215d0284a52ab61","datavalue":{"value":"nested applications","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361250$FBAB2D56-DF61-4746-9191-884363EE5031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"905898c43185600c6379f45499d0a4d4a7a5c61a","datavalue":{"value":"provably recursive function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361250$32AE2413-14AC-49A1-B3BC-BDB86CEE3FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20237dafc2e5874fe9954a476fd1b8dbe063a050","datavalue":{"value":"induction rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361250$CA0BC1AC-A7DE-4646-ABB0-CC16F8A69418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b66c6531605642201eac88586885d8f237b626e","datavalue":{"value":"reflection principle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361250$16FDFE68-40C9-4D17-8215-BF2CC45984B7","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":"Q1361250$100FF6C5-4F2F-4A89-85E0-49B71CE1696F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c473e525ddb30377e0108bbc9cb0dd0c2ff0887","datavalue":{"value":{"entity-type":"item","numeric-id":1361250,"id":"Q1361250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$1E418F33-C829-4BB4-AEC8-B6BE01FB7701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b6e4157373fd58274a40973fa66ad7b141c13cd","datavalue":{"value":{"entity-type":"item","numeric-id":3962995,"id":"Q3962995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$9EF7390D-ECDB-4DD4-A9BC-EFFCA825F9CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dccf19753fdc4aceb4fe2e72e418d7c4420dcc62","datavalue":{"value":{"entity-type":"item","numeric-id":5286672,"id":"Q5286672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$BB0544D9-5B57-4957-845E-5A4B733EB3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bd72dbbdbb28e49bc58fdcc6d69fc1738d5bbb0","datavalue":{"value":{"entity-type":"item","numeric-id":5552747,"id":"Q5552747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$67AFDF67-D0FD-49D1-A284-8998658C4C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de0e45c6d24f23b7bf00bdec0730aa590fa74f9a","datavalue":{"value":{"entity-type":"item","numeric-id":3661556,"id":"Q3661556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$A51EF47A-1564-4EC8-8B85-749E785C0971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4236271ac9b8c64aa5de82c9646e2e98252bf93","datavalue":{"value":{"entity-type":"item","numeric-id":5628105,"id":"Q5628105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$CA558DFD-977F-481A-9A6E-3EA38101668E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7010a800e4336b7ae6e486d3fa7f31c97756c9fc","datavalue":{"value":{"entity-type":"item","numeric-id":3745836,"id":"Q3745836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$A26B969C-43E6-4D4F-A5A3-65D125B8D0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e92021f96a77533aa53974edef4b49222fa4ead","datavalue":{"value":{"entity-type":"item","numeric-id":5560277,"id":"Q5560277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$02A3FD55-0778-467B-9E82-C58B67548F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d356ebfaf5725a6262f13de5d5313f007ee40e","datavalue":{"value":{"entity-type":"item","numeric-id":5600870,"id":"Q5600870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$BC82470A-A2C2-4563-9FC0-069259CFEB3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58cc241747ec6fa1130277e3fe9cbb65e8f8d05e","datavalue":{"value":{"entity-type":"item","numeric-id":5680103,"id":"Q5680103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$28E1A01B-D6D3-43DA-917B-41209539FA03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a4afd0b3b0b8757574f62e3ae80a63d3876f24e","datavalue":{"value":{"entity-type":"item","numeric-id":5533181,"id":"Q5533181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$9A06FAB8-D2AC-474D-B72E-1AB37D8C2110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3961712aa73d0d7e49904f6e1571dab96fdf8ac4","datavalue":{"value":{"entity-type":"item","numeric-id":3325707,"id":"Q3325707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$C5000A41-7D8A-4BAC-B3A6-52C16F6C6B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4def144a6c01a2c5f09f7a663c86480a856bf8a1","datavalue":{"value":{"entity-type":"item","numeric-id":3866106,"id":"Q3866106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$8192974B-ECAF-4994-A043-AD0F7D9EBEE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59b8c1e1554d59c9415a18a29b48a1fb456f45a1","datavalue":{"value":{"entity-type":"item","numeric-id":5614654,"id":"Q5614654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$400F3266-3F02-460D-911D-27E298013884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f82318748b8514096d13bc80763ff6e3cbefb3d9","datavalue":{"value":{"entity-type":"item","numeric-id":762484,"id":"Q762484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$984EB869-5A1F-4B4D-9B8D-913F6806A454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bacb5aa102ce6c71274c34a5360472cea903ae3a","datavalue":{"value":{"entity-type":"item","numeric-id":2641297,"id":"Q2641297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$E8D47489-4CFD-479D-B11A-BD6B0927642D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fde004a2ef0063eaa78d324362d52151caf647a","datavalue":{"value":{"entity-type":"item","numeric-id":4525292,"id":"Q4525292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$79D77996-02D6-4978-A515-7220654C8A89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d93c0216bb7a2404c766e146541a6f49efebe1b2","datavalue":{"value":{"entity-type":"item","numeric-id":1104318,"id":"Q1104318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361250$1CD4FA67-ECB7-4C03-85D3-CB4A70378D85","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd3f0f3d0dc1754a94ce55ce01b1f95ee3d79d89","datavalue":{"value":"https://doi.org/10.1016/s0168-0072(96)00045-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1361250$6C5CF403-6B7D-40E3-B0B6-D0A9344CC25C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9e0f5bac36fad5ab2eede65f242b34d4f0a4b4c7","datavalue":{"value":"W2076792546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361250$7E7E7295-6616-4968-84ED-081FF6D57198","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be430bb3d221ef48670b0abc618e8abe24745bcc","datavalue":{"value":{"entity-type":"item","numeric-id":4981456,"id":"Q4981456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f829fd4f6c8dd35dd473bff91b5cb82807bc0127","datavalue":{"value":{"amount":"+0.809214174747467","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":"Q1361250$B8C5D72B-52B7-4776-A6C3-97D922215A9E","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":"eeaad3138f68f32a976a53d53fc90882ab798851","datavalue":{"value":{"amount":"+0.802879810333252","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":"Q1361250$874CD033-1C02-425E-94DD-9E8AC3174F7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"434fbee7e80928919a731924aa3e402f924a291e","datavalue":{"value":{"entity-type":"item","numeric-id":1960416,"id":"Q1960416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d9eadd5f3aa1de3d0b026e97d396bca135171b","datavalue":{"value":{"amount":"+0.7953060865402222","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":"Q1361250$25C1A5AF-7B94-4640-85EA-33A117F79BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"442ac36bb417514e27cd9ff039b47e32d6b5fd8a","datavalue":{"value":{"entity-type":"item","numeric-id":5311268,"id":"Q5311268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdbe5f90a4210e147cd303184bbc0613f379ee4b","datavalue":{"value":{"amount":"+0.7913899421691895","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":"Q1361250$2116FD2F-B87E-4F03-B7A5-E2E572D858BB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1361250","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1361250"}}}}}