{"entities":{"Q6545087":{"pageid":14156241,"ns":120,"title":"Item:Q6545087","lastrevid":55668364,"modified":"2026-02-17T20:42:57Z","type":"item","id":"Q6545087","labels":{"en":{"language":"en","value":"Forbidden induced subgraphs and the \u0141o\u015b-Tarski theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7854629"}},"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":"Q6545087$92E5AFDB-F2B5-42DF-A878-6733B0DBCEC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba57eda3825b28f7b90f113b880fede0edae7980","datavalue":{"value":{"text":"Forbidden induced subgraphs and the \u0141o\u015b-Tarski theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6545087$4207340C-05FD-4366-B50D-992C81464A52","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8704f55b81438dec9b36ef863240a213d13e9a33","datavalue":{"value":{"entity-type":"item","numeric-id":490657,"id":"Q490657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$1CC14426-A348-44C2-AAFA-724AD9896A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"533e6a2f2483a32398b8daadaa250165970e45d9","datavalue":{"value":{"entity-type":"item","numeric-id":490658,"id":"Q490658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$BE9A536E-C83D-4CCC-829F-30010DF228A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2c775b7be76488bf652b31b8283b5e517156ef32","datavalue":{"value":{"time":"+2024-05-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6545087$A055836F-3CDB-4F52-B74B-32804820A930","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f08edb2ac368796aa8a02c887ff5f572af1baed","datavalue":{"value":"A result of Los and Tarski implies that if \\(C\\) is the class of (finite and infinite) models of a first-order sentence \\(\\varphi\\) and \\(C\\) is closed under substructures, then there is a universal sentence \\(\\psi\\) such that \\(C\\) is also the class of models of \\(\\psi\\). It is known that the result does not hold if we instead let \\(C\\) be the class of finite models of \\(\\varphi\\). This paper strengthens this later ``negative'' result by proving that there is a first-order sentence \\(\\varphi\\) in the language of graphs such that the class \\(\\mathrm{Graph}_{fin}(\\varphi)\\) of finite undirected graphs that are models of \\(\\varphi\\) is closed under induced subgraphs but not aximatized by any universal sentence, which is equivalent to the nonexistence of a finite set of finite graphs \\(F\\) such that \\(\\mathrm{Graph}_{fin}(\\varphi)\\) is the class of finite graphs that do not have an induced subgraph isomorphic to a member of \\(F\\).\\N\\NThe authors then show that there is no algorithm which, for any first-order sentence \\(\\varphi\\) such that \\(\\mathrm{Graph}_{fin}(\\varphi)\\) is closed under induced subgraphs, decides whether \\(\\varphi\\) is equivalent, on finite graphs, to a universal sentence. Even if such a universal sentence exists, it is hard to find, since the authors also prove: There is no algorithm that, for any first-order sentence \\(\\varphi\\) that is equivalent to a universal sentence \\(\\psi\\) on finite graphs computes such \\(\\psi\\). Finally, they prove that there is no computable function \\(f\\) such that, for all \\(\\varphi\\) and \\(\\psi\\) as above, \\(|\\psi| \\leq f(|\\varphi|)\\) where \\(|\\psi|\\) and \\(|\\varphi|\\) are the lengths of \\(\\psi\\) and \\(\\varphi\\), respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6545087$B4D21738-0E1C-48F5-AFAB-7380CDD8D78F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"63d582552c02fffafb280152e2d5e020473417a2","datavalue":{"value":{"entity-type":"item","numeric-id":494646,"id":"Q494646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$01421DE3-4655-4AC1-B1D4-885835AD1F3D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b58df756e27df0e7b4d6d54dbbfd9015b563e63d","datavalue":{"value":"03C13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6545087$45D64435-2482-49CA-B8A7-A99D7369296F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6545087$CB00F2BD-324E-4612-B5E1-EC863B0176D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52396c8ceafc7d853b85970faf40f29f2bdb7712","datavalue":{"value":"7854629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6545087$78AF4129-EB8E-421D-99B6-BDF715CED31D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"873121a0edcc455b0008e61ee2cb42fbdc9ae381","datavalue":{"value":"preservation theorem for graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6545087$9866A186-AEB1-46F7-BB06-6FDB4BFAE67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0421a88d9599388a9af4b0e2102ab403f6c36e7f","datavalue":{"value":"finite model theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q6545087$F77ADB5C-5EA5-4B7B-BBF7-B97DE7C5C42D","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":"Q6545087$D6715210-3A74-44E4-BC71-6AFE772E3878","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"994e34bbc8e60f91f664220e14ef380ffbaf4d42","datavalue":{"value":{"entity-type":"item","numeric-id":4362725,"id":"Q4362725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$00432EA5-02C3-4A07-A61A-DC4F8B4103BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a0243f268a97be037123df33987f70eb9a79bb9","datavalue":{"value":{"entity-type":"item","numeric-id":3395035,"id":"Q3395035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$FD31B36C-9512-4916-9E6D-7DA9C160F882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"961ea460842f4e2008391c7bfa0e2e51f574f0fb","datavalue":{"value":{"entity-type":"item","numeric-id":5874201,"id":"Q5874201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$E3B602D2-325D-4D58-A4B4-4CD673A8A607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4753b4659469e60d103626aaca4d897985fe79a","datavalue":{"value":{"entity-type":"item","numeric-id":5428869,"id":"Q5428869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$CCA8875F-1167-47A5-A7D7-29A2D4E0330B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8e732ac24fced24328d5e2eb0ec178a3b48efbf","datavalue":{"value":{"entity-type":"item","numeric-id":4020706,"id":"Q4020706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$1E9E540A-4ED7-4828-9C7E-81A000321471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8093eacc214b074c62a67487eff17580caf521a","datavalue":{"value":{"entity-type":"item","numeric-id":5390610,"id":"Q5390610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$0BC694FC-35EF-4FE9-AD26-24ED62623348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34c67f651a094164e68836e8699323c4884fd8af","datavalue":{"value":{"entity-type":"item","numeric-id":412288,"id":"Q412288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$596EBFEB-2494-4644-8E80-16705F9F4134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c20ebeed862feb6e0841b92fd1c342102e628d","datavalue":{"value":{"entity-type":"item","numeric-id":4255575,"id":"Q4255575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$FB1F6197-C0DB-46BC-BD97-9BDEDF2A0A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ff516dc04d7555080c7d68d738a7f914b899ea7","datavalue":{"value":{"entity-type":"item","numeric-id":1342869,"id":"Q1342869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$BED259DB-F8B5-465C-97A6-37CA94973A7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e789f8888a8816e8086f3f08fa0eb4b344301cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5874333,"id":"Q5874333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$BC7D5E62-C6F7-4A01-983A-C8916A63CCDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b52d38642291b912b3c66870b59b7955113fa8a","datavalue":{"value":{"entity-type":"item","numeric-id":4625695,"id":"Q4625695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$ECA7389D-CAD8-4B3B-8DA9-6D0FA5F108D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5be26686519bb8e9a89243733e0e5570f5da5a3","datavalue":{"value":{"entity-type":"item","numeric-id":2912741,"id":"Q2912741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$83FABDC0-F8E2-408B-B68C-BA2F2B038A06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"632317fe51438065bf57941f71730a4664ec3cc8","datavalue":{"value":{"entity-type":"item","numeric-id":3758820,"id":"Q3758820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$BD464725-7096-4C09-8603-69AB26E46905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f54fad673f4c35626384a9f87e4fd22580dd23ea","datavalue":{"value":{"entity-type":"item","numeric-id":5848895,"id":"Q5848895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$341AA93A-319B-4969-9D58-74AD16890C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0faa9c95bdeaf3e64dedf9df1dabb427b484223b","datavalue":{"value":{"entity-type":"item","numeric-id":1235153,"id":"Q1235153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$421F61FA-A774-4F53-9EC2-D40D217A6737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8184aaf98b668acd5b2f8a968bacc120e77ebfc5","datavalue":{"value":{"entity-type":"item","numeric-id":3546368,"id":"Q3546368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$95CFC665-3CC0-46A2-9ED5-3FD829C1CA71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4abf9e50c4870444d159c1e9465ee00ecdeb0757","datavalue":{"value":{"entity-type":"item","numeric-id":2284179,"id":"Q2284179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$EFED6147-BD66-4A98-B9B3-B67EA6C44F7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"013917acbf15808e97ad1a6bcdcdb15805439fb1","datavalue":{"value":{"entity-type":"item","numeric-id":904143,"id":"Q904143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$C19B44BA-9B98-4C48-9A47-FF5C8ED1CBCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5903d75afa1437d26190a72d887538e5dfa1890","datavalue":{"value":{"entity-type":"item","numeric-id":3268307,"id":"Q3268307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$DDC28003-CD81-4BAD-B6FC-141396E268F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3e7d0ee4956d1a10738a5bbdb7fe0fbf6dfa5e","datavalue":{"value":{"entity-type":"item","numeric-id":5833216,"id":"Q5833216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$B2CE9980-6258-4FE0-B981-747C029485E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bdb22a75b41af474c1eaabbe0cf1b187535128f","datavalue":{"value":{"entity-type":"item","numeric-id":2413330,"id":"Q2413330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$FCA67A4E-84B0-40BE-8C14-0B4EF1C2981B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6218d42f0175ef35f91c4900eb5db86484a9463d","datavalue":{"value":{"entity-type":"item","numeric-id":2710590,"id":"Q2710590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6545087$DB527770-85F4-4138-889C-86C89D97983D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"03d4e2372254dd76a99bf8f7c08361eb61c0449e","datavalue":{"value":"10.1017/JSL.2023.99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6545087$DFC0BAD2-D487-40D9-8866-02DCCF7EA176","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6d7a6f92975ccd5498a85ec5628fc7210b9b6f6","datavalue":{"value":{"entity-type":"item","numeric-id":5278195,"id":"Q5278195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e9da3ca31e556c5ef4e64f02fc965164417f384","datavalue":{"value":{"amount":"+0.7380303740501404","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":"Q6545087$344BBDDF-23A5-4F73-A99C-FF7D1F08F40B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3ed56d7529dc25a98b5da3880a5c71a0fc3c57a","datavalue":{"value":{"entity-type":"item","numeric-id":259729,"id":"Q259729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bf4b05047cd357bca878a11a625fba72a53b78c","datavalue":{"value":{"amount":"+0.7301242351531982","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":"Q6545087$68FAAFFF-87AD-420C-89F9-1ED551C4FB34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d2c4bfffb867740547cca0ba64e6b985505f907","datavalue":{"value":{"entity-type":"item","numeric-id":2922040,"id":"Q2922040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76b906ad9997d85192baa2964a7f36430218e9d7","datavalue":{"value":{"amount":"+0.7277918457984924","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":"Q6545087$347EAACA-AF72-455E-8176-504F6E6DE621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b265a94fadff15b585c221c60c9ba5062b59e36a","datavalue":{"value":{"entity-type":"item","numeric-id":2986803,"id":"Q2986803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd8334b4f12474252cf06c6aeed42319ca0f9101","datavalue":{"value":{"amount":"+0.7241101264953613","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":"Q6545087$F25E0CEB-8ADA-496B-BDB1-4594920899A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6545087","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6545087"}}}}}