2
$\begingroup$

Suppose we have a Boolean algebra over $n$ bits, meaning when viewed as a vector space over $F_2$, the dimension is $n$.

Then we can define $n$ unary predicates $P_n$ which return the value of the $n$'th bit in the corresponding bitvector.

In other words, for some arbitrary element $v$ in the algebra, $P_n(v) = 1$ if the $n$'th bit of $v$ is $1$, or $P_n(v) = 0$ if it is $0$. In this case, we take $0$ and $1$ to be the minimal and maximal elements of the Boolean algebra, respectively.

It is clear that given a Boolean algebra and a set of unary predicates defined from it in this fashion, that we get a quantifier-free monadic predicate logic.

Question: Does the converse hold? In other words, given a quantifier-free monadic predicate logic, is it always equivalent to some Boolean algebra in the above fashion, or derived easily from what I've written here?

The tricky thing here is that defined the way we do it above, the predicates appear to distribute over $\land$, $\lor$, and $\lnot$. In other words, we have:

  • $P_n(a \land b)$ = $P_n(a) \land P_n(b)$
  • $P_n(a \lor b)$ = $P_n(a) \lor P_n(b)$
  • $P_n(\lnot a)$ = $\lnot P_n(a)$

Arbitrary unary predicates do not have to obey these laws, but they do hold for the predicates stated above for bits in the Boolean algebra. However, it is relatively easy for us to define "compound predicates" from these primitive ones which exhibit more complex behavior, i.e. defining a predicate $P_x(a) = (\lnot P_1(a) \lor P_2(a)) \land (P_1(a) \lor \lnot P_2(a))$, for instance.

$\endgroup$
4
  • 1
    $\begingroup$ I am not sure if I understand your question correctly. Are you asking if any set of monadic sentences has a model of certain form? Note also that in monadic first-order logic you can't apply $\land, \lor, \lnot$ to elements. So $a \land b$, etc. is not expressible in monadic first-order logic. $\endgroup$
    – Levon Haykazyan
    Commented Oct 13, 2017 at 20:09
  • $\begingroup$ Thanks, I hadn't realized that. Is this true in first-order logic in general? For instance we can formulate PA in first-order logic, but $13 \land 25$ doesn't make much sense to me. $\endgroup$
    – Mike Battaglia
    Commented Oct 13, 2017 at 20:26
  • 1
    $\begingroup$ $a \land b$ is not defined in first-order logic itself. But there can be a function symbol $\land$ just like $+$ or $\times$. Though normally we would try to denote it by something else to avoid confusion. $\endgroup$
    – Levon Haykazyan
    Commented Oct 14, 2017 at 0:18
  • $\begingroup$ Thanks, I hadn't realized that. The question comes from the notion (found on Wikipedia and elsewhere) that ordinary propositional logic can be thought of "zeroth-order" logic, so that the propositions are basically "constant predicates" which take no argument at all. But that is a bizarre setup where logical connectives apply to "zeroth-order predicates" only in propositional logic, but not in higher order logics. I asked a question to clarify here - math.stackexchange.com/questions/2472329/… $\endgroup$
    – Mike Battaglia
    Commented Oct 14, 2017 at 18:46

0

Reset to default

You must log in to answer this question.