Difference between formal systems and theories

  1. A theory is a subset of a formal language together with a set of inference rules on that formal language in which the members of the theory need no premises to be true, right? So if I had a subset ##\mathcal{T}## of a formal language ##\mathcal{F}##, and a set of inference rules in which all members of ##\mathcal{T}## were true without any premises, that would make ##\mathcal{T}## a theory, right?

    Now a formal system is an alphabet ##\Sigma## together with a subset ##F## of all words over ##\Sigma## whose members are well formed formulas, a set of inference rules on ##F## and another subset of ##F## that make up the axioms of the formal system.

    In short:
    • theory: formal language, inference rules, axioms.
    • formal system: alphabet, wff, inference rules, axioms.

    But isn't a subset of all words over an alphabet a formal language anyway? Making theories and formal systems the "same" concepts?

    Or are theories more general than subsets of formal languages? So the premises and conclusions in the rules of inference of a theory need not be well formed formulas of a formal language. Is that the case?

    Also, what field of mathematics should I look into to learn more about these concepts? Logic? Proof theory?
     
  2. jcsd
  3. jedishrfu

    Staff: Mentor

    While I can't answer your question on the differences between the two, I did find this writeup on formal language theory:

    http://en.wikipedia.org/wiki/Formal_language

    It mentions it has a basis in mathematics, computer science and linguistics. I've studied compiler language definition which is a mix of mathematics of set theory and compsci concepts so it seems to me that computer science will cover most of it in the context of compiler design.

    http://www.inf.unibz.it/~artale/Compiler/slide2.pdf

    the pdf above covers it in the context of compiler theory.

    I think the key difference is the wff feature of formal language that adds more rules on how you can form sentences from words.
     
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?

0
Draft saved Draft deleted