To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

A syntactical proof of th… - University of Gothenburg, Sweden Till startsida
To content Read more about how we use cookies on

A syntactical proof of the marriage lemma

Journal article
Authors Thierry Coquand
Published in Theoretical Computer Science
Volume 290
Issue 1
Pages 1107-1113
ISSN 0304-3975
Publication year 2003
Published at Department of Computer Science and Engineering, Computing Science, Programming Logic
Pages 1107-1113
Language en
Subject categories Computer Science


We give a proof of the classical Marriage Lemma (Amer. J. Math. 72 (1950) 214) using completeness of hyperresolution. This argument is purely syntactical, and extends directly to the infinite case. As an application we give a purely syntactical version of a proof that resolution is exponential on the pigeon-hole principle.

Page Manager: Webmaster|Last update: 9/11/2012

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?