1
$\begingroup$

In page 13 of Mathematical Logic, Tourlakis defines the set of all well-formed-formulae as:

... the smallest set of strings, WFF, that satisfies: 1) All Boolean variables are in WFF, and so are the symbols ⊤ and ⊥. 2) If A and B are strings in WFF, then so are the strings (¬A), (A∧B), (A∨B), (A→B), (A≡B).

Capture from the book

But as I understand it, the set of Boolean variables is infinite.

So, how can a set be a smallest one when the cardinality is infinite?

In this question somebody asked about it and the answer was

The "smallest set" condition there is crucial: if we omit it, there are lots of sets satisfying the definition

and I would go even further as to say, indeed there are infinite sets that satisfy the condition of being sets of Well Formed formulas, it's not unique because I can always find an element (Boolean variable) that belongs to another set of WFF.

$\endgroup$
1
3
$\begingroup$

The natural numbers $\mathbb{N} = \{0,1,2,3,\ldots\}$ is the smallest set $I$ with the property that $0 \in I$ and whenever $n \in I$ then $n+1 \in I$ ($I$ is an inductive set). What do we mean when we say 'smallest' though? In this context we aren't talking about cardinality, but about set containment. So saying that $\mathbb{N}$ is the smallest set with the aforementioned property means that if $I$ were another such set then $\mathbb{N} \subseteq I$.

This is the same sort of thing with $\mathsf{WFF}$ - we specify some initial set of things that must belong to it (the Boolean variables and $\bot,\top$ in this case) and then require that it be closed under a certain set of operations (in this case, the Boolean connectives followed by surrounding with parentheses). $\mathsf{WFF}$ is the smallest (with respect to containment, not cardinality) set with the aforementioned properties.

How do we know there is such a set? One can show that the intersection of all such sets (either all inductive sets in the case of $\mathbb{N}$, or all sets containing the Boolean variables and so on in the case of $\mathsf{WFF}$) also has the corresponding properties. Since we took the intersection of every set with those properties, it must be the smallest in terms of containment.

$\endgroup$
1
  • $\begingroup$ Thank you so much! $\endgroup$ – Darvid Jan 19 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.