Category Archives: Basic Set Theory and Logic

On Georg Cantor: Paradise Lost: E T Bell’s views

Mathematics, like all other subject, has now to take its turn under the microscope and reveal to the world any weaknesses there may be in its foundations. F. W. Westaway.

The controversial topic of Mengenlehre (theory of sets, or classes, particularly of infinite sets) created in 1874-1895 by Georg Cantor (1945-1918) may well be taken, out of its chronological order, as the conclusion of the whole story. This topic typifies for mathematics the general collapse of those principles which the prescient seers of the nineteenth century, foreseeing everything but the grand debacle, believed to be fundamentally sound in all things from physical science to democratic government.

If “collapse” is perhaps too strong to describe the transition the world is doing its best to enjoy, it is nevertheless true that the evolution of scientific ideas is now proceeding so vertiginously that evolution is barely distinguishable from revolution.

Without the errors of the past as a deep-seated focus of disturbance the present upheaval in physical science would perhaps not have happened; but to credit our predecessors with all the inspiration for what our own generation is doing, is to give them more than their due. This point is worth a moment’s consideration, as some may be tempted to say that the corresponding “revolution” in mathematical thinking, whose beginnings are now plainly apparent, is merely an echo of Zeno and other doubters of ancient Greece.

The difficulties of Pythagoras over the square root of 2 and the paradoxes of Zeno on continuity (or “infinite divisibility”) are — so far as we know — the origins of our present mathematical schism. Mathematicians today who pay any attention to the philosophy (or foundations) of their subject are split into at least two factions, apparently beyond present hope of reconciliation, over the validity of the reasoning used in mathematical analysis, and this disagreement can be traced back through the centuries to the Middle Ages and thence to ancient Greece. All sides have had their representatives in all ages of mathematical thought, whether that thought was disguised in provocative paradoxes as with Zeno, or in logical subtleties, as with some of the most exasperating logicians of the Middle Ages. The root of these differences is commonly accepted by mathematicians as being a matter of temperament: any attempt to convert an analyst like Weierstrass to the skepticism of a doubter like Kronecker is bound to be as futile as trying to convert a Christian fundamentalist to rabid atheism.

A few dated quotations from leaders in a dispute may serve as a stimulant — or, sedative according to taste — for our answer to the singular intellectual career of Georg Cantor, whose “positive theory of the infinite” precipitated in our generation the fiercest frog mouse battle (as Einstein once called it) in history over the validity of traditional mathematical reasoning.

In 1831 Gauss expressed his “horror of the actual infinite” as fpllows: “I protest against the use of infinite magnitude as something completed, which is never permissible in mathematics. Infinity is merely a way of speaking, the true meaning being a limit which certain ratios approach indefinitely close, while others are permitted to increase without restriction.”

Thus, if x denotes a real number, the fraction 1/x diminishes as x increases, and we can find a value of x such that 1/x differs from zero y any preassigned amount (other than zero) which may be as small as we please, and as x continues to increase, the difference remains less than ths preassigned amount; the limit of 1/x, “as x tends to infinity,” is zero. The symbol of infinity \infty ; the assertion \frac{1}{\infty}=0 is nonsensical for two reasons:”division by infinity” is an operation which is undefined, and hence, has no meaning; the second reason was stated by Gauss. Similarly, the symbol \frac{1}{0} = \infty is meaningless.

Cantor agrees and disagrees with Gauss. Writing in 1886 on the problem of the actual (what Gauss called completed) infinite, Cantor says that “in spite of the essential difference between the concepts of the potential and the actual infinite, the former meaning a variable finite magnitude increasing beyond all finite limits (like x in 1/x above), while the latter is a fixed, constant magnitude lying beyond all finite magnitudes, it happens only too often that they are confused.”

Cantor goes on to state that misuse of the infinite in mathematics had justly inspired a horror of the infinite among careful mathematicians of his day, precisely as it did in Gauss. Nevertheless, he maintains that the resulting “uncritical rejection of the legitimate actual infinite is no lesser a violation of the nature of things (whatever that may be — it does not appear to have been revealed to mankind as a whole), which must be taken as they are”—- however, that may be. Cantor thus definitely aligns himself with the great theologians of the Middle Ages, of whom he was a deep student and an ardent admirer.

Absolute certainties and complete solutions of age-old problems always go down better if well salted before swallowing. Here is what Bertrand Russell had to say in 1901 about Cantor’s Promethean attack on the infinite.

“Zeno was concerned with three problems…These are the problem of the infinitesimal, the infinite, and continuity….From his day to our own, the finest intellects of each generation in turn attacked these problems, but achieved, broadly speaking, nothing. …Weierstrass, Dedekind, and Cantor …have completely solved them. Their solutions…are so clear as to leave no longer the slightest doubt of difficulty. This achievement is probably the greatest of which the age can boast…The problem of the infinitesimal was solved by Weierstrass, the solutions of the other two was begun by Dedekind and definitely accomplished by Cantor.”

The enthusiasm of this passage warms us even today, although we know that Russell in the second edition of his and Whitehead’s Principia Mathematica admitted that all was not well with the Dedekind “cut”, which is the spinal cord of analysis. Nor is it well today. More is done for or against a particular creed in science or mathematics in a decade than was accomplished in a century of antinquity, the Middle Ages, or the late renaissance. More good minds attack on outstanding scientific or mathematical problem today than ever before, and finality has become the private property of fundamentalists. Not one of the finalities in Russell’s remarks of 1901 has survived. A quarter of a century agon those who were unable to see the great light which the prophets assured them was blazing overhead like the noonday sun in a midnight sky were called merely stupid. Today for every competent expert on the side of the prophets there is an equally competent and opposite expert against them. If there is stupidtiy anywhere it is so evenly distributed that it has ceased to be a mark of distinction. We are entering a new era, one of doubt and decent humility.

On the doubtful side about the same time (1905) we find Poincare “I have spoken of …of our need to return continually to the first principles of our science, and of the advantages of this for the study of the human mind. This need has inspired two enterprises which have assumed a very prominent place in the most recent development of mathematics. The first is Cantorism…Cantor introduced into science a new way of considering the mathematical infinite…but it has come about that we have encountered certain paradoxes, certain apparent contradictions that would have delighted Zeno the Eleatic and the school of Megara. So each must seek the remedy. I, for my part, and I am not alone — think that the important thing is never to indtroduce entities not completely definable in a finite number of words. Whatever be the cure adopted, we may promise ourselves the joy of the physician called in to treat a beautiful pathologic case.”

A few years later Poincare’s interest in pathology for its own sake had abated somewhat. At the International Mathematical Congress of 1908 at Rome, the satiated physician delivered himself of this prognosis: “Later generations will regard Mengenlehre as a disease from which one has recovered.”

It was Cantor’s greatest merit to have discovered in spite of himself and against his own wishes in the matter that the “body mathematic” is profoundly diseased and that the sickness with which Zeno infected it has not yet been alleviated. His disturbing discovery is a curious echo of his own intellectual life. We shall first glance at his material existence, not of much interest in themselves, perhaps, but singularly illuminative in their later aspects of his theory.

Of pure Jewish descent on both sides, Georg Ferdinand Ludwig Philipp Cantor was the first child of the prosperous merchant Georg Waldemar Cantor and his artistic wife Maria Bohm. The father was born in Copenhagen, Denmark, but migrated as a young man to St. Petersburg, Russia, where the mathematician Georg Cantor was born on March 3, 1845. Pulmonary disease caused the father to move in 1856 to Frankfurt, Germany where he lived in comfortable retirement till his death in 1863. From this curious medley of nationalities, it is possible for several fatherlands to call Cantor as their son. Cantor himself favoured Germany, but it cannot be said that Germany favoured him very cordially.

Georg had a brother Constantin, who became a German army officer (very few Jews ever did), and a sister Sophie Nobiling. The brother was a fine pianist; the sister an accomplished designer. Georg’s pent-up artistic nature found its turbulent outlet in mathematics and philosophy, both classical and scholastic. The marked artistic temperaments of the children were inherited from their mother, whose grandfather was a musical conductor, one of whose brothers, living in Vienna, taught the celebrated violinist Joachim. A brother of Maria Cantor was a musician, and one of her nieces a painter. If it is true, as claimed by the psychological proponents of drab mediocrity, that normality and phlegmatic stability are equivalent, all this artistic brilliance in his family may have been the root of Cantor’s instability.

The family were Christians, the father having been converted to Protestantism; the mother was a born Roman Catholic. Like his arch enemy Kronecker, Cantor favoured the Protestant side and acquired a singular taste for the endless hairsplitting of medieval theology. Had he not become a mathematician it is quite possible that he would have left his mark on theology or philosophy. As an item of interest that may be noted in this connection, Cantor’s theory of the infinite was eagely pounced upon by the Jesuits, whose keen logical minds detected in the mathematical imagery beyong their theological comprehension indubitable proofs of the existence of God and the self-consistency of the Holy Trinity with its three-in-one, one-in-three, co-equal and co-eternal. Mathematics has strutted to some pretty queer tunes in the past 2500 years, but this takes the cake. It is only fair to say that Cantor, who had a sharp wit and a sharper tongue when he was angered, ridiculed the pretentious absurdity of such “proofs,” devout Christian and expert theologian though he himself was.

Cantor’s school career was like that of most highly gifted mathematicians — an early recognition (before the age of fifteen) of his greatest talent and an absorbing interest in mathemtical studies. His first instruction was under a private tutor, followed by a course in an elementary school in St. Petersburg. When the family moved to Germany, Cantor first attended private schools at Frankfurt and the Darmstadt nonclassical school, entering the Wiesbaden Gymnasium in 1860 at the age of fifteen.

Georg was determined to become a mathematician, but his practical father, recognizing the boy’s mathematical ability, obstinately tried to force him into engineering as a more promising bread-and-butter profession. On the occasion of Cantor’s confirmation in 1860, his father wrote to him expressing the high hopes he and all Georg’s numerous aunts, uncles, and cousins in Germany, Denmark, and Russia had placed on the gifted boy””They expect from you nothing less than that you become a Theodor Schaeffer and later, perhaps, if God so wills, a shining star in the engineering firmament. ” When will parents recognize the presumptuous stupidity of trying to make a cart horse out of a born racer?

The pious appeal to God which was intended to blackjack the sensitive, religious boy of fifteen into submission in 1860 would today (thank God!) rebound like a tennis ball from the harder heads of our own younger generation. But it hit Cantor pretty hard. In fact, it knocked him out cold. Loving his father devotedly and being of a deeply religious nature, young Cantor could not see that the old man was merely rationalizing his own absurd ambition. Thus began the warping of Georg Cantor’s acutely sensitive mind. Instead of rebelling, as a gifted boy today might do with some hope of success, Georg submitted till it became apparent even to the obstinate father that he was wrecking his son’s disposition. But in the process of trying to please his father against the promptings of his own instincts Georg Cantor sowed the seeds of the self-distrust which was to make him an easy victim for Kronecker’s vicious attack in later life and cause him to doubt the value of his work. Had Cantor been brought up as an independent human being he would never have acquired the timid deference to men of established reputation which made his life wretched.

The father gave in the mischief was already done. On Georg’s completion of his school course with distinction at the age of seventeen, he was permitted by “dear papa” to seek a university career in mathematics. ‘My dear papa!” Georg writes in his boyish gratitude:”You can realize for yourself how greatly your letter delighted me. The letter fixes my future…Now I am happy when I see that it will not displease you if I follow my feelings in the choice. I hope you will live to find joy in me, dear father; since my soul, my whole being, lives in my vocation; what a man desires to do, and that to which an inner compulsion drives him, that will he accomplish!” Papa no doubt deserves a vote of thanks, even if Georg’s gratitude is a shade too servile for a modern taste.

Cantor began his university studies at Zurich in 1862, but migrated to the University of Berlin the following year, on the death of his father. At Berlin he specialized in mathematics, philosophy, and physics. The first two divided his interests about equally; for physics he never had any sure feeling. In mathematics his instructors were Kummer, Weierstrass, and his future enemy Kronecker. Following the usual German custom, Cantor spent a short time at another university, and was in residence for one semester of 1866 at Gottingen.

