--- OA_place: repository _id: '21393' abstract: - lang: eng text: "This thesis documents a voyage towards truth and beauty via formal verification of theorems. To this end, we develop libraries in Lean 4 that present definitions and results from diverse areas of MathematiCS (i.e., Mathematics and Computer Science). The aim is to create code that is understandable, believable, useful, and elegant. The code should stand for itself as much as possible without a need for documentation; however, this text redundantly documents our code artifacts and provides additional context that isn’t present in the code. This thesis is written for readers who know Lean 4 but are not familiar with any of the topics presented. We manifest truth and beauty in three formalized areas of MathematiCS.\r\n\r\nWe formalize general grammars in Lean 4 and use grammars to show closure of the class of type-0 languages under four operations; union, reversal, concatenation, and the Kleene star.\r\n\r\nOur second stop is the theory of optimization. Farkas established that a system of linear inequalities has a solution if and only if we cannot obtain a contradiction by taking a linear combination of the inequalities. We state and formally prove several Farkas-like theorems over linearly ordered fields in Lean 4. Furthermore, we extend duality theory to the case when some coefficients are allowed to take “infinite values”. Additionally, we develop the basics of the theory of optimization in terms of the framework called General-Valued Constraint Satisfaction Problems, and we prove that, if a Rational-Valued Constraint Satisfaction Problem template has symmetric fractional polymorphisms of all arities, then its basic LP relaxation is tight.\r\n\r\nOur third stop is matroid theory. Seymour’s decomposition theorem is a hallmark result in matroid theory, presenting a structural characterization of the class of regular matroids. We aim to formally verify Seymour’s theorem in Lean 4. First, we build a library for working with totally unimodular matrices. We define binary matroids and their standard representations, and we prove that they form a matroid in the sense how Mathlib defines matroids. We define regular matroids to be matroids for which there exists a full representation rational matrix that is totally unimodular, and we prove that all regular matroids are binary. We define 1-sum, 2-sum, and 3 sum of binary matroids as specific ways to compose their standard representation matrices. We prove that the 1-sum, the 2-sum, and the 3-sum of regular matroids are a regular matroid, which concludes the composition direction of the Seymour’s theorem. The (more difficult) decomposition direction remains unproved.\r\n\r\nIn the pursuit of truth, we focus on identifying the trusted code in each project and presenting it faithfully. We emphasize the readability and believability of definitions rather than choosing definitions that are easier to work with. In search for beauty, we focus on the philosophical framework of Roger Scruton, who emphasizes that beauty is not a mere decoration but, most importantly, beauty is the means for shaping our place in the world and a source of redemption, where it can be viewed as a substitute for religion." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Martin full_name: Dvorak, Martin id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425 last_name: Dvorak orcid: 0000-0001-5293-214X citation: ama: 'Dvorak M. Pursuit of truth and beauty in Lean 4 : Formally verified theory of grammars, optimization, matroids. 2026. doi:10.15479/AT-ISTA-21393' apa: 'Dvorak, M. (2026). Pursuit of truth and beauty in Lean 4 : Formally verified theory of grammars, optimization, matroids. Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-21393' chicago: 'Dvorak, Martin. “Pursuit of Truth and Beauty in Lean 4 : Formally Verified Theory of Grammars, Optimization, Matroids.” Institute of Science and Technology Austria, 2026. https://doi.org/10.15479/AT-ISTA-21393.' ieee: 'M. Dvorak, “Pursuit of truth and beauty in Lean 4 : Formally verified theory of grammars, optimization, matroids,” Institute of Science and Technology Austria, 2026.' ista: 'Dvorak M. 2026. Pursuit of truth and beauty in Lean 4 : Formally verified theory of grammars, optimization, matroids. Institute of Science and Technology Austria.' mla: 'Dvorak, Martin. Pursuit of Truth and Beauty in Lean 4 : Formally Verified Theory of Grammars, Optimization, Matroids. Institute of Science and Technology Austria, 2026, doi:10.15479/AT-ISTA-21393.' short: 'M. Dvorak, Pursuit of Truth and Beauty in Lean 4 : Formally Verified Theory of Grammars, Optimization, Matroids, Institute of Science and Technology Austria, 2026.' corr_author: '1' date_created: 2026-03-04T09:26:46Z date_published: 2026-03-04T00:00:00Z date_updated: 2026-03-27T12:37:00Z day: '04' ddc: - '511' - '000' degree_awarded: PhD department: - _id: GradSch - _id: VlKo doi: 10.15479/AT-ISTA-21393 file: - access_level: open_access checksum: cface6dc18152680962b5361575f6e4f content_type: application/pdf creator: mdvorak date_created: 2026-03-04T08:56:15Z date_updated: 2026-03-04T08:56:15Z file_id: '21394' file_name: 2026_Dvorak_Martin_Thesis.pdf file_size: 1771231 relation: main_file success: 1 - access_level: closed checksum: 290ddfacfb7e07fb07e6f0b334e67c90 content_type: application/vnd.openxmlformats-officedocument.wordprocessingml.document creator: mdvorak date_created: 2026-03-04T09:03:37Z date_updated: 2026-03-04T09:03:37Z file_id: '21395' file_name: 2026_Dvorak_Martin_Thesis.docx file_size: 864585 relation: source_file file_date_updated: 2026-03-04T09:03:37Z has_accepted_license: '1' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '03' oa: 1 oa_version: Published Version page: '160' publication_identifier: isbn: - 978-3-99078-074-9 issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: link: - description: Full version of all definitions, statements, and proofs for Chapter 3.1 (Linear duality) relation: software url: https://github.com/madvorak/duality/tree/v3.5.0 - description: Full version of all definitions, statements, and proofs for Chapter 3.2 (Valued Constraint Satisfaction Problems) relation: software url: https://github.com/madvorak/vcsp/tree/v8.2.0 - description: Full version of all definitions, statements, and proofs for Chapter 4 (Seymour project) relation: software url: https://github.com/Ivan-Sergeyev/seymour/tree/v1.2.0 - description: Full version of all definitions, statements, and proofs for Chapter 5 (Theory of grammars) relation: software url: https://github.com/madvorak/chomsky/tree/v1.2.0 - description: Old version (Lean 3) of the project about grammars relation: software url: https://github.com/madvorak/grammars - description: Demonstration of (minimal) requirements for selected algebraic classes used in my Ph.D. thesis relation: software url: https://github.com/madvorak/preliminaries/blob/main/Preliminaries.lean record: - id: '13120' relation: part_of_dissertation status: public - id: '21398' relation: part_of_dissertation status: public - id: '20071' relation: part_of_dissertation status: public status: public supervisor: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Jasmin full_name: Blanchette, Jasmin last_name: Blanchette title: 'Pursuit of truth and beauty in Lean 4 : Formally verified theory of grammars, optimization, matroids' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: dissertation user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2026' ...