We present a new and formal coinductive proof of confluence and normalisation of B "ohm reduction in infinitary lambda calculus. The proof is simpler than previous proofs of this result. The technique of the proof is new, i.e., it is not merely a coinductive reformulation of any earlier proofs. We formalised the proof in the Coq proof assistant.
In a previous paper we have established the theory of transfinite reduction for orthogonal term rewriting systems. In this paper we perform the same task for the lambda calculus. This results in several new Bohm-like models of the lambda calculus, and new descriptions of existing models.  Towards the Theory. Introduction. Conversion. Reduction. Theories. Models. Conversion. Classical Lambda Calculus. The Theory of Combinators. Classical Lambda Calculus (Continued). The Lambda-Calculus. Bohm Trees. Reduction. Fundamental Theorems. Strongly Equivalent Reductions. Reduction Strategies. Labelled Reduction. Other Notions of Reduction. Theories. Sensible Theories. Other Lambda Theories. Models. Construction of Models. Local Structure of Models. Global Structure of Models. Combinatory Groups. Appendices: Typed Lambda Calculus. Illative Combinatory Logic. Variables. References.  We show the existence of an infinitary confluen t and normalising extension of the finite extensional lambda calculus with beta and eta. Besides infinite beta reductions also infinite eta reductions are possible in this extension, and terms without head normal form can be reduced to bottom. As corollaries we obtain a simple, syntax based construction of an extensional Bohm model of the finite lambda calculus; and a simple, syntax based proof that two lambda terms have the same semantics in this model if and only if theyha ve the same eta-Bohm tree if and only if they are observationally equivalent wrt to beta normal forms. The confluence proof reduces confluence of beta, bottom and eta via infinitary commutation and postponement arguments to confluence of beta and bottom and confluence of eta.We give counterexamples against confluence of similar extensions based on the identification of the terms without weak head normal form and the terms without top normal form (rootactive terms) respectively. In a previous paper we have established the theory of transfinite reduction for orthogonal term rewriting systems. In this paper we perform the same task for the lambda calculus. From the viewpoint of infinitary rewriting, the Bohm model of the lambda calculus can be seen as an infinitary term model. In contrast to term rewriting, there are several different possible notions of infinite term, which give rise to different Bohm-like models, which embody different notions of lazy or eager computation. On introduit les termes du λ-calcul et les termes de la logique combinatoire d'ordres divers, correspondant aux niveaux de fonctionnalite ou au nombre de λ-abstractions. On donne les algebres PSE. On presente une caracterisation semantique des λ-termes de tout ordre fini. Applications de theorie des modeles principales