tlooto
Sign up
MathematicsComputer Science

Matrix identities and the pigeonhole principle

Michael Soltys, A. Urquhart

2004.1.15ARCHIVE FOR MATHEMATICAL LOGIC

DOI: 10.1007/s00153-003-0205-z

tlooto Summary

It is shown that short bounded-depth Frege proofs of matrix identities, such as PQ=I⊃QP=I (over the field of two elements), imply short bounded, depth FregeProof of the pigeonhole principle, which implies the propositional version of the matrix principle.

Abstract

Abstract is not available.

Citation format

SOLTYS, Michael; URQUHART, A. Matrix identities and the pigeonhole principle. ARCHIVE FOR MATHEMATICAL LOGIC, 2004, 43: 351–357.