I'm a beginner in mathematical logic, and currently studying(myself, without any colleague, which is sad and so asking in here) basics of formal system. Before asking a question, I'll introduce my understandings of the concepts about collation and rules of formation.

My understandings.
Collation : A collation is a structure which comprised with placeholders. A placeholder is a representation of entry for strings. We denote a premise free placeholder by $\square$ and if we want to represent a placeholder which is quantified by a specific set of strings, we say a placeholder is a variable.
Rule of formation : A rule of formation, or simply a rule, is literally a rule which defines how to construct a collation. (and I don't know why do we have to know this concept. If someone gives you a collation, then the collation itself contains a rule, so I am thinking that a rule is not relevant concept.)

and a bonus,

Formal grammar : A Formal grammar, or simply a syntax, comprises of collations which determine WFF(Well Formed Formula) in formal language.

My Question.
As I mentioned above, I don't know why do we define a rule of formation, as it contained in the concept of collation. Of course, in the precondition that my understandings are correct (however, you can point me out if some of my understandings are wrong). What are the differences between a collation and a rule of formation?


You can see in ProofWiki Formal Language, with pointers to collation and formal grammar, where "collation" is exemplified with "words and the method of concatenation".

In the article about Formal language I've not found this term.

Personally, I think it is too complicated a way to present a formal system for mathematical logic.

You can see some textbooks, like :

Mordechai Ben-Ari, Mathematical Logic for Computer Science (3rd ed - 2012), page 14-on : A Formal Grammar for Formulas [of propositional logic]

and :

Richard Kaye, The Mathematics of Logic : A Guide to Completeness Theorems and their Applications (2007), page 24-on : Ch.3 : Formal systems.

Roughly speaking, in mathematical logic we need the following concepts : alphabet, made of symbols, words (strings of symbols) and formulas : certain strings of symbols built up accordding to formation rules.

  • $\begingroup$ I've read a link before and read it now again and still ambiguous to me. In the link, it said that "Often, the collation system is left implicit, and taken simply to match the formal grammar." but I really don't know the difference between collation and rules of formation. I really want some wise man to solve and straight my problem. And I appreciate for book recommendations. I currently use the textbook Mathematical logic - Ebbinghaus, but this book is really cryptic for me, as a beginner. $\endgroup$ – Guinea Pig Jul 14 '14 at 16:35
  • $\begingroup$ @GuineaPig - sorry, but I've read many math log books, some with the definition of Formal System by means of Formal Grammer, but I've never found this use of "collation" ... $\endgroup$ – Mauro ALLEGRANZA Jul 14 '14 at 19:15
  • $\begingroup$ But as you can see, there exist a term collation. When I first learn about formal grammar in the textbook, it was really hard to understand as they didn't explained the notion of collation. But after I learned collation, I can understand quite better. You can check this link if you want to know about the concept explained in the textbook of Ebbinghaus. :) $\endgroup$ – Guinea Pig Jul 14 '14 at 19:20
  • $\begingroup$ @GuineaPig - I'm browsing Heinz-Dieter Ebbinghaus & Jörg Flum & Wolfgang Thomas, Mathematical Logic (2nd ed - 1984) and I do not found "collation". We have the usual terminology : alphabet (made of symbols), words (strings of symbols) and formulas : certain strings of symbols built up accordding to formation rules. In ProofWiki "collation" are explained as "words and the method of concatenation". Thus, I confirm that in math log it is not "standard". $\endgroup$ – Mauro ALLEGRANZA Jul 14 '14 at 19:38

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.