To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This method differs from the algebraic ones, mainly because it is able to find equational features of the extended objects. Two-ary integers turn out to form the free algebra corresponding to the Jónsson-Tarski's "paradoxical" equations. This entails that they have a "sum" operation as well as other operations of higher dimensions. Two-ary integers can provide LISP memories with convenient direct access jumps and the above low complexity hints at feasible hardware implementations.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1099,
author = {Gabriele Ricci},
title = {A semantic construction of two-ary integers},
journal = {Discussiones Mathematicae - General Algebra and Applications},
volume = {25},
year = {2005},
pages = {165-219},
zbl = {1098.08004},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1099}
}
Gabriele Ricci. A semantic construction of two-ary integers. Discussiones Mathematicae - General Algebra and Applications, Tome 25 (2005) pp. 165-219. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1099/
[000] [1] G.J. Chaitin, Algorithmic Information Theory, IBM J. Res. Develop. 21 (1977), 350-359, 496. | Zbl 0362.94035
[001] [2] G.J. Chaitin, Information-Thoretic Incompleteness (World Scientific, Singapore 1992).
[002] [3] R. Chuaqui, Axiomatic Set Theory (Nort-Holland, Mathematics Studies, Amsterdam 1981). | Zbl 0471.03049
[003] [4] H.B. Curry, R. Feys and W. Craig, Combinatory Logic, 1, (North-Holland, Amsterdam 1959). | Zbl 0175.27601
[004] [5] A. Goetz and C. Ryll-Nardzewski, On bases of abstract algebras, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 157-161. | Zbl 0123.00603
[005] [6] G. Grätzer, Universal Algebra, 2th ed., (Springer-Verlag, New York 1979).
[006] [7] J.R. Hindley and J.P. Seldin, Introduction to Combinators and l-Calculus (Cambridge University Press, London 1986). | Zbl 0614.03014
[007] [8] B. Jónsson and A. Tarski, Two general theorems concerning free algebras, Bull. Amer. Math. Soc. 62 (1956), 554.
[008] [9] E.G. Manes, Algebraic theories (Springer-Verlag, Berlin 1976).
[009] [10] E. Marczewski, Independence and homomorphisms in abstract algebras, Fund. Math. 50 (1961-62), 45-61. | Zbl 0104.25501
[010] [11] I. Mason and C. Talcott, Inferring the equivalence of functional program that mutate data, Theoretical Computer Science 105 (1992), 167-215. | Zbl 0768.68092
[011] [12] M.L. Minsky, Problems of formulation for Artificial IntelligenceR.E. Bellman, Mathematical Problems in the Biological Sciences, Proceedings of Symposia in Applied Mathematics XIV, American Mathematical Society, Providence, R.I. 1962, 35. | Zbl 0116.11803
[012] [13] J.D. Monk, Introduction to Set Theory (McGraw-Hill, New York 1969). | Zbl 0200.00066
[013] [14] G. Ricci, Universal eigenvalue equations, Pure Math.and Appl. Ser. B, 3, 2-3-4 (1992), 231-288. (Most of the misprints appear in ERRATA to Universal eigenvalue equations, Pure Math.and Appl. Ser. B, 5, 2 (1994), 241-243.).
[014] [15] G. Ricci, A Whitehead generator, Quaderni del Dipartimento di Matematica 86, (Universitá di Parma, Parma 1993).
[015] [16] G. Ricci, Two isotropy properties of 'universal eigenspaces' (and a problem for DT0L rewriting systems), G. Pilz, Contributions to General Algebra 9 (Verlag Hölder-Pichler-Tempsky, Wien 1995 - Verlag B.G. Teubner), 281-290. | Zbl 0884.08001
[016] [17] G. Ricci, New characterizations of universal matrices show that neural networks cannot be made algebraic, D. Dorninger, G. Eigenthaler, H.K. Kaiser, H. Kautschitsch, W. Moren and W.B. Müller, Contributions to General Algebra 10 (J. Hein Verlag, Klagenfurt 1998), 269-291.
[017] [18] G. Ricci, Boolean matrices ... neither Boolean nor matrices, Discuss. Math. General Algebra and Applications 20 (2000), 141-151. | Zbl 0964.08003
[018] [19] G. Ricci, Isomorphisms between analytic monoids, The Eighth International Workshop in Mathematics Gronów 2000, Institute of Mathematics, Technical University of Zielona Góra', September 25-29, 2000, 33.
[019] [20] G. Ricci, Some analytic features of algebraic data, Discrete Appl. Math. 122/1-3 (2002), 235-249. | Zbl 1002.68031
[020] [21] G. Ricci, Analytic monoids versus abstract monoids, Italian Journal of pure and Applied Mathematics, 16 (2004), 125-136. | Zbl 1177.08002
[021] [22] M. Servi, Classificazione dei Clan binari, Quaderni del Dipartimento di Matematica 113, (Universitá di Parma, Parma 1995).
[022] [23] M. Servi, Definizione dei clan binari e loro classificazione, Rend. Mat. Acc. Lincei (9) 9 (1998).
[023] [24] M. Servi, Due parole sui Clan di Ordine, Quaderni del Dipartimento di Matematica 186, (Universitá di Parma, Parma 1998).
[024] [25] M. Servi, I clan binari di ordine, Riv. Mat. Univ. Parma (6) 1 (1998), 207-214.
[025] [26] S. Świerckowski, Algebras independently generated by every n elements, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 7 (1959), 501-502. | Zbl 0091.03003
[026] [27] S. Świerckowski, Algebras which are independently generated by every n elements, Fund. Math. 49 (1960-61), 93-104.
[027] [28] D.S. Touretzky, Common LISP: a Gentle Introduction to Symbolic Computation (The Benjamin/Cummings Publishing Co. Inc, Redwood City 1990). | Zbl 0548.68005
[028] [29] C. Weissman, LISP 1.5 Primer (Dickenson, Belmont, Ca., 1967).
[029] [30] A.N. Whitehead, A treatise on Universal Algebra with Applications, 1, (Cambridge University Press, Cambridge 1898). | Zbl 29.0066.03