7
$\begingroup$

I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.

Consider a countably infinite set $P$ of propositional atoms, indexed by the positive integers like so: $p_1,p_2,p_3,p_4,...$. We also have the connectives $\land$, $\vee$, and $\neg$ as well as the parentheses $($ and $)$. We define the set $W$ of well-formed formulas from the alphabet $P \cup \{\land,\vee,\neg,(,)\}$ in the standard recursive way given in almost any mathematical logic textbook. Over the set $W$, I define an equivalence relation $E$ by saying that two wffs $A$ and $B$ are related by $E$ iff they are logically equivalent, where logical equivalence is defined in the standard way in any logic textbook. Now, let $B$ be the set of equivalence classes of $W$ under $E$, and consider the Boolean algebra structure $(B;\land,\vee,\neg,0,1)$, where $0$ is the set of contradictions, $1$ is the set of tautologies, and $\land$, $\vee$, and $\neg$ are operations defined by passing to representatives (and it is easy to check that they are well-defined).

I previously asked if the set of propositional atoms, or even any non-empty subset of it, is definable without parameters in the structure $B$. The answer was negative. Now, if we use parameters, certainly any finite subset of the set of propositional atoms is definable. But I believe that is the best possible. So, my current question is, is the set of propositional atoms, or even any infinite subset of it, definable even with parameters? I believe it is not, but how to prove it?

Edit: As a bonus question, can anyone give a complete classification of all the parameter-definable subsets of the structure $B$?

Edit 2: As a matter of fact, I now conjecture that the parameter-definable subsets are finite and cofinite subsets of $B$, that is, $B$ is a minimal structure. Can anyone confirm or deny this conjecture?

$\endgroup$
2
  • $\begingroup$ Please edit n a link to the question on m.se, and put a link to this question there. $\endgroup$ Commented Oct 29, 2022 at 9:52
  • $\begingroup$ Your conjecture about finite/cofinite is not true, since for any given nontrivial element $b$, the set $\{x\mid x\leq b\}$ is definable from $b$ but it is neither finite nor cofinite. The definable sets, however, as I explained in my answer, are finite Boolean combinations of such trivial cones, whose vertices are the points in the finite Boolean algebra generated by the parameters, as I mention in my answer. $\endgroup$ Commented Oct 29, 2022 at 12:04

1 Answer 1

11
$\begingroup$

It's a nice question. This Boolean algebra, known as the Lindenbaum algebra, is a countable atomless Boolean algebra — it is atomless because we can always take the conjunction of any formula with a new atom or its negation — and all such Boolean algebras are isomorphic by a standard back-and-forth argument. So your particular presentation of the algebra is inessential, since there are many presentations of this algebra.

The back-and-forth argument also shows that the structure is homogeneous — any finite partial isomorphism will extend to an automorphism of the whole algebra. Any finitely many parameters are contained in a finite Boolean subalgebra, and so any two elements that stand in the same relation to the atoms of that subalebra will be automorphic images. This severely limits the definable sets and will support a classification. Every definable set from parameters will be a finite union of the sets of points that all relate to the atoms of the finite subalgebra generated by those parameters in the same way. (Perhaps someone can provide a fully detailed account.)

In particular, the set of propositional atoms will not be definable with parameters, since any atom $p$ not appearing in the expressions of the parameters will be automorphic with the conjunction of two other such atoms $q\wedge r$ over those parameters. Similarly, no infinite set of atoms will be definable with parameters, since we can always move one of them automorphically to something that isn't an atom.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .