{"entities":{"Q1071760":{"pageid":1082512,"ns":120,"title":"Item:Q1071760","lastrevid":69794964,"modified":"2026-04-13T09:26:28Z","type":"item","id":"Q1071760","labels":{"en":{"language":"en","value":"Lower bound results on lengths of second-order formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3939341"}},"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":"Q1071760$57D49D5B-4DD5-417F-87E6-9C37F91CD42F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9d04228171d73197e17215b4ce6ff8149bbbc8a","datavalue":{"value":{"text":"Lower bound results on lengths of second-order formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1071760$7FD3EAB3-6E8D-4C65-9C24-61F26421EF65","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"648df78db2774acaee220a496a714e0bedbfcf28","datavalue":{"value":"0586.03029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$1B7C20DC-563F-4EBA-835B-BD6B4C53BC9E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d0c17b53d0423cdefa5c6d20b914d61157bb12c","datavalue":{"value":"10.1016/0168-0072(85)90034-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$47E889E4-9030-47E0-8E0B-33629D5ED9BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6cc4c083d5cb82a5c48ffbb3d27cb0e0019a5bc","datavalue":{"value":{"entity-type":"item","numeric-id":580584,"id":"Q580584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$80765E23-3BDD-47AE-A445-DD5D321D5557","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":"Q1071760$64B1CBF1-32D0-49DA-BB9F-663764E51AC8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1071760$484C5A71-E01E-4CA5-9026-5CB17D96C842","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4fd00eb57525092664b4ba6a0310c4d43c3a2be1","datavalue":{"value":"Let L be the language of second order predicate calculus with equality \\(=\\) and ordering \\(<\\). C(s,h) denotes the class of prenex formulas from L such that \\(F\\in C(s,h)\\) iff: (1) the only free variable in F is monadic, (2) only predicate variables with \\(\\leq s\\) number of places occur in F, (3) the prefix of F has \\(\\leq h\\) quantifier changes. A formula G belongs to the class \\(C^*(s,h)\\) iff there is an \\(F\\in C(s,h)\\) and a two place predicate variable Q free for in F such that G results from F by substitution of Q for \\(<\\). F(P)\\(\\in C(s,h)\\) is true in \\(D_ n=\\{0,...,n- 1\\}\\) under the assignment of \\(P^*\\subseteq D_ n\\) to P if it is true when second order quantifiers range over the associated set of relations on \\(D_ n\\), while individual quantifiers range over \\(D_ n\\), with \\(=\\), \\(<\\) interpreted as equality and natural order on \\(D_ n\\). \\(| F(P)|\\) denotes the length of F(P).    The basic result is: Theorem 1: There are integers \\(A,c>0\\) as follows. Given \\(s\\geq 3\\), \\(h\\geq 0\\) there is a formula E(P)\\(\\in C(s+1,c+h+2s)\\) and an \\(n_ s\\) with the property: (*) if \\(n\\geq n_ s\\), \\(t\\leq s-3\\) and F(P)\\(\\in C(t,h)\\) are such that F(P)\\(\\equiv E(P)\\) is identically true on \\(D_ n\\), then \\(| F(P)|^ 3\\geq (At^ 2)^{-1}n^{s-t-2}\\). The formula E(P) has \\(\\leq h+6\\) second order quantifier changes.    Definition: For \\(F(P,Q)\\in C^*(s,h)\\) (P monadic, Q second order) put \\(S_ n(F)=\\{(P^*,Q^*)/\\) \\(P^*\\subseteq D_ n\\), \\(Q^*\\subseteq D^ 2_ n\\) and \\(F(P^*,Q^*)\\) true in \\(D_ n\\}\\). The set \\(S(F)=\\{S_ n(F)/\\) \\(n=1,2,...\\}\\) is the generalized second order spectrum of F.    Corollary: Let c be as in theorem 1, \\(s\\geq 3\\), \\(h\\geq 0\\). Then there is a formula E(P,Q)\\(\\in C^*(s+1,c+h+2s)\\) such that S(F)\\(\\cap S(E)\\) is finite whenever \\(t\\leq s-3\\) and F(P,Q)\\(\\in C^*(t,h).\\)    There are further results of a similar type. The proofs are based on techniques introduced by the author in Trans. Am. Math. Soc. 284, 203-218 (1984; Zbl 0548.03018).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$B4E4E741-6814-4086-A404-606EE5921B38","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$3C79C049-F902-4DD8-86DE-85649C0D800E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd1ebd9dd665e7350d17a40eafa30f7b99b8c1e0","datavalue":{"value":"03C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$4F67E723-EB99-40BB-9B70-7A3476ECD247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dd8503cb84d44ac2adb520ebbb11872e6dc1ec3b","datavalue":{"value":"03B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$B91105B7-7783-4BA3-987C-D9E1D43769A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$D3D5CD31-11C5-4FCF-9BC0-E72419F426DD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7bc58bd56fdaefc33cd017d74dbcd016e9e39dd6","datavalue":{"value":"3939341","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071760$D0630C84-5690-4939-9F00-D1D36993E394","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11acd2fb6ad6c566c252aa4b6fd795400412f6ca","datavalue":{"value":"complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$48A44A22-D7EC-47C8-8EF0-F7A6BFD9CF52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d57d4cab5a76e700adbc3136ae85204519052fb","datavalue":{"value":"length of formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$48A20A04-CAB9-463D-A06E-DEDD8AE5696F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66ed45a4502917d9123f824d7bf807c20eac7a67","datavalue":{"value":"alternating machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$DF5BB36B-E2BF-4EBA-9340-1A0D78C95B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8370a4602c7ab7dcc8fb9150b090097d5c0b28","datavalue":{"value":"second order predicate calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$11F80A9A-95EC-42C4-B15F-9527CAB4DC30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffccfa1103d1beca3bbaf9f9fbb4392c046d43df","datavalue":{"value":"second order quantifier","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$461B99BA-03AE-491A-A7D1-102B08826F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5397c9da1cfa200098fb392c88c7cd46d4f7c8a5","datavalue":{"value":"second order spectrum","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071760$F6B9C62B-9671-430E-B4BD-A3BB9FAFE4C7","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":"Q1071760$136A6537-8491-41B9-AFFA-55F32D1730C5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$36B556AA-0524-497F-937C-62898EC50859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bb73f98826b7a466d2ab60b16ec0466f1aead8a","datavalue":{"value":{"entity-type":"item","numeric-id":5585368,"id":"Q5585368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$1083A17C-C438-4C36-9B68-C23E075F8C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7402dc5bdf53dcf826b894508745d7a339429a41","datavalue":{"value":{"entity-type":"item","numeric-id":4775859,"id":"Q4775859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$7D861364-8580-4C67-A583-1E0A7A0AD9C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3a5f8c38dc9aa69650033303ed3bcc47054a76a","datavalue":{"value":{"entity-type":"item","numeric-id":3942945,"id":"Q3942945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$9193156C-E869-46D8-83F1-0C42B0F53790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e69094de10a4adace17c337f42fc95786cce9146","datavalue":{"value":{"entity-type":"item","numeric-id":1144008,"id":"Q1144008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$640196BC-5AA5-4B99-906C-76549414E9A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbefacb8c8f33b0f1be9db7004061a91697d97bd","datavalue":{"value":{"entity-type":"item","numeric-id":3340842,"id":"Q3340842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$C812430E-9ED2-42AE-9862-428B2EDD235A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071760$53F5A916-3D7C-4711-8A07-7D009124520E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b0234f7ab626aac116c456c565e6c2c6a612144","datavalue":{"value":{"entity-type":"item","numeric-id":3340834,"id":"Q3340834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f2148ca1498a14a3ee02ae0ab7850baa1404174","datavalue":{"value":{"amount":"+0.822152316570282","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":"Q1071760$A4E17505-D3EC-4CFA-B721-B9AD8250C389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6e7c5836c0663cee15a6ebc1528541b45739438","datavalue":{"value":{"entity-type":"item","numeric-id":3677731,"id":"Q3677731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0658067c87f7781d3bfd898d1f33bd8150d70a62","datavalue":{"value":{"amount":"+0.8137912750244141","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":"Q1071760$F18C2E02-5825-40A3-A2A9-ECDE92AD3ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c4481310e5f9c286048a36688cdc0a25e3b7a6","datavalue":{"value":{"entity-type":"item","numeric-id":3352993,"id":"Q3352993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa9b8294a032d607c1dc736d91e4b4cd92158d4d","datavalue":{"value":{"amount":"+0.7332520484924316","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":"Q1071760$EA20B9F4-1912-4162-B16E-069B458C9A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1531fbf461ed9655e9199a2ec736e2cee3075df7","datavalue":{"value":{"entity-type":"item","numeric-id":3728886,"id":"Q3728886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1853057096dcebb16386f70d88715e71712f38d","datavalue":{"value":{"amount":"+0.7253310680389404","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":"Q1071760$88406430-7089-4664-81E2-324F7605EB5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c07e9316d068246cada83dbda1bfa6a906536061","datavalue":{"value":{"entity-type":"item","numeric-id":1078169,"id":"Q1078169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e183919f36d648d010a5d3b6bd030e7fb033981","datavalue":{"value":{"amount":"+0.7180648446083069","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":"Q1071760$2023D38A-F7DF-4F67-858D-1A6C49AE74C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bound results on lengths of second-order formulas","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bound_results_on_lengths_of_second-order_formulas"}}}}}