PDF

Discussiones Mathematicae General Algebra and Applications 25(2) (2005) 165-219
DOI: https://doi.org/10.7151/dmgaa.1099

A SEMANTIC CONSTRUCTION OF TWO-ARY INTEGERS

Gabriele Ricci

Universitá di Parma
Dipartimento di Matematica,
I-43100 Parma, Italy
e-mail: gabriele.ricci@unipr.it

Abstract

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.

Keywords: universal matrix, analytic monoid, LISP, semantics, jump.

CCS codes: E1, Fm.

2000 Mathematics Subject Classification: 08B20, 68P05.

References

[1]	G.J. Chaitin, Algorithmic Information Theory, IBM J. Res. Develop. 21 (1977), 350-359, 496.
[2]	G.J. Chaitin, Information-Thoretic Incompleteness (World Scientific, Singapore 1992).
[3]	R. Chuaqui, Axiomatic Set Theory (Nort-Holland, Mathematics Studies, Amsterdam 1981).
[]	H.B. Curry, R. Feys and W. Craig, Combinatory Logic, 1, (North-Holland, Amsterdam 1959).
[4]	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.
[5]	G. Grätzer, Universal Algebra, 2th ed., (Springer-Verlag, New York 1979).
[6]	J.R. Hindley and J.P. Seldin, Introduction to Combinators and l-Calculus (Cambridge University Press, London 1986).
[7]	B. Jónsson and A. Tarski, Two general theorems concerning free algebras, Bull. Amer. Math. Soc. 62 (1956), 554.
[8]	E.G. Manes, Algebraic theories (Springer-Verlag, Berlin 1976).
[9]	E. Marczewski, Independence and homomorphisms in abstract algebras, Fund. Math. 50 (1961-62), 45-61.
[10]	I. Mason and C. Talcott, Inferring the equivalence of functional program that mutate data, Theoretical Computer Science 105 (1992), 167-215.
[11]	M.L. Minsky, Problems of formulation for Artificial Intelligence, p. 35 in: R.E. Bellman, Mathematical Problems in the Biological Sciences, Proceedings of Symposia in Applied Mathematics XIV, American Mathematical Society, Providence, R.I. 1962.
[12]	J.D. Monk, Introduction to Set Theory (McGraw-Hill, New York 1969).
[13]	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.)
[14]	G. Ricci, A Whitehead generator, Quaderni del Dipartimento di Matematica 86, (Universitá di Parma, Parma 1993).
[15]	G. Ricci, Two isotropy properties of "universal eigenspaces" (and a problem for DT0L rewriting systems), p. 281-290 in: G. Pilz, Contributions to General Algebra 9 (Verlag Hölder-Pichler-Tempsky, Wien 1995 - Verlag B.G. Teubner).
[16]	G. Ricci, New characterizations of universal matrices show that neural networks cannot be made algebraic, p. 269-291 in: 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).
[17]	G. Ricci, Boolean matrices ... neither Boolean nor matrices, Discuss. Math. General Algebra and Applications 20 (2000), 141-151.
[18]	G. Ricci, Isomorphisms between analytic monoids, p. 33-33 in: The Eighth International Workshop in Mathematics Gronów 2000, Institute of Mathematics, Technical University of Zielona Góra", September 25-29, 2000.
[19]	G. Ricci, Some analytic features of algebraic data, Discrete Appl. Math. 122/1-3 (2002), 235-249.
[20]	G. Ricci, Analytic monoids versus abstract monoids, Italian Journal of pure and Applied Mathematics, 16 (2004), 125-136.
[21]	M. Servi, Classificazione dei Clan binari, Quaderni del Dipartimento di Matematica 113, (Universitá di Parma, Parma 1995).
[22]	M. Servi, Definizione dei clan binari e loro classificazione, Rend. Mat. Acc. Lincei (9) 9 (1998).
[23]	M. Servi, Due parole sui Clan di Ordine, Quaderni del Dipartimento di Matematica 186, (Universitá di Parma, Parma 1998).
[24]	M. Servi, I clan binari di ordine, Riv. Mat. Univ. Parma (6) 1 (1998), 207-214.
[25]	S. Świerckowski, Algebras independently generated by every n elements, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 7 (1959), 501-502.
[26]	S. Świerckowski, Algebras which are independently generated by every n elements, Fund. Math. 49 (1960-61), 93-104.
[27]	D.S. Touretzky, Common LISP: a Gentle Introduction to Symbolic Computation (The Benjamin/Cummings Publishing Co. Inc, Redwood City 1990).
[28]	C. Weissman, LISP 1.5 Primer (Dickenson, Belmont, Ca., 1967).
[29]	A.N. Whitehead, A treatise on Universal Algebra with Applications, 1, (Cambridge University Press, Cambridge 1898).

Received 3 May 2005