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
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
0.8877683281898499
0 references
0.887009859085083
0 references
0.8783409595489502
0 references
0.8595824241638184
0 references
0.8559552431106567
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