{"entities":{"Q2266708":{"pageid":2277451,"ns":120,"title":"Item:Q2266708","lastrevid":71717334,"modified":"2026-04-14T00:05:07Z","type":"item","id":"Q2266708","labels":{"en":{"language":"en","value":"All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3895034"}},"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":"Q2266708$9F0182CF-D37D-4680-A952-E7366CDFB003","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"696b2a0b7bdb6346c20ac59fff694c2c5f9546fc","datavalue":{"value":{"text":"All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2266708$9840F0F7-D040-4C1D-858E-2C4545D10561","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a37e04fa8a74f1e469d14a7b15ab77b8e03d6148","datavalue":{"value":"0562.03006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266708$C0D623C2-1F09-4BC9-8BFA-34FBAE097FBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"78b8c106a117c6aa153086ba315e62a75454ec62","datavalue":{"value":"10.1016/0012-365X(85)90144-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266708$E04D6D8B-EA56-4FE8-B5AE-37F080E0F7D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3bd3332221caea6d47c524c4ab128bd0030b6f84","datavalue":{"value":{"entity-type":"item","numeric-id":1401350,"id":"Q1401350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266708$59D03521-B51E-45A2-ACA8-044BE71B7F78","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266708$321ACA63-6FA2-40C1-AC89-B36BE2519958","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":"Q2266708$1BF4AF4D-8D2D-4E03-A099-0A9E4AAAD063","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6555a05a6ac0752b56c66852bcab3cbeea6648fd","datavalue":{"value":"The study of representability in arithmetic goes back to G\u00f6del who showed in 1931 that the exponential function can be first-order defined in the structure \\(<{\\mathbb{N}},+,\\circ,=>\\) where \\({\\mathbb{N}}\\) denotes the set of non-negative integers; he actually proved that inductive definitions - which in fact are not first order definitions but second-order definitions - can be translated as first-order formulas of the language \\(\\{+,\\circ,=\\}.\\)    A natural problem related to G\u00f6del's result is to determine families of arithmetical relations and functions from which \\(+\\), \\(\\circ\\) and \\(=\\) are first-order definable; such families will be called synonymous with \\(\\{+,\\circ,=\\}\\). Robinson (1949) showed that \\(\\{\\) S,\\(| \\}\\) (where \\(|\\) stands for the divisibility relation) is synonymous with \\(\\{+,\\circ,=\\}\\). She asked whether \\(\\{+,\\perp \\}\\), and \\(\\{\\) S,\\(\\perp \\}\\) are synonymous (where \\(\\perp\\) stands for the relation of coprimeness, i.e. \\(\\{(x,y)\\in {\\mathbb{N}}^ 2|\\) x and y are relatively prime\\(\\})\\). The synonymy of \\(\\{+,\\circ,=\\}\\) with \\(\\{+,\\perp \\}\\) has been proved independently by Robinson (unpublished), \\textit{A. Woods} [Thesis, Univ. Manchester (1981)] and the author. The synonymy of \\(\\{+,\\circ,=\\}\\) and \\(\\{\\) S,\\(\\perp \\}\\) is still open. The interest of this last problem has been emphasized by Wood's thesis, where it is demonstrated that the synonymy of \\(\\{+,\\circ,=\\}\\) and \\(\\{\\) S,\\(\\perp \\}\\) is equivalent to the following conjecture: Is there an integer k such that, for all x and y, the equality \\(x=y\\) holds if and only if \\((x+i)\\) and \\((y+i)\\) have the same prime divisors for \\(i=0,1,2,...,k.\\)    Woods also proved in this thesis that \\(\\{\\leq,\\perp \\}\\) is synonymous with \\(\\{+,\\circ,=\\}\\); we have shown that \\(\\{EXP_ p,S,\\perp \\}\\) (where \\(EXP_ p\\) denotes the function \\(x\\mapsto p^ x\\) for any fixed prime p) is also synonymous with \\(\\{+,\\circ,=\\}.\\)    We show in this paper that all recursive relations and functions over the set of powers of primes are \\(\\{\\) S,\\(\\perp \\}\\)-definable in \\({\\mathbb{N}}\\); in particular, this is true for the restriction to that set of the order relation and of the exponentiation \\((x,y)\\mapsto x^ y\\). The techniques used are coding devices based on \\(\\alpha)\\) the existence of prime(s) dividing \\(x^ n-1\\) (resp. \\(x^ n+1)\\) but no \\(x^ m-1\\) (resp. \\(x^ m+1)\\) for \\(0<m<n\\) (result due to Zsigmondy (1892) and Birkhoff-Vandiver (1904)); \\(\\beta)\\) the existence of prime solutions of certain congruence systems (a result combining the chinese remainders theorem and Dirichlet's theorem). This permits to develop a sort of finite set theory over the structure \\(<{\\mathbb{N}},S,\\perp >\\). Device \\(\\alpha)\\) gives convenient codes for finite subsets of \\({\\mathbb{N}}\\) and device \\(\\beta)\\) provides sorts of choice functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266708$FC2AAB31-B7EA-4CF7-875B-F4800E6A81CD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c06e0874e30722381d620ef69fb36c407a01cb04","datavalue":{"value":"03B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266708$05DE8187-8378-4092-85D5-C056280F76DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266708$196AB798-1D3E-456C-A3B3-578304CA0A91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b005c014736a7656397e4e62621d15941080b2c3","datavalue":{"value":"3895034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266708$3F807385-D63C-48A9-9DD3-1249E0A946B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29e85a61e7939ee6f14f83214f0f77882dcad4fc","datavalue":{"value":"first-order arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266708$C0CAA574-EB30-4EB7-AF08-85D219944266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ddc84d0bd7587c2bd86897b4a6314bdd2914d19","datavalue":{"value":"coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266708$3942E01D-9A17-4728-8267-92D9091D6EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f736d02e86573c887541b685d4ac9ad40d12259b","datavalue":{"value":"first-order definability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266708$51773676-CB38-4D14-A549-202744FECABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de2add0c870e112e20d46c0f9e9f2a9ddab2a09a","datavalue":{"value":"isomorphic reinterpretation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266708$17CFDE02-997F-49D2-88B9-FE49FBE6B220","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":"Q2266708$65B3BE16-39F8-4666-88BB-722C3DCDCF47","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae82ec9051de413b345d3f4d7d16e27298e06adc","datavalue":{"value":{"entity-type":"item","numeric-id":3218118,"id":"Q3218118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266708$F3858530-DD82-4DB8-81D4-ED9564AAFEB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73ea1a986b8212f90121d21e0a14bb9807498264","datavalue":{"value":{"entity-type":"item","numeric-id":5791204,"id":"Q5791204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266708$B6F6142E-6E18-4D22-BC56-C95EB0607F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3213aeba5d7351e6fdd1d683def3e6a568bc077e","datavalue":{"value":{"entity-type":"item","numeric-id":3863937,"id":"Q3863937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266708$8F8FA646-BE8D-4EC8-9194-E5E4F2A2826B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be156d9810b97fc2fa97349425dd32c263bb9228","datavalue":{"value":{"entity-type":"item","numeric-id":3701419,"id":"Q3701419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d3c1d93a8bd18b259a2ecc1184a13d56b8e1e0a","datavalue":{"value":{"amount":"+0.8785892128944397","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":"Q2266708$7E45912F-B8BD-40CB-B705-6F376CE3FAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d27b5bd94db008d186559cd2e75bc3cc451080cf","datavalue":{"value":{"entity-type":"item","numeric-id":3478404,"id":"Q3478404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65485a7b2b4a8eb1f48185e7171a9b6f442f769e","datavalue":{"value":{"amount":"+0.8624270558357239","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":"Q2266708$7EAFB6B1-CA3F-440E-AD75-D13726E62C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"601d854961b175ad91d2c12dc6ab25232a5a39c0","datavalue":{"value":{"entity-type":"item","numeric-id":3714077,"id":"Q3714077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"145ace314c9114628625fbe3cc6a227fbdace7be","datavalue":{"value":{"amount":"+0.8493857383728027","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":"Q2266708$EC4A74CB-ABE6-426C-BDF0-E2E1DE8806A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb5bf130b92c8150f46f4703df86eed1301665eb","datavalue":{"value":{"entity-type":"item","numeric-id":3834042,"id":"Q3834042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2de60924a6d976efb5b2f3cf0aec496fae3c46f3","datavalue":{"value":{"amount":"+0.8443346619606018","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":"Q2266708$EF7972A9-29C4-494B-BEB0-9411F69A2F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f7702578785a543f2b7b2de15c75cd1f8db16e9","datavalue":{"value":{"entity-type":"item","numeric-id":4894724,"id":"Q4894724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3adcc6192c4754f2999c3b8ed057b78b66195d7","datavalue":{"value":{"amount":"+0.7998641133308411","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":"Q2266708$C75205DF-C60F-4AEE-8F29-272E26F74E61","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate","badges":[]}}}}}