## Category Archives: Basic Set Theory and Logic

### All The Twos

Alex, Brad, Colin, Doug, Eric and Frank had a race to school from the bus-stop and then another race from school to the bus-stop. In the first race, Brad wasn’t last and Eric finished before Colin, Frank wasn’t first but finished before Doug, Brad finished before Frank but after Alex and Colin. Alex finished four places ahead of Doug. In the second race, Alex finished two places ahead of Doug and before Eric who in turn was two places ahead of Doug and before Eric who in turn was two places behind Colin. Alex wasn’t first and nor was Brad who finished before Eric. Frank finished one place ahead of Doug.

From the information given:

1. Which two boys finished in a better position in the first race than in the second race?
2. Which two boys finished in the same position in the second race as they did in the first race?

Let me see which of my student(s) is first in this !

Nalin Pithwa.

### Fun with English !!!

Done what ?

Arthur said Dave did it, Dave said Bill did it, Bill said Charlie did it, Charlie said that he didn’t do it and Eddie confessed that he did it. If Arthur didn’t do it, one of the five of them did do it and only one of them is telling the truth, who did do it?

🙂 🙂 🙂

Nalin Pithwa

### Geometry problems for Pre-RMO

Practice Quiz:

1. Prove that the median of a triangle which lies between two of its unequal sides forms a greater angle with the smaller of those sides.
2. Point A is given inside a triangle. Draw a line segment with end-points on the perimeter of the triangle so that the point divides the segment in half.
3. If the sides of a triangle are longer than 1000 inches, can its area be less than one inch?

Nalin Pithwa

In 1905, Jules Richard, a French logician, invented a very curious paradox. In the English language, some sentences define positive integers and others do not. For example, “The year of the Declaration of Independence” defines 1776, whereas “The historical significance of the Declaration of Independence” does not define a number. So what about this sentence: “The smallest number that cannot be defined by a sentence in the English language containing fewer than 20 words.” Observe that whatever this number may be, we have just defined it using a sentence in the English language containing only 19 words. Oops.

A plausible way out is to say that the proposed sentence does not actually define a specific number. However, it ought to. The English language contains a finite number of words, so the number of sentences with fewer than 20 words is itself finite. Of course, many of  these sentences make no  sense, and many of those do make sense don’t define a positive integer — but, that just means that we have fewer sentences to consider. Between them, they define a finite set of positive integers, and it is a standard theorem of mathematics that in such circumstances there is a unique smallest positive integer that is not in the set. So on the face of it, the sentence does not define a specific positive integer.

But logically, it can’t.

Possible ambiguities of definition such as “A number which when multiplied by zero gives zero” don’t let us off the logical hook. If a sentence is ambiguous, then we must rule it out, because an ambiguous sentence doesn’t define anything. Is the troublesome sentence ambiguous, then? Uniqueness is not the issue:  there can’t be two distinct smallest-numbers-not-definable- (etc.), because one must be smaller than the other.

One possible escape route involves how we decide which sentences do or do not define a positive integer. For instance, if we go through them in some kind of order, excluding bad ones in turn, then the sentences that survive depend on the order in which they are considered. Suppose that two consecutive sentences are:

1. The number in the next valid sentence plus one.
2. The number in the previous valid sentence plus two.

These sentences cannot both be valid — they would then contradict each other. But, once we have excluded one of them, the other one is valid, because it now refers to a different sentence altogether.

Forbidding this type of sentence puts us on a slippery slope, with more and more sentences being excluded for various reasons. All of which strongly suggests that the alleged sentence does not, in fact, define a specific number — even though it seems to

With thanks to Prof Ian Stewart for this gem from his Cabinet of Mathematical Curiosities,

Nalin Pithwa

### G H Hardy on Set Theory

In these days of conflict between ancient and modern studies, there must surely be something to be said for a study, which did not start with Pythagoras and which will not end with Einstein, but is the oldest and the youngest — G H Hardy

