###### 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].

###### Diophantine Sets. Part II

## Summary

The article is the next in a series aiming to formalize the MDPR-theorem using the Mizar proof assistant [3], [6], [4]. We analyze four equations from the Diophantine standpoint that are crucial in the bounded quantifier theorem, that is used in one of the approaches to solve the problem.

Based on our previous work [1], we prove that the value of a given binomial coefficient and factorial can be determined by its arguments in a Diophantine way. Then we prove that two products

where *y > x* are Diophantine.

The formalization follows [10], Z. Adamowicz, P. Zbierski [2] as well as M. Davis [5].

###### Formalization of the MRDP Theorem in the Mizar System

## Summary

This article is the final step of our attempts to formalize the negative solution of Hilbert’s tenth problem.

In our approach, we work with the Pell’s Equation defined in [2]. We analyzed this equation in the general case to show its solvability as well as the cardinality and shape of all possible solutions. Then we focus on a special case of the equation, which has the form *x*
^{2}
*−* (*a*
^{2} − 1)*y*
^{2} = 1 [8] and its solutions considered as two sequences *n*-th element of these sequences can be obtained from lists of several basic Diophantine relations as linear equations, finite products, congruences and inequalities, or more precisely that the equation *x* = *y*
_{i}(*a*) is Diophantine. Following the post-Matiyasevich results we show that the equality determined by the value of the power function *y* = *x*
^{z} is Diophantine, and analogously property in cases of the binomial coe cient, factorial and several product [9].

In this article, we combine analyzed so far Diophantine relation using conjunctions, alternatives as well as substitution to prove the bounded quantifier theorem. Based on this theorem we prove MDPR-theorem that *every recursively enumerable set is Diophantine,* where recursively enumerable sets have been defined by the Martin Davis normal form.

The formalization by means of Mizar system [5], [7], [4] follows [10], Z. Adamowicz, P. Zbierski [3] as well as M. Davis [6].

###### Implicit Function Theorem. Part II

## Summary

In this article, we formalize differentiability of implicit function theorem in the Mizar system [3], [1]. In the first half section, properties of Lipschitz continuous linear operators are discussed. Some norm properties of a direct sum decomposition of Lipschitz continuous linear operator are mentioned here.

In the last half section, differentiability of implicit function in implicit function theorem is formalized. The existence and uniqueness of implicit function in [6] is cited. We referred to [10], [11], and [2] in the formalization.

###### Invertible Operators on Banach Spaces

## Summary

In this article, using the Mizar system [2], [1], we discuss invertible operators on Banach spaces. In the first chapter, we formalized the theorem that denotes any operators that are close enough to an invertible operator are also invertible by using the property of Neumann series.

In the second chapter, we formalized the continuity of an isomorphism that maps an invertible operator on Banach spaces to its inverse. These results are used in the proof of the implicit function theorem. We referred to [3], [10], [6], [7] in this formalization.

###### Isomorphisms from the Space of Multilinear Operators

## Summary

In this article, using the Mizar system [5], [2], the isomorphisms from the space of multilinear operators are discussed. In the first chapter, two isomorphisms are formalized. The former isomorphism shows the correspondence between the space of multilinear operators and the space of bilinear operators.

The latter shows the correspondence between the space of multilinear operators and the space of the composition of linear operators. In the last chapter, the above isomorphisms are extended to isometric mappings between the normed spaces. We referred to [6], [11], [9], [3], [10] in this formalization.

###### 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.

###### On Monomorphisms and Subfields

## Summary

This is the second part of a four-article series containing a Mizar [2], [1] formalization of Kronecker’s construction about roots of polynomials in field extensions, i.e. that for every field *F* and every polynomial *p* ∈ *F* [*X*]*\F* there exists a field extension *E* of *F* such that *p* has a root over *E*. The formalization follows Kronecker’s classical proof using *F* [*X*]*/<p>* as the desired field extension *E* [5], [3], [4].

In the first part we show that an irreducible polynomial *p* ∈ *F* [*X*]*\F* has a root over *F* [*X*]*/<p>*. Note, however, that this statement cannot be true in a rigid formal sense: We do not have *F* ⊆ [*X*]*/ < p >* as sets, so *F* is not a subfield of *F* [*X*]*/<p>*, and hence formally *p* is not even a polynomial over *F* [*X*]*/ < p >*. Consequently, we translate *p* along the canonical monomorphism *ϕ : F → F* [*X*]*/<p>* and show that the translated polynomial *ϕ* (*p*) has a root over *F* [*X*]*/<p>*.

Because *F* is not a subfield of *F* [*X*]*/<p>* we construct in this second part the field (*E \ ϕF* )∪*F* for a given monomorphism *ϕ : F → E* and show that this field both is isomorphic to *F* and includes *F* as a subfield. In the literature this part of the proof usually consists of saying that “one can identify *F* with its image *ϕF* in *F* [*X*]*/<p>* and therefore consider *F* as a subfield of *F* [*X*]*/<p>*”. Interestingly, to do so we need to assume that *F* ∩ *E* = ∅, in particular Kronecker’s construction can be formalized for fields *F* with *F* ∩ *F* [*X*] = ∅.

Surprisingly, as we show in the third part, this condition is not automatically true for arbitray fields *F* : With the exception of _{2} we construct for every field *F* an isomorphic copy *F′* of *F* with *F′* ∩ *F′* [*X*] *≠* ∅. We also prove that for Mizar’s representations of _{n}, and we have _{n} ∩ _{n}[*X*] = ∅, ∩ [*X*] = ∅ and ∩ [*X*] = ∅, respectively.

In the fourth part we finally define field extensions: *E* is a field extension of *F* iff *F* is a subfield of *E*. Note, that in this case we have *F* ⊆ *E* as sets, and thus a polynomial *p* over *F* is also a polynomial over *E*. We then apply the construction of the second part to *F* [*X*]*/<p>* with the canonical monomorphism *ϕ : F → F* [*X*]*/<p>*. Together with the first part this gives - for fields *F* with *F ∩ F* [*X*] = ∅ - a field extension *E* of *F* in which *p* ∈ *F* [*X*]*\F* has a root.

######
On Roots of Polynomials over *F*[*X*]/ 〈*p*〉

## Summary

This is the first part of a four-article series containing a Mizar [3], [1], [2] formalization of Kronecker’s construction about roots of polynomials in field extensions, i.e. that for every field *F* and every polynomial *p* ∈ *F* [*X*]*\F* there exists a field extension *E* of *F* such that *p* has a root over *E*. The formalization follows Kronecker’s classical proof using *F* [*X*]*/<p>* as the desired field extension *E* [9], [4], [6].

In this first part we show that an irreducible polynomial *p* ∈ *F* [*X*]*\F* has a root over *F* [*X*]*/<p>*. Note, however, that this statement cannot be true in a rigid formal sense: We do not have *F* ⊆ [*X*]*/ < p >* as sets, so *F* is not a subfield of *F* [*X*]*/<p>*, and hence formally *p* is not even a polynomial over *F* [*X*]*/ < p >*. Consequently, we translate *p* along the canonical monomorphism *ϕ*: *F* → *F* [*X*]*/<p>* and show that the translated polynomial *ϕ*(*p*) has a root over *F* [*X*]*/<p>*.

Because *F* is not a subfield of *F* [*X*]*/<p>* we construct in the second part the field (*E \ ϕF* )∪*F* for a given monomorphism *ϕ : F* → *E* and show that this field both is isomorphic to *F* and includes *F* as a subfield. In the literature this part of the proof usually consists of saying that “one can identify *F* with its image *ϕF* in *F* [*X*]*/<p>* and therefore consider *F* as a subfield of *F* [*X*]*/<p>*”. Interestingly, to do so we need to assume that *F ∩ E* =∅, in particular Kronecker’s construction can be formalized for fields *F* with *F \ F* [*X*] =∅.

Surprisingly, as we show in the third part, this condition is not automatically true for arbitray fields *F* : With the exception of _{2} we construct for every field *F* an isomorphic copy *F*
^{′} of *F* with *F′* ∩ *F′* [*X*] *≠*∅. We also prove that for Mizar’s representations of _{n}, and we have _{n} ∩ _{n}[*X*] = ∅, ∩ [*X*] = ∅and ∩ [*X*] = ∅, respectively.

In the fourth part we finally define field extensions: *E* is a field extension of *F* i *F* is a subfield of *E*. Note, that in this case we have *F ⊆ E* as sets, and thus a polynomial *p* over *F* is also a polynomial over *E*. We then apply the construction of the second part to *F* [*X*]*/<p>* with the canonical monomorphism *ϕ : F* → *F* [*X*]*/<p>*. Together with the first part this gives - for fields *F* with *F* ∩ *F* [*X*] = ∅ - a field extension *E* of *F* in which *p* ∈ *F* [*X*]*\F* has a root.