With Kummer and Kronecker at Berlin the mathematical atmosphere was highly charged with arithmetic. Cantor made a profound study of the Disquisitiones Arithmeticae of Gauss and wrote his dissertation, accepted for the Ph.D. degree in 1867, on a difficult point which Gauss had left aside concerning the solution in integers x, y, z of the indeterminate equation:

ax^{2}+by^{2}+cz^{2}=0

where a, b, c are any given integers. This was a fine piece of work, but it is safe to say that no mathematician who read it anticipated that the conservative author of twenty two was to become one of the most radical originators in the history of mathematics. Talent no doubt is plain enough in his first attempt, but genius —- no. There is not a single hint of the great originator in this severely classical dissertation.

The like may be said for all of Cantor’s earliest work published before he was twenty nine. It was excellent, but might have been done by any brilliant man who had thoroughly absorbed, as Cantor had the doctrine of rigorous proof from Gauss and Weierstrass. Cantor’s first love was the Gaussian theory of numbers, to which he was attracted by the sharp, hard, clear perfection of the proofs. From this, under the influence of the Weierstrassians, he presently branched off into rigorous analysis, particularly in the theory of trigonometric series. (Fourier series).

The subtle difficulties of this theory (where question of convergence of infinite series are less easily approachable than in the theory of power series) seem to have inspired Cantor to go deeper for the foundations of analysis than any of his contemporaries had cared to look, and he was led to his grand attack on the mathematics and philosophy of the infinite itself, which is at the bottom of all questions concerning continuity, limits and convergence. Just before he was thirty, Cantor published his first revolutionary paper (in Crelle’s Journal) on the theory of infinite sets. This will be described presently. The unexpected and paradoxical result concerning the set of all algebraic numbers which Cantor established in this paper and the complete novelty of the methods employed immediately marked the young author as a creative mathematician of extraordinary originality. Whether all agreed that the new methods were sound or not is beside the point: it was universally admitted that a man had arrived with something fundamentally new in mathematics. He should have been given an influential position at once.

Cantor’s material career was that of any of the less eminent German professors of mathematics. He never achieved his ambition of a professorship at Berlin, possibly the highest German distinction during the period of Cantor’s greatest and most original productivity (1874-1884, age twenty nine to thirty nine). All his active professional career was spent at the University of Halle, a distinctly third-rate institution, where he was appointed Privatdozent (a lecturer who lives by what fees he can collect from his students) in 1869 at the age of twenty four. In 1872 he was made assistant professor and in 1879 — before the criticism of his work had begun to assume the complexion of a malicious personal attack on himself — he was appointed full professor. His earliest teaching experience was in a girls’ school in Berlin. For this curiously inappropriate task he had qualified himself by listening to dreary lectures on pedagogy by an uninspired mathematical mediocrity before securing his state license to teach children. More social waste.

Rightly or wrongly, Cantor blamed Kronecker for his failure to obtain the coveted position at Berlin. When two academic specialists disagree violently on purely scientific matters, they have a choice, if discretion seems the better part of valour, of laughing their hatreds of and not making a fuss about them, or of acting in any of the number of belligerent ways that other people resort to when confronted with situations of antagonism. One way is to go at the other in an efficient, underhand manner, which often enables one to gain his spiteful end under the guise of sincere friendship. Nothing of this sort here ! When Cantor and Kronecker fell out, they disagreed all over, threw reserve to the dogs, and did everything but slit the other’s throat. Perhaps all this is a more decent way of fighting — if men must fight — than the sanctimonious hypocrisy of the other. The object of any war is to destroy the enemy, and being sentimental or chivalrous about the unpleasant business is the mark of an incompetent of fighter. Kronecker was one of the most competent warriors in the history of scientific controversy; Cantor, one of the least competent. Kronecker won. But, as will appear later, Kronecker’s bitter animosity toward Cantor was not wholly personal but at least partly scientific and disinterested.

The year 1874 which saw the appearance of Cantor’s first revolutionary paper on the theory of sets was also that of his marriage, at the age of twenty nine, to Vally Guttmann. Two sons and four daughters were born out of this marriage. None of the children inherited their father’s mathematical ability.

On their honeymoon at Interlaken the young couple saw a lot of Dedekind, perhaps the one first rate mathematician of the time who made a serious and sympathetic attempt to understand Cantor’s subversive doctrine.

Himself somewhat of a persona non grata to the leading German overloads of mathematics in the last quarter of the nineteenth century, the profoundly original Dedekind was in a position to sympathize with the scientifically disreputable Cantor. It is sometimes imagined by outsiders that originality is always assured of a cordial welcome in science. The history of mathematics contradicts this happy fantasy; the way of the transgressor in a well established science is likely to be the hard as it is in any other field of human conservatism, even when the transgressor is admitted to have found something valuable by overstepping the narrow bounds of bigoted orthodoxy.

Both Dedekind and Cantor got what they might have expected had they paused to consider before striking out in new directions. Dedekind spent his entire working life in mediocre positions; the claim — now that Dedekind’s work is recognized as one of the most important contributions to mathematics that Germany has ever made — that Dedekind preferred to stay in obscure holes while men who were in no sense his intellectual superiors shone like tin plates in the glory of the public and academic esteem, strikes observers who are themselves “Aryans” but not Germans as highly diluted eyewash.

The ideal of German scholarship in the nineteenth century was the lofty one of a thoroughly coordinated “safety first,” and perhaps rightly it showed an extreme Gaussian caution toward radical originality — the new thing might conceivably be not quite right. After all an honestly edited encyclopaedia is in general a more reliable source of information about the soaring habits of skylarks than a poem, say Shelley’s, on the same topic.

In such an atmosphere of cloying alleged fact, Cantor’s theory of the infinite —- one of the most disturbingly original contributions in mathematics in the past 2500 years — felt about as much freedom as a skylark trying to soar up through an atmosphere of cold glue. Even if the theory was totally wrong — and there are some who believe it cannot be salvaged in any shape resembling the thing Cantor thought he had launched — it deserved something better than the brickbats which were hurled at it chiefly because it was new and unbaptized in the holy name of orthodox mathematics.

The pathbreaking paper of 1874 undertook to establish a totally unexpected and highly paradoxical property of the set of all algebraic numbers. Definition: If r satisfies an algebraic equation of degree n with rational integer (common whole number) coefficients, and if r satisfies no such equation of degree less than n, then r is an algebraic number of degree n.

This can be generalized. For it is easy to prove that any root of an equation of the type

c_{0}x^{n}+c_{1}x^{n-1}+\ldots+c_{n-1}x+c_{n}=0,

in which the c’s are any given algebraic numbers (as defined above ), is itself an algebraic number. For example, according to this theorem, all roots of

(1-3\sqrt{-1})x^{2}-(2+5\sqrt{17})x+\sqrt[3]{90}=0

are algebraic numbers, since the coefficients are. (The first coefficient satisfies x^{2}-2x+10=0, the second, x^{2}-4x-421=0, the third, x^{3}-90=0, of the respective degrees 2, 2, and 3.)

Imagine (if you can) the set of all algebraic numbers. Among these will be all the positive rational integers 1, 2, 3, …, since any one of them, say, n, satisfies an algebraic equation, x-n=0, in which the coefficients (1 and -n) are rational integers. But in addition to these the set of all algebraic equations will include all roots of all quadratic equations with rational integer coefficients, and all roots of all cubic equations with rational integer coefficients, and so on, indefinitely. Is it not intuitively evident that the set of all algebraic numbers will contain infinitely more members than its subset of the rational integers 1, 2, 3, …? It might indeed be so, but it happens to be false.

Cantor proved that the set of all rational integers 1, 2, 3, …contains precisely as many members as the “infinitely more inclusive” set of all algebraic numbers.

A proof of this paradoxical statement cannot be given here, but the kind of device — that of “one-to-one correspondence” — upon which the proof is based can be easily be made intelligible. This should induce in the philosophical mind an understanding of what a cardinal number is. Before describing this simple but somewhat elusive concept it will be helpful to glance at an expression of opinion on this and other definitions of Cantor’s theory which emphasizes a distinction between the attitudes of some mathematicians and many philosophers toward all questions regarding “number” or “magnitude.”

“A mathematician never defines magnitudes in themselves, as a philosopher would be tempted to do; he defines their equality, their sum and their product, and these definitions determine, or rather constitute, all the mathematical properties of magnitudes. In a yet more abstract and more formal manner he lays down symbols and at the same time prescribes the rules according to which they must be combined; these rules suffice to characterize these symbols and to give them a mathematical value. Briefly, he creates mathematical entities by means of arbitrary conventions, in the same way that the several chessmen are defined by the conventions which govern their moves and the relations between them. Not all schools of mathematical thought would subscribe to these opinions, but they suggest at least one “philosophy” responsible for the following definition of cardinal numbers.

Note that the initial stage in the definition is the description of “same cardinal number,” in the spirit of Couturat’s opening remarks; “cardinal number” then arises phoenix-like from the ashes of its “sameness.” It is all a matter of relations between concepts not explicitly defined.

Two sets are said to have the same cardinal number when all the things in the sets can be paired off one-to-one. After the pairing there are to be no unpaired things in either set.

Some examples will clarify this esoteric definition. It is one of those trivially obvious and fecund nothings which are so profound that they are overlooked for thousands of years. The sets \{x,y,z \} and \{ a, b, c\} have the same cardinal number (we shall not commit the blunder of saying, “Of course! Each contains three letters”) because we can pair off the things x, y, z in the first set with those a, b, c in the second as follows: x with a, y with b, z with c, and having done so, find that none remain unpaired in either set. Obviously there are other ways for effecting the pairing. Again, in a Christian community practising technical monogamy, if twenty married couples sit down together to dinner, the set of husbands will have the same cardinal number as the set of wives.

As another instance of this obvious sameness, we recall Galileo’s example of the set of all squares of positive integers and the set of all positive integers:

1^{2}, 2^{2}, 3^{2}, 4^{2}, \ldots , n^{2}, \ldots

1, 2, 3, 4, \ldots, n, \ldots

The “paradoxical” distinction between this and the preceding example is apparent. If all the wives retire to the drawing room, leaving their spouses to sip port and tell stories, there will be precisely twenty human beings sitting at the table, just half as many as there were before. But if all the squares desert the natural numbers, there are just as many left as there were before. Dislike it or not we may (we sashould not, if we are rational animals), the crude miracle stares us in the fact that a part of a set may have the same cardinal number as the entire set. If anyone dislikes the “pairing” definition of “same cardinal number,” he may be challenged to produce a comelier. Intuition (male, female or mathematical) has been greatly overrated. Intuition is the root of all superstitions.

Notice at this stage that a difficulty of the first magnitude has been glossed. What is a set, or a class ? “That,” in the words of Hamlet,, “is the question.” We shall return to it, but we shall not answer it. Whoever succeeds in answering that innocent question to the entire satisfaction of Cantor’s critics will quite likely dispose of the more serious objections against his ingenious theory on the infinite and at the same time establish mathematical analysis on a non-emotional basis. To see that the difficulty is not trivial, try to imagine the set of all positive rational integers 1, 2, 3, …, and ask yourself whether, with Cantor, you can hold this totality — which is a class — in your mind as a definite object of thought, as easily apprehended as the class x, y, z of three letters. Cantor requires us to do just this thing in order to reach the transfinite numbers which he created.

Proceeding now to the definition of “cardinal number,” we introduce a convenient technical term; two sets or classes whose members can be paired off one-to-one (as in the examples given previously) are said to be similar. How many things are there in the set (or class) x, y, z? Obviously three. But what is “three”? An answer is contained in the following definition: “The number of things in a given class is the class of all classes that are similar to the given class.”

This definition gains nothing from attempted explanation: it must be grasped as it is. It was proposed in 1879 by Gottlob Frege, and again (independently) by Bertrand Russell in 1901. One advantage which it has over other definition of “cardinal number of a class” is its applicability to both finite and infinite classes. Those who believe the definition too mystical for mathematics can avoid it by following Couturat’s advice and not attempting to define “cardinal number.” However, that way also leads to difficulties.

Cantor’s spectacular result that the class of all algebraic numbers is similar (in the technical sense defined above) to its subclass of all the positive rational integers was but the first of many wholly unexpected properties of infinite classes. Granting for the moment that his reasoning in reaching these properties is sound, or, if not unobjectionable in the form in which Cantor left it, that it can be made rigorous, we must admit its power.

