{"entities":{"Q998136":{"pageid":999984,"ns":120,"title":"Item:Q998136","lastrevid":65821314,"modified":"2026-04-12T05:36:01Z","type":"item","id":"Q998136","labels":{"en":{"language":"en","value":"Complexity ranks of countable models"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5178764"}},"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":"Q998136$817BB775-5884-4F06-8F19-7A5AF7BCA68D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e372e1a417bab357a83271f637f7ee070c5e9ec1","datavalue":{"value":{"text":"Complexity ranks of countable models","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q998136$BE6A9E69-6F7B-49B2-B306-A72B42BE6B32","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a060a9f8049606fe14023e3f494116b555b922fb","datavalue":{"value":"1125.03026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$5A9498ED-2912-4E16-B994-300864E47639","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2b264e376d370e18d6d207d6d992ada669ebf5a","datavalue":{"value":{"entity-type":"item","numeric-id":195360,"id":"Q195360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q998136$AAD97B0E-459A-4818-9823-4505EB4D6973","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q998136$C48E1562-D0E8-46FF-AC29-4B706B66858F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"afb98c4ec1048abba6e7f701413ea5fbc62888f9","datavalue":{"value":{"time":"+2007-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q998136$5A415D8A-B4FD-4175-990F-B1EC4F7C126A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f5d3ddd797edf042502e32658888de363c62fcc","datavalue":{"value":"The Scott Isomorphism Theorem and its attendant analysis of countable models yields the following invariants. For \\(\\mathcal L\\) a countable relational language, \\(M\\) a countable \\(\\mathcal L\\)-structure, and \\(\\vec{a}\\in | M| ^n\\), \\(\\text{sr}_{M}(\\vec{a})\\) is the least \\(\\alpha<\\omega_1\\) such that for any \\(\\vec{b}\\in | M| ^n\\), \\((M, \\vec{a})\\equiv_{\\alpha}(M,\\vec{b})\\) implies \\((M, \\vec{a})\\cong (M, \\vec{b})\\). Further, \\(\\text{sr}(M)=\\text{sup}\\{\\text{sr}_{M}(\\vec{a})\\mid \\vec{a}\\in | M| ^n, n>0\\}\\) is called the Scott rank of \\(M\\).   The author discusses variants of Scott rank. Of particular interest is a notion of rank arising from the Ehrenfreuct-Fra\u00efss\u00e9 game version of \\(\\alpha\\)-equivalence. For \\(\\mathcal L\\)-structures \\(M\\) and \\(N\\), the two-person game that detects \\(\\alpha\\)-equivalence is denoted by \\(\\text{EF}_\\alpha(M,N)\\). For \\(M\\) countable, Scott's analysis produces a countable ordinal \\(\\alpha<\\text{sr}(M)+\\omega\\) such that whenever \\(N\\) is a countable \\(\\mathcal L\\)-structure with \\(N\\equiv_{\\alpha}M\\), then \\(N\\cong M\\); for this \\(\\alpha\\), player II having a winning strategy in \\(\\text{EF}_\\alpha(M,N)\\) means \\(M\\) and \\(N\\) are isomorphic. The least such ordinal for which this happens is called the game rank of \\(M\\) (\\(\\text{gr}(M)\\)). It is known that \\(\\text{gr}(M)\\leq\\text{sr}(M)+\\omega\\). The author presents an argument of Hjorth for the ``folklore'' inequality: \\(\\text{sr}(M)\\leq\\text{gr}(M)+\\omega\\).   The bulk of the article is taken up with an investigation of mono-unary algebras. These partially ordered structures arise from the relational version of the language \\(\\mathcal L=\\{f\\}\\), \\(f\\) a unary function. For \\(\\mathbb A\\) a mono-unary algebra and \\(x\\in\\mathbb A\\), \\(\\mathbb A(x)=\\{y\\in\\mathbb A\\mid x\\leq y\\}\\) is a tree. The author's main result is: for any \\(x\\in \\mathbb A\\), \\(\\text{gr}(\\mathbb A(x))\\leq \\omega+\\text{gr}(\\mathbb A)\\). The author points out that similar questions about linear orderings remain unresolved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q998136$001B1689-0694-45BE-AC84-842ABF980306","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"49ac28ac151a8a9103bbae52e8a00e91b3069fd7","datavalue":{"value":{"entity-type":"item","numeric-id":590477,"id":"Q590477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q998136$3F1DCE24-04FB-460B-AFB1-FCBE51B96F1D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a813b4bdb99e25945b5eea647242a11d10dedf0a","datavalue":{"value":"03C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$09FD7CC1-697B-491A-BAF0-0A80632B5990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fa744827be5f9a42ae7c118ff4838149cde7498","datavalue":{"value":"03C64","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$19BB0FFC-9801-462A-8BFF-2E3E921B4517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3636caf529c49b2a7d814c7a65de2b21aedf761","datavalue":{"value":"03E15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$4819E1F4-BC4E-4946-9901-C0C212E94E6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c34ade26e98bd3598696cdeb72b4377547f3ca99","datavalue":{"value":"5178764","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$CD0C8D18-90AC-4A85-9BCF-CA0FF6C8344B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef69e1d8e9b8aed3c88b4c50589048295d0e9656","datavalue":{"value":"isomorphism relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q998136$0DECBA8F-C768-46B3-8D3D-46022DEE88EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1972ba718f4ad2fb7fd6b7afb932489e10f77e60","datavalue":{"value":"Scott rank","type":"string"},"datatype":"string"},"type":"statement","id":"Q998136$1224746F-FDA5-47C6-9460-E908C1D4043D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1c530c0d66ca9cf6e87f660ae91928f341dc613","datavalue":{"value":"mono-unary algebras","type":"string"},"datatype":"string"},"type":"statement","id":"Q998136$D0766D03-2962-4457-90AA-E7D56564DEBB","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":"Q998136$5CF48757-BBB9-4366-B457-F53F9BADFC4C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b839d3c78dc15e4c81a15b0735294e9c91ad0f4","datavalue":{"value":"https://doi.org/10.1305/ndjfl/1172787543","type":"string"},"datatype":"url"},"type":"statement","id":"Q998136$F6CAFDD8-8EC0-455E-935C-29C3C9BE99F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a72ace48003343214e9e84ca170c89d97483cf13","datavalue":{"value":"W2085054174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$939A7984-5D40-4C8E-B00D-4314D3E163DE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6aba0d501f1599daae71ba8375666f7d96655a46","datavalue":{"value":"10.1305/NDJFL/1172787543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q998136$8373F12B-951B-4934-8BF3-903CB673AE93","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe02fe9857848298bddb584c270dfdbe4e996bed","datavalue":{"value":{"entity-type":"item","numeric-id":3676125,"id":"Q3676125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69996bc9b08513e9442e286194f56f20b8197c16","datavalue":{"value":{"amount":"+0.9073103","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$AB0D94E8-0769-43B3-BF69-9A7FD5ED0A95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2142f3c7344a2a839f746a307b444271a987c32","datavalue":{"value":{"entity-type":"item","numeric-id":4432545,"id":"Q4432545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7e4b169085dc1107d91a11d0a9624816e113926","datavalue":{"value":{"amount":"+0.9063046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$4FB89B12-7E2D-4B83-8980-279B667FFED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf646b040c58309b2841f74337423b56d660972d","datavalue":{"value":{"entity-type":"item","numeric-id":1057259,"id":"Q1057259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a61d24e2a8149409d0ea0092b28a73937ed537c8","datavalue":{"value":{"amount":"+0.90054655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$CEA79B3D-84E2-4519-AAD5-38C32D842589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3b8326c83d9be67a4d6cf9b0b70511b29893028","datavalue":{"value":{"entity-type":"item","numeric-id":2885255,"id":"Q2885255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49adb7412dd09ac047bee09b080b118c450bbffd","datavalue":{"value":{"amount":"+0.8913549","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$0805A3F9-45D6-4843-BD6B-E84F2842EAB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e6cfde227febc1d3a7139337cc5f044bc2fc298","datavalue":{"value":{"entity-type":"item","numeric-id":2303508,"id":"Q2303508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a91684f4016c493dd5c804c5491740cbfa96739a","datavalue":{"value":{"amount":"+0.88441896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$A36001AB-17B2-499D-8613-3C6DC6F71114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cc71ab4df00e6c11e4a533e3485923a5a5d1ab0","datavalue":{"value":{"entity-type":"item","numeric-id":5119907,"id":"Q5119907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7e19ef70dd714e326c6f3415d5f457c292b1c2d","datavalue":{"value":{"amount":"+0.8832655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$32144E25-D17C-4A7B-A631-951EC3916605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"897cecbd674041fc58668a8a413cb10077701308","datavalue":{"value":{"entity-type":"item","numeric-id":4526735,"id":"Q4526735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0acca3880fce441ff0aa888dbdd91f6306a4b50d","datavalue":{"value":{"amount":"+0.88307357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$BE47C80B-DFB2-4AD2-90BA-16A36766D32F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e186c85b9a2124e7741ee4560ede255b563955dc","datavalue":{"value":{"entity-type":"item","numeric-id":3988261,"id":"Q3988261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac2b5e9cbc7bdb515ba70344921d195a43bcd188","datavalue":{"value":{"amount":"+0.8826233","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$B786C25E-DD9E-4823-9EA3-17CB3E0CC495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f305f4ff18c83844141b6b7c6c17d817a3770925","datavalue":{"value":{"entity-type":"item","numeric-id":4372920,"id":"Q4372920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c4729d4cc8d09f62c3fed2b2ab145cd22ead7b4","datavalue":{"value":{"amount":"+0.8798727","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$F12F894A-10DA-48BE-B451-CAAA75F2FABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15b92d96393824d599e6830646d8ba277a793ae9","datavalue":{"value":{"entity-type":"item","numeric-id":5316385,"id":"Q5316385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81d318d6f75a5f683c079e2970e86e5630f2a1fd","datavalue":{"value":{"amount":"+0.8784288","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q998136$1B93E041-C092-45A1-A85C-11C241491C25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity ranks of countable models","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_ranks_of_countable_models"}}}}}