Mathematical Logic - The basic introduction
Table of Contents
What is Logic?
If mathematics is regarded as a language, then logic is its grammar.
In other words, logical precision has the same importance in mathematics as grammatical accuracy in a language. As linguistic grammar has sentences, statements--- logic has them too. After we discuss Sentence & Statements, we will proceed to further logical theories.
Sentences & Statements
A sentence is a collection of some words, those together having some sense.
For example:
- Math is a tough subject.
- English is not a tough subject.
- Math and English both are tough subjects.
- Either Math or English is tough subject.
- If Math is a tough subject, then English is also a tough subject.
- Math is a tough subject, if and only if English is a tough subject.
Just have a quick look on above collections of words. Those are sentences, as they yield some meanings too. First sentence is called Prime Sentence, i.e., sentence that either contains no connectives or, by choice, is regarded as "indivisible" . The five words
- not
- and
- or
- if .... then
- if and only if
and their combinations are called 'connectives'. The sentences (all but first) are called composite sentences, i.e., a declarative sentence (statement ) in which one or more connectives appear. Remember that there is no difference between a sentence and statement in general logic. In this series, sentences and statements would have the same meaning.
Connectives
not: A sentence which is modified by the word "not " is called the negation of the original sentence.
For example: "English is not a tough subject " is the negation of "English is a tough subject". Also, "3 is not a prime" is the negation of "3 is a prime". Always note that negation doesn't really mean the converse of a sentence . For example, you can not write "English is a simple subject " as the negation of "English is a tough subject ".
In mathematical writings, symbols are often used for conciseness. The negation of sentences/statements is expressed by putting a slash (/) over that symbol which incorporates the principal verb in the statement.
For example: The statement $ x=y$ (read 'x is equal to y') is negated as $ x \ne y $ (read 'x is not equal to y '). Similarly, $x \notin A$ (read 'x does not belong to set A ') is the negation of $x \in A$ (read 'x belongs to set A ').
Statements are sometimes represented by symbols like p, q, r, s etc. With this notation there is a symbol, $\not$ or ¬ (read as 'not') for negation. For example if 'p' stands for the statement "Terence Tao is a professor" then $\not p$ [or ¬p] is read as 'not p' and states for "Terence Tao is not a professor." Sometimes ~p is also used for the negation of p.
and: The word "and " is used to join two sentences to form a composite sentence which is called the conjunction of the two sentences.
For example, the sentence "I am writing, and my sister is reading " is the conjunction of the two sentences: "I am writing " and "My sister is reading ". In ordinary language (English), words like "but, while " are used as approximate synonyms for "and ", however in math, we shall ignore possible differences in shades of meaning which might accompany the use of one in the place of the other. This allows us to write "I am writing, but my sister is reading " having the same mathematical meaning as above.
The standard notation for conjunction is \wedge , read as 'and '. If p and q are statements then their conjunction is denoted by p \wedge q and is read as 'p and q'.
or: A sentence formed by connecting two sentences with the word "or " is called the disjunction of the two sentences. For example, "Justin Bieber is a celebrity, or Sachin Tendulkar is a footballer ." is a disjunction of "Justin Bieber is a celebrity " and "Sachin Tendulkar is a footballer ".
Sometimes we put the word 'either ' before the first statement to make the disjunction sound nice, but it is not necessary to do so, so far as a logician is concerned. The symbolic notation for disjunction is $ \vee$, read 'or'. If p and q are two statements, their disjunction is represented by $p \vee q$ and read as p or q.
if....then: From two sentences we may construct one of the from "If . . . . . then . . ."; which is called a conditional sentence. The sentence immediately following IF is the antecedent, and the sentence immediately following THEN is the consequent.
For example, "If 5 <6, 6<7, then 5<7 " is a conditional sentence with "5<6, 6<7 " as antecedent and "5<7 " as consequent. If p and q are antecedent and consequent sentences respectively, then the conditional sentence can be written as:
"If p then q".
This can be mathematically represented as $p \Rightarrow q$ and is read as "p implies q" and the statement sometimes is also called implication statement. Several other ways are available to paraphrase implication statements including:
- If p then q
- p implies q
- q follows from p
- q is a logical consequence of p
- p (is true) only if q (is true)
- p is a sufficient condition for q
- q is a necessary condition for p
If and Only If : The phrase "if and only if " (abbreviated as 'iff') is used to obtain a bi-conditional sentence. For example, "A triangle is called a right-angled triangle, if and only if one of its angles is 90° ."
This sentence can be understood in either ways: "A triangle is called a right-angled triangle if one of its angles is 90° " and "One of angles of a triangle is 90° if the triangle is right-angled triangle. " This means that first prime sentence implies second prime sentence and second prime sentence implies first one. (This is why 'iff' is sometimes called double-implication.)
Another example is "A glass is half filled iff that glass is half empty. "
If p and q are two statements, then we regard the biconditional statement as "p if and only if q" or "p iff q" and mathematically represent by " $p\iff q$ ". $\iff$ represents double implication and read as 'if and only if'.
In the statement $p \iff q$ , the implication $p \Rightarrow q$ is called direct implication and the implication $q \Rightarrow p$ is called the converse implication of the statement.
Other terms in logic:
Stronger and Weaker Statements: A statement p is stronger than a statement q (or that q is weaker than p) if the implication statement $p \Rightarrow q$ is true.
Strictly Stronger and Strictly Weaker Statements: The word 'stronger'(or weaker) does not necessarily mean 'strictly stronger' (or strictly weaker).
For example, every statement is stronger than itself, since $p \Rightarrow p$ . The apparent paradox here is purely linguistic. If we want to avoid it, we should replace the word stronger by the phrase 'stronger than' or 'possibly as strong as'.
If $p \Rightarrow q$ is true but its converse is false ( $q \not \Rightarrow p$ ), then we say that p is strictly stronger than q (or that q is strictly weaker than p). For example it is easy to say that a given quadrilateral is a rhombus that to say it is a parallelogram.
Another understandable example is that " If a blog is hosted on WordPress.com, it is powered with WordPress software." is true but " If a blog is powered with WordPress software , it is hosted on WordPress.com" is not true.
Logical Approach
What exactly is the difference between a mathematician, a physicist and a layman?
Let us suppose they all start measuring the angles of hundreds of triangles of various shapes, find the sum in each case and keep a record.
Suppose the layman finds that with one or two exceptions the sum in each case comes out to be 180 degrees. He will ignore the exceptions and state 'The sum of the three angles in a triangle is 180 degrees.'
A physicist will be more cautious in dealing the exceptional cases. He will examine then more carefully. If he finds that the sum in them some where 179 degrees to 181 degrees, say, then if will attribute the deviation to experimental errors. He will state a law - 'The sum of the three angles of any triangle is 180 degrees.' He will then watch happily as the rest of the world puts his law to test and finds that it holds good in thousands of different cases until somebody comes up with a triangle in which the law fails miserably.
The physicist now has to withdraw his law altogether or else to replace it by some other law which holds good in all the cases tried. Even this new law may have to be modified at a later date. And this will continue without end.
A mathematician will be the fuzziest of all. If there is even a single exception, he will refrain from saying anything. Even when millions of triangles are tried without a single exception, he will not state it as a theorem that the sum of the three angles in 'any' triangle is 180 degrees. The reason is that there are infinitely many different types of triangles. To generalize from a million to infinity is as baseless to a mathematician as to generalize from one to a million. He will at the most make a conjecture and say that there is a 'strong evidence' suggesting that the conjecture is true.
The approach taken by the layman or the physicist is known as the inductive approach whereas the mathematician's approach is called the deductive approach.
Inductive Approach
In inductive approach, we make a few observations and generalize. Exceptions are generally not counted in inductive approach.
Deductive Approach
In this approach, we deduce from something which is already proven.
Axioms or Postulates
Sometimes, when deducting theorems or conclusion from another theorems, we reach at a stage where a certain statement cannot be proved from any 'other' proved statement and must be taken for granted to be true, then such a statement is called an axiom or a postulate.
Each branch of mathematics has its own populates or axioms. For example, the most fundamental axiom of geometry is that infinitely many lines can be drawn passing through a single point. The whole beautiful structure of geometry is based on five or six such axioms and every theorem in geometry can be ultimately Deducted from these axioms.
Argument, Premises and Conclusion
An argument is really speaking nothing more than an implication statement. Its hypothesis consists of the conjunction of several statements, called premises. In giving an argument, its premises are first listed (in any order), then connecting all, a conclusion is given.
Example of an argument:
Premises:
- $p_1$ Every man is mortal.
- $p_2$ Ram is a man.
---------------------------------------------------------------------------------- - Conclusion: $q$ Ram is mortal.
Symbolically, let us denote the premises of an argument by $p_1, p_2, \ldots , p_n$ and its conclusion by $q$. Then the argument is the statement $(p_1 \wedge p_2 \wedge \ldots \wedge p_n) \Rightarrow q$ . If this implication is true, the argument is valid otherwise, it is invalid.