4

Let $S$ be the set of all n-ary functions on $\{0,1\}$ for all n, including the 0-ary functions. Let $F$ be a finite subset of $S$. Consider a countably infinite set of propositional constants $PROP$. Now, we define recursively a language on $PROP \cup F$, by stipulating that members of $PROP$ are in the language, and if $f$ is an n-ary function in $F$ and $x_1,...,x_n$ are already in the language, then the concatenation $fx_1,...x_n$ is also in the language.

We can now form a consequence relation on this language, by saying that a member $w$ is implied by a set $W$ iff there is no boolean valuation that simultaneously makes all members of $W$ true but makes $w$ false.

Although the consequence relation has infinitely many members, we can sometimes use a finite generating set. For example, considering the set that only contains conjunction, I believe this is a finite generating set: 1. $\{p_1,p_2\}$ $\vdash$ $p_1 \land p_2$ 2. $\{p_1 \land p_2\}$ $\vdash$ $p_1$ 3.$\{p_1 \land p_2\}$ $\vdash$ $p_2$.

Now that I have set the background theory for my question, my question is, given any finite set of boolean connectives, does it always have a finite generating set? If so, what is the proof.

user107952
  • 20,508
  • The obvious tool to use here is Post's lattice : you have a classificiation into 40-or-so cases. Answering your question is equivalent to determining in each of those 40 cases whether the clone is "finitely generated" in your sense. – Ewan Delanoy Apr 21 '19 at 08:14
  • For the example of conjunction, how is that a finite generating set? Don’t your relations have to hold for all $p_1,p_2$ in the language, which is countably infinite? – George Lowther Apr 26 '19 at 23:15
  • @GeorgeLowther I mean, if you close the generating set under substitution, you get the whole consequence relation. – user107952 May 28 '19 at 18:21
  • Cross-posted to https://mathoverflow.net/questions/333863 (and now answered there). – Emil Jeřábek Jun 13 '19 at 16:12

0 Answers0