I'm reading a text book about propositional calculus and it says that $ \bigvee_{\phi_i \in \Phi}{\phi_i} $ and $ \bigwedge_{\phi_i \in \Phi}{\phi_i} $ are not allowed, if $ \Phi $ is not finite. It does not give an explanation. Could you please explain the reason behind this?
1 Answers
Because "standard" logic syntax defines formulae as expression of finite lenght.
The "reason" is due to the fact that formal languages model (or mimick) natural language, where we are not accustomed to use "text" (spoken or writen) of infinite lenght.
But we have also Infinitary Logic.
In general, we can refer to Formal Languages:
In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.
An alphabet, in the context of formal languages, can be any set, although it often makes sense to use an alphabet in the usual sense of the word. The elements of an alphabet are called its letters.
Alphabets may be infinite; however, most definitions in formal language theory specify finite alphabets, and most results only apply to them.
A word over an alphabet can be any finite sequence (i.e., string) of letters. In some applications, especially in logic, the alphabet is also known as the vocabulary and words are known as formulas.
You can see, for a gentle introduction to mathematical logic:
- Richard Kaye, The Mathematics of Logic: A guide to completeness theorems and their applications, Cambridge UP (2007), page 24:
Formal systems are kinds of mathematical games with strings of symbols and precise rules. They mimic the idea of a ‘proof’. [...] The particular system that we shall look at here [...] is based on finite sequences, or strings, of $0$s and $1$s.
And page 64:
We are going to develop a formal system for proofs about boolean algebras [the propositional calculus].
Let $X$ be any set, which for this definition will be called a set of propositional letters. The set of boolean terms $\text {BT}(X)$ over $X$ is defined as a set of expressions, or strings [or finite sequences] of symbols, from a set of symbols including $(, ), \land, \lor, \top, \bot, ¬$ and all elements of $X$, as follows [...]
A formal proof or derivation from assumptions $Σ ⊆ \text{BT}(X)$ is a derivation of finite length where each statement in it is [...]
As you can see, the "finiteness" requirement is at the core of elementary logic.
- 94,169
-
Is it because of being able to validate whether a formula is true or not? – Said Savci Apr 20 '17 at 11:35
-
@Javiator - not necessarily; in FOL the truth table method does not work, irrespective of the fact that the formulae are of finite lenght. – Mauro ALLEGRANZA Apr 20 '17 at 11:55
-
Does that also have to do with the inductive definition of a formula in propositional calculus? I.e. every formula in propositional calculus is inductively defined to be finite. I do understand you answer, but I'm just trying to lead this back to some definition(s) in propositional calculus. – Said Savci Apr 20 '17 at 12:12
-
@Javiator - No; as you can see from the SEP's entry, as long as we introduce an infinitary conjunction (and disjunction) symbol, the usual clauses for the def of formula will work. – Mauro ALLEGRANZA Apr 20 '17 at 12:17
-
So it's just a matter of definition in propositional calculus that conjunctions or disjunctions over an infinite set of functions are not allowed? – Said Savci Apr 20 '17 at 12:26
-
As I said, I'm just missing an explanation that goes back to some definition in propositional calculus. My book says "it is not possible to have an infinite set of formulas in a conjunction or disjunction". From your answer, I do not see why it should not be possible. – Said Savci Apr 20 '17 at 12:34
-
@Javiator - in fact, is it not impossible... see Infinitary Logics. But we have to follow a "pedagogically reasonable" path to learn things. To a schoolboy we teach sum saying that we can add only a finite number of numbers at a time. And later we introduce $\sum_{i=0}^{\infty}$; this means that the rules of elementary arithmetic are wrong and that $2+2$ is not $4$ ? – Mauro ALLEGRANZA Apr 20 '17 at 12:44