SMALL MODELS OF THE HIGH SCHOOL IDENTITIES (Q4039446)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 179566
Language Label Description Also known as
default for all languages
No label defined
    English
    SMALL MODELS OF THE HIGH SCHOOL IDENTITIES
    scientific article; zbMATH DE number 179566

      Statements

      SMALL MODELS OF THE HIGH SCHOOL IDENTITIES (English)
      0 references
      0 references
      0 references
      1 June 1993
      0 references
      high school identities
      0 references
      Wilkie's identity
      0 references
      finite models
      0 references
      equational theory
      0 references
      small countermodel
      0 references
      quotients
      0 references
      In the 1960's Tarski asked if the set HSI of eleven basic identities which one learns in high school about the natural numbers \(\mathbb{N}=\langle N,+,\times,\uparrow,1\rangle\) form a basis for the equational theory of \(\mathbb{N}\). In 1980 Wilkie found an identity \(W(x,y)\) which was true of \(\mathbb{N}\) but did not follow from the high school identities, answering Tarski's question in the negative. His proof that \(W(x,y)\) does not follow from HSI was rather complicated; and in 1985 R. Gurevic gave a new proof using a 59 element model of HSI which did not satisfy \(W(x,y)\). Our paper was inspired by a question of Ward Henson as to whether or not one could find a very small countermodel, say with just 5 elements, to \(W(x,y)\). This would provide a truly simple proof of Wilkie's theorem. We are able to show that the smallest countermodel has between 7 and 15 elements. In addition to establishing these bounds, and exhibiting a 15 element countermodel, we look at some fascinating questions connected with the quotients of \(\mathbb{N}\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references