Journal of Formalized Mathematics
Volume 8, 1996
University of Bialystok
Copyright (c) 1996 Association of Mizar Users

## The Correspondence Between Monotonic Many Sorted Signatures and Well-Founded Graphs. Part II

Czeslaw Bylinski
Warsaw University, Bialystok
Piotr Rudnicki
University of Alberta, Edmonton

### Summary.

The graph induced by a many sorted signature is defined as follows: the vertices are the symbols of sorts, and if a sort $s$ is an argument of an operation with result sort $t$, then a directed edge $[s, t]$ is in the graph. The key lemma states relationship between the depth of elements of a free many sorted algebra over a signature and the length of directed chains in the graph induced by the signature. Then we prove that a monotonic many sorted signature (every finitely-generated algebra over it is locally-finite) induces a {\em well-founded} graph. The converse holds with an additional assumption that the signature is finitely operated, i.e. there is only a finite number of operations with the given result sort.

This work was partially supported by NSERC Grant OGP9207.

#### MML Identifier: MSSCYC_2

The terminology and notation used in this paper have been introduced in the following articles [21] [12] [26] [25] [1] [22] [27] [9] [11] [10] [14] [2] [4] [5] [6] [19] [3] [15] [16] [23] [24] [8] [20] [18] [17] [13] [7]

Contents (PDF format)

#### Bibliography

[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
[2] Grzegorz Bancerek. Introduction to trees. Journal of Formalized Mathematics, 1, 1989.
[3] Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.
[4] Grzegorz Bancerek. K\"onig's Lemma. Journal of Formalized Mathematics, 3, 1991.
[5] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. Journal of Formalized Mathematics, 4, 1992.
[6] Grzegorz Bancerek. Joining of decorated trees. Journal of Formalized Mathematics, 5, 1993.
[7] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
[8] Ewa Burakowska. Subalgebras of many sorted algebra. Lattice of subalgebras. Journal of Formalized Mathematics, 6, 1994.
[9] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[10] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.
[11] Czeslaw Bylinski. Partial functions. Journal of Formalized Mathematics, 1, 1989.
[12] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.
[13] Czeslaw Bylinski and Piotr Rudnicki. The correspondence between monotonic many sorted signatures and well-founded graphs. Part I. Journal of Formalized Mathematics, 8, 1996.
[14] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.
[15] Krzysztof Hryniewiecki. Graphs. Journal of Formalized Mathematics, 2, 1990.
[16] Yatsuka Nakamura and Piotr Rudnicki. Vertex sequences induced by chains. Journal of Formalized Mathematics, 7, 1995.
[17] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, I. Journal of Formalized Mathematics, 6, 1994.
[18] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, II. Journal of Formalized Mathematics, 6, 1994.
[19] Andrzej Nedzusiak. $\sigma$-fields and probability. Journal of Formalized Mathematics, 1, 1989.
[20] Beata Perkowska. Free many sorted universal algebra. Journal of Formalized Mathematics, 6, 1994.
[21] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.
[22] Andrzej Trybulec. Tuples, projections and Cartesian products. Journal of Formalized Mathematics, 1, 1989.
[23] Andrzej Trybulec. Many-sorted sets. Journal of Formalized Mathematics, 5, 1993.
[24] Andrzej Trybulec. Many sorted algebras. Journal of Formalized Mathematics, 6, 1994.
[25] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.
[26] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.
[27] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.