Three propositional atoms isomorphic to 32 element powerset algebra

201 Views Asked by At

I've been struggling to figure out the following (feeble attempt below question).

Using three propositional atoms, A, B, and C. Provide a theory (one or more formulas) such that the set of "equivalence classes" which has exactly 32 elements, i.e., such that the algebraic structure corresponds directly to (is isomorphic to) the powerset algebra over a 5 element set.Powerset algebra diagram over four element setTwo propositional atom algebra of A and B which is isomorphic to the powerset algebra for a four element set

So I know that we must use the Stone Representation that every boolean algebra is isomorphic to a powerset algebra, and so far it occurred to me to look for the powerset algebra over a five element set which would clearly contain 32 elements, yet I am not certain how extending the two propositional atom diagram of A and B to include a third, C, would affect the diagram--if anything I suspect a much larger diagram to result and not just a 32 element one. Thoughts?

1

There are 1 best solutions below

6
On BEST ANSWER

Indeed, for three atoms, there are $2^{2^3} = 256$ boolean functions (or equivalence classes of formulae), and it’s far too many. But let’s label each formula with binary string of values in its truth table. Then consider all the formulas whose strings have e. g. the same suffix (say, 10) of length $\ell$. Forgetting about this suffix, one can see we have $256/2^\ell$-element boolean algebra with respect to the original algebra’s $\vee$ and $\wedge$, but its own negation, as it’s not closed under the first’s $\neg$, which doesn’t conserve the fixed suffix (in example above, it maps to 01).

Then, I suppose, a theory should entail any formula it contains (which is not mentioned in the question now). This filters out some candidates: it should contain original $\top$ which has code $11\ldots1$. So, you should pick a suffix consisting only of 1s. (In this case, 3 ones, so there are 5 unfrozen digits giving us 32-element set.) To describe this theory, you could epresent each equivalence class as corresponding full disjunctive normal form which is in simple relationship to the truth table of corresponding boolean function: as we fix some values in the table, in FDNF some conjuncts should always be present, so it is of form $\mathrm{somethingArbitrary}\vee\mathrm{fixedPart}$.

I hope I filled the blanks right with the latter paragraph. Please comment if not.