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 I

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

### Summary.

We prove a number of auxiliary facts about graphs, mainly about vertex sequences of chains and oriented chains. Then we define a graph to be {\em well-founded} if for each vertex in the graph the length of oriented chains ending at the vertex is bounded. A {\em well-founded} graph does not have directed cycles or infinite descending chains. In the second part of the article we prove some auxiliary facts about free algebras and locally-finite algebras.

This work was partially supported by NSERC Grant OGP9207.

#### MML Identifier: MSSCYC_1

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

#### Contents (PDF format)

1. Some properties of graphs
2. Some properties of many sorted algebras

#### Bibliography

[1] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.
[2] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
[3] Grzegorz Bancerek. Introduction to trees. Journal of Formalized Mathematics, 1, 1989.
[4] Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.
[5] Grzegorz Bancerek. Cartesian product of functions. Journal of Formalized Mathematics, 3, 1991.
[6] Grzegorz Bancerek. K\"onig's Lemma. Journal of Formalized Mathematics, 3, 1991.
[7] Grzegorz Bancerek. Sets and functions of trees and joining operations of trees. Journal of Formalized Mathematics, 4, 1992.
[8] Grzegorz Bancerek. Joining of decorated trees. Journal of Formalized Mathematics, 5, 1993.
[9] Grzegorz Bancerek. Subtrees. Journal of Formalized Mathematics, 6, 1994.
[10] Grzegorz Bancerek. Terms over many sorted universal algebra. Journal of Formalized Mathematics, 6, 1994.
[11] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
[12] Grzegorz Bancerek and Piotr Rudnicki. On defining functions on trees. Journal of Formalized Mathematics, 5, 1993.
[13] Ewa Burakowska. Subalgebras of many sorted algebra. Lattice of subalgebras. Journal of Formalized Mathematics, 6, 1994.
[14] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[15] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.
[16] Czeslaw Bylinski. Partial functions. Journal of Formalized Mathematics, 1, 1989.
[17] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.
[18] Patricia L. Carlson and Grzegorz Bancerek. Context-free grammar --- part I. Journal of Formalized Mathematics, 4, 1992.
[19] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.
[20] Agata Darmochwal and Yatsuka Nakamura. The topological space $\calE^2_\rmT$. Arcs, line segments and special polygonal arcs. Journal of Formalized Mathematics, 3, 1991.
[21] Krzysztof Hryniewiecki. Graphs. Journal of Formalized Mathematics, 2, 1990.
[22] Malgorzata Korolkiewicz. Homomorphisms of many sorted algebras. Journal of Formalized Mathematics, 6, 1994.
[23] Yatsuka Nakamura and Piotr Rudnicki. Vertex sequences induced by chains. Journal of Formalized Mathematics, 7, 1995.
[24] Yatsuka Nakamura, Piotr Rudnicki, Andrzej Trybulec, and Pauline N. Kawamoto. Preliminaries to circuits, II. Journal of Formalized Mathematics, 6, 1994.
[25] Andrzej Nedzusiak. $\sigma$-fields and probability. Journal of Formalized Mathematics, 1, 1989.
[26] Beata Perkowska. Free many sorted universal algebra. Journal of Formalized Mathematics, 6, 1994.
[27] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.
[28] Andrzej Trybulec. Many-sorted sets. Journal of Formalized Mathematics, 5, 1993.
[29] Andrzej Trybulec. Many sorted algebras. Journal of Formalized Mathematics, 6, 1994.
[30] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.
[31] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.