Seven trees in one

DOI10.1016/0022-4049(95)00098-HMaRDI QIDQ1901018zbMATH OpenFDO

Authors Andreas Blass

Publication date 22 September 1996

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9405205

zbMATH Keywords

polynomialssemiringsprovabilityintuitionistic set theoryfinite binary treesobjective number theoryseven-tuples of treesvery explicit bijection

Mathematics Subject Classification ID

Trees (05C05) Combinatorial identities, bijective combinatorics (05A19) Other constructive mathematics (03F65) Semirings (16Y60) Topoi (18B25)

Abstract: Following a remark of Lawvere, we explicitly exhibit a particularly elementary bijection between the set T of finite binary trees and the set T^7 of seven-tuples of such trees. "Particularly elementary" means that the application of the bijection to a seven-tuple of trees involves case distinctions only down to a fixed depth (namely four) in the given seven-tuple. We clarify how this and similar bijections are related to the free commutative semiring on one generator X subject to X=1+X^2. Finally, our main theorem is that the existence of particularly elementary bijections can be deduced from the provable existence, in intuitionistic type theory, of any bijections at all.

Recommendations

• The arithmetic of trees
• Bijections between formulae and trees which are compatible with equivalences of the type ((f g) h) ((f h) g)
• Objects of categories as complex numbers

Cites work

• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 19477 (Why is no real title available?)
• scientific article; zbMATH DE number 19501 (Why is no real title available?)
• scientific article; zbMATH DE number 192841 (Why is no real title available?)
• scientific article; zbMATH DE number 3554471 (Why is no real title available?)
• scientific article; zbMATH DE number 3574077 (Why is no real title available?)
• Classifying topoi and finite forcing
• Forcing and classifying topoi
• Method for constructing bijections for classical partition identities
• Sheaf models for set theory

Cited in

(11)

• Objects of categories as complex numbers
• Computing with semirings and weak rig groupoids
• The compositional construction of Markov processes. II
• Left and right adjoint operations on spaces and data types
• On the generic solution to \(P(X)\cong X\) in distributive categories
• An objective representation of the Gaussian integers
• Every rig with a one-variable fixed point presentation is the Burnside rig of a prextensive category
• Gröbner-Shirshov bases for semirings.
• A general theory of self-similarity
• On analytic groupoid cardinality
• GRÖBNER-SHIRSHOV BASIS FOR MONOMIALS SEMIRING OVER D-A RINGS

This page was built for publication: Seven trees in one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1901018)