Register to reply

Difference between formal systems and theories

by V0ODO0CH1LD
Tags: difference, formal, systems, theories
Share this thread:
V0ODO0CH1LD
#1
Apr30-14, 11:27 AM
P: 242
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?
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
jedishrfu
#2
Apr30-14, 09:09 PM
P: 2,809
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.


Register to reply

Related Discussions
Some theories concerning potential difference Introductory Physics Homework 12
Difference between 'Quantum theories' Quantum Physics 70
Proof theoretic ordinal of zfc, and other formal systems Set Theory, Logic, Probability, Statistics 10
What is the difference between these systems of mass Chemistry 1
Formal series solutions to systems of linear or non-linear DEs (Cauchy problem) General Physics 0