Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm completely unfamiliar with terminologies of mathematical logic and I have never taken any 'mathematical logic' class.

The first time i started to study Mathematics (Set Theory), I memorized the 'Truth Table' shows truth or falsity values of $\neg P$, $P\vee Q, P\wedge Q$ and $P\Rightarrow Q$.

Then I showed that "$\neg P \vee Q$ is true iff $P\Rightarrow Q$ is true" and "$P\Rightarrow Q$ is true iff $\neg Q \Rightarrow \neg P$ is true" and etc.

(I think this approach of introducing mathematical logic to students (just like me) who wishes to study this first in their life time, is not good.)

I guess my logic system is 'Classical Logic', is it?


I want to make a brief and concrete summary of mathematical logic. I, of course, tried to read wikipedia articles about mathematical logic, but there are tons of terminologies I have never seen. Here's what I understood and what I am curious to know:

  1. There seems to be two different meanings of mathematical logic. One is "Classical Logic, Intuitionistic Logic, etc" and another "Set theory, Model Theory, Recursive Theory, etc (http://en.wikipedia.org/wiki/Mathematical_logic). Then, Theory is a somewhat mixture of one from the one class, and one from another class. Am I right?

  2. What does "$P$ is a provable sentence in a theory $T$" mean? Does this mean "starting from the axioms of $T$, showing that the sentence $P$ is true with respect to the Truth Table above"?

share|improve this question
    
I guess a theory is a set of axioms and rules of inference that allow you to somehow relate those axioms. That $P$ is provable under $T$ means that from those axioms and with those rules, you can build $P$ as a theorem. For example, under the Peano axioms, defining the sum $m+n$ recursively to get to the axiom os succesors, $P:3+2=5$ is provable. The rules could be that if $m+n=a$ is an axiom or a theorem, then $s(m)+n=s(a)$ and $m+s(n)=s(a)$ are also theorems, with $s(m)$ referring to the succesor of a natural number as defined by those Peano axioms. –  MyUserIsThis Jan 25 '13 at 19:22
1  
What you have seems to be (classical) propositional logic. The "propositional" indicates that you are not dealing with quantifiers, but only with connectives (and, or, ...). The "classical" differentiates it from other versions, where truth values are computed differently, such as in intuitionistic logic. –  Andres Caicedo Jan 25 '13 at 19:23
    
BTW, if you want a very divulgative and great book about mathematical logic, you might like GEB, by Douglas Hofstadter –  MyUserIsThis Jan 25 '13 at 19:24
    
Now, when dealing with logic you have two components: A semantic, where you define truth, and in this case this is done via truth tables. And a syntactic component, where you can talk about proofs. There is a set of axioms and rules that allow you to carry out proofs of propositional statements. There is a completeness theorem that tells you that everything true is provable, and a soundness theorem that tells you that, vice versa, everything provable is true. –  Andres Caicedo Jan 25 '13 at 19:26
1  
I would say yes. Naturally, one can get a decent understanding and even a good working understanding of portions of these fields while skipping the foundations, but to truly understand them, there is no way to circumvent these foundations, and I personally would not recommend trying to do it. –  Andres Caicedo Jan 25 '13 at 19:43

1 Answer 1

  1. There seems to be two different meanings of mathematical logic. One is "Classical Logic, Intuitionistic Logic, etc" and another "Set theory, Model Theory, Recursive Theory, etc (http://en.wikipedia.org/wiki/Mathematical_logic). Then, Theory is a somewhat mixture of one from the one class, and one from another class. Am I right?

Yes. "(Mathematical) Logic" refers both to a mathematical subject, and to specific logics (propositional, first-order, modal etc.), much the same as the term "algebra".

"Theory" is often used to denote a system which is not a system of logic. However, theories are based on (a specific) logic; they extend the base logic with additional external content (e.g. $(\forall n\in\mathbb{N})(n + 0 = 0)$). Theories are often categorized according to which logic they use as their base; e.g. you can hear about "first-order theories". The external content can be anything one would like to talk about in a formalized manner. Probably the most famous example is the first-order Peano Arithmetic (PA).

Theories and logics are similiar, for example they both have axioms, rules of inference and we try to give appropriate semantics to both. And there are differences: if $F$ is a random well-formed-formula (wff) of logic $L$, we (often) don't care whether we can deduce either $F$ or $\neg F$ (the fact that we can't deduce $F$ from $L$ is written as $L \nvdash F$). If $F$ is a propositional variable and $L$ propositional logic, then we want $F$ (and $\neg F$) not to be deducible from $L$. On the other hand, we try to avoid such phenomena in theories such as PA (where it's unavoidable due to incompleteness).

  1. What does "P is a provable sentence in a theory T" mean? Does this mean "starting from the axioms of T, showing that the sentence P is true with respect to the Truth Table above"?

Roughly, yes.

When given a theory, you are given a set of axioms - which are looked at as just strings of symbols (we know they mean something, for example in $2 + 2 = 4$, we know that $+$ refers to the operations we know of; but we pretend we don't know the "meaning"), and the set of rules of transformations, which basically say what you can do with the axioms. These two (and the language defining what is wff) are called the syntax.

When it comes to propositional logic (PL), one such system (there is more than one formalization of PL) might give you axioms like $\neg(P \wedge \neg P)$ and rules such as "When given $P$ you are allowed to deduce $P \vee S$". Things like commutation of disjunction have to be proven using such rules (even though you already know that "$\vee$" means "or", so it's obvious that commutation holds, you aren't allowed to use such outside knowledge).

On the other hand, there is semantics. Semantics doesn't use rules of transformation, but "the definition of truth". There are many tools helping you to see when is a given formula true according to such definition: truth tables are one of them. When a formula is "true" according to logic's definition of truth, we write $L \models F$. When a formula is deducible, $L \vdash F$. Property that $L \models F \Rightarrow L \vdash F$ is called completeness. $L \vdash F \Rightarrow L \models F$ is called soundness. Both hold for PL and First-order logic, so that you indeed (indirectly) know that F is deducible if it's truth table contain only $\top$'s.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.