Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-26T19:41:12.606Z Has data issue: false hasContentIssue false
  • English
  • Français

Small decidable sheaves

Published online by Cambridge University Press:  12 March 2014

Andreas Blass  and
Andre Scedrov
Andreas Blass
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109
Andre Scedrov
Affiliation:
Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104
Get access Rights & Permissions [Opens in a new window]

Extract

Fred Richman conjectured that the following principle is not constructive:

(*) If A is a decidable subset of the set N of natural numbers and if, for every decidable subset B of N, either A ⊆ B or A ⊆ N − B, then, for some n ∈ N, A ⊆ {n}.

A set A of natural numbers is called decidable if ∀n(n ∈ A ∨ ⌉ (n ∈ A)) holds. In recursive models, this agrees with the recursion-theoretic meaning of decidability. In other contexts, “complemented” and “detachable” are often used.

Richman's conjecture was motivated by the problem of uniqueness of divisible hulls of abelian groups in constructive algebra. Richman showed that a countable discrete abelian p-group G has a unique (up to isomorphism over G) divisible hull if the subgroup pG is decidable. He also showed that the converse implies.

We confirm the nonconstructive nature of by showing (in §1) that it is not provable in intuitionistic set theory, IZF. Thus, in the models we construct, there are countable discrete abelian p-groups G whose divisible hulls are unique but whose subgroups pG are not decidable.

Our models do not satisfy further conditions imposed by Richman, namely Church's Thesis and Markov's Principle, so the full conjecture remains an open problem. We do, however, show (in §2) how to embellish our first model so that the fan theorem (i.e., compactness of 2N) fails. (Church's Thesis implies the stronger statement that the negation of the fan theorem holds.)

Our models will be constructed by the method of sheaf semantics [1], [3]. That is, we shall construct Grothendieck topoi in whose internal logic fails.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 51 , Issue 3 , September 1986 , pp. 726 - 731
Copyright
Copyright © Association for Symbolic Logic 1986

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]Boileau, A. and Joyal, A., La logique des topos, this Journal, vol. 46 (1981), pp. 6–16.Google Scholar
[2]Fourman, M., Sheaf models of set theory, Journal of Pure and Applied Algebra, vol. 19 (1980), pp. 91–101.CrossRefGoogle Scholar
[3]Fourman, M. and Hyland, J. M. E., Sheaf models for analysis, Applications of sheaves (Fourman, M.et al, editors), Lecture Notes in Mathematics, vol. 753, Springer-Verlag, Berlin, 1979, pp. 280–301.CrossRefGoogle Scholar
[4]Fourman, M. and Scott, D., Sheaves and logic, Applications of sheaves (Fourman, M.et al, editors), Lecture Notes in Mathematics, vol. 753, Springer-Verlag, Berlin, 1979, pp. 302–401.CrossRefGoogle Scholar
[5]Scedrov, A., Independence of the fan theorem in the presence of continuity principles, The L. E. J. Brouwer Centenary Symposium (Troelstra, A. and van Dalen, D., editors), North-Holland, Amsterdam, 1982, pp. 435–442.Google Scholar
[6]Scott, D., Extending the topological interpretation to intuitionistic analysis, Compositio Mathematica, vol. 20 (1968), pp. 194–210.Google Scholar