### Alien Encounter: test your logic skills

Alien Encounter.

The starship Indefensible was in orbit around the planet Noncompostments, and Captain Quirk and Mr. Crock had beamed down to the surface.

“According to the Good Galaxy Guide, there are two species of intelligent aliens on this planet,” said Quirk.

“Correct, Captain —- Veracitous and Gibberish. They all speak Galaxic, and they can be distinguished by how they answer questions. The Veracitors reply truthfully, and the Gibberish always lie.’

‘But physically —‘

‘— they are indistinguishable, Captain.’

Quirk heard a sound, and turned to find three aliens creeping up on them. They looked identical.

‘Welcome to Noncomposimentis,’ said one of the aliens.

‘I thank you. My name is Quirk. Now, you are…’ Quirk paused. ‘No point in asking their names,’ he muttered. ‘For all we know, they will be wrong.’

‘That is logical, Captain,’ said Crock.

‘Because we are poor speakers of Galaxic,’ Quirk improvised, ‘I hope you will not mind if I call you Alfy, Betty and Gemma. As he spoke, he pointed to each of them in turn. Then, he turned to Crock and whispered, ‘Not that we know what sex they are, either.’

‘They are all hermandrofemigynes,’ said Crock.

‘Whatever. Now, Alfy: to which species does Betty belong?’

‘Gibberish.’

‘Ah, Betty: do Alfy and Gemma belong to different species?’

‘No.’

‘Right…Talkative lot, aren’t they? Um…Gemma: to which species does Betty belong?’

‘Veracitor.’

Quirk nodded knowledgeably.’Right, that’s settled it, then!’

‘Settled what, Captain?’

‘Which species each belongs to.’

‘I see. And those species are —?’

‘Haven’t the foggiest idea, Crock. You’re the one who’s supposed to be logical!’

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

So, dear students, have some fun!!

More later,

Nalin Pithwa

### Injections, surjections and bijections

A function $f: A \rightarrow B$ is called an injection if $f(a)=f(a^{'})$ implies $a=a^{'}$. There is another name for this kind of function. It is also called a one-to-one function or an injective map. A map $f:A \rightarrow B$ is one-one if two distinct elements of A have distinct images under f.

A function $f: A \rightarrow B$ is called a surjection if for every $b \in B$ there is an element $a \in A$ such that $f(a)=b$. In other words, $f(A)=B$. That is to say, every element of B is an image of some element of A under f. A surjective map is also called an onto map.

A map $f:A \rightarrow B$ which is both one-to-one and onto is called a bijection or a bijective map.

Examples.

1) Suppose $f: \Re \rightarrow \Re$ is defined by $f(x) =\cos{x}$. It is clear that this is neither one-to-one nor onto. Indeed because $f(x)=f(x+2\pi)$, it cannot be one-to-one. Since $f(x)$ never takes a value below -1 or above 1, it cannot be onto.

2) $f: \Re \rightarrow \Re$ defined by

$f(x)= x$, if $x \geq 0$ and $f(x)=x-1$, if $x<0$ is one-to-one but not onto as $-1/2$ is never attained by the function.

3) $f:\Re \rightarrow \Re$ defined by $f(x)=\frac{x}{1+|x|}$ is one-to-one but not onto.

Warning.

Trigonometric functions like sine and cosine are neither one-to-one nor onto. So, how does one define $\sin^{-1}{x}$ or $\cos^{-1}{x}$? Actually, there is ambiguity in defining these. If we write $\sin^{-1}{x}=\theta$, it means that $\sin{\theta}=x$. It is easily seen that there is no $\theta$ if x is more than 1 or less than -1. Thus, the domain of $\sin^{-1}{x}$ or $\cos^{-1}{x}$ must be $[-1.1]$. Then, again

