Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Operators on sets

There is always more than one operator that yields a given collection of equivalences. So for ordinary logic both Nand and Nor work. And with k=4 any of the 12 operators

{1116699, 169585339, 290790239, 459258879, 1090522958, 1309671358, 1430343258, 1515110058, 2184380593, 2575151445, 2863760025, 2986292093}

also turn out to work. One can see why this happens by considering the analogy between operations in logic and operations on sets. As reflected in their traditional notations—and emphasized by Venn diagrams—And (\[And]), Or (\[Or]) and Not correspond directly to Intersection (\[Intersection]), Union (\[Union]) and Complement. If one starts from the single-element set {1} then applying Union, Intersection and Complement one always gets either {} or {1}. And applying Complement[s, Intersection[a, b]] to these two elements gives the same results and same equivalences as Nand[a, b] applied to True and False. But if one uses instead s={1,2} then starts with {1} and {2} one gets any of {{}, {1}, {2}, {1, 2}} and in general with s=Range[n] one gets any of the 2^n elements in the powerset

Distribute[Map[{{}, {#}} &, s], List, List, List, Join]

But applying Complement[s, Intersection[a, b]] to these elements still always produces the same equivalences as with Nand[a, b]. Yet now k=2^n. And so one therefore has a representation of Boolean algebra of size 2^n. For ordinary logic based on Nand it turns out that there are no other finite representations (though there are other infinite ones). But if one works, say, with Implies then there are for example representations of size 3 (see above). And the reason for this is that with s={1,2} the function Union[Complement[s, a], b] corresponding to Implies[a, b] only ever gets to the 3 elements {{1}, {2}, {1,2}}. Indeed, in general with operators Implies, And and Or one gets to 2^n-1 elements, while with operators Xor and Equal one gets to 2^(2Floor[n/2]) elements.

(One might think that one could force there only ever to be two elements by adding an axiom like Or[a==b,b==c,c==a]. But all this actually does is to force there to be only two objects analogous to True and False.)


From Stephen Wolfram: A New Kind of Science [citation]