Consider for example the “existence” of transcendental numbers. It is known that it cost Hermite a tremendous effort to prove the transcendence of a particular number of this kind. Even today there is no general method known whereby the transcendence of any number which we suspect is transcendental can be proved; each new type requires the invention of special and ingenious methods. It is suspected. for example, that the number (it is a constant, although it looks as if it might be a variable from its definition) which is defined as the limit of

1+\frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} -\log{n}

as n tends to infinity is transcendental, but we cannot prove that it is. What is required is to show that this constant is not a root of any algebraic equation with rational integer coefficients.

All this suggests the question “How many transcendental number are there/” Are they more numerous than the integers, or the rationals, or the algebraic numbers as a whole, or are they less numerous? Since (by Cantor’s theorem) the integers, the rationals, and all algebraic numbers are equally numerous, the question amounts to this: can the transcendental numbers be counted off 1, 2, 3, …? Is the class of all transcendental numbers similar to the class of all positive rational integers? The answer is no; the transcendentals are infinitely more numerous than the integers.

Here we begin to get into the controversial aspects of the theory of sets. The conclusion just stated was like a challenge to a man of Kronecker’s temperament. Discussing Lindemann’s proof that $latex $\pi$ is transcendental, Kronecker had asked, “Of what use is your beautiful investigation regarding \pi? Why study such problems, since irrational (and hence, transcendental numbers) do not exist? ” We can imagine the effect of such a skepticism on Cantor’s proof that transcendentals are infinitely more numerous than the integers 1, 2, 3, …, which, according to Kronecker, are the noblest work of God and the only numbers that do exist.

Even a summary of Cantor’s proof is out of the question here, but something of the kind of reasoning he used can be seen from the following simple considerations. If a class is similar (in the above technical sense) to the class of all positive rational integers, the class is said to be denumerable. The things in a denumerable class can be counted off 1, 2, 3, …; the things in a non-denumerable class cannot be counted off 1, 2, 3, ….; there will be more things in a nondenumerable class than in a denumerable class. Do non-denumerable classes exist? Cantor proved that they do. In fact, the class of all points on any line-segment, no matter how small the segment is (provided it is more than a single point), is non-denumerable.

From this we see a hint of why the transcendentals are non-denumerable. We assume we know that any root of any algebraic equation is representable by a point on the plane of Cartesian geometry. All these roots constitute the set of all algebraic numbers, which Cantor proved to be denumerable. But if the points on a mere line segment are non-denumerable, it follows that all the points on the Cartesian plane are likewise non-denumerable. The algebraic numbers are spotted over the plane like stars against a black sky; the dense blackness is the firmament of the transcendentals.

The most remarkable thing about Cantor’s proof is that it provides no means whereby a single one of the transcendentals can be constructed. To Kronecker any such proof was sheer nonsense. Much milder instances of “existence proofs” roused his wrath. One of these in particular is of interest as it prophesied Brouwer’s objection to the full use of classical (Aristotelean logic) in reasoning about infinite sets.

A polynomial ax^{n}+bx^{n-1}+\ldots+l in which coefficients a, b, …, l are rational numbers is said to be irreducible if it cannot be factored into a product of two polynomials both of which have rational number coefficients. Now, it is a meaningful statement to most human beings to assert, as Aristotle would, that a given polynomial either is irreducible or is not irreducible.

Not so for Kronecker. Until some definite process, capable of being carried out in a finite number of nontentative steps, is provided whereby we can settle the reducibility of any given polynomial, we have no logical right, according to Kronecker, to use the concept of irreducibility in our mathematical proofs. To do otherwise, according to him, is to court inconsistencies in our conclusions and, at best, the use of “irreducibility” without the process described, can give us only a Scotch verdict of “not proven.” All such non-constructive reasoning is — according to Kronecker — illegitimate.

As Cantor’s reasoning in this theory of infinite classes is largely non-constructive, Kronecker regarded it as a dangerous type of mathematical insanity. Seeing mathematics headed for the madhouse under Cantor’s leadership, and being passionately devoted to what he considered the truth of mathematics, Kronecker attacked “the positive theory of infinity” and its hypersensitive author vigorously and viciously with every weapon that came to his hand, and the tragic outcome was that not the theory of sets went to the asylum, but Cantor. Kronecker’s attack broke the creator of the theory.

In the spring of 1884, in his fortieth year, Cantor experienced the first of those complete breakdowns which were to recur with varying intensity throughout the rest of his long life and drive him society to the shelter of a mental clinic. His explosive temper aggravated his difficulty. Profound fits of depression humbled himself in his own eyes and he came to doubt the soundness of his work. During one lucid interval he begged the authorities at Halle to transfer him from his professorship of mathematics to a chair of philosophy. Some of his best work on the positive theory of the infinite was done in intervals between one attack and the next. On recovering from a seizure he noticed that his mind became extraordinarily clear.

Kronecker perhaps has been blamed too severely for Cantor’s tragedy: his attack was but one of many contributing causes. Lack of recognition embittered the man who believed he had taken the first — and last — steps towards a rational theory of the infinite and he brooded himself into melancholia and irrationality. Kronecker however does appear to have been largely responsible for Cantor’s failure to obtain the position he craved in Berlin. It is usually considered not quite sporting for one scientist to deliver a savage attack on the work of a contemporary to his students. The disagreement can be handled objectively in scientific papers. Kronecker laid himself out in 1891 to criticize Cantor’s work to his students at Berlin, and it became obvious that there was no room for both under one roof. As Kronecker was already in possession, Cantor resigned himself to staying out in the cold.

However, he was not without some comfort. The sympathetic Mittag-Leffler not only published some of Cantor’s work in his journal (Acta Mathematica) but comforted Cantor in his fight against Kronecker. In one year alone Mittag-Leffler received no less than fifty two letters from the suffering Cantor. Of those who believed in Cantor’s theories, the genial Hermite was one of the most enthusiastic. His cordial acceptance of the new doctrine warmed Cantor’s modest heart: “The praises which Hermite pours out to me in this letter ….on the subject of the theory of sets are so high in my eyes, so unmerited, that I should not care to publish them lest I incur the reproach of being dazzled by them.”

With the opening of the new century Cantor’s work gradually came to be accepted as a fundamental contribution to all mathematics and particularly to the foundations of analysis. But unfortunately for the theory itself the paradoxes and antinomies which still infect it began to appear simultaneously. These may in the end be the greatest contribution which Cantor’s theory is destined to make to mathematics, for their unsuspected existence in the very rudiments of logical and mathematical reasoning about the infinite was the direct inspiration of the present critical movement in all deductive reasoning. Out of this we hope to derive a mathematics which is both richer and “truer” — freer from inconsistency — than the mathematics of the pre-Cantor era.

Cantor’s most striking results were obtained in the theory of non-denumerable sets, the simplest example of which is the set of all points on a line segment. Only one of the simplest of his conclusions can be stated here. Contrary to what intuition would predict, two unequal line segments contain the same number of points. Remembering that two sets contain the same number of things if, and only if, things in them can be paired off one-to-one, we easily see the reasonableness of Cantor’s conclusion.

An even more unexpected result can be proved. Any line-segment, no matter how small, contains as many points as an infinite straight line. Further, the segment contains as many points as there are in an entire plane, or in the whole 3-dimensional space, or in the whole of space of n dimensions (where n is any integer greater than zero) or, finally, in a space of denumerably infinite number of dimensions.

In this we have not yet attempted to define a class or a set. Possibly (as Russell held in 1912) it is not necessary to do so in order to have a clear conception of Cantor’s theory or for that theory to be consistent with itself — which is enough to demand of any mathematical theory. Nevertheless, present disputes seem to require that some clear, self-consistent definition be given. The following used to be thought satisfactory.

A set is characterized by three qualities: it contains all things to which a certain definite property (any redness, volume, or taste) belongs; no thing not having this property belongs to the set; each thing in the set is recognizable as the same thing and as different from all other things in the set — briefly, each thing in the set has a permanently recognizable individuality. The set itself is to be grasped as a whole. This definition may be too drastic for use.. Consider, for example, what happens to Cantor’s set of all transcendental numbers under the third demand.

At this point we may glance back over the whole history of mathematics — or as much of it as is revealed by the treatises of the master mathematicians in their purely technical works — and note two modes of expression which recur constantly in nearly all mathematical exposition. The reader perhaps has been irritated by the repetitious use of phrases such as “we can find a whole number greater than 2,” or “we can choose a number less than n and greater than n-2.” The choice of such phraseology is not merely stereotyped pedantry. There is a reason for its use, and careful writers mean exactly what they say when they assert that “we can find, etc.” They mean that “they can do what they say.”

In sharp distinction to this is the other phrase which is reiterated over and over again in mathematical writing: “there exists.” For example, some would say “there exists a whole number greater than 2,” or “there exists a number less than n and greater than n-2.” The use of such phraseology definitely commits its user to the creed which Kronecker held to be untenable, unless, of course, the “existence” is proved by a construction. The existence is not proved for the sets (as defined above) which appear in Cantor’s theory.

These two ways of speaking divide mathematicians into two types: the “we can” men believe (possibly subconsciously) that mathematics is a purely human invention; the “there exists” men believe that mathematics has an extra-human “existence” of its own, and that “we” merely come upon the “eternal truths” of mathematics in our journey through life, in much the same way that a man taking a walk in a city comes across a number of streets with whose planning he had nothing whatever to do.

Theologians are “exist” men; cautious skeptics for the most part “we” men. “There exist an infinity of even numbers, or of primes,” say the advocates of extra-human “existence”; “produce them,” says Kronecker and the “we” men.

That the distinction is not trivial can be seen from a famous instance of it in the New Testament. Christ asserted that the Father “exists”; Philip demanded “Show us the Father and it sufficeth us.” Cantor’s theory is almost wholly on the “existence” side. Is it possible that Cantor’s passion for theology determined his allegiance? If so, we shall have to explain why Kronecker, also a connoisseur of Christian theology, was the rabid “we” man that he was. As in all such questions ammunition for either side can be filched from any pocket.

A striking and important instance of the “existence” way of looking at the theory of sets is afforded by what is known as Zermelo’s postulate (stated in 1904). “For every set M whose elements are sets P (that is, M is a set of sets, or a class of classes), the sets P being non-empty and non-overlapping (no two contain things in common), there exists at least one set N which contains precisely one element from each of the sets P which constitute M.” Comparison of this with the previously stated definition of a set (or class) will show that the “we” men would not consider the postulate self-evident if the set M consisted, say, of an infinity of non-overlapping line segments. Yet the postulate seems reasonable enough. Attempts to prove it have failed. It is of considerable importance in all questions relating to continuity.

A word as how to this postulate came to be introduced into mathematics will suggest another of the unsolved problems of Cantor’s theory. A set of distinct, countable things, like all the bricks in a certain wall, can easily be ordered; we need only count them off 1, 2, 3, …, in any dozens of different ways that will suggest themselves. But how would we go about ordering all the points on a straight line? They cannot be counted off 1, 2, 3, ….The task appears hopeless when we consider that between any two points of the line “we can find,” or “there exists” another point of the line. If every time we counted two adjacent bricks another sprang in between them in the wall our counting would become slightly confused. Nevertheless, the points on a straight line do appear to have some sort of order: we can say whether one point is to the right or the left of another, and so on. Attempts to order the points of a line have not succeeded. Zermelo proposed his postulate as a means for making the attempt easier, but it itself is not universally accepted as a reasonable assumption or as one which it is safe to use.

Cantor’s theory contains a great deal more about the actual infinite and the “arithmetic” of transfinite (infinite) numbers than what has been indicated here. But, as the theory is still in the controversial stage, we may leave it with the statement of a last riddle. Does there “exist,” or can we “construct,” an infinite set which is not similar (technical sense of one-to-one matching) either to the set of all the positive rational integers or to the set of all points of a line? The answer is unknown.

Cantor died in a mental hospital in Halle on January 6, 1913, at the age of seventy three. Honours and recognition were his at the last, and even the old bitterness against Kronecker was forgotten. It was no doubt a satisfaction to Cantor to recall that he and Kronecker’s death in 1891. Could Cantor have lived till today he might have taken a just pride in the movement toward more rigorous thinking in all mathematics for which his own efforts to found analysis (and the infinite) on a sound basis were largely responsible.

Looking back over the long struggle to make the concepts of real number, continuity, limit, and infinity precise and consistently usable in mathematics, we see that Zeno and Eudoxus were not so far in time from Weierstrass, Dedekind and, Cantor as the twenty four or twenty five centuries which separate modern Germany from ancient Greece might seem to imply. There is no doubt that we have a clearer conception of the nature of the difficulties involved than our predecessors had, because we see the same unsolved problems cropping up in new guises and fields the ancients never dreamed of, but to say that we have disposed of those hoary old difficulties is a gross mis-statement of fact. Nevertheless, the net score records a greater gain than any which our predecessors could rightfully claim. We are going deeper than they ever imagined necessary, and we are discovering that some of the “laws” — for instance those of Aristotelian logic — which they accepted in their reasoning are better replaced by others — pure conventions — in our attempts to correlate our experiences. As has already been said, Cantor’s revolutionary work gave our present activity, its initial impulse. But, it was soon discovered — twenty one years before Cantor’s death — that his revolution was either too revolutionary or not revolutionary enough. The latter now appears to be the case.

The first shot in the counter revolution was fired in 1897 by the Italian mathematician Burali-Forti who produced a flagrant contradiction by reasoning of the type used by Cantor in his theory of infinite sets. This particular paradox was only the first of several, and as it would require lengthy explanations to make it intelligible, we shall state instead Russell’s of 1908.

Frege had given the “class of all classes similar to a given class” definition of the cardinal number of the given class. Frege had spent years trying to put the mathematics of numbers on a sound logical basis. His life work is Grundgesetze der Arithmetik (the Fundamental Laws of Arithmetic), of which the first volume was published in 1893, the second in 1903. In this work the concept of sets is used. There is also a considerable use of more or less sarcastic invective against previous writers on the foundations of arithmetic for their manifest blunders and manifold stupidities. The second volume closes with the following acknowledgement:

” A scientist can hardly encounter anything more undesirable than to have the foundation collapse just as the work is finished. I was put in this position by a letter from Bertrand Russell when the work was almost through the press.”

Russell had sent Frege his ingenious paradox of “the set of all sets which are not members of themselves.” Is this set a member of itself? Either answer can be puzzled out with a little thought to be wrong. Yet Frege had freely used “sets of all sets.”

Many ways were proposed for evading or eliminating the contradictions which began exploding like a barrage in and over the Frege-Dedekind-Cantor theory of the real numbers, continuity, and the infinite. Frege, Cantor, and Dedekind quit the field, beaten and disheartened. Russell proposed his “vicious circle principle” as a remedy; “whatever involves all of a collection must not be a one of the collection”; later he put forth his “axiom of reducibility,” which as it is now practically abandoned, need not be described. For a time these restoratives were brilliantly effective (except in the opinion of the German mathematicians, who never swallowed them). Gradually, as the critical examination of all mathematical reasoning gained headway, physic was thrown to the dogs and a concerted effort was begun to find out what really ailed the patient in his irrational and real number system before administering further nostrums.

The present effort to understand our difficulties originated in the work of David Hilbert of Gottingen in 1899 and in that of L.E.J. Brouwer of Amsterdam in 1912. Both of these men and their numerous followers have the common purpose of putting mathematical reasoning on a sound basis. although in several respects their methods and philosophies are violently opposed. It seems unlikely that both can be as wholly right as each appears to believe he is.

Hilbert returned to Greece for the beginning of his philosophy of mathematics. Resuming the Pythagorean program of a rigidly and fully stated set of postulates from which a mathematical argument must proceed by strict deductive reasoning, Hilbert made the program of the postulational development of mathematics more precise than it had been with the Greeks, and in 1899 issued the first edition of his classic on the foundations of geometry. One demand which Hilbert made, and which the Greeks do not seem to have thought of, was that the proposed postulates for geometry shall be proved to be self-consistent (free of internal, concealed contradictions). To produce such a proof for geometry it is shown that any contradiction in the geometry developed from the postulates would imply a contradiction in arithmetic. The problem is thus shoved back to proving the consistency of arithmetic, and there it remains today.

Thus we are back once more asking the sphinx to tell us what a number is. Both Dedekind and Frege fled to the infinite — Dedekind with his infinite classes defining irrationals, Frege with his class of all classes similar to a given class defining a cardinal number — to interpret the numbers that puzzled Pythagoreans. Hilbert, too, would seek the answer in the infinite which, he believes, is necessary for an understanding of the finite. He is quite emphatic in his belief that Cantorism will ultimately be redeemed from the purgatory in which it now tosses. “This (Cantor’s theory) seems to me the most admirable fruit of the mathematical mind and indeed one of the highest achievements of man’s intellectual processes.” But he admits that the paradoxes of Burali-Forti, Russell, and others are not resolved. However, his faith surmounts all doubts: “No one shall expel us from the paradise which Cantor has created for us.”

But at this moment of exaltation Brouwer appears with something that looks suspiciously like a flaming sword in his strong right hand. The chase is on: Dedekind, in the role of Adam, and Cantor disguised as Eve at his side, are already eyeing the gate apprehensively under the stern regard of the uncomprimising Dutchman. The postulational method for securing freedom from contradiction proposed by Hilbert will, says Brouwer, accomplish its end — produce no contradictions, “but nothing of mathematical value will be attained in this manner; a false theory which is not stopped by a contradiction is none the less false, just as a criminal policy unchecked by a reprimanding court is none the less criminal.”

The root of Brouwer’s objection to the criminal policy of his opponents is something new — at least in mathematics. He objects to an unrestricted use of Aristotelian, particularly in dealing with infinite sets , and he maintains that such logic is bound to produce contradictions when applied to sets which cannot be definitely constructed in Kronecker’s sense (a rule of procedure must be given whereby the things in the set can be produced). The law of excluded middle (a thing must have a certain property or must not have that property, as for in the example in the assertion that a number is prime or not prime) is legitimately usable only when applied to finite sets. Aristotle devised his logic as a body of working rules for finite sets, basing his method on human experience of finite sets , and there is no reason whatever for supposing that a logic which is adequate for the finite will continue to produce consistent (non contradictory) results when applied to the infinite. This seems reasonable enough when we recall that the very definition of an infinite set emphasizes that a part of an infinite set may contain precisely as many things as the whole set, a situation which never happens for a finite set when “part” means some, but not all (as it does in the definition of an infinite set).

Here we have what some consider the root of the trouble in Cantor’s theory of the actual infinite. For the definition of a set (as stated some time back), by which all things having a certain property are “united” to form a “set”(or “class”), is not suitable as a basis for the theory of sets, in that definition either is not constructive (in Kronecket’s sense) or assumes a constructability which no mortal can produce. Brouwer claims that the use of the law of excluded middle in such a situation is at best merely a heuristic guide to propositions which may be true, but which are not necessarily so, even when they have been deduced by a rigid application of Aristotlelian logic, and he says that numerous false theories (including Cantor’s) have been erected on this rotten foundation during the past half century.

Such a revolution in the rudiments of mathematical thinking does not go unchallenged. Brouwer’s radical move to the left is speeded by an outraged roar from the reactionary right. “What Weyl and Brouwer are doing (Brouwer is the leader, Weyl his companion in revolt) is mainly following in the steps of Kronecker,” according to Hilbert, the champion of the status quo. “They are trying to establish mathematics by jettisoning everything which does not suit them and setting up an embargo. The effect is to dismember our science and to run the risk of losing a large part of our most valuable possessions. Weyl and Brouwer condemn the general notion of irrational numbers, of functions — even of such functions as occur in the theory of numbers — Cantor’s transfinite numbers, etc., the theorem that an infinite set of positive integers has a least, and even the law of the excluded middle, as for example the assertion: Either there is only a finite number of primes or there are infinitely many. These are examples of (to them) forbidden theorems and modes of reasoning. I believe that impotent as Kronecker was to abolish irrational numbers (Weyl and Brouwer do permit us to retain the torso), no less impotent will their efforts prove today. No! Brouwer’s program is not a revolution, but merely the repetition of a futile coup de main with old methods, but which was then undertaken with greater verve, yet failed utterly. Today the State (“mathematics”) is thoroughly armed and strengthened through the labours of Frege, Dedekind, and Cantor. The efforts of Brouwer and Weyl are foredoomed to futility.

To which the other side replies by a shrug of shoulders and goes ahead with its great and fundamentally new task of reestablishing mathematics (particularly the foundations of analysis) on a firmer basis than any laid down by the men of the past 2500 years from Pythagoras to Weierstrass.

What will mathematics be like a generation hence when — we hope — these difficulties will have been cleared up? Only a prophet or the seventh son of a prophet sticks his head into the noose of prediction. But if there is any continuity at all in the evolution of mathematics — and the majority of dispassionate observers believe that there is — we shall find that the mathematics which is to come will be broader, firmer, and richer in content than that which we or our predecessors have known.

Already the controversies of the past third of a century have added new fields — including totally new logics — to the vast domain of mathematics, and the new is being rapidly consolidated and coordinated with the old. If we may rashly venture a prediction, what is it to come will be fresher, younger in every respect, and closer to human thought and human needs — freer of appeal for its justification to extra-human “existence”— than what is now being vigorously refashioned. The spirit of mathematics is eternal youth. As Cantor said,

Already the controversies of the past third of a century have added new fields — including totally new logics — to the vast domain of mathematics, and the new is being rapidly consolidated and coordinated with the old. If we may rashly venture a prediction, what is it to come will be fresher, younger in every respect, and closer to human thought and human needs — freer of appeal for its justification to extra-human “existence”— than what is now being vigorously refashioned. The spirit of mathematics is eternal youth. As Cantor said, “The essence of mathematics resides in its freedom”; the present “revolution” is but another assertion of this freedom.

Cheers,

Nalin Pithwa

Set Theory Primer : Some basic thinking and problem solving

Reference: AMS, Student Mathematical Library: Basic Set Theory by A. Shen, et al. Chapter 1. Section 1.

Problem 1:

Consider the oldest mathematician amongst chess players and the oldest chess player amongst mathematicians. Could they be two different people?

Problem 2:

The same question for the best mathematician amongst chess players and the best chess player amongst mathematicians.

Problem 3:

One tenth of mathematicians are chess players, and one sixth of chess players are mathematicians. Which group (mathematicians or chess players) is bigger? What is the ratio of sizes of these two groups?

Problem 4:

Do there exist sets A, B and C such that A \bigcap B \neq \phi, A \bigcap C = \phi and (A\bigcap B)-C = \phi ?

Problem 5:

Which of the following formulas are true for arbitrary sets A, B and C:

i) (A \bigcap B) \bigcup C = (A \bigcup C) \bigcap (B \bigcup C)

ii) (A \bigcup B) \bigcap C = (A \bigcap C) \bigcup (B \bigcap C)

iii) (A \bigcup B) - C = (A-C)\bigcup B

iv) (A \bigcap B) - C = (A - C) \bigcap B

v) A - (B \bigcup C) = (A-B) \bigcap (A-C)

vi) A - (B \bigcap C) = (A-B) \bigcup (A-C)

Problem 6:

Give formal proofs of all valid formulas from the preceding problem. (Your proof should go like this : “We have to prove that the left hand side equals the right hand side. Let x be any element of the left hand side set. Then, ….Therefore, x belongs to the right hand side set. On the other hand, let…”)

Please give counterexamples to the formulas which are not true.

Problem 7:

Prove that the symmetric difference is associative:

A \triangle (B \triangle C) = (A \triangle B) \triangle C for any sets A, B and C. Hint: Addition modulo two is associative.

Problem 8:

Prove that:

(A_{1}\bigcap A_{2}\bigcap \ldots A_{n}) \triangle (B_{1} \bigcap B_{2} \bigcap \ldots B_{n}) = (A_{1} \triangle B_{1}) \bigcup (A_{2} \triangle B_{2}) \ldots (A_{n} \triangle B_{n}) for arbitrary sets A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}.

Problem 9:

Consider an inequality whose left hand side and right hand side contain set variables and operations \bigcap, \bigcup and -. Prove that if this equality is false for some sets, then it is false for some sets that contain at most one element.

Problem 10:

How many different expressions can be formed from set variables A and B by using union, intersection and set difference? (Variables and operations can be used more than once. Two expressions are considered identical if they assume the same value for each set of values of the variables involved.) Solve the same problem for three sets and for n sets. (Answer: In the general case, 2^{2^{n}-1})

Problem 11:

Solve the same problem if only \bigcup and \bigcap are allowed. For n=2 and n-3, this problem is easy to solve; however, no general formula for any n is known. This problem is also called “counting monotone Boolean functions in n variables”.)

Problem 12:

How many subsets does an n-element subset have?

Problem 13:

Assume that A consists of n elements and B \subset A consists of k elements. Find the number of different sets C such that B \subset C \subset A.

Problem 14:

A set U contains 2n elements. We select k subsets of A in such a way that none of them is a subset of another one. What is the maximum possible value of k? (Hint: Maximal k is achieved when all subsets have n elements. Indeed, imagine the following process: We start with an empty set and add random elements one by one until we get U. At most one selected set can appear in this process. On the other hand, the expected number of selected sets that appear during this process can be computed using the linearity of expectation. Take into account that the probability to come across some set Z \subset U is minimal when Z contains n elements, since all the sets of a given size are equiprobable.)

Your comments/solutions are welcome.

Regards,

Nalin Pithwa.

Purva building, 5A
Flat 06
Near Dimple Arcade, Thakur Complex
Mumbai, Maharastra 400101
India.

Set theory, relations, functions: preliminaries: Part V

Types of functions: (please plot as many functions as possible from the list below; as suggested in an earlier blog, please use a TI graphing calculator or GeoGebra freeware graphing software): 

  1. Constant function: A function f:\Re \longrightarrow \Re given by f(x)=k, where k \in \Re is a constant. It is a horizontal line on the XY-plane.
  2. Identity function: A function f: \Re \longrightarrow \Re given by f(x)=x. It maps a real value x back to itself. It is a straight line passing through origin at an angle 45 degrees to the positive X axis.
  3. One-one or injective function: If different inputs give rise to different outputs, the function is said to be injective or one-one. That is, if f: A \longrightarrow B, where set A is domain and set B is co-domain, if further, x_{1}, x_{2} \in A such that x_{1} \neq x_{2}, then it follows that f(x_{1}) \neq f(x_{2}). Sometimes, to prove that a function is injective, we can prove the conrapositive statement of the definition also; that is, y_{1}=y_{2} where y_{1}, y_{2} \in codomain \hspace{0.1in} range, then it follows that x_{1}=x_{2}. It might be easier to prove the contrapositive. It would be illuminating to construct your own pictorial examples of such a function. 
  4. Onto or surjective: If a function is given by f: X \longrightarrow Y such that f(X)=Y, that is, the images of all the elements of the domain is full of set Y. In other words, in such a case, the range is equal to co-domain. it would be illuminating to construct your own pictorial examples of  such a function.
  5. Bijective function or one-one onto correspondence: A function which is both one-one and onto is called a bijective function. (It is both injective and surjective). Only a bijective function will have a well-defined inverse function. Think why! This is the reason why inverse circular functions (that is, inverse trigonometric functions have their domains restricted to so-called principal values). 
  6. Polynomial function: A function of the form f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots + a_{n}x^{n}, where n is zero or positive integer only and a_{i} \in \Re is called a polynomial with real coefficients. Example. f(x)=ax^{2}=bx+c, where a \neq 0, a, b, c \in \Re is called a quadratic function in x. (this is a general parabola).
  7. Rational function: The function of the type \frac{f(x)}{g(x)}, where g(x) \neq 0, where f(x) and g(x) are polynomial functions of x, defined in a domain, is called a rational function. Such a function can have asymptotes, a term we define later. Example, y=f(x)=\frac{1}{x}, which is a hyperbola with asymptotes X and Y axes.
  8. Absolute value function: Let f: \Re \longrightarrow \Re be given by f(x)=|x|=x when x \geq 0 and f(x)=-x, when x<0 for any x \in \Re. Note that |x|=\sqrt{x^{2}} since the radical sign indicates positive root of a quantity by convention.
  9. Signum function: Let f: \Re \longrightarrow \Re where f(x)=1, when x>0 and f(x)=0 when x=0 and f(x)=-1 when x<0. Such a function is called the signum function. (If you can, discuss the continuity and differentiability of the signum function). Clearly, the domain of this function  is full \Re whereas the range is \{ -1,0,1\}.
  10. In part III of the blog series, we have already defined the floor function and the ceiling function. Further properties of these functions are summarized (and some with proofs in the following wikipedia links): (once again, if you can, discuss the continuity and differentiablity of the floor and ceiling functions): https://en.wikipedia.org/wiki/Floor_and_ceiling_functions
  11. Exponential function: A function f: \Re \longrightarrow \Re^{+} given by f(x)=a^{x} where a>0 is called an exponential function. An exponential function is bijective and its inverse is the natural logarithmic function. (the logarithmic function is difficult to define, though; we will consider the details later). PS: Quiz: Which function has a faster growth rate — exponential or a power function ? Consider various parameters.
  12. Logarithmic function: Let a be a positive real number with a \neq 1. If a^{y}=x, where x \in \Re, then y is called the logarithm of x with base a and we write it as y=\ln{x}. (By the way, the logarithmic function is used in the very much loved mp3 music :-))

Regards,

Nalin Pithwa

Set Theory, Relations and Functions: Preliminaries: IV:

Problem Set based on previous three parts:

I) Solve the inequalities in the following exercises expressing the solution sets as intervals or unions of intervals. Also, graph each solution set on the real line:

a) |x| <2 (b) |x| \leq 2 (c) |t-1| \leq 3 (d) |t+2|<1 (e) |3y-7|<4(f) |2y+5|<1 (g) |\frac{z}{5}-1| \leq 1 (h) | \frac{3}{2}z-1| \leq 2 (i) |3-\frac{1}{x}|<\frac{1}{2} (j) |\frac{2}{x}-4|<3 (k) |2x| \geq 4 (l) |x+3| \geq \frac{1}{2} (m) |1-x| >1 (n) |2-3x| > 5 (o) |\frac{x+1}{2}| \geq 1 (p) |\frac{3x}{5}-1|>\frac{2}{5}

II) Quadratic Inequalities:

Solve the inequalities in the following exercises. Express the solution sets as intervals or unions of intervals and graph them. Use the result \sqrt{a^{2}}=|a| as appropriate.

(a) x^{2}<2 (b) 4 \leq x^{2} (c) 4<x^{2}<9 (d) \frac{1}{9} < x^{2} < \frac{1}{4} (e) (x-1)^{2}<4 (f) (x+3)^{2}<2 (g) x^{2}-x<0 (h) x^{2}-x-2 \geq 0

III) Theory and Examples:

i) Do not fall into the trap |-a|=a. For what real numbers a is the equation true? For what real numbers is it false?

ii) Solve the equation: |x-1|=1-x.

iii) A proof of the triangle inequality: 

Give the reason justifying each of the marked steps in the following proof of the triangle inequality:

|a+b|^{2}=(a+b)^{2}…..why ?

=a^{2}+2ab++b^{2}

\leq a^{2}+2|a||b|+b^{2}….why ?

\leq |a|^{2}+2|a||b|+|b|^{2}….why?

=(|a|+|b|)^{2}….why ?

iv) Prove that |ab|=|a||b| for any numbers a and b.

v) If |x| \leq 3 and x>-\frac{1}{2}, what can you say about x?

vi) Graph the inequality: |x|+|y| \leq 1

Questions related to functions:

I) Find the domain and range of each function:

a) f(x)=1-\sqrt{x} (b) F(t)=\frac{1}{1+\sqrt{t}} (c) g(t)=\frac{1}{\sqrt{4-t^{2}}}

II) Finding formulas for functions:

a) Express the area and perimeter of an equilateral triangle as a function of the triangle’ s side with length s.

b) Express the side length of a square as a function of the cube’s diagonal length d. Then, express the surface area  and volume of the cube as a function of the diagonal length.

c) A point P in the first quadrant lies on the graph of the function f(x)=\sqrt{x}. Express the coordinates of P as functions of the slope of the line joining P to the origin.

III) Functions and graphs:

Graph the functions in the questions below. What symmetries, if any, do the graphs have?

a) y=-x^{3} (b) y=-\frac{1}{x^{2}} (c) y=-\frac{1}{x} (d) y=\frac{1}{|x|} (e) y = \sqrt{|x|} (f) y=\sqrt{-x} (g) y=\frac{x^{3}}{8} (h) y=-4\sqrt{x} (i) y=-x^{\frac{3}{2}} (j) y=(-x)^{\frac{3}{2}} (k) y=(-x)^{\frac{2}{3}} (l) y=-x^{\frac{2}{3}}

IV) Graph the following equations ad explain why they are not graphs of functions of x. (a) |y|=x (b) y^{2}=x^{2}

V) Graph the following equations and explain why they are not graphs of functions of x: (a) |x|+|y|=1 (b) |x+y|=1

VI) Even and odd functions:

In the following questions, say whether the function is even, odd or neither.

a) f(x)=3 (b) f(x=x^{-5} (c) f(x)=x^{2}+1 (d) f(x)=x^{2}+x (e) g(x)=x^{4}+3x^{2}-1 (f) g(x)=\frac{1}{x^{2}-1} (g) g(x)=\frac{x}{x^{2}-1} (h) h(t)=\frac{1}{t-1} (i) h(t)=|t^{3}| (j) h(t)=2t+1 (k) h(t)=2|t|+1

Sums, Differences, Products and Quotients:

In the two questions below, find the domains and ranges of f, g, f+g, and f-g.

i) f(x)=x, g(x)=\sqrt{x-1} (ii) f(x)=\sqrt{x+1}, g(x)=\sqrt{x-1}

In the two questions below, find the domains and ranges of f, g, \frac{f}{g} and \frac{g}{f}

i) f(x)=2, g(x)=x^{2}+1

ii) f(x)=1, g(x)=1+\sqrt{x}

Composites of functions:

  1. If f(x)=x+5, and g(x)=x^{2}-5, find the following: (a) f(g(0)) (b) g(f(0)) (c) f(g(x)) (d) g(f(x)) (e) f(f(-5)) (f) g(g(2)) (g) f(f(x)) (h) g(g(x))
  2. If f(x)=x-1 and g(x)=\frac{1}{x+1}, find the following: (a) f(g(\frac{1}{2})) (b) g(f(\frac{1}{2})) (c) f(g(x)) (d) g(f(x)) (e) f(f(2)) (f) g(g(2)) (g) f(f(x)) (h) g(g(x))
  3. If u(x)=4x-5, v(x)=x^{2}, and f(x)=\frac{1}{x}, find formulas or formulae for the following: (a) u(v(f(x))) (b) u(f(v(x))) (c) v(u(f(x))) (d) v(f(u(x))) (e) f(u(v(x))) (f) f(v(u(x)))
  4. If f(x)=\sqrt{x}, g(x)=\frac{x}{4}, and h(x)=4x-8, find formulas or formulae for the following: (a) h(g(f(x))) (b) h(f(g(x))) (c) g(h(f(x))) (d) g(f(h(x))) (e) f(g(h(x))) (f) f(h(g(x)))

Let f(x)=x-5, g(x)=\sqrt{x}, h(x)=x^{3}, and f(x)=2x. Express each of the functions in the questions below as a composite involving one or more of f, g, h and j:

a) y=\sqrt{x}-3 (b) y=2\sqrt{x} (c) y=x^{\frac{1}{4}} (d) y=4x (e) y=\sqrt{(x-3)^{3}} (f) y=(2x-6)^{3} (g) y=2x-3 (h) y=x^{\frac{3}{2}} (i) y=x^{9} (k) y=x-6 (l) y=2\sqrt{x-3} (m) \sqrt{x^{3}-3}

Questions:

a) g(x)=x-7, f(x)=\sqrt{x}, find (f \circ g)(x)

b) g(x)=x+2, f(x)=3x, find (f \circ g)(x)

c) f(x)=\sqrt{x-5}, (f \circ g)(x)=\sqrt{x^{2}-5}, find g(x).

d) f(x)=\frac{x}{x-1}, g(x)=\frac{x}{x-1}, find (f \circ g)(x)

e) f(x)=1+\frac{1}{x}, (f \circ g)(x)=x, find g(x).

f) g(x)=\frac{1}{x}, (f \circ g)(x)=x, find f(x).

Reference: Calculus and Analytic Geometry, G B Thomas. 

NB: I have used an old edition (printed version) to prepare the above. The latest edition may be found at Amazon India link:

https://www.amazon.in/Thomas-Calculus-George-B/dp/9353060419/ref=sr_1_1?crid=1XDE2XDSY5LCP&keywords=gb+thomas+calculus&qid=1570492794&s=books&sprefix=G+B+Th%2Caps%2C255&sr=1-1

Regards,

Nalin Pithwa

 

Set Theory, Relations, Functions Preliminaries: II

Relations:

Concept of Order:

Let us say that we create a “table” of two columns in which the first column is the name of the father, and the second column is name of the child. So, it can have entries like (Yogesh, Meera), (Yogesh, Gopal), (Kishor, Nalin), (Kishor, Yogesh), (Kishor, Darshna) etc. It is quite obvious that “first” is the “father”, then “second” is the child. We see that there is a “natural concept of order” in human “relations”. There is one more, slightly crazy, example of “importance of order” in real-life. It is presented below (and some times also appears in basic computer science text as rise and shine algorithm) —-

Rise and Shine algorithm: 

When we get up from sleep in the morning, we brush our teeth, finish our morning ablutions; next, we remove our pyjamas and shirt and then (secondly) enter the shower; there is a natural order here; first we cannot enter the shower, and secondly we do not remove the pyjamas and shirt after entering the shower. 🙂

Ordered Pair: Definition and explanation:

A pair (a,b) of numbers, such that the order, in which the numbers appear is important, is called an ordered pair. In general, ordered pairs (a,b) and (b,a) are different. In ordered pair (a,b), ‘a’ is called first component and ‘b’ is called second component.

Two ordered pairs (a,b) and (c,d) are equal, if and only if a=c and b=d. Also, (a,b)=(b,a) if and only if a=b.

Example 1: Find x and y when (x+3,2)=(4,y-3).

Solution 1: Equating the first components and then equating the second components, we have:

x+3=4 and 2=y-3

x=1 and y=5

Cartesian products of two sets:

Let A and B be two non-empty sets then the cartesian product of A and B is denoted by A x B (read it as “A cross B”),and is defined as the set of all ordered pairs (a,b) such that a \in A, b \in B.

Thus, A \times B = \{ (a,b): a \in A, b \in B\}

e.g., if A = \{ 1,2\} and B = \{ a,b,c\}, tnen A \times B = \{ (1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}.

If A = \phi or B=\phi, we define A \times B = \phi.

Number of elements of a cartesian product:

By the following basic counting principle: If a task A can be done in m ways, and a task B can be done in n ways, then the tasks A (first) and task B (later) can be done in mn ways.

So, the cardinality of A x B is given by: n(A \times B)= n(A) \times n(B).

So, in general if a cartesian product of p finite sets, viz, A_{1}, A_{2}, A_{3}, \ldots, A_{p} is given by n(A_{1} \times A_{2} \times A_{3} \ldots A_{p}) = n(A_{1}) \times n(A_{2}) \times \ldots \times n(A_{p})

Definitions of relations, arrow diagrams (or pictorial representation), domain, co-domain, and range of a relation:

Consider the following statements:

i) Sunil is a friend of Anil.

ii) 8 is greater than 4.

iii) 5 is a square root of 25.

Here, we can say that Sunil is related to Anil by the relation ‘is a friend of’; 8 and 4 are related by the relation ‘is greater than’; similarly, in the third statement, the relation is ‘is a square root of’.

The word relation implies an association of two objects according to some property which they possess. Now, let us some mathematical aspects of relation;

Definition:

A and B are two non-empty sets then any subset of A \times B is called relation from A to B, and is denoted by capital letters P, Q and R. If R is a relation and (x,y) \in R then it is denoted by xRy.

y is called image of x under R and x is called pre-image of y under R.

Let A=\{ 1,2,3,4,5\} and B=\{ 1,4,5\}.

Let R be a relation such that (x,y) \in R implies x < y. We list the elements of R.

Solution: Here A = \{ 1,2,3,4,5\} and B=\{ 1,4,5\} so that R = \{ (1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)\} Note this is the relation R from A to B, that is, it is a subset of A x B.

Check: Is a relation R^{'} from B to A defined by x<y, with x \in B and y \in A — is this relation R^{'} *same* as R from A to B? Ans: Let us list all the elements of R^{‘} explicitly: R^{'} = \{ (1,2),(1,3),(1,4),(1,5),(4,5)\}. Well, we can surely compare the two sets R and R^{'} — the elements “look” different certainly. Even if they “look” same in terms of numbers, the two sets R and R^{'} are fundamentally different because they have different domains and co-domains.

Definition : Domain of a relation R: The set of all the first components of the ordered pairs in a relation R is called the domain of relation R. That is, if R \subseteq A \times B, then domain (R) is \{ a: (a,b) \in R\}.

Definition: Range: The set of all second components of all ordered pairs in a relation R is called the range of the relation. That is, if R \subseteq A \times B, then range (R) = \{ b: (a,b) \in R\}.

Definition: Codomain: If R is a relation from A to B, then set B is called co-domain of the relation R. Note: Range is a subset of co-domain.

Type of Relations:

One-one relation: A relation R from a set A to B is said to be one-one if every element of A has at most one image in B and distinct elements in A have distinct images in B. For example, let A = \{ 1,2,3,4\}, and let B=\{ 2,3,4,5,6,7\} and let R_{1}= \{ (1,3),(2,4),(3,5)\} Then R_{1} is a one-one relation. Here, domain of R_{1}= \{ 1,2,3\} and range of R_{1} is \{ 3,4,5\}.

Many-one relation: A relation R from A to B is called a many-one relation if two or more than two elements in the domain A are associated with a single (unique) element in co-domain B. For example, let R_{2}=\{ (1,4),(3,7),(4,4)\}. Then, R_{2} is many-one relation from A to B. (please draw arrow diagram). Note also that domain of R_{1}=\{ 1,3,4\} and range of R_{1}=\{ 4,7\}.

Into Relation: A relation R from A to B is said to be into relation if there exists at least one element in B, which has no pre-image in A. Let A=\{ -2,-1,0,1,2,3\} and B=\{ 0,1,2,3,4\}. Consider the relation R_{1}=\{ (-2,4),(-1,1),(0,0),(1,1),(2,4) \}. So, clearly range is \{ 0,1,4\} and range \subseteq B. Thus, R_{3} is a relation from A INTO B.

Onto Relation: A relation R from A to B is said to be ONTO relation if every element of B is the image of some element of A. For example: let set A= \{ -3,-2,-1,1,3,4\} and set B= \{ 1,4,9\}. Let R_{4}=\{ (-3,9),(-2,4), (-1,1), (1,1),(3,9)\}. So, clearly range of R_{4}= \{ 1,4,9\}. Range of R_{4} is co-domain of B. Thus, R_{4} is a relation from A ONTO B.

Binary Relation on a set A:

Let A be a non-empty set then every subset of A \times A is a binary relation on set A.

Illustrative Examples:

E.g.1: Let A = \{ 1,2,3\} and let A \times A = \{ (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. Now, if we have a set R = \{ (1,2),(2,2),(3,1),(3,2)\} then we observe that R \subseteq A \times A, and hence, R is a binary relation on A.

E.g.2: Let N be the set of natural numbers and R = \{ (a,b) : a, b \in N and 2a+b=10\}. Since R \subseteq N \times N, R is a binary relation on N. Clearly, R = \{ (1,8),(2,6),(3,4),(4,2)\}. Also, for the sake of completeness, we state here the following: Domain of R is \{ 1,2,3,4\} and Range of R is \{ 2,4,6,8\}, codomain of R is N.

Note: (i) Since the null set is considered to be a subset of any set X, so also here, \phi \subset A \times A, and hence, \phi is a relation on any set A, and is called the empty or void relation on A. (ii) Since A \times A \subset A \times A, we say that A \subset A is a relation on A called the universal relation on A. 

Note: Let the cardinality of a (finite) set A be n(A)=p and that of another set B be n(B)=q, then the cardinality of the cartesian product n(A \times B)=pq. So, the number of possible subsets of A \times B is 2^{pq} which includes the empty set.

Types of relations:

Let A be a non-empty set. Then, a relation R on A is said to be: (i) Reflexive: if (a,a) \in R for all a \in A, that is, aRa for all a \in A. (ii) Symmetric: If (a,b) \in R \Longrightarrow (b,a) \in R for all a,b \in R (iii) Transitive: If (a,b) \in R, and (b,c) \in R, then so also (a,c) \in R.

Equivalence Relation: 

A (binary) relation on a set A is said to be an equivalence relation if it is reflexive, symmetric and transitive. An equivalence appears in many many areas of math. An equivalence measures “equality up to a property”. For example, in number theory, a congruence modulo is an equivalence relation; in Euclidean geometry, congruence and similarity are equivalence relations.

Also, we mention (without proof) that an equivalence relation on a set partitions the set in to mutually disjoint exhaustive subsets. 

Illustrative examples continued:

E.g. Let R be an equivalence relation on \mathbb{Q} defined by R = \{ (a,b): a, b \in \mathbb{Q}, (a-b) \in \mathbb{Z}\}. Prove that R is an equivalence relation.

Proof: Given that R = \{ (a,b) : a, b \in \mathbb{Q}, (a-b) \in \mathbb{Z}\}. (i) Let a \in \mathbb{Q} then a-a=0 \in \mathbb{Z}, hence, (a,a) \in R, so relation R is reflexive. (ii) Now, note that (a,b) \in R \Longrightarrow (a-b) \in \mathbb{Z}, that is, (a-b) is an integer \Longrightarrow -(b-a) \in \mathbb{Z} \Longrightarrow (b-a) \in \mathbb{Z} \Longrightarrow (b,a) \in R. That is, we have proved (a,b) \in R \Longrightarrow (b,a) \in R and so relation R is symmetric also. (iii) Now, let (a,b) \in R, and (b,c) \in R, which in turn implies that (a-b) \in \mathbb{Z} and (b-c) \in \mathbb{Z} so it \Longrightarrow (a-b)+(b-c)=a-c \in \mathbb{Z} (as integers are closed under addition) which in turn \Longrightarrow (a,c) \in R. Thus, (a,b) \in R and (b,c) \in R implies (a,c) \in R also, Hence, given relation R is transitive also. Hence, R is also an equivalence relation on \mathbb{Q}.

Illustrative examples continued:

E.g.: If (x+1,y-2) = (3,4), find the values of x and y.

Solution: By definition of an ordered pair, corresponding components are equal. Hence, we get the following two equations: x+1=3 and y-2=4 so the solution is x=2,y=6.

E.g.: If A = (1,2), list the set A \times A.

Solution: A \times A = \{ (1,1),(1,2),(2,1),(2,2)\}

E.g.: If A = \{1,3,5 \} and B=\{ 2,3\}, find A \times B, and B \times A, check if cartesian product is a commutative operation, that is, check if A \times B = B \times A.

Solution: A \times B = \{ (1,2),(1,3),(3,2),(3,3),(5,2),(5,3)\} whereas B \times A = \{ (2,1),(2,3),(2,5),(3,1),(3,3),(3,5)\} so since A \times B \neq B \times A so cartesian product is not a commutative set operation.

E.g.: If two sets A and B are such that their cartesian product is A \times B = \{ (3,2),(3,4),(5,2),(5,4)\}, find the sets A and B.

Solution: Using the definition of cartesian product of two sets, we know that set A contains as elements all the first components and set B contains as elements all the second components. So, we get A = \{ 3,5\} and B = \{ 2,4\}.

E.g.: A and B are two sets given in such a way that A \times B contains 6 elements. If three elements of A \times B are (1,3),(2,5),(3,3), find its remaining elements.

Solution: We can first observe that 6 = 3 \times 2 = 2 \times 3 so that A can contain 2 or 3 elements; B can contain 3 or 2 elements. Using definition of cartesian product of two sets, we get that A= \{ 1,2,3\} and \{ 3,5\} and so we have found the sets A and B completely.

E.g.: Express the set \{ (x,y) : x^{2}+y^{2}=25, x, y \in \mathbb{W}\} as a set of ordered pairs.

Solution: We have x^{2}+y^{2}=25 and so

x=0, y=5 \Longrightarrow x^{2}+y^{2}=0+25=25

x=3, y=4 \Longrightarrow x^{2}+y^{2}=9+16=25

x=4, y=3 \Longrightarrow x^{2}+y^{2}=16+9=25

x=5, y=0 \Longrightarrow x^{2}+y^{2}=25+0=25

Hence, the given set is \{ (0,5),(3,4),(4,3),(5,0)\}

E.g.: Let A = \{ 1,2,3\} and B = \{ 2,4,6\}. Show that R = \{ (1,2),(1,4),(3,2),(3,4)\} is a relation from A to B. Find the domain, co-domain and range.

Solution: Here, A \times B = \{ (1,2),(1,4),(1,6),(2,2),(2,4),(2,6),(3,2),(3,4),(3,6)\}. Clearly, R \subseteq A \times B. So R is a relation from A to B. The domain of R is the set of first components of R (which belong to set A, by definition of cartesian product and ordered pair)  and the codomain is set B. So, Domain (R) = \{ 1,3\} and co-domain of R is set B itself; and Range of R is \{ 2,4\}.

E.g.: Let A = \{ 1,2,3,4,5\} and B = \{ 1,4,5\}. Let R be a relation from A to B such that (x,y) \in R if x<y. List all the elements of R. Find the domain, codomain and range of R. (as homework quiz, draw its arrow diagram);

Solution: Let A = \{ 1,2,3,4,5\} and B = \{ 1,4,5\}. So, we get R as (1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5). domain(R) = \{ 1,2,3,4\}, codomain(R) = B, and range(R) = \{ 4,5\}.

E.g. Let A = \{ 1,2,3,4,5,6\}. Define a binary relation on A such that R = \{ (x,y) : y=x+1\}. Find the domain, codomain and range of R.

Solution: By definition, R \subseteq A \times A. Here, we get R = \{ (1,2),(2,3),(3,4),(4,5),(5,6)\}. So we get domain (R) = \{ 1,2,3,4,5\}, codomain(R) =A, range(R) = \{ 2,3,4,5,6\}

Tutorial problems:

  1. If (x-1,y+4)=(1,2), find the values of x and y.
  2. If (x + \frac{1}{3}, \frac{y}{2}-1)=(\frac{1}{2} , \frac{3}{2} )
  3. If A=\{ a,b,c\} and B = \{ x,y\}. Find out the following: A \times A, B \times B, A \times B and B \times A.
  4. If P = \{ 1,2,3\} and Q = \{ 4\}, find the sets P \times P, Q \times Q, P \times Q, and Q \times P.
  5. Let A=\{ 1,2,3,4\} and \{ 4,5,6\} and C = \{ 5,6\}. Find A \times (B \bigcap C), A \times (B \bigcup C), (A \times B) \bigcap (A \times C), A \times (B \bigcup C), and (A \times B) \bigcup (A \times C).
  6. Express \{ (x,y) : x^{2}+y^{2}=100 , x, y \in \mathbf{W}\} as a set of ordered pairs.
  7. Write the domain and range of the following relations: (i) \{ (a,b): a \in \mathbf{N}, a < 6, b=4\} (ii) \{ (a,b): a,b \in \mathbf{N}, a+b=12\} (iii) \{ (2,4),(2,5),(2,6),(2,7)\}
  8. Let A=\{ 6,8\} and B=\{ 1,3,5\}. Let R = \{ (a,b): a \in A, b \in B, a+b \hspace{0.1in} is \hspace{0.1in} an \hspace{0.1in} even \hspace{0.1in} number\}. Show that R is an empty relation from A to B.
  9. Write the following relations in the Roster form and hence, find the domain and range: (i) R_{1}= \{ (a,a^{2}) : a \hspace{0.1in} is \hspace{0.1in} prime \hspace{0.1in} less \hspace{0.1in} than \hspace{0.1in} 15\} (ii) R_{2} = \{ (a, \frac{1}{a}) : 0 < a \leq 5, a \in N\}
  10. Write the following relations as sets of ordered pairs: (i) \{ (x,y) : y=3x, x \in \{1,2,3 \}, y \in \{ 3,6,9,12\}\} (ii) \{ (x,y) : y>x+1, x=1,2, y=2,4,6\} (iii) \{ (x,y) : x+y =3, x, y \in \{ 0,1,2,3\}\}

More later,

Nalin Pithwa

 

 

 

 

 

 

 

 

Set Theory, Relations, Functions Preliminaries: I

In these days of conflict between ancient and modern studies there must surely be something to be said of a study which did not begin with Pythagoras and will not end with Einstein. — G H Hardy (On Set Theory)

In every day life, we generally talk about group or collection of objects. Surely, you must have used the words such as team, bouquet, bunch, flock, family for collection of different objects.

It is very important to determine whether a given object belongs to a given collection or not. Consider the following conditions:

i) Successful persons in your city.

ii) Happy people in your town.

iii) Clever students in your class.

iv) Days in a week.

v) First five natural numbers.

Perhaps, you have already studied in earlier grade(s) —- can you state which of the above mentioned collections are sets? Why? Check whether your answers are as follows:

First three collections are not examples of sets but last two collections represent sets. This is because in first three collections, we are not sure of the objects. The terms ‘successful persons’, ‘happy people’, ‘clever students’ are all relative terms. Here, the objects are not well-defined. In the last two collections, we can determine the objects clearly (meaning, uniquely, or without ambiguity). Thus, we can say that the objects are well-defined.

So what can be the definition of a set ? Here it goes:

A collection of well-defined objects is called a set. (If we continue to “think deep” about this definition, we are led to the famous paradox, which Bertrand Russell had discovered: Let C be a collection of all sets such which are not elements of themselves. If C is allowed to be a set, a contradiction arises when one inquires whether or not C is an element of itself. Now plainly, there is something suspicious about the idea of a set being an element of itself, and we shall take this as evidence that the qualification “well-defined” needs to be taken seriously. Bertrand Russell re-stated this famous paradox in a very interesting way: In the town of Seville lives a barber who shaves everyone who does not shave himself. Does the barber shave himself?…)

The objects in a set are called elements or members of that set.

We denote sets by capital letters : A, B, C etc. The elements of a set are represented by small letters : a, b, c, d, e, f ….etc. If x is an element of a set A, we write x \in A. And, we read it as “x belongs to A.” If x is not an element of a set A, we write x \not\in A, and read as ‘x does not belong to A.’e.g., 1 is a “whole” number but not a “natural” number.

Hence, 0 \in W, where W is the set of whole numbers and 0 \not\in N, where N is a set of natural numbers.

There are two methods of representing a set:

a) Roster or Tabular Method or List Method (b) Set-Builder or Ruler Method

a) Roster or Tabular or List Method:

Let A be the set of all prime numbers less than 20. Can you enumerate all the elements of the set A? Are they as follows?

A=\{ 2,3,5,7,11,15,17,19\}

Can you describe the roster method? We can describe it as follows:

In the Roster method, we list all the elements of the set within braces \{, \} and separate the elements by commas.

In the following examples, state the sets using Roster method:

i) B is the set of all days in a week

ii) C is the set of all consonants in English alphabets.

iii) D is the set of first ten natural numbers.

2) Set-Builder Method:

Let P be the set of first five multiples of 10. Using Roster Method, you must have written the set as follows:

P = \{ 10, 20, 30, 40, 50\}

Question: What is the common property possessed by all the elements of the set P?

Answer: All the elements are multiples of 10.

Question: How many such elements are in the set?

Answer: There are 5 elements in the set.

Thus, the set P can be described using this common property. In such a case, we say that set-builder method is used to describe the set. So, to summarize:

In the set-builder method, we describe the elements of the set by specifying the property which determines the elements of the set uniquely.

Thus, we can write : P = \{ x: x =10n, n \in N, n \leq 5\}

In the following examples, state the sets using set-builder method:

i) Y is the set of all months of a year

ii) M is the set of all natural numbers

iii) B is the set of perfect squares of natural numbers.

Also, if elements of a set are repeated, they are written once only; while listing the elements of a set, the order in which the elements are listed is immaterial. (but this situation changes when we consider sets from the view-point of permutations and combinations. Just be alert in set-theoretic questions.)

Subset: A set A is said to be a subset of a set B if each element of set A is an element of set B. Symbolically, A \subseteq B.

Superset: If A \subset B, then B is called the superset of set A. Symbolically: B \supset A

Proper Subset: A non empty set A is said to be a proper subset of the set B, if and only if all elements of set A are in set B, and at least one element of B is not in A. That is, if A \subseteq B, but A \neq B then A is called a proper subset of B and we write A \subset B.

Note: the notations of subset and proper subset differ from author to author, text to text or mathematician to mathematician. These notations are not universal conventions in math.

Intervals: 

  1. Open Interval : given a < b, a, b \in R, we say a<x<b is an open interval in \Re^{1}.
  2. Closed Interval : given a \leq x \leq b = [a,b]
  3. Half-open, half-closed: a <x \leq b = (a,b], or a \leq x <b=[a,b)
  4. The set of all real numbers greater than or equal to a : x \geq a =[a, \infty)
  5. The set of all real numbers less than or equal to a is (-\infty, a] = x \leq a

Types of Sets:

  1. Empty Set: A set containing no element is called the empty set or the null set and is denoted by the symbol \phi or \{ \} or void set. e.g., A= \{ x: x \in N, 1<x<2\}
  2. Singleton Set: A set containing only one element is called a singleton set. Example : (i) Let A be a set of all integers which are neither positive nor negative. Then, A = \{ 0\} and example (ii) Let B be a set of capital of India. Then B= \{ Delhi\}

We will define the following sets later (after we giving a working definition of a function): finite set, countable set, infinite set, uncountable set.

3. Equal sets: Two sets are said to be equal if they contain the same elements, that is, if A \subseteq B and B \subseteq A. For example: Let X be the set of letters in the word ‘ABBA’ and Y be the set of letters in the word ‘BABA’. Then, X= \{ A,B\} and Y= \{ B,A\}. Thus, the sets X=Y are equal sets and we denote it by X=Y.

How to prove that two sets are equal?

Let us say we are given the task to prove that A=B, where A and B are non-empty sets. The following are the steps of the proof : (i) TPT: A \subset B, that is, choose any arbitrary element x \in A and show that also x \in B holds true. (ii) TPT: B \subset A, that is, choose any arbitrary element y \in B, and show that also y \in A. (Note: after we learn types of functions, we will see that a fundamental way to prove two sets (finite) are equal is to show/find a bijection between the two sets).

PS: Note that two sets are equal if and only if they contain the same number of elements, and the same elements. (irrespective of order of elements; once again, the order condition is changed for permutation sets; just be alert what type of set theoretic question you are dealing with and if order is important in that set. At least, for our introduction here, order of elements of a set is not important).

PS: Digress: How to prove that in general, x=y? The standard way is similar to above approach: (i) TPT: x < y (ii) TPT: y < x. Both (i) and (ii) together imply that x=y.

4. Equivalent sets: Two finite sets A and B are said to be equivalent if n(A)=n(B). Equal sets are always equivalent but equivalent sets need not be equal. For example, let A= \{ 1,2,3 \} and B = \{ 4,5,6\}. Then, n(A) = n(B), so A and B are equivalent. Clearly, A \neq B. Thus, A and B are equivalent but not equal.

5. Universal Set: If in a particular discussion all sets under consideration are subsets of a set, say U, then U is called the universal set for that discussion. You know that the set of natural numbers the set of integers are subsets of set of real numbers R. Thus, for this discussion is a universal set. In general, universal set is denoted by or X.

6. Venn Diagram: The pictorial representation of a set is called Venn diagram. Generally, a closed geometrical figures are used to represent the set, like a circle, triangle or a rectangle which are known as Venn diagrams and are named after the English logician John Venn.

In Venn diagram the elements of the sets are shown in their respective figures.

Now, we have these “abstract toys or abstract building-blocks”, how can we get new such “abstract buildings” using these “abstract building blocks”. What I mean is that we know that if we are a set of numbers like 1,2,3, …, we know how to get “new numbers” out of these by “adding”, subtracting”, “multiplying” or “dividing” the given “building blocks like 1, 2…”. So, also what we want to do now is “operations on sets” so that we create new, more interesting or perhaps, more “useful” sets out of given sets. We define the following operations on sets:

  1. Complement of a set: If A is a subset of the universal set U then the set of all elements in U which are not in A is called the complement of the set A and is denoted by A^{'} or A^{c} or \overline{A} Some properties of complements: (i) {A^{'}}^{'}=A (ii) \phi^{'}=U, where U is universal set (iii) U^{'}= \phi
  2. Union of Sets: If A and B are two sets then union of set A and set B is the set of all elements which are in set A or set B or both set A and set B. (this is the INCLUSIVE OR in digital logic) and the symbol is : $latex A \bigcup B
  3. Intersection of sets: If A and B are two sets, then the intersection of set A and set B is the set of all elements which are both in A and B. The symbol is A \bigcap B.
  4. Disjoint Sets: Let there be two sets A and B such that A \bigcap B=\phi. We say that the sets A and B are disjoint, meaning that they do not have any elements in common. It is possible that there are more than two sets A_{1}, A_{2}, \ldots A_{n} such that when we take any two distinct sets A_{i} and A_{j} (so that i \neq j, then A_{i}\bigcap A_{j}= \phi. We call such sets pairwise mutually disjoint. Also, in case if such a collection of sets also has the property that \bigcup_{i=1}^{i=n}A_{i}=U, where U is the Universal Set in the given context, We then say that this collection of sets forms a partition of the Universal Set.
  5. Difference of Sets: Let us say that given a universal set U and two other sets A and B, B-A denotes the set of elements in B which are not in A; if you notice, this is almost same as A^{'}=U-A.
  6. Symmetric Difference of Sets: Suppose again that we are two given sets A and B, and a Universal Set U, by symmetric difference of A and B, we mean (A-B)\bigcup (B-A). The symbol is A \triangle B. Try to visualize this (and describe it) using a Venn Diagram. You will like it very much. Remark : The designation “symmetric difference” for the set A \triangle B is not too apt, since A \triangle B has much in common with the sum A \bigcup B. In fact, in A \bigcup B the statements “x belongs to A” and “x belongs to B” are joined by the conjunction “or” used in the “either …or …or both…” sense, while in A \triangle B the same two statements are joined by “or” used in the ordinary “either…or….” sense (as in “to be or not to be”). In other words, x belongs to A \bigcup B if and only if x belongs to either A or B or both, while x belongs to A \triangle B if and only if x belongs to either A or B but not both. The set A \triangle B can be regarded as a kind of a “modulo-two-sum” of the sets A and B, that is, a sum of the sets A and B in which elements are dropped if they are counted twice (once in A and once in B).

Let us now present some (easily provable/verifiable) properties of sets:

  1. A \bigcup B = B \bigcup A (union of sets is commutative)
  2. (A \bigcup B) \bigcup C = A \bigcup (B \bigcup C) (union of sets is associative)
  3. A \bigcup \phi=A
  4. A \bigcup A = A
  5. A \bigcup A^{'}=U where U is universal set
  6. If A \subseteq B, then A \bigcup B=B
  7. U \bigcup A=U
  8. A \subseteq (A \bigcup B) and also B \subseteq (A \bigcup B)

Similarly, some easily verifiable properties of set intersection are:

  1. A \bigcap B = B \bigcap A (set intersection is commutative)
  2. (A \bigcap B) \bigcap C = A \bigcap (B \bigcap C) (set intersection is associative)
  3. A \bigcap \phi = \phi \bigcap A= \phi (this matches intuition: there is nothing common in between a non empty set and an empty set :-))
  4. A \bigcap A =A (Idempotent law): this definition carries over to square matrices: if a square matrix is such that A^{2}=A, then A is called an Idempotent matrix.
  5. A \bigcap A^{'}=\phi (this matches intuition: there is nothing in common between a set and another set which does not contain any element of it (the former set))
  6. If A \subseteq B, then A \bigcap B =A
  7. U \bigcap A=A, where U is universal set
  8. (A \bigcap B) \subseteq A and (A \bigcap B) \subseteq B
  9. i: A \bigcap (B \bigcap )C = (A \bigcap B)\bigcup (A \bigcap C) (intersection distributes over union) ; (9ii) A \bigcup (B \bigcap C)=(A \bigcup B) \bigcap (A \bigcup C) (union distributes over intersection). These are the two famous distributive laws.

The famous De Morgan’s Laws for two sets are as follows: (it can be easily verified by Venn Diagram):

For any two sets A and B, the following holds:

i) (A \bigcup B)^{'}=A^{'}\bigcap B^{'}. In words, it can be captured beautifully: the complement of union is intersection of complements.

ii) (A \bigcap B)^{'}=A^{'} \bigcup B^{'}. In words, it can be captured beautifully: the complement of intersection is union of complements.

Cardinality of a set: (Finite Set) : (Again, we will define the term ‘finite set’ rigorously later) The cardinality of a set is the number of distinct elements contained in a finite set A and we will denote it as n(A).

Inclusion Exclusion Principle:

For two sets A and B, given a universal set U: n(A \bigcup B) = n(A) + n(B) - n(A \bigcap B).

For three sets A, B and C, given a universal set U: n(A \bigcup B \bigcup C)=n(A) + n(B) + n(C) -n(A \bigcap B) -n(B \bigcap C) -n(C \bigcup A) + n(A \bigcap B \bigcap C).

Homework Quiz: Verify the above using Venn Diagrams. 

Power Set of a Set:

Let us consider a set A (given a Universal Set U). Then, the power set of A is the set consisting of all possible subsets of set A. (Note that an empty is also a subset of A and that set A is a subset of A itself). It can be easily seen (using basic definition of combinations) that if n(A)=p, then n(power set A) = 2^{p}. Symbol: P(A).

Homework Tutorial I:

  1. Describe the following sets in Roster form: (i) \{ x: x \hspace{0.1in} is \hspace{0.1in} a \hspace{0.1in} letter \hspace{0.1in} of \hspace{0.1in} the \hspace{0.1in} word \hspace{0.1in}  PULCHRITUDE\} (II) \{ x: x \hspace{0.1in } is \hspace{0.1in} an \hspace{0.1in} integer \hspace{0.1in} with \hspace{0.1in} \frac{-1}{2} < x < \frac{1}{2} \} (iii) \{x: x=2n, n \in N\}
  2. Describe the following sets in Set Builder form: (i) \{ 0\} (ii) \{ 0, \pm 1, \pm 2, \pm 3\} (iii) \{ \}
  3. If A= \{ x: 6x^{2}+x-15=0\} and B= \{ x: 2x^{2}-5x-3=0\}, and x: 2x^{2}-x-3=0, then find (i) A \bigcup B \bigcup C (ii) A \bigcap B \bigcap C
  4. If A, B, C are the sets of the letters in the words, ‘college’, ‘marriage’, and ‘luggage’ respectively, then verify that \{ A-(B \bigcup C)\}= \{ (A-B) \bigcap (A-C)\}
  5. If A= \{ 1,2,3,4\}, B= \{ 3,4,5, 6\}, C= \{ 4,5,6,7,8\} and universal set X= \{ 1,2,3,4,5,6,7,8,9,10\}, then verify the following:

5i) A\bigcup (B \bigcap C) = (A\bigcup B) \bigcap (A \bigcup C)

5ii) A \bigcap (B \bigcup C)= (A \bigcap B) \bigcup (A \bigcap C)

5iii) A= (A \bigcap B)\bigcup (A \bigcap B^{'})

5iv) B=(A \bigcap B)\bigcup (A^{'} \bigcap B)

5v) n(A \bigcup B)= n(A)+n(B)-n(A \bigcap B)

6. If A and B are subsets of the universal set is X, n(X)=50, n(A)=35, n(B)=20, n(A^{'} \bigcap B^{'})=5, find (i) n(A \bigcup B) (ii) n(A \bigcap B) (iii) n(A^{'} \bigcap B) (iv) n(A \bigcap B^{'})

7. In a class of 200 students who appeared certain examinations, 35 students failed in MHTCET, 40 in AIEEE, and 40 in IITJEE entrance, 20 failed in MHTCET and AIEEE, 17 in AIEEE and IITJEE entrance, 15 in MHTCET and IITJEE entrance exam and 5 failed in all three examinations. Find how many students (a) did not flunk in any examination (b) failed in AIEEE or IITJEE entrance.

8. From amongst 2000 literate and illiterate individuals of a town, 70 percent read Marathi newspaper, 50 percent read English newspapers, and 32.5 percent read both Marathi and English newspapers. Find the number of individuals who read

8i) at least one of the newspapers

8ii) neither Marathi and English newspaper

8iii) only one of the newspapers

9) In a hostel, 25 students take tea, 20 students take coffee, 15 students take milk, 10 students take both tea and coffee, 8 students take both milk and coffee. None of them take the tea and milk both and everyone takes at least one beverage, find the number of students in the hostel.

10) There are 260 persons with a skin disorder. If 150 had been exposed to chemical A, 74 to chemical B, and 36 to both chemicals A and B, find the number of persons exposed to  (a) Chemical A but not Chemical B (b) Chemical B but not Chemical A (c) Chemical A or Chemical B.

11) If A = \{ 1,2,3\} write down the power set of A.

12) Write the following intervals in Set Builder Form: (a) (-3,0) (b) [6,12] (c) (6,12] (d) [-23,5)

13) Using Venn Diagrams, represent (a) (A \bigcup B)^{'} (b) A^{'} \bigcup B^{'} (c) A^{'} \bigcap B (d) A \bigcap B^{'}

Regards,

Nalin Pithwa.

Permutations and Combinations: A primer only

The infinite hotel paradox : due Jeff Dekofsky

This hardcore stuff about “infinity” , quite nicely, explained was pointed out to me by my ISC XII student, Mr. Utkarsh Malhotra! 🙂

 

Logicalympics — 100 meters!!!

Just as you go to the gym daily and increase your physical stamina, so also, you should go to the “mental gym” of solving hard math or logical puzzles daily to increase your mental stamina. You should start with a laser-like focus (or, concentrate like Shiva’s third eye, as is famous in Hindu mythology/scriptures!!) for 15-30 min daily and sustain that pace for a month at least. Give yourself a chance. Start with the following:

The logicalympics take place every year in a very quiet setting so that the competitors can concentrate on their events — not so much the events themselves, but the results. At the logicalympics every event ends in a tie so that no one goes home disappointed 🙂 There were five entries in the room, so they held five races in order that each competitor could win, and so that each competitor could also take his/her turn in 2nd, 3rd, 4th, and 5th place. The final results showed that each competitor had duly taken taken their turn in finishing in each of the five positions. Given the following information, what were the results of each of the five races?

The five competitors were A, B, C, D and E. C didn’t win the fourth race. In the first race A finished before C who in turn finished after B. A finished in a better position in the fourth race than in the second race. E didn’t win the second race. E finished two places  behind C in the first race. D lost the fourth race. A finished ahead of B in the fourth race, but B finished before A and C in the third race. A had already finished before C in the second race who in turn finished after B again. B was not first in the first race and D was not last. D finished in a better position in the second race than in the first race and finished before B. A wasn’t second in the second race and also finished before B.

So, is your brain racing now to finish this puzzle?

Cheers,

Nalin Pithwa.

PS: Many of the puzzles on my blog(s) are from famous literature/books/sources, but I would not like to reveal them as I feel that students gain the most when they really try these questions on their own rather than quickly give up and ask for help or look up solutions. Students have finally to stand on their own feet! (I do not claim creating these questions or puzzles; I am only a math tutor and sometimes, a tutor on the web.) I feel that even a “wrong” attempt is a “partial” attempt; if u can see where your own reasoning has failed, that is also partial success!

Pick’s theorem to pick your brains!!

Pick’s theorem:

Consider a square lattice of unit side. A simple polygon (with non-intersecting sides) of any shape is drawn with its vertices at the lattice points. The area of the polygon can be simply obtained as (B/2)+I-1 square units, where B is number of lattice points on the boundary, I is number of lattice points in the interior of the polygon. Prove this theorem!

Do you like this challenge?

Nalin Pithwa.