$\sin{\theta}=x$ has many solutions $\theta$ for the same x. For example, $\sin{\pi/6}=\sin{5\pi/6}=1/2$. So, which of $\pi/6$ or $5\pi/6$ should claim to be the value of $\sin^{-1}{(1/2)}$? In such a case, we agree to take only one value in a definite way. For $0 \leq x \leq 1$, we choose $0 \leq \theta \leq \pi/2$ such that $\sin{\theta}=x$. It is obvious that there is only one such $\theta$. Similarly, for $-1 \leq x <0$, we choose $-\pi/2 \leq \theta < 0$ such that $\sin{\theta}=x$. Thus, this way of choosing $\theta$ such that $\sin{\theta}=x$ for $-1 \leq x <1$ has no ambiguity. such a value of the inverse circular function is called its principal value, though we could choose another set of values with equal ease.

Similar problems arise in the context of a function $f:\Re \rightarrow \Re$ defined by $f(x)=x^{2}$. The function f is neither one-to-one nor onto. But, if we take $f: \Re \rightarrow \Re_{+}$ as $f(x)=x^{2}$, then f is onto. We would like to define $f^{-1}:\Re_{+} \rightarrow \Re$ as a function. In order that we are able to define $f^{-1}$ as a function we must agree, once and for all, the sign of $f^{-1}{(x)}$. Indeed, since $f(-1)=f(1)=1$, which one would we call $f^{-1}$ ? In fact, $f^{-1}{(x)}$ is what we would like to denote by $\sqrt{x}$. But, we must decide if we are taking the positive value or the negative value. Once, we decide that, $f^{-1}$ would become a function.

More later,

Nalin Pithwa

### Composition of functions

Suppose A, B and C are sets and $f:A \rightarrow B$ and $g:B \rightarrow C$ are functions. We define a function

$h: A \rightarrow C$ by

$h(a)=g(f(a))$ for every $a \in A$.

It is easily seen that h is a well-defined function, as $f(a) \in B$ for every $a \in A$ and $g(b) \in C$ for every $b \in B$. The function h is called the composition of the functions g and f and is denoted by $g \circ f$.

Examples.

a) Suppose that in a forest, carnivorous animals sustain themselves by feeding only on herbivorous animals and the nutrition level of a herbivorous animal depends on the vegetation around the animal. So the nutrition level of a carnivorous animal ultimately depends on the vegetation around the population of herbivorous animals it feeds on. Thus, if V is the density of vegetation around the herbivorous animals n is the level of nutrition of the herbivorous animal (for simplicity measured by its weight, though there are often more parameters depicting the level of nutrition of an animal), $n: V \rightarrow \Re$ is a function. Similarly, if c is the level of nutrition of a carnivorous animal, then c is a function depending on the level of nutrition of herbivorous animals it feeds on:

$c: \Re \rightarrow \Re$

Thus, $c \circ n: V \rightarrow \Re$

is the level of nutrition of the carnivorous animal ultimately depending on the density of vegetation.

b) Take for example the force experienced by a moving charged particle in a magnetic field which is varying in time. We know that the force on the charged particle depends on the strength of the magnetic field in which it moves. Again, as the magnetic field strength varies with time, the force experienced is ultimately a function of time and position.

c) Suppose there is a lamp  in the room. The intensity of illumination at point in the room depends on the illuminating power of the lamp. The illuminating power of the lamp again depends on the voltage of the electricity supply which makes the lamp glow. So, ultimately, the intensity of illumination depends on the voltage of the power supply.

Exercise.

Give five more examples of composition of functions.

More later,

Nalin Pithwa

### Basic Set Theory: Functions

Among the kinds of relations we have been talking about, there are some which are very useful in mathematics. A relation $f \subset A \times B$ is called a function from A to B if

i) domain of $f=A$

ii) $(a,b) \in f$ and $(a,b^{'}) \in f \Longrightarrow b=b^{'}$.

Thus a function from A to B is a relation whose domain is the whole of A and which is not one-to-many. The set B is called the codomain or range of the function f.

If $f \subset A \times B$ is a function from A to B, then we write $f: A \rightarrow B$ and say that f is a function from A to B. We also say that f maps A into B and often a function is called a map or mapping. If

$(a,b) \in f$, we write

$b=f(a)$.

We call b the value of the function f at a or image of a under f. Observe that there can be no ambiguity in writing f(a) because it is impossible that $(a,b) \in f$ and $(a,b^{'}) \in f$ and $b \neq b^{'}$. So by definition of a function $f: A \rightarrow B$, we have for every $a \in A$ a unique $f(a) \in B$. Thus, a function would be completely determined if we knew $f(a) \in B$ for every $a \in A$. That is why sometimes a function is defined as a “rule” which associates to every element $a \in A$ a unique element $f(a)$ of B. We are obliged to put the word rule within quotation marks for the simple reason that the rule is often elusive. In fact, the aim in many situations is to “discover” the rule.

Examples

a) Suppose we are observing the position of a particle moving in a straight line. We know that at every instant of time the particle has a unique position on the line. If we agree that every point of the line corresponds to a real number with some convenient point on it decided to represent the real number zero, then the position of the particle at the time t is represented by the real number $x(t)$. We observe that our with our ordinary notion of time and position, we do not expect a particle to occupy two different positions at the same time (nothing prevents, though,the particle from occupying the same position at two different times. Indeed, if the particle is at rest for a certain length of time, then it would have the same position for the entire length of time.) Suppose every time is represented by a real number, zero being a certain time deemed as the present time, then all future times are represented by positive real numbers and past times by negative real numbers. Here, a real number is used as an intuitive object, say, as points on a line, postponing a mathematical discussion of real numbers later. Let $\Re$ be the set of real numbers, then the position of the particle moving in a straight line is, in fact, a function

$x: \Re \rightarrow \Re$

which associates to every time t, the position $x(t)$.

b) Look at a railway time table. Below a particular train there are times recorded in a column. It records the times of arrival and departure of a train at certain stations. We may look upon this as a function whose domain consists of disjoint intervals of time and range consists of certain cities where the train stops. Thus, for every time in the mentioned interval we have a city where the train is at that time. The table does not say anything about the train’s position at a time after its departure and before its arrival at the next. This does not disqualify it to be a function if we take the domain to be the intervals of time depicting the times of arrival and departure at certain stations.

c) Consider the distance of a particle, falling freely under gravity, measured from the point from where the particle started its fall. if we record the time since it began to fall, we know that the distance $x(t)$ at a time is given by the formula

$x(t)=(1/2)gt^{2}$

(assuming, of course that the gravity does not vary and there is no air resistance).

Here we have in fact a “rule” which tells us where the particle would be at any time. This certainly represents a function. However, we are often not so lucky to have a neat formula like this for other functions.

d) The incoming news on a particular day that tells us the temperature of the four metros recorded at 5.30 am on that day. Here, we have a definite temperature for every such metro at 5.30am of that day. So it is in fact a function whose domain consists of the set of four metros and range the real numbers quantifying temperature.

e) Look at your school time table. What does it record on a particular day? it records the subjects to be taught at different times of the day. A particular student has a particular subject being taught during a particular period,as a student is not expected to be in two different classes at the same time. So, for each student, the time table is a function whose domain is the set of periods and the range the set of subjects.

f) When we want to mail a letter enclosed in an envelope, we usually go to the post master with it to tell us the denomination of the stamp to be affixed. The post master weighs the letter and tells us the postage according to the weight. Here, we have a definite postage for a definite weight, we don’t have different rates for the same weight (for same kind of mail like registered or ordinary). The rate chart, with the post master, for a particular kind of mail, truly, is a function whose domain is the set of positive real numbers representing the weights of the mail and the range again consists of positive real numbers representing the postage. We write the chart as a function f such that

$p-f(a)$

meaning p is the postage to mail a letter of weight w.

g) We know that the solubility of a salt varies with temperature. That is to say that a given salt has a definite solubility at a definite temperature. So the relation which associates to every temperature the definite solubility of a salt is in fact a function.

h) Consider the population of a community of biological species at different times. If $N(t)$ is the population of the community at time t, then surely

$N: \Re \rightarrow \Re$

represents a function.

i) If we measure the voltage of an AC power supply over a period of time, we observe that it is different at different times. At every instant of time, it has a voltage Sometimes, it is positive, sometimes it is negative and sometimes zero. In fact, for ordinary domestic supply in India, the voltage varies between 330 volts and -330 volts. But this change from 330 volts to -330 volts occurs within an interval of $1/100$th of a second. (The ordinary DC voltmeters of your lab won’t be able to record this quick change in voltage). In fact, if $V(t)$ is the volrage at time t, we have

$V(t)$=E_{0}\sin{(\omega t + \phi)}

where $\omega=2\pi/50$ and $E_{0}=330$ and $\phi$ is a constant known as the phase.

j) Let S be a sphere resting on a horizontal plane H. Let n be the north pole and s be the southpole, where the sphere is touching the plane. Now let us join any other point $p \in S$ to n and extend it to meet the plane at some point q. Now to every point $p \in S - \{ n \}$, we have a unique point q on H. This defines a function

$f: S - \{ n \} \rightarrow H$. This function is called the stereographic projection of the sphere on the plane.

k) The trivial map or function $id: A \rightarrow A$ which sends every element of the set A to itself is called the identity map.

Look around, see and think…are there any functions that come to your notice? Let me know…

More later,

Nalin Pithwa

### Basic Set Theory: Relations

Among the various kinds of relations, we are familiar with, father, mother, son, brother, sister, husband, wife, less than, equal to, parallel to, etc., are a few examples. We would like to fix our ideas as to what exactly is meant by a relation. Let us see how we use the terms in common parlance. We say Dasaratha is the father of Rama. Similarly, Babar is the father of Humayun and Janaka is the father of Sita. The above statements like Dasaratha is the father or Rama are but examples fatherhood. But, what do we exactly mean by fatherhood? We may attempt to define fatherhood as the collection of pairs like Dasaratha and Rama, Babar and Humayun, Janaka and Sita, etc. But in our usage “Dasaratha is the father of Rama” we cannot interchange the positions of Dasaratha and Rama. Indeed the statement “Rama is the father of Dasaratha” does not convey the same meaning as the statement “Dasaratha is the father of Rama”. Again, in the statement “Dasaratha is the father of Rama”, if we drop  the word Rama, then too it won’t mean anything. For the statement about fatherhood, what is important is a pair in a definite order: (Dasartha, Rama). Thus, a certain collection of ordered pairs stands for a definite relation, as in this case the ordered pairs

(Dasaratha, Rama), (Babar, Humayun), (Janaka, Sita)

are examples of relation of fatherhood. So fatherhood would stand for a certain collection of ordered pairs of human beings. Similarly, the relation of brotherhood would stand for a certain other collection of ordered pairs. So would sisterhood, etc. In each case, they are different collections of ordered pairs. Now we proceed to define the term relation formally. For that we need the notion of a cartesian product.

Cartesian Product.

For sets A and B, the set of all ordered pairs formed by the first element from A and the second element from B, is called the Cartesian product of A and B. It is denoted by $A \times B$. We have

$A \times B= \{ (a,b): a \in A \hspace{0.1in} \textup{and} \hspace{0.1in} b \in B\}$

Relation.

By a relation or correspondence between the elements of a set A and those of a set B, we mean a subset f of the Cartesian product $A \times B$. Thus, f is a relation between set A and set B if

$f \subset A \times B$

