Academic literature on the topic 'Lemmas'

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>PROGRAMA DE MESTRADO PROFISSIONAL EM MATEMÁTICA EM REDE NACIONAL<br>Esse trabalho visa demonstrar os lemas de Sperner e aplicá-los nasdemonstrações do teorema de Monsky em Q2 e do teorema do ponto fixo deBrouwer em R2. Além disso, relatamos como esses lemas foram abordados com alunos da educação básica tendo como ferramenta educacional jogos de tabuleiro.<br>This work aims to prove the Sperner s Lemmas and to apply them in proving the Monsky s Theorem in Q2 and the Brouwer fixed point Theorem in R2. Moreover, we report how these lemmas were addressed with students in basic education using board games as educational tools.

The word problem of a finitely generated group is commonly defined to be a formal language over a finite generating set. The class of finite groups has been characterised as the class of finitely generated groups that have word problem decidable by a finite state automaton. We give a natural generalisation of the notion of word problem from finitely generated groups to finitely generated semigroups by considering relations of strings. We characterise the class of finite semigroups by the class of finitely generated semigroups whose word problem is decidable by finite state automata. We then examine the class of semigroups with word problem decidable by asynchronous two tape finite state automata. Algebraic properties of semigroups in this class are considered, towards an algebraic characterisation. We take the next natural step to further extend the classes of semigroups under consideration to semigroups that have word problem decidable by a finite collection of asynchronous automata working independently. A central tool used in the derivation of structural results are so-called iteration lemmas. We define a hierarchy of the considered classes of semigroups and connect our original results with previous research.

The discovery of unknown lemmas, case-splits and other so called eureka steps are challenging problems for automated theorem proving and have generally been assumed to require user intervention. This thesis is mainly concerned with the automated discovery of inductive lemmas. We have explored two approaches based on failure recovery and theory formation, with the aim of improving automation of firstand higher-order inductive proofs in the IsaPlanner system. We have implemented a lemma speculation critic which attempts to find a missing lemma using information from a failed proof-attempt. However, we found few proofs for which this critic was applicable and successful. We have also developed a program for inductive theory formation, which we call IsaCoSy. IsaCoSy was evaluated on different inductive theories about natural numbers, lists and binary trees, and found to successfully produce many relevant theorems and lemmas. Using a background theory produced by IsaCoSy, it was possible for IsaPlanner to automatically prove more new theorems than with lemma speculation. In addition to the lemma discovery techniques, we also implemented an automated technique for case-analysis. This allows IsaPlanner to deal with proofs involving conditionals, expressed as if- or case-statements.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2017.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 123-127).<br>In this thesis, we analyze the regularity method pioneered by Szemerédi, and also discuss one of its prevalent applications, the removal lemma. First, we prove a new lower bound on the number of parts required in a version of Szemerédi's regularity lemma, determining the order of the tower height in that version up to a constant factor. This addresses a question of Gowers. Next, we turn to algorithms. We give a fast algorithmic Frieze-Kannan (weak) regularity lemma that improves on previous running times. We use this to give a substantially faster deterministic approximation algorithm for counting subgraphs. Previously, only an exponential dependence of the running time on the error parameter was known; we improve it to a polynomial dependence. We also revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for some co-NP-complete problems. We show how to use the Frieze-Kannan regularity lemma to approximate the regularity of a pair of vertex sets. We also show how to quickly find, for each [epsilon]' > [epsilon], an [epsilon]'-regular partition with k parts if there exists an [epsilon]-regular partition with k parts. After studying algorithms, we turn to the arithmetic setting. Green proved an arithmetic regularity lemma, and used it to prove an arithmetic removal lemma. The bounds obtained, however, were tower-type, and Green posed the problem of improving the quantitative bounds on the arithmetic triangle removal lemma, and, in particular, asked whether a polynomial bound holds. The previous best known bound was tower-type with a logarithmic tower height. We solve Green's problem, proving an essentially tight bound for Green's arithmetic triangle removal lemma in Fn/p. Finally, we give a new proof of a regularity lemma for permutations, improving the previous tower-type bound on the number of parts to an exponential bound.<br>by László Miklós Lovász.<br>Ph. D.

Thesis (MSc)--Stellenbosch University, 2011.<br>ENGLISH ABSTRACT: Some of the diagram lemmas of Homological Algebra, classically known for abelian categories, are not characteristic of the abelian context; this naturally leads to investigations of those non-abelian categories in which these diagram lemmas may hold. In this Thesis we attempt to bring together two different directions of such investigations; in particular, we unify the five lemma from the context of homological categories due to F. Borceux and D. Bourn, and the five lemma from the context of modular semi-exact categories in the sense of M. Grandis.<br>AFRIKAANSE OPSOMMING: Verskeie diagram lemmata van Homologiese Algebra is aanvanklik ontwikkel in die konteks van abelse kategorieë, maar geld meer algemeen as dit behoorlik geformuleer word. Dit lei op ’n natuurlike wyse na ’n ondersoek van ander kategorieë waar hierdie lemmas ook geld. In hierdie tesis bring ons twee moontlike rigtings van ondersoek saam. Dit maak dit vir ons moontlik om die vyf-lemma in die konteks van homologiese kategoieë, deur F. Borceux en D. Bourn, en vyflemma in die konteks van semi-eksakte kategorieë, in die sin van M. Grandis, te verenig.

