# logic and set theory

# Set theory, relations, functions: preliminaries part 1

# Why do we need proofs? In other words, difference between a mathematician, physicist and a layman

Yes, I think it is a very nice question, which kids ask me. Why do we need proofs? Well, here is a detailed explanation (I am not mentioning the reference I use here lest it may intimidate my young enthusiastic, hard working students or readers. In other words, the explanation is not my own; I do not claim credit for this…In other words, I am just sharing what I am reading in the book…)

Here it goes:

What exactly is the difference between a mathematician, a physicist, and a layman? Let us suppose that 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 say “the sum of the three angles in a triangle is 180 degrees.” A physicist will be more cautious in dealing with the exceptional cases. He will examine them more carefully. If he finds that the sum in them is somewhere between 179 degrees to 180 degrees, say, then he will attribute the deviation to experimental errors. He will then state a law: The sum of 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 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 fussiest 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. But that is not the same thing as a proving a theorem. The only proof acceptable to a mathematician is the one which follows from earlier theorems by sheer logical implications (that is, statements of the form : If P, then Q). For example, such a proof follows easily from the theorem that an external angle of a triangle is the sum of the other two internal angles.

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. In the former, we make a few observations and generalize. In the latter, we deduce from something which is already proven. Of course, a question can be raised as to on what basis this supporting theorem is proved. The answer will be some other theorem. But then the same question can be asked about the other theorem. Eventually, a stage is reached where a certain statement cannot be proved from any other earlier proved statement(s) and must, therefore, be taken for granted to be true. Such a statement is known as an axiom or a postulate. Each branch of math has its own axioms or postulates. For examples, one of the axioms of geometry is that through two distinct points, there passes exactly one line. The whole beautiful structure of geometry is based on 5 or 6 axioms such as this one. Every theorem in plane geometry or Euclid’s Geometry can be ultimately deduced from these axioms.

PS: One of the most famous American presidents, Abraham Lincoln had read, understood and solved all of Euclid’s books (The Elements) by burning mid-night oil, night after night, to “sharpen his mental faculties”. And, of course, there is another famous story (true story) of how Albert Einstein as a very young boy got completely “addicted” to math by reading Euclid’s proof of why three medians of a triangle are concurrent…(you can Google up, of course).

Regards,

Nalin Pithwa

# Basic set theory and logic tutorial

- In the town of Seville lives a barber who shaves everyone who does not shave himself. Does the barber shave himself? In terms of set theory, the question is : Let
*R*be the set of all sets that are not members of themselves. Does R contain itself? (please do not Google else you will lose a golden chance to train your intellect. Think of the tutorial question as nurturing your intellect in math and logic…) - Suppose X has 3 friends: A, B and C, who are respectively, good at cricket, music and mountaineering, but not at any other fields. What is the fallacy in the following? “The statement ‘One of X’s friends is a cricketer’ is true and so is the statement ‘One of X’s friends is a musician’. So their conjunction is true, that is, the statement ‘One of X’s friends is both a cricketer and a musician’ is true. But X has no such friends.
- Take an English-to-English dictionary (any other language will also do). Start with any word and note down any word occurring in its definition as given in the dictionary. Take this new word and note down any word appearing in its definition. Repeat the process with this new word until a vicious circle results. Prove that a vicious circle is unavoidable no matter which word one starts with . (Caution: the vicious circle may not always involve the original word)
*Note: So, now, do you see that the words “point” , “line” and “surface” are not defined, but taken as known “intuitively”?* - On both the sides of a piece of paper it is written: “The sentence on the other side is false”. Are the two sentences so written statements? Why? What if on one side,”the sentence on the other side is true” is written and on the other side, “the sentence on the other side is false”?
*Note that in math: a statement can have only one truth value; it cannot contradict itself.*

Regards,

Nalin Pithwa.

# Definition of definition: Prof Tim Gowers, Fields Medalist

https://www.dpmms.cam.ac.uk/~wtg10/definition.html

With thanks and regards to Prof. Gowers,

Nalin Pithwa

# Definition meaning

In math especially, we encounter the word “definition” from middle school or high school. But, what is the definition of definition ??? In simpler words, what is the exact meaning of definition? I think you can see a standard dictionary.

The definition of definition is as follows:

It means the precise or exact or unique (one and only one) meaning of some thing/some concept we are considering/discussing.

For example, in math, we talk of rational numbers. But there is nothing “rational” about “rational numbers”. So, also there is nothing “irrational” about “irrational” numbers. The definition of a rational number is: if a number can be expressed in the form , where p, q are integers and , then such a number is called rational. This is “the” “definition” of a “rational” number. That means, this is the one and only one meaning of a rational number. Irrespective of whether a person is studying math in some country, some village, or even one hundred before and one hundred years later from now.

Whereas in humanities, social sciences, arts, politics etc. the “meaning” of word like “good painting”, “good music” etc can be hotly debated (and perhaps, forever…:-) the meaning of the word “rational number” is unique — that is why math is an exact/precise/objective science.

So, it is v important to understand and remember and apply various math definitions by dint of practising different kinds of problems.

Regards,

Nalin Pithwa

# Axiomatic Method : A little explanation

I) Take an English-into-English dictionary (any other language will also do). Start with any word and note down any word occurring in its definition, as given in the dictionary. Take this new word and note down any word appearing in it until a vicious circle results. Prove that a vicious circle is unavoidable no matter which word one starts with , (Caution: the vicious circle may not always involve the original word).

