1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difference between formal systems and theories

  1. Apr 30, 2014 #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. Apr 30, 2014 #2


    Staff: Mentor

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


    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 [Broken]

    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.
    Last edited by a moderator: May 6, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook