Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-28T10:00:28.199Z Has data issue: false hasContentIssue false
  • English
  • Français

Nowhere simplicity in matroids

Part of: Computability and recursion theory

Published online by Cambridge University Press:  09 April 2009

R. Downey
R. Downey
Affiliation:
Department of MathematicsNational University of SingaporeKent Ridge, 0511, Singapore
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We examine the concepts of nowhere simplicity in a wide class of abstract dependence systems. Initially we examine how many of the existing results valid for L(ω), the lattice of r.e. sets, have analogues valid for more general lattices. For example, we show that any r. e. subspace of V∞ can be decomposed into a pair of nowhere simple subspaces.

MSC classification

Secondary: 03D45: Theory of numerations, effectively presented structures 03D25: Recursively (computably) enumerable sets and degrees
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 35 , Issue 1 , August 1983 , pp. 28 - 45
Copyright
Copyright © Australian Mathematical Society 1983

References

[0]Ash, C. J. and Downey, R., ‘Decidable subspaces and recursively enumerable subspaces’, to appear.Google Scholar
[1]Baldwin, J. T., ‘Recursion theory and abstract dependence’, to appear.Google Scholar
[2]Crossley, J. N. and Nerode, A., ‘Recursive equivalence on matroids’, Aspects of effective algebra ed. Crossley, J. N. (∀ Book Company, Steel's Creek, Australia, 1981).Google Scholar
[3]Downey, R., ‘Abstract dependence and recursion theory’, Monash Logic paper No. 33.Google Scholar
[4]Downey, R., ‘On a question of Retzlaff’, Z. Math. Logik Grundlagen Math., to appear.Google Scholar
[5]Downey, R., ‘On the lattice of r.e. filters, axiomatizable theories and π01 classes’, submitted.Google Scholar
[6]Downey, R., ‘On bases of supermaximal subspaces and Steinitz systems’, in preparation.Google Scholar
[7]Metakides, G. and Nerode, A., ‘Recursively enumerable vector spaces’, Ann. Math. Logic 11 (1977) 147–171.Google Scholar
[8]Metakides, G. and Nerode, A., ‘Recursion theory on fields and abstract dependence’, J. Algebra 65 (1980) 36–59.Google Scholar
[9]Nerode, A. and Smith, R., ‘The undecidability of the lattice of recursively enumerable subspaces’, Proceedings of the Third Brazilion Conference on Mathematical Logic, pp. 245–252, eds. Arruda, , Da Costa, Sette (1982).Google Scholar
[10]Remmel, J. B., ‘Recursion theory on algebraic structures with independent sets’, Ann. Math. Logic 18 (1980) 153–191.CrossRefGoogle Scholar
[11]Retzlaff, A., ‘Direct summands of r.e. vector spaces’, Z. Math. Logik Grundlagen Math. 25 (1979) 363–372.Google Scholar
[12]Rogers, H. J. Jr, Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967).Google Scholar
[13]Shore, R., ‘Determining automorphism of recursively enumerable sets’, Proc. Amer. Math. Soc. 65 (1977), 318–326.Google Scholar
[14]Shore, R., ‘Nowhere simple sets and r.e. sets’, J. Symbolic Logic 43 (1978), 513–530.CrossRefGoogle Scholar
[15]Shore, R., ‘Controlling the dependence degree of a recursively enumerable vector space’, J. Symbolic Logic 43 (1978), 13–23.Google Scholar
[16]Shore, R., ‘The infinite injury priority method’, J. Symbolic Logic 41 (1976), 513–530.Google Scholar
[17]Yates, C. E. M., ‘Three theorems on the degrees of recursively enumerable sets’, Duke Math. J. 32 (1965), 461–468.CrossRefGoogle Scholar