For example, in geometry the word “point” is undefined. For example, in set theory, when we write or say : ; the element “a” ‘belongs to’ “set A” —- the word “belong to” is not defined.

So, in all branches of math or physics especially, there are such “atomic” or “undefined” terms that one starts with.

After such terms come the “axioms” — statements which are assumed to be true; that is, statements whose proof is not sought.

The following are the axioms based on which equations are solved in algebra:

- If to equals we add equals, we get equals.
- If from equals we take equals, the remainders are equal.
- If equals are multiplied by equals, the products are equal.
- If equals are divided by equals (not zero), the quotients are equal.

More later,

Nalin Pithwa.

# Check your mathematical induction concepts

Discuss the following “proof” of the (false) theorem:

If n is any positive integer and S is a set containing exactly n real numbers, then all the numbers in S are equal:

PROOF BY INDUCTION:

Step 1:

If , the result is evident.

Step 2: By the induction hypothesis the result is true when ; we must prove that it is correct when . Let S be any set containing exactly real numbers and denote these real numbers by . If we omit from this list, we obtain exactly k numbers ; by induction hypothesis these numbers are all equal:

.

If we omit from the list of numbers in S, we again obtain exactly k numbers ; by the induction hypothesis these numbers are all equal:

.

It follows easily that all numbers in S are equal.

*************************************************************************************

Comments, observations are welcome 🙂

Regards,

Nalin Pithwa

# Tutorial on Basic Set Theory and Functions: for PRMO, RMO and IITJEE Mains maths

I) Prove that every function can be represented as a sum of an even function and an odd function.

II)Let A, B, C be subsets of a set S. Prove the following statements and illustrate them with Venn Diagrams:

2a) The famous DeMorgan’s laws in their basic forms: and . Assume that both sets A and B are subsets of Set S. In words, the first is: union of complements is the complement of intersection; the second is: intersection of two complements is the complement of the union of the two sets.

**Sample Solution:**

Let us say that we need to prove: .

Proof: It must be shown that the two sets have the same elements; in other words, that each element of the set on LHS is an element of the set on RHS and vice-versa.

If , then and . This means that , and and . Since and , hence . Hence, .

Conversely, if , then and . Therefore, and . Thus, and , so that . QED.

2b) .

2c)

III) Prove that if I and S are sets and if for each , we have , then .

**Sample Solution: **

It must be shown that each element of the set on the LHS is an element of the set on RHS, and vice-versa.

If , then and . Therefore, , for at least one . Thus, , so that .

Conversely, if , then for some , we have . Thus, and . Since , we have . Therefore, . QED.

IV) If A, B and C are sets, show that :

4i)

4ii)

4iii)

4iv)

V) Let I be a nonempty set and for each let be a set. Prove that

5a) for any set B, we have :

5b) if each is a subset of a given set S, then

VI) Prove that if , , and are functions, then :

VII) Let be a function, let A and B be subsets of X, and let C and D be subsets of Y. Prove that:

7i) ; in words, image of union of two sets is the union of two images;

7ii) ; in words, image of intersection of two sets is a subset of the intersection of the two images;

7iii) ; in words, the inverse image of the union of two sets is the union of the images of the two sets.

7iv) ; in words, the inverse image of intersection of two sets is intersection of the two inverse images.

7v) ; in words, the inverse of the image of a set contains the set itself.

7vi) ; in words, the image of an inverse image of a set is a subset of that set.

For questions 8 and 9, we can assume that the function f is and a set A lies in domain X and a set C lies in co-domain Y.

8) Prove that a function f is 1-1 if and only if for all ; in words, a function sends different inputs to different outputs iff a set in its domain is the same as the inverse of the image of that set itself.

9) Prove that a function f is onto if and only if for all ; in words, the image of a domain is equal to whole co-domain (which is same as range) iff a set in its domain is the same as the image of the inverse image of that set.

Cheers,

Nalin Pithwa

# Check your talent: are you ready for math or mathematical sciences or engineering

At the outset, let me put a little sweetener also: All I want to do is draw attention to the importance of symbolic manipulation. If you can solve this tutorial easily or with only a little bit of help, I would strongly feel that you can make a good career in math or applied math or mathematical sciences or engineering.

On the other hand, this tutorial can be useful as a “miscellaneous or logical type of problems” for the ensuing RMO 2019.

I) Let S be a set having an operation * which assigns an element a*b of S for any . Let us assume that the following two rules hold:

i) If a, b are any objects in S, then

ii) If a, b are any objects in S, then

Show that S can have at most one object.

II) Let S be the set of all integers. For a, b in S define * by a*b=a-b. Verify the following:

a) unless .

b) in general. Under what conditions on a, b, c is ?

c) The integer 0 has the property that for every a in S.

d) For a in S,

III) Let S consist of two objects and . We define the operation * on S by subjecting and to the following condittions:

i)

ii)

iii)

Verify by explicit calculation that if a, b, c are any elements of S (that is, a, b and c can be any of or ) then:

i)

ii)

iii)

iv) There is a particular a in S such that for all b in S

v) Given , then , where a is the particular element in (iv) above.

This will be your own self-appraisal !!

Regards,

Nalin Pithwa