Most General Algebraic Specifications for an Abstract Datatype of Rational Numbers

Published in Volume XXX, Issue 1, 2020, pages 1-24, doi: 10.7561/SACS.2020.1.1

Authors: J.A. Bergstra

Abstract

The notion of a most general algebraic specification of an arithmetical datatype of characteristic zero is introduced.Three examples of such specifications are given. A preference is formulated for a specification by means of infinitely many equations which can be presented via a finite number of so-called schematic equations phrased in terms of an infinite signature. On the basis of the latter specification three topics are discussed: (i) fracterm decomposition operators and the numerator paradox,  (ii) foundational specifications of arithmetical datatypes, and  (iii) poly-infix operations.

Full Text (PDF)

References

[1] J.A. Anderson, N. Völker, and A.A. Adams. Perspecx Machine VIII: Axioms of Transreal Arithmetic. In J. Latecki, D.M. Mount, A.Y. Wu (Eds.) SPIE 6499, Vision Geometry XV, 2007. doi:10.1117/12. 698153.

[2] J.A. Bergstra. Division by Zero, a Survey of Options. Transmathematica, 2019. doi:10.36285/tm.v0i0.17.

[3] J.A. Bergstra. Arithmetical Datatypes, Fracterms, and the Fraction Definition Problem. Transmathematica, 2020. doi:10.36285/tm.v0i0.1710.36285/tm.33.

[4] J.A. Bergstra, I. Bethke. A Negative Result on the Algebraic Specification of the Meadow of Rational Numbers. 2016. arXiv:1507.00548v2.

[5] J.A. Bergstra, I. Bethke. Subvarieties of the Variety of Meadows. Scientific Annals of Computer Science. 27(1), 1-18, 2017. doi:10.7561/SACS.2017.1.1.

[6] J.A. Bergstra, I. Bethke, D. Hendriks. Universality of Univariate Mixed Fractions in Divisive Meadows. 2017 arXiv:1707.00499v1.

[7] J.A. Bergstra, I. Bethke, A. Ponse. Equations for Formally Real Meadows. Journal of Applied Logic 13(2), 1-23, 2015. doi:10.1016/j.jal.2015.01.004.

[8] J.A. Bergstra, J. Heering, P. Klint. Module Algebra. Journal of the ACM 37(2), 335-372, 1990. doi:10.1145/77600.77621.

[9] J.A. Bergstra, Y. Hirshfeld, J.V. Tucker. Meadows and the Equational Specification of Division. Theoretical Computer Science 410(12), 1261-1271, 2009. doi:10.1016/j.tcs.2008.12.015.

[10] J.A. Bergstra, C.A. Middelburg. Inversive Meadows and Divisive Meadows. Journal of Applied Logic 9(3): 203-220, 2011. doi:10.1016/j.jal.2011.03.001.

[11] J.A. Bergstra, C.A. Middelburg. Transformation of Fractions into Simple Fractions in Divisive Meadows. Journal of Applied Logic 16, 92-110, 2015. doi:10.1016/j.jal.2016.03.001.

[12] J.A. Bergstra, A. Ponse. Division by Zero in Common Meadows. In R. de Nicola, R. Hennicker (Eds.), Software, Services, and Systems – Essays Dedicated to Martin Wirsing on the Occasion of His Retirement from the Chair of Programming and Software Engineering, Lecture Notes in Computer Science 8950, 46-61, 2015. doi:10.1007/978-3-319-15545-6\_6.

[13] J.A. Bergstra, A. Ponse. Poly-Inx Operators and Operator Families. 2015. arXiv:1505.01087v1.

[14] J.A. Bergstra, A. Ponse. Fracpairs and Fractions Over a Reduced Commutative Ring. Indigationes Mathematicae 27, 727-748, 2016. doi:10.1016/j.indag.2016.01.007.

[15] J.A. Bergstra, J.V. Tucker. Initial and Final Algebra Semantics for Data Type Specification: Two Characterization Theorems. SIAM Journal on Computing 12(2), 366-387, 1983. doi:10.1137/0212024.

[16] J.A. Bergstra, J.V. Tucker. The Rational Numbers as an Abstract Data Type. Journal of the ACM 54(2), Article 7, 2007. doi:10.1145/1219092.1219095.

[17] I. Bethke, P.H. Rodenburg. The Initial Meadows. Journal of Symbolic Logic 75(3), 888-895, 2010. doi:10.2178/jsl/1278682205.

[18] I. Bethke, P.H. Rodenburg, A. Sevenster. The Structure of Finite Meadows. Journal of Logical and Algebraic Methods in Programming 84 (2), 276-282, 2015. doi:10.1016/j.jlamp.2014.08.004.

[19] J. Carlström. Wheels-On Division by Zero. Mathematical Structures in Computer Science 14(1), 143-184, 2004. doi:10.1017/S0960129503004110.

[20] H.D. Ehrich, M. Wolf, J. Loeckx. Specification of Abstract Data Types (German Edition). Wiley & Teubner, 1997.

[21] M.I.F. Fandino Pinilla. Fractions: Conceptual and Didactic Aspects. Acta Didactica Universitatis Comenianae 7, 82-115, 2007.

[22] J.A. Goguen. Memories of ADJ. In G. Rozenberg, A. Salomaa (Eds.) Current Trends in Theoretical Computer Science – Essays and Tutorials 40, 76-81, 1993. doi:10.1142/9789812794499\_0004.

[23] S.J. Lamon. Teaching Fractions and Ratios for Understanding-Essential Content Knowledge and Instructional Strategies for Teachers (3rd Edition). Routledge, 2012. doi:10.4324/9780203803165.

[24] F.J. Mueller. On the Fraction as a Numeral. The Arithmetic Teacher 8(5), 234-238, 1961. jstor:41184445.

[25] J.-.F. Nicaud, D. Bouhineau, J.-M. Gelis. Syntax and Semantics in Algebra. Proceedings of the 12th ICMI Study Conference, The University of Melbourne, Australia, 2001. hal:00962023.

[26] H. Ono. Equational Theories and Universal Theories of Fields. Journal of the Mathematical Society of Japan 35(2), 289-306, 1983. doi:10.2969/jmsj/03520289.

[27] H. M. Pycior. Early Critcism of the Symbolical Approach to Algebra. Historia Mathematica 9(4), 392-412, 1992. doi:10.1016/0315-0860(82)90105-7.

[28] S. Rollnik. Das pragmatische Konzept für den Bruchrechenunterricht (In German). PhD thesis, University of Flensburg, Germany, 2009.

[29] H. van Engen. Rate Pairs, Fractions, and Rational Numbers. The Arithmetic Teacher 7(8), 389-399, 1960. jstor:41184353.

[30] A. Setzer. Wheels (draft). 1997. http://www.cs.swan.ac.uk/~csetzer/articles/wheel.pdf.

Bibtex

@article{sacscuza:bergstra20mgasadrn,
  title={Most General Algebraic Specifications for an Abstract Datatype of Rational Numbers},
  author={J.A. Bergstra},
  journal={Scientific Annals of Computer Science},
  volume={30},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2020},
  pages={1–24},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2020.1.1}
}