About Graph Complements
Summary This article formalizes different variants of the complement graph in the Mizar system [3], based on the formalization of graphs in [6].
About Quotient Orders and Ordering Sequences
Summary In preparation for the formalization in Mizar [4] of lotteries as given in [14], this article closes some gaps in the Mizar Mathematical Library (MML) regarding relational structures. The quotient order is introduced by the equivalence relation identifying two elements x, y of a preorder as equivalent if x ⩽ y and y ⩽ x. This concept is known (see e.g. chapter 5 of [19]) and was first introduced into the MML in [13] and that work is incorporated here. Furthermore given a set A, partition D of A and a finite-support function f : A → ℝ, a function Σ f : D → ℝ, Σ f (X)= ∑ x∈X f(x) can be defined as some kind of natural “restriction” from f to D. The first main result of this article ca…
Some Remarks about Product Spaces
Summary This article covers some technical aspects about the product topology which are usually not given much of a thought in mathematics and standard literature like [7] and [6], not even by Bourbaki in [4]. Let {Ti}i∈I be a family of topological spaces. The prebasis of the product space T = ∏ i∈I Ti is defined in [5] as the set of all π −1 i (V) with i ∈ I and V open in Ti . Here it is shown that the basis generated by this prebasis consists exactly of the sets ∏ i∈I Vi with Vi open in Ti and for all but finitely many i ∈ I holds Vi = Ti . Given I = {a} we have T ≅ Ta , given I = {a, b} with a≠ b we have T ≅ Ta ×Tb . Given another family of topological spaces {Si}i∈I such that Si ≅ Ti fo…
Underlying Simple Graphs
Summary In this article the notion of the underlying simple graph of a graph (as defined in [8]) is formalized in the Mizar system [5], along with some convenient variants. The property of a graph to be without decorators (as introduced in [7]) is formalized as well to serve as the base of graph enumerations in the future.
Miscellaneous Graph Preliminaries
Summary This article contains many auxiliary theorems which were missing in the Mizar Mathematical Library [2] to the best of the author’s knowledge. Most of them regard graph theory as formalized in the GLIB series (cf. [8]) and most of them are preliminaries needed in [7] or other forthcoming articles.
Miscellaneous Graph Preliminaries. Part I
Summary This article contains many auxiliary theorems which were missing in the Mizar Mathematical Library to the best of the author’s knowledge. Most of them regard graph theory as formalized in the GLIB series and are needed in upcoming articles.
Extended Natural Numbers and Counters
Summary This article introduces extended natural numbers, i.e. the set ℕ ∪ {+∞}, in Mizar [4], [3] and formalizes a way to list a cardinal numbers of cardinals. Both concepts have applications in graph theory.
About Supergraphs. Part III
Summary The previous articles [5] and [6] introduced formalizations of the step-by-step operations we use to construct finite graphs by hand. That implicitly showed that any finite graph can be constructed from the trivial edgeless graph K 1 by applying a finite sequence of these basic operations. In this article that claim is proven explicitly with Mizar[4].
Unification of Graphs and Relations in Mizar
Summary A (di)graph without parallel edges can simply be represented by a binary relation of the vertices and on the other hand, any binary relation can be expressed as such a graph. In this article, this correspondence is formalized in the Mizar system [2], based on the formalization of graphs in [6] and relations in [11], [12]. Notably, a new definition of createGraph will be given, taking only a non empty set V and a binary relation E ⊆ V × V to create a (di)graph without parallel edges, which will provide to be very useful in future articles.
Natural Addition of Ordinals
Summary In [3] the existence of the Cantor normal form of ordinals was proven in the Mizar system [6]. In this article its uniqueness is proven and then used to formalize the natural sum of ordinals.
Refined Finiteness and Degree Properties in Graphs
Summary In this article the finiteness of graphs is refined and the minimal and maximal degree of graphs are formalized in the Mizar system [3], based on the formalization of graphs in [4].
About Graph Mappings
Summary In this articles adjacency-preserving mappings from a graph to another are formalized in the Mizar system [7], [2]. The generality of the approach seems to be largely unpreceeded in the literature to the best of the author’s knowledge. However, the most important property defined in the article is that of two graphs being isomorphic, which has been extensively studied. Another graph decorator is introduced as well.
About Vertex Mappings
Summary In [6] partial graph mappings were formalized in the Mizar system [3]. Such mappings map some vertices and edges of a graph to another while preserving adjacency. While this general approach is appropriate for the general form of (multidi)graphs as introduced in [7], a more specialized version for graphs without parallel edges seems convenient. As such, partial vertex mappings preserving adjacency between the mapped verticed are formalized here.
About Graph Unions and Intersections
Summary In this article the union and intersection of a set of graphs are formalized in the Mizar system [5], based on the formalization of graphs in [7].