Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-25T14:11:45.740Z Has data issue: false hasContentIssue false
  • English
  • Français

Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings

Published online by Cambridge University Press:  15 January 2014

Jan Krajíček  and
Thomas Scanlon
Jan Krajíček
Affiliation:
Mathematical Institute, Academy Of Sciences žItná 25, Prague 115 67, The Czech RepublicE-mail:[email protected]
Thomas Scanlon
Affiliation:
Department Of Mathematics, University Of CaliforniaBerkeley, Ca 94720-3840, USAE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We recall the notions of weak and strong Euler characteristics on a first order structure and make explicit the notion of a Grothendieck ring of a structure. We define partially ordered Euler characteristic and Grothendieck ring and give a characterization of structures that have non-trivial partially ordered Grothendieck ring. We give a generalization of counting functions to locally finite structures, and use the construction to show that the Grothendieck ring of the complex numbers contains as a subring the ring of integer polynomials in continuum many variables. We prove the existence of a universal strong Euler characteristic on a structure. We investigate the dependence of the Grothendieck ring on the theory of the structure and give a few counter-examples. Finally, we relate some open problems and independence results in bounded arithmetic to properties of particular Grothendieck rings.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 6 , Issue 3 , September 2000 , pp. 311 - 330
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Ax, J., The elementary theory of finite fields, Annals of Mathematics, vol. 88 (1968), no. 2, pp. 239–271.CrossRefGoogle Scholar
[2] Beame, P., Impagliazzo, R., Krajíček, J., Pitassi, T., and Pudlák, P., Lower bounds on Hilbert's Nullstellensatz and propositional proofs, Proceedings of the London Mathematical Society, vol. (3) 73, 1996, pp. 1–26.CrossRefGoogle Scholar
[3] Krajíček, J., Bounded arithmetic, propositional logic, and complexity theory, Encyclopedia of Mathematics and Its Applications, vol. 60, Cambridge University Press, 1995.Google Scholar
[4] D'Aquino, P. and Macintyre, A., Non standard finite fields over I Δ0 + Ω1 , 1999, preprint.Google Scholar
[5] Denef, J. and Loeser, F., Germs of arcs on singular algebraic varieties and motivic integration, Inventiones Mathematicae, vol. 135 (1999), pp. 201–232.CrossRefGoogle Scholar
[6] Gromov, M., Endomorphisms of symbolic algebraic varieties, Journal of the European Mathematical Society, vol. 1 (04 1999), no. 2, pp. 109–236.CrossRefGoogle Scholar
[7] Haskell, D., K0(ℚp) = 0, unpublished notes, 1999.Google Scholar
[8] Krajíček, J., Uniform families of polynomial equations over a finite field and structures admitting an Euler characteristic of definable sets, Proceedings of the London Mathematical Society, preprint 1997, to appear.Google Scholar
[9] Krajíček, J., Pudlák, P., and Woods, A., Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle, Random Structures and Algorithms, vol. 7 (1995), no. 1, pp. 15–39.CrossRefGoogle Scholar
[10] Macintyre, A., Residue fields of models of P, Logic, methodology and philosophy of science (Cohen, L. E. et al., editors), 1982, pp. 193–206.Google Scholar
[11] Moreno, C., Algebraic Curves Over Finite Fields, Cambridge University Press, 1993.Google Scholar
[12] Parikh, R., Existence and feasibility in arithmetic, The Journal of Symbolic Logic, vol. 36 (1971), pp. 494–508.CrossRefGoogle Scholar
[13] Paris, J. B. and Harrington, L., A mathematical incompleteness in Peano Arithmetic, Handbook of Mathematical Logic (Barwise, J., editor), North-Holland, 1978, pp. 1133–1142.Google Scholar
[14] Paris, J. B., Wilkie, A. J., and Woods, A. R., Provability of the pigeonhole principle and the existence of infinitely many primes, The Journal of Symbolic Logic, vol. 53 (1988), pp. 1235–1244.CrossRefGoogle Scholar
[15] Pitassi, T., Beame, P., and Impagliazzo, R., Exponential lower bounds for the pigeonhole principle, Computational complexity, vol. 3 (1993), pp. 97–308.CrossRefGoogle Scholar
[16] Schanuel, S. H., Negative sets have Euler characteristic and dimension, Category Theory Como'90 (Carboni, A., Pedicchio, M., and Rosolini, G., editors), Lecture Notes in Mathematics, vol. 1488, Springer, 1991, pp. 379–385.CrossRefGoogle Scholar
[17] Shelah, S., Every two elementarily equivalent models have isomorphic ultrapowers, Israel Journal of Mathematics, vol. 10 (1971), pp. 224–233.CrossRefGoogle Scholar
[18] Toda, S, On the computational power of PP and ⊕P, Proceedings of the 30th IEEE Symposium on the Foundations of Computer Science, 1989, pp. 514–519.Google Scholar
[19] van den Dries, L., Tame topology and o-minimal structures, London mathematical society lecture note series, vol. 248, Cambridge University Press, 1998.Google Scholar