If $(a,b) \in f$, then we say that a is related to b through f. We write this as afb. Thus, if f is the set of all human beings and M is the set of all male human beings, then fatherhood is a subset of $M \times H$, whereas brotherhood is another subset of $M \times H$. Motherhood is a subset of $W \times H$, where

$W = \{ w: w is a woman\}$. So if $f \subset M \times H$ is the fatherhood relation, $(a,b) \in f$ means a is the father of b. Similarly, if $g \in M \times H$ is the brotherhood relation, then $(a,b) \in G$ means a is a brother of b. (Observe that a is a brother of b does not imply b is a brother of a since b could be a sister of a. )

Definition:

For sets A and B if $f \subset A \times B$, then $\{ x: (x,u) \in f \hspace{0.1in} \textup{for some} \hspace{0.1in} u \in B\}$ is called the domain of the relation f, and $\{ y: (x,y) \in f \hspace{0.1in textup{for some} \hspace{0.1in} x \in A}\}$ is called the range of the relation f.

It is quite obvious that the domain of f, above, is a subset of A and the range. a subset of B.

In the above example of fatherhood, its domain cannot contain a woman. Nor did it contain all men. Indeed many men are not fathers.

Like father, mother, brother, sister we also have the relation less than, equal to, greater than, similar to, congruent to, perpendicular to, etc.

For the set $A=\{ 1,2,3,4\}$, let $f \subset A \times A$ be defined by

$f=\{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)\}$.

We see that the relation f here is the relation less than in the set A. Here the domain of f is $\{ 1,2,3\}$ whereas the range is $\{ 2,3,4\}$.

In case, $f \subset A \times A$, we call f a relation in A. For A, the set of all lines parallel to is a subset of

$A \times A$. Similarly, for the set T of all triangles, similarity and congruence are subsets of $T \times T$. We enumerate a few relations.

1) A relation f in A{ that is, $f \subset A \times A$ is called a symmetric relation if $afb \Longleftrightarrow bfa$.

2) $f \subset A \times A$ is called a reflexive relation if afa for all $a \in A$.

3) $f \subset A \times A$ is called an antisymmetric relation if $afb \hspace{0.1in} \textup{and} \hspace{0.1in} bfa \Longrightarrow a=b$

4) A relation $f \subset A \times A$ is called a transitive relation if $afb, bfc \Longrightarrow afc$.

Examples.

a) Similarity of triangles is reflexive, symmetric and transitive.

b) Fatherhood is neither reflexive, nor symmetric, nor transitive.

c) “Ancestor of” is transitive but is neither reflexive nor symmetric.

d) The relationship “a is the spouse of b” is symmetric but neither reflexive nor symmetric.

e) “Less than” is transitive but not reflexive.

f) “Less than or equal to” is reflexive, antisymmetric and transitive.

g) If X is a class of sets, let $R \subset X \times X$ be defined by ARB if $A \subset B$. We see that R is a reflexive, antisymmetric and transitive relation.

Digression.

The way we have defined relation should strictly be called binary relation as it consists of ordered pairs. But, we have other kinds of relations too. Like collinearity of points, concurrence of lines, etc. They are not binary relations. But we don’t go into them here.

Equivalence relation.

A relation $\sim$ on A is called an equivalence relaiton if it is reflexive, symmetric and transitive, that is,

i) $a \sim a$ for all $a \in A$.

ii) $a \sim b \Longleftrightarrow b \sim a$

iii) $a \sim b \hspace{0.1in} \textup{and} \hspace{0.1in} b \sim c \Longrightarrow a \sim c$.

Examples.

a) Equality is certainly an equivalence relation.

b) Similarity between triangles is an equivalence relation.

c) Congruence of triangles is an equivalence relation.

d) Parallelism between lines is an equivalence relation if we agree that a line is parallel to itself.

e) Define a relation $\equiv (\mod 5)$ on Z by $m \equiv n (\mod 5)$ if $m - n$ is divisible by 5. Note that this is an equivalence relation.

More later,

Nalin Pithwa