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

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)

Some properties of graphs
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.

Received February 14, 1996

[ Download a postscript version, MML identifier index, Mizar home page]