We study logical reduction (factorization) of relations into relations of lower arity by Boolean or relative products that come from applying conjunctions and existential quantifiers to predicates, i.e. by primitive positive formulas of predicate calculus. Our algebraic framework unifies natural joins and data dependencies of database theory and relational algebra of clone theory with the bond algebra of C.S. Peirce. We also offer new constructions of reductions, systematically study irreducible relations and reductions to them and introduce a new characteristic of (...) relations, ternarity, that measures their ‘complexity of relating’ and allows to refine reduction results. In particular, we refine Peirce’s controversial reduction thesis, and show that reducibility behaviour is dramatically different on finite and infinite domains. (shrink)

We argue that traditional formulations of the reduction thesis that tie it to privileged relational operations do not suffice for Peirce’s justification of the categories and invite the charge of gerrymandering to make it come out as true. We then develop a more robust invariant formulation of the thesis, one that is immune to that charge, by explicating the use of triads in any relational operations. The explication also allows us to track how Thirdness enters the structure of higher order (...) relations and even to propose a numerical measure of it. Our analysis reveals new conceptual phenomena when negation or disjunction are used to compound relations. (shrink)

We give a new and elementary construction of primitive positive decomposition of higher arity relations into binary relations on finite domains. Such decompositions come up in applications to constraint satisfaction problems, clone theory and relational databases. The construction exploits functional completeness of 2-input functions in many-valued logic by interpreting relations as graphs of partially defined multivalued ‘functions’. The ‘functions’ are then composed from ordinary functions in the usual sense. The construction is computationally effective and relies on well-developed methods of functional (...) decomposition, but reduces relations only to ternary relations. An additional construction then decomposes ternary into binary relations, also effectively, by converting certain disjunctions into existential quantifications. The result gives a uniform proof of Peirce’s reduction thesis on finite domains, and shows that the graph of any Sheffer function composes all relations there. (shrink)

Wittgenstein's paradoxical theses that unproved propositions are meaningless, proofs form new concepts and rules, and contradictions are of limited concern, led to a variety of interpretations, most of them centered on rule-following skepticism. We argue, with the help of C. S. Peirce's distinction between corollarial and theorematic proofs, that his intuitions are better explained by resistance to what we call conceptual omniscience, treating meaning as fixed content specified in advance. We interpret the distinction in the context of modern epistemic logic (...) and semantic information theory, and show how removing conceptual omniscience helps resolve Wittgenstein's paradoxes and explain the puzzle of deduction, its ability to generate new knowledge and meaning. (shrink)