In this work we cover some counting techniques used to solve some classic problems in Combinatorics. We also show a link between the so called ârencontre problemâ, the âmÃnage problemâ and the permanent of a square matrix.<br>Neste trabalho abordamos algumas tÃcnicas de contagem utilizadas para solucionar alguns problemas clÃssicos da AnÃlise CombinatÃria. Mostramos tambÃm uma relaÃÃo entre o problema das cartas mal endereÃadas, o problema de Lucas e os permanentes de uma matriz quadrada.

Dans cette thèse, nous nous intéressons aux propriétés statistiques des systèmes dynamiques aléatoires et non-autonomes. Dans le premier chapitre, consacré aux systèmes aléatoires, nous établissons un cadre fonctionnel abstrait, couvrant une large classe de systèmes dilatants en dimension 1 et supérieure, permettant de démontrer de nombreux théorèmes limites annealed. Nous donnons aussi une condition nécessaire et suffisante pour que la version quenched du théorème de la limite centrale soit valide en dimension 1. Dans le chapitre deux, après avoir introduit la notion de système non-autonome, nous étudions un système composé d'applications en dimension 1 ayant un point fixe neutre commun, et nous montrons que celui-ci admet une vitesse de perte de mémoire polynomiale. Le chapitre trois est consacré aux inégalités de concentration. Nous établissons de telles inégalités pour des systèmes dynamiques aléatoires et non-autonomes, et nous étudions diverses applications. Dans le chapitre quatre, nous nous intéressons aux lemmes dynamiques de Borel-Cantelli pour l'induction de Rauzy-Veech-Zorich, et présentons quelques résultats liés aux statistiques de récurrence pour cette application<br>The first chapter, devoted to random systems, we establish an abstract functional framework, including a large class of expanding systems in dimension 1 and higher, under which we can prove annealed limit theorems. We also give a necessary and sufficient condition for the quenched central limit theorem to hold in dimension 1. In chapter 2, after an introduction to the notion of non-autonomous system, we study an example consisting of a family of maps of the unit interval with a common neutral fixed point, and we show that this system admits a polynomial loss of memory. The chapter 3 is devoted to concentration inequalities. We establish such inequalities for random and non-autonomous dynamical systems in dimension 1, and we study some of their applications. In chapter 4, we study dynamical Borel-Cantelli lemmas for the Rauzy-Veech-Zorich induction, and we present some results concerning statistics of recurrence for this map

Made available in DSpace on 2014-06-11T19:27:10Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-12-09Bitstream added on 2014-06-13T20:47:43Z : No. of bitstreams: 1 cobra_tt_me_rcla.pdf: 485593 bytes, checksum: 107d36859b5a9c932411b3a54094c4ac (MD5)<br>O principal objetivo deste trabalho é apresentar conceitos básicos sobre coincidências e pontos fixos de aplicações contínuas usando como ferramentas os Lemas Combinatórios de Sperner e grau de aplicações. Apresentamos também um cálculo do número de Lefschetz de f; g : T2 ¡! T3, onde Th denota uma superfície de genus h, através da fórmula dada por Gonçalves e Oliveira em [3]<br>The main goal of this work is present basic concepts on coincidences and fixed points of continuous maps with Sperner’s Combinatorial Lemmas, and degree maps approaches. We also present a calculation of the Lefschetz number of f; g : T2 ¡! T3, where Th denotes surface of genus h, by using the formula given by Gonçalves and Oliveira in [3]

Orientador: Alice Kimie Miwa Libardi<br>Banca: Edson de Oliveira<br>Banca: Thiago de Melo<br>Resumo: O principal objetivo deste trabalho é apresentar conceitos básicos sobre coincidências e pontos fixos de aplicações contínuas usando como ferramentas os Lemas Combinatórios de Sperner e grau de aplicações. Apresentamos também um cálculo do número de Lefschetz de f; g : T2 ¡! T3, onde Th denota uma superfície de genus h, através da fórmula dada por Gonçalves e Oliveira em [3]<br>Abstract: The main goal of this work is present basic concepts on coincidences and fixed points of continuous maps with Sperner's Combinatorial Lemmas, and degree maps approaches. We also present a calculation of the Lefschetz number of f; g : T2 ¡! T3, where Th denotes surface of genus h, by using the formula given by Gonçalves and Oliveira in [3]<br>Mestre