Geodesic
Proofs without syntax
Dominic J. D. Hughes1
1Department of Mathematics, Stanford University, Stanford, CA 94305, United States
Annals of mathematics, Tome 164 (2006) no. 3, pp. 1065-1076
Cet article a éte moissonné depuis la source Annals of Mathematics website

Voir la notice de l'article

Proofs are traditionally syntactic, inductively generated objects. This paper presents an abstract mathematical formulation of propositional calculus (propositional logic) in which proofs are combinatorial (graph-theoretic), rather than syntactic. It defines a combinatorial proof of a proposition $\phi$ as a graph homomorphism $h:C\to G(\phi)$, where $G(\phi)$ is a graph associated with $\phi$ and $C$ is a coloured graph. The main theorem is soundness and completeness: $\,\phi$ is true if and only if there exists a combinatorial proof $h:C\to G(\phi)$.

DOI : 10.4007/annals.2006.164.1065

Dominic J. D. Hughes  1

1 Department of Mathematics, Stanford University, Stanford, CA 94305, United States 
@article{10_4007_annals_2006_164_1065,
     author = {Dominic J. D. Hughes},
     title = {Proofs without syntax},
     journal = {Annals of mathematics},
     pages = {1065--1076},
     year = {2006},
     volume = {164},
     number = {3},
     doi = {10.4007/annals.2006.164.1065},
     mrnumber = {2259253},
     zbl = {1130.03009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2006.164.1065/}
}
TY  - JOUR
AU  - Dominic J. D. Hughes
TI  - Proofs without syntax
JO  - Annals of mathematics
PY  - 2006
SP  - 1065
EP  - 1076
VL  - 164
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2006.164.1065/
DO  - 10.4007/annals.2006.164.1065
LA  - en
ID  - 10_4007_annals_2006_164_1065
ER  - 
%0 Journal Article
%A Dominic J. D. Hughes
%T Proofs without syntax
%J Annals of mathematics
%D 2006
%P 1065-1076
%V 164
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2006.164.1065/
%R 10.4007/annals.2006.164.1065
%G en
%F 10_4007_annals_2006_164_1065
Dominic J. D. Hughes. Proofs without syntax. Annals of mathematics, Tome 164 (2006) no. 3, pp. 1065-1076. doi: 10.4007/annals.2006.164.1065

Cité par Sources :