{"entities":{"Q2339960":{"pageid":2350703,"ns":120,"title":"Item:Q2339960","lastrevid":73059039,"modified":"2026-04-14T10:02:41Z","type":"item","id":"Q2339960","labels":{"en":{"language":"en","value":"A new proof of Ajtai's completeness theorem for nonstandard finite structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6425029"}},"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":"Q2339960$EFE8C2DC-3623-4A44-AF68-47C2EBE0B30A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fcb0bafc9a6a290e6150f8cb63ce8506dcae94e0","datavalue":{"value":{"text":"A new proof of Ajtai's completeness theorem for nonstandard finite structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2339960$E8A99342-0C8B-4B70-8D87-69B573C01DD7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d2d22cfa4bf13e860bd6ff5fd4d2250e6747ffa6","datavalue":{"value":"1345.03118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$45F9A8F1-818F-4E24-8E0C-F642B833447B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d1e78f24de2e0af3b81e99cbfe00a1cf71bfac5","datavalue":{"value":{"entity-type":"item","numeric-id":506953,"id":"Q506953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$8B0F717A-F319-4526-A05B-37D280193EF3","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":"Q2339960$50CD7AE2-C217-4562-AE7B-9CC324EEE161","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dd55b543fec3f4a634a8fef5b7b15e29b44c38db","datavalue":{"value":{"time":"+2015-04-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2339960$991117A8-C0C7-4BD5-9A1E-C72A8252D18B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02cbde935d230081f58b8920300ce0c0a29f6659","datavalue":{"value":"Ajtaji's completeness theorem is a tool for investigating problems in computational complexity theory by means of model theory [\\textit{M. Ajtai}, Lect. Notes Comput. Sci. 4484, 13--33 (2007; Zbl 1198.03038)]. It is a statement about countably infinite structures that can be coded as finite elements of a nonstandard model of arithmetic, and a suitably formulated internal notion of consistency. The author proves a slightly modified version of Ajtai's theorem for a notion of a Hilbert style \\(\\mathbf H^{(A)}\\)-proof allowing possibly infinite proof trees that are definable over a linearly ordered structure \\(A\\), and a notion of an expanded end-extension of \\(A\\). The theorem states that for linearly ordered \\(A\\) coded in a model of \\(I\\Delta_0+\\exp\\) and a theory \\(G\\) in an extension of the language of \\(A\\), satisfying some further conditions, the following statements are equivalent: (I) There exists a positive integer \\(l\\) and an \\(\\mathbf H^{(A)}\\)-proof of a contradiction with formula length \\(l\\) from \\(G\\) and the atomic diagram of \\(A\\); (II) \\(G\\) does not have a model over \\(A\\). The proof of (I)\\(\\Longrightarrow\\)(II) is essentially the same as Ajtai's. The author's simplification is in the (II)\\(\\Longrightarrow\\)(I) direction. He replaces a lengthy explicit construction of a model of \\(G\\) by an argument using the ideas behind the proof of the theorem of \\textit{J. Barwise} and \\textit{J. Schlipf} [J. Symb. Log. 41, 531--536 (1976; Zbl 0343.02032)], and independently \\textit{J. P. Ressayre} [Ann. Math. Logic 11, 31--55 (1977; Zbl 0376.02032)], stating that countable recursively saturated models are resplendent.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2339960$E3A89046-2DFE-4824-9FE8-9065B0F1C38A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a22eb1f642cbb79777784e33676c61b720925aab","datavalue":{"value":"03H15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$A42E9328-01D3-4E42-9A6E-C1FDEB46C1FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$6C400A20-5129-4F9D-B293-F0B660294E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$60794E6F-5A81-438B-ACC8-3F9015208B0F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1273cba8012abbca2dd575bb4dba2e13bc2281cc","datavalue":{"value":"6425029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$2FFA4037-A212-41D9-AC11-C73EBC46F568","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"669e1ab0be3b0e96a51a2ef7e433c212210f37a0","datavalue":{"value":"completeness theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2339960$D6993ED2-4831-482C-97E1-D63C6974B90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d7a50079e1fe284b07275d45555d083dfa56e8e","datavalue":{"value":"end-extensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2339960$DA27AD68-0379-474F-8B8E-4E038AA96C08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2339960$D94268E4-C326-4CF8-A3EF-4D01DDC25071","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc2fe705c7d582d4c8ad19b50ec74a3e6e0c8ae1","datavalue":{"value":{"entity-type":"item","numeric-id":384285,"id":"Q384285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$105B0FEF-8A91-4191-A590-A60CCC03D41A","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":"Q2339960$04404C28-4807-417D-B581-D3DE89A88835","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c783c3c72a7a19d40d9548c8724f6e43585682ef","datavalue":{"value":"https://doi.org/10.1007/s00153-014-0416-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q2339960$7CAC78AB-7CC9-4004-995C-C9C241211032","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f88ba05b48fde9c294ee0e41e564b9f19fbe16b0","datavalue":{"value":"W2099426626","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$80960D20-3AF7-4349-B909-3F7D106297FF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$97EF8D81-2D3B-4475-8FE7-3E8861E46DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f39c2c83dbbb50b5b0bb84dd916cc610bc3a4e9","datavalue":{"value":{"entity-type":"item","numeric-id":5425417,"id":"Q5425417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$21D10BAD-8B16-4434-BFBB-7A51FD107C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6989014e34d3a9775035abf0cfcc3b2c1b5a10b","datavalue":{"value":{"entity-type":"item","numeric-id":4110996,"id":"Q4110996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$68C5FFBE-04C5-4DEF-8313-A917E9E1D82D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$88736C34-97E8-449F-906E-257C578C00CA","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":"Q2339960$24CDFFEC-73BB-413C-96B9-F63AD64EAAEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ecd81987eb2b3620646f2d151ff26bdb537b884","datavalue":{"value":{"entity-type":"item","numeric-id":4001935,"id":"Q4001935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$87141627-3B44-4525-8E66-6155875C38CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c6d07dd80de4de8f6f1d51aa5d78e790a6fd51","datavalue":{"value":{"entity-type":"item","numeric-id":5812175,"id":"Q5812175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$912A329C-4916-492A-9D8E-C8CC3C0E4CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fa34ae3e34f6a863a9f8db67c2bfb8bb6401943","datavalue":{"value":{"entity-type":"item","numeric-id":4856172,"id":"Q4856172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$6928E088-78F6-4109-875F-2707F3C5E1E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"352a2a41026a9aea11c54f3081aa8074c4dc9983","datavalue":{"value":{"entity-type":"item","numeric-id":4154547,"id":"Q4154547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2339960$CF393E7A-AA23-4833-8D92-1C9B5424B22B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eedc36e4702891c67f1073243152336f28a11875","datavalue":{"value":"10.1007/S00153-014-0416-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2339960$F7300343-3C14-4BA5-ABB7-99CA5A044DFA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f23811a5eb20ae9ffcbe0ad0ded14336a5980d2","datavalue":{"value":{"entity-type":"item","numeric-id":4351930,"id":"Q4351930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"362407b9cbb79f680b14b7b6734233c3f1ff82dc","datavalue":{"value":{"amount":"+0.7604966163635254","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":"Q2339960$1DC7BA10-8E8D-42F3-B7C9-49D228F2742E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fbb8f88af23cbb78c72a5a523ec48ca43ada8a1","datavalue":{"value":{"entity-type":"item","numeric-id":5425417,"id":"Q5425417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f1abc6fc1a0a1208d53562a53b5770bef9565f4","datavalue":{"value":{"amount":"+0.7513042688369751","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":"Q2339960$A91E1D3F-1A3C-4D9A-876F-7D608F51BF78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaf7a18299e9fb9ade88dbd653b062d10a36e6ed","datavalue":{"value":{"entity-type":"item","numeric-id":1117212,"id":"Q1117212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52cea8bd9654ac4bab69b67f37a7e29b591c574d","datavalue":{"value":{"amount":"+0.7200852036476135","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":"Q2339960$B728F979-F199-4A8E-91B8-9BE986ECF6DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15c20e227107b8e6cbdd24a1384b3faf5ab7efa3","datavalue":{"value":{"entity-type":"item","numeric-id":4359314,"id":"Q4359314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5543a6d67a8ec1286de1d51fe7efe9a19c3ce102","datavalue":{"value":{"amount":"+0.7162320017814636","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":"Q2339960$4C296BBE-AD0D-48D9-B812-B33D45F10DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e38d87a41576350bc11313d34b474f32976283c8","datavalue":{"value":{"entity-type":"item","numeric-id":2322259,"id":"Q2322259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb1bc1dcf32fd8a6853955a938c0588aea94abad","datavalue":{"value":{"amount":"+0.7159081101417542","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":"Q2339960$D83B6819-F9DB-4BBF-9161-FD8D87D1A1C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A new proof of Ajtai's completeness theorem for nonstandard finite structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_new_proof_of_Ajtai%27s_completeness_theorem_for_nonstandard_finite_structures"}}}}}