BASIC CONCEPTS OF MATHEMATICS
CONTENTS CHAPTER 1 SOME SET THEORETICAL NOTIONS 1 INTRODUCTION SETS AND THEIR ELEMENTS 2 OPERATIONS ON SETS PROBLEMS IN SET THEORY 3 LOGICAL QUANTI?ERS 4 RELATIONS (CORRESPONDENCES) PROBLEMS IN THE THEORY OF RELATIONS 5 MAPPINGS ?6 COMPOSITION OF RELATIONS AND MAPPINGS ?7 EQUIVALENCE RELATIONS ?9 SOME THEOREMS ON COUNTABLE SETS PROBLEMS ON COUNTABLE AND UNCOUNTABLE SETS CHAPTER 2 THE REAL NUMBER SYSTEM 1 INTRODUCTION 2 AXIOMS OF AN ORDERED FIELD 3 ARITHMETIC OPERATIONS IN A FIELD PROBLEMS ON ARITHMETIC OPERATIONS AND INEQUALITIES IN A FIELD 5 NATURAL NUMBERS INDUCTION 6 INDUCTION (CONTINUED) 7 INTEGERS AND RATIONALS PROBLEMS ON INTEGERS AND RATIONALS 8 BOUNDED SETS IN AN ORDERED FIELD 10 SOME APPLICATIONS OF THE COMPLETENESS AXIOM PROBLEMS ON COMPLETE AND ARCHIMEDEAN FIELDS 11 ROOTS IRRATIONAL NUMBERS PROBLEMS ON ROOTS AND IRRATIONALS ?12 POWERS WITH ARBITRARY REAL EXPONENTS PROBLEMS ON POWERS ?13 DECIMAL AND OTHER APPROXIMATIONS ?14 ISOMORPHISM OF COMPLETE ORDERED FIELDS ?15 DEDEKIND CUTS CONSTRUCTION OF E1 CHAPTER 3 THE GEOMETRY OF N DIMENSIONS ?VECTOR SPACES 1 EUCLIDEAN N-SPACE, EN 2 INNER PRODUCTS ABSOLUTE VALUES DISTANCES 4 LINES AND LINE SEGMENTS PROBLEMS ON LINES, ANGLES, AND DIRECTIONS IN EN 5 HYPERPLANES IN EN ?LINEAR FUNCTIONALS ON EN 7 INTERVALS IN EN ADDITIVITY OF THEIR VOLUME PROBLEMS ON INTERVALS IN EN 8 COMPLEX NUMBERS PROBLEMS ON COMPLEX NUMBERS ?10 NORMED LINEAR SPACES PROBLEMS ON NORMED LINEAR SPACES CHAPTER SOME SET THEORETICAL NOTIONS §1 INTRODUCTION SETS AND THEIR ELEMENTS THE THEORY OF SETS, INITIATED BY THE GERMAN MATHEMATICIAN G CANTOR (1842– 1918), CONSTITUTES THE BASIS OF ALMOST ALL MODERN MATHEMATICS THE SET CONCEPT ITSELF CANNOT BE DE?NED IN SIMPLER TERMS A SET IS OFTEN DESCRIBED AS A COLLECTION (“AGGREGATE”, “CLASS”, “TOTALITY”, “FAMILY”) OF OBJECTS OF ANY SPECI?ED KIND HOWEVER, SUCH DESCRIPTIONS ARE NO DE?NITIONS, AS THEY MERELY REPLACE THE TERM “SET” BY OTHER UNDE?NED TERMS THUS THE TERM “SET” MUST BE ACCEPTED AS A PRIMITIVE NOTION, WITHOUT DE?NITION EXAMPLES OF SETS ARE AS FOLLOWS: THE SET OF ALL MEN; THE SET OF ALL LETTERS APPEARING ON THIS PAGE; THE SET OF ALL STRAIGHT LINES IN A GIVEN PLANE; THE SET OF ALL POSITIVE INTEGERS; THE SET OF ALL ENGLISH SONGS; THE SET OF ALL BOOKS IN A LIBRARY; THE SET CONSISTING OF THE THREE NUMBERS 1, 4, 17 SETS WILL USUALLY BE DENOTED BY CAPITAL LETTERS, A, B, C, , X, Y , Z THE OBJECTS BELONGING TO A SET A ARE CALLED ITS ELEMENTS OR MEMBERS WE WRITE X ?A IF X IS AN ELEMENT OF THE SET A, AND X /?A IF IT IS NOT EXAMPLE IF N IS THE SET OF ALL POSITIVE INTEGERS, THEN 1 ?N, 3 ?N, + ? 9 ?N, BUT ? 7 /?N, 0 /?N, ?1 /?N, 2 /?N IT IS ALSO CONVENIENT TO INTRODUCE THE SO-CALLED EMPTY (“VOID”, “VACUOUS”) SET, DENOTED BY ?, I E , A SET THAT CONTAINS NO ELEMENTS AT ALL INSTEAD OF SAYING THAT THERE ARE NO OBJECTS OF SOME SPECI?C KIND, WE SHALL SAY THAT THE SET OF THESE ELEMENTS IS EMPTY; HOWEVER, THIS SET ITSELF , THOUGH EMPTY, WILL BE REGARDED AS AN EXISTING THING ONCE A SET HAS BEEN FORMED, IT IS REGARDED AS A NEW ENTITY, THAT IS, A NEW OBJECT, DI?ERENT FROM ANY OF ITS ELEMENTS THIS OBJECT MAY, IN ITS TURN, BE AN ELEMENT OF SOME OTHER SET IN FACT, WE CAN CONSIDER WHOLE COLLECTIONS OF SETS (ALSO CALLED “FAMILIES OF SETS”, “CLASSES OF SETS”, ETC ), I E , SETS WHOSE ELEMENTS ARE OTHER SETS THUS, IF M IS A COLLECTION OF CERTAIN SETS A, B, C, , THEN THESE SETS ARE ELEMENTS OF M, I E , WE HAVE A ?M, B ?M, C ?M, ; A SET A MAY CONSIST OF A SINGLE ELEMENT P; IN THIS CASE WE WRITE A = {P} THIS SET MUST NOT BE CONFUSED WITH THE ELEMENT P ITSELF, ESPECIALLY IF P ITSELF IS A SET CONSISTING OF SOME ELEMENTS A, B, C, , (RECALL THAT THESE ELEMENTS ARE NOT REGARDED AS ELEMENTS OF A; THUS A CONSISTS OF A SINGLE ELEMENT P, WHEREAS P MAY HAVE MANY ELEMENTS; A AND P THEN ARE NOT IDENTICAL) SIMILARLY, THE EMPTY SET 1 THE EQUALITY SIGN, HERE AND IN THE SEQUEL, IS TANTAMOUNT TO LOGICAL IDENTITY A FORMULA LIKE “A = B” MEANS THAT THE LETTERS A AND B DENOTE ONE AND THE SAME THING 2 SOME AUTHORS WRITE A ?B FOR A ?B WE PREFER, HOWEVER, TO RESERVE THE SIGN ?FOR PROPER INCLUSION 3 THE STATEMENT THAT A = B IF A AND B HAVE THE SAME ELEMENTS SHALL BE TREATED AS AN AXIOM, NOT A DE?NITION IF P(X) IS SOME PROPOSITION OR FORMULA INVOLVING A VARIABLE X, WE SHALL USE THE SYMBOL {X | P(X)} TO DENOTE THE SET OF ALL OBJECTS X FOR WHICH THE FORMULA P(X) IS TRUE FOR INSTANCE, THE SET OF ALL MEN CAN BE DENOTED BY {X | X IS A MAN} SIMILARLY, {X | X IS A NUMBER, X < 5} STANDS FOR “THE SET OF ALL NUMBERS LESS THAN 5 ” WE WRITE {X ?A | P(X)} FOR “THE SET OF ALL ELEMENTS OF A FOR WHICH P(X) IS TRUE ” THE VARIABLE X IN SUCH SYMBOLS MAY BE REPLACED BY ANY OTHER VARIABLE; {X | P(X)} IS THE SAME AS {Y | P(Y)} THUS THE SET OF ALL POSITIVE INTEGERS LESS THAN 5 CAN BE DENOTED EITHER BY {1, 2, 3, 4}, OR BY {X | X IS AN INTEGER, 0 < X < 5} NOTE: THE COMMA IN SUCH SYMBOLS STANDS FOR THE WORD “AND” §2 OPERATIONS ON SETS WE NOW PROCEED TO DE?NE SOME OPERATIONS ON SETS 4 “I?” MEANS “IF AND ONLY IF” 5 WE SHALL NOT ATTEMPT AT THIS STAGE TO GIVE A DE?NITION OF AN ORDERED PAIR OR N-TUPLE, THOUGH THIS CAN BE DONE (CF PROBLEM 6 AFTER §2) EXAMPLES (1) IF A = {1, 2, 3, 4, 5} AND B = {2, 4, 6}, THEN A ?B = {1, 2, 3, 4, 5, 6}, A ?B = {2, 4}, A ?B = {1, 3, 5}, B ?A = {6} (2) IF A IS THE SET OF ALL SOLDIERS AND B THE SET OF ALL STUDENTS, THEN A ?B CONSISTS OF ALL PERSONS WHO ARE EITHER SOLDIERS OR STUDENTS OR BOTH; A ?B IS THE SET OF ALL STUDYING SOLDIERS; A ?B IS THE SET OF ALL SOLDIERS WHO DO NOT STUDY; AND B ?A CONSISTS OF THOSE STUDENTS WHO ARE NOT SOLDIERS WHEN SPEAKING OF SETS, WE SHALL ALWAYS TACITLY ASSUME THAT WE ARE GIVEN SOME “MASTER SET”, CALLED THE SPACE, FROM WHICH OUR INITIAL ELEMENTS ARE SELECTED FROM THESE ELEMENTS WE THEN FORM THE VARIOUS SETS (SUBSETS OF THE SPACE); THEN WE PROCEED TO FORM FAMILIES OF SETS, ETC THE SPACE WILL OFTEN REMAIN UNSPECI?ED, SO THAT WE RETAIN THE POSSIBILITY OF CHANGING IT IF REQUIRED IF S IS 1 THE WORD “OR” IS USED IN MATHEMATICS IN THE INCLUSIVE SENSE; THAT IS, “X ?A OR X ?B” MEANS “X ?A OR X ?B OR BOTH” 2 SOME AUTHORS WRITE A \ B FOR A ?B; SOME USE THIS NOTATION ONLY IF B ?A OTHERS USE THE TERMS “SUM” AND “PRODUCT” FOR “UNION” AND “INTERSECTION”, RESPECTIVELY WE SHALL NOT FOLLOW THIS PRACTICE THE NOTIONS OF UNION, INTERSECTION, AND DI?ERENCE CAN BE GRAPHICALLY ILLUS- TRATED BY MEANS OF SO-CALLED “VENN DIAGRAMS”4 ON WHICH THEY APPEAR AS THE SHADED AREAS OF TWO OR MORE INTERSECTING CIRCLES OR OTHER SUITABLE AREAS IN FIG- URES 1, 2, AND 3, WE PROVIDE VENN DIAGRAMS ILLUSTRATING THE UNION, INTERSECTION, AND DI?ERENCE OF TWO SETS A AND B A B FIGURE 1: A ?B A B FIGURE 2: A ?B A B FIGURE 3: A ?B THEOREM 1 FOR ANY SETS A, B, AND C, WE HAVE THE FOLLOWING: (A) A ?A = A; A ?A = A (IDEMPOTENT LAWS) (B) A ?B = B ?A; A ?B = B ?A (COMMUTATIVE LAWS) (C) (A ?B) ?C = A ?(B ?C) (D) (A ?B) ?C = A ?(B ?C) ) (ASSOCIATIVE LAWS) (E) (A ?B) ?C = (A ?C) ?(B ?C) (F) (A ?B) ?C = (A ?C) ?(B ?C) ) (DISTRIBUTIVE LAWS) (G) A ??= A; A ??= ?; A ??= A; A ?A = ? TO VERIFY THESE FORMULAS, WE HAVE TO CHECK, EACH TIME, THAT EVERY ELEMENT CONTAINED IN THE SET OCCURRING ON THE LEFT-HAND SIDE OF THE EQUATION ALSO BELONGS TO THE RIGHT-HAND SIDE, AND CONVERSELY FOR EXAMPLE, WE SHALL VERIFY FORMULA (E), LEAVING THE PROOF OF THE REMAINING FORMULAS TO THE READER SUPPOSE THEN THAT SOME ELEMENT X BELONGS TO THE SET (A ?B) ?C; THIS MEANS THAT X ?(A ?B) AND, SIMULTANEOUSLY, X ?C; IN OTHER WORDS, WE HAVE X ?A OR X ?B AND, SIMULTANEOUSLY, X ?C IT FOLLOWS THAT WE HAVE (X ?A AND X ?C) OR (X ?B AND X ?C); THAT IS, X ?(A?C) OR X ?(B ?C), WHENCE X ?[(A?C)?(B ?C)] THUS WE SEE THAT EVERY ELEMENT X CONTAINED IN THE LEFT-HAND SIDE OF (E) IS ALSO CONTAINED IN THE RIGHT-HAND SIDE THE CONVERSE ASSERTION IS PROVED IN THE SAME WAY BY SIMPLY REVERSING THE ORDER OF THE STEPS OF THE PROOF IN FIGURES 4 AND 5, WE ILLUSTRATE THE DISTRIBUTIVE LAWS (E) AND (F) BY VENN DIAGRAMS; THE SHADED AREA REPRESENTS THE SET RESULTING FROM THE OPERATIONS INVOLVED IN EACH CASE 3 OTHER NOTATIONS IN USE FOR COMPLEMENT ARE AS FOLLOWS: ?E, E E, E?, ?E, E?, ETC 4 AFTER THE ENGLISH LOGICIAN JOHN VENN (1834–1883) BASIC CONCEPTS OF MATHEMATICS A B C (A ?B) ?C = (A ?C) ?(B ?C) FIGURE A B C (A ?B) ?C = (A ?C) ?(B ?C) FIGURE BECAUSE OF THE ASSOCIATIVE LAWS, WE MAY OMIT THE BRACKETS IN EXPRESSIONS OCCURRING IN FORMULAS (C) AND (D) THUS WE MAY WRITE A?B ?C AND A?B ?C INSTEAD OF (A ?B) ?C AND (A ?B) ?C, RESPECTIVELY 5 SIMILARLY, UNIONS AND INTERSECTIONS OF FOUR OR MORE SETS MAY BE WRITTEN IN VARIOUS WAYS: A ?B ?C ?D = (A ?B) ?(C ?D) = A ?(B ?C ?D) = (A ?B ?C) ?D; A ?B ?C ?D = (A ?B ?C) ?D = (A ?B) ?(C ?D), ETC AS WE NOTED IN §1, WE MAY CONSIDER NOT JUST ONE OR TWO, BUT A WHOLE FAMILY OF SETS, EVEN IN?NITELY MANY OF THEM SOMETIMES WE CAN NUMBER THE SETS UNDER CONSIDERATION: X1, X2, X3, , XN, (COMPARE THIS TO THE NUMBERING OF BUILDINGS IN A STREET, OR BOOKS IN A LIBRARY) MORE GENERALLY, WE MAY DENOTE ALL SETS OF A FAMILY M BY ONE AND THE SAME LETTER (SAY, X), WITH SOME INDICES (SUBSCRIPTS OR SUPERSCRIPTS) ATTACHED TO IT: XI OR XI, WHERE I RUNS OVER A SUITABLE (SU?CIENTLY LARGE) SET I OF INDICES, CALLED THE INDEX SET THE INDICES MAY, BUT NEED NOT, BE NUMBERS THEY ARE JUST “LABELS” OF ARBITRARY NATURE, USED SOLELY TO DISTINGUISH THE SETS FROM EACH OTHER, IN THE SAME WAY THAT A GOOD COOK USES LABELS TO DISTINGUISH THE JARS IN THE KITCHEN THE WHOLE FAMILY M THEN IS DENOTED BY {XI | I ?I}, BRIE?Y {XI} HERE I IS A VARIABLE RANGING OVER THE INDEX SET I THIS IS CALLED INDEX NOTATION THE NOTIONS OF UNION AND INTERSECTION CAN EASILY BE EXTENDED TO ARBITRARY FAMILIES OF SETS IF M IS SUCH A FAMILY, WE DE?NE ITS UNION, S M, TO BE THE SET OF ALL ELEMENTS X, EACH BELONGING TO AT LEAST ONE SET OF THE FAMILY THE INTERSECTION, T M, CONSISTS OF THOSE ELEMENTS X THAT BELONG TO ALL SETS OF THE FAMILY SIMULTANEOUSLY INSTEAD OF S M AND T M, WE ALSO USE [ {X | X ?M} AND \ {X | X ?M}, RESPECTIVELY HERE X IS A VARIABLE DENOTING ANY ARBITRARY SET OF THE FAMILY NOTE: X ?S M I?X IS IN AT LEAST ONE SET X OF THE FAMILY; X ?T M I?X BELONGS TO EVERY SET X OF THE FAMILY 5 AS WILL BE SEEN, UNIONS AND INTERSECTIONS OF THREE OR MORE SETS CAN BE DE?NED INDEPEN- DENTLY THUS, IN SET THEORY, SUCH FORMULAS AS A?B?C = (A?B)?C OR A?B?C = (A?B)?C ARE THEOREMS, NOT DE?NITIONS XN, ? [ N=K XN, X1 ?X2 ? ?XN ? , OR THE SAME WITH S AND T INTERCHANGED, IMITATING A SIMILAR NOTATION KNOWN FROM ELEMENTARY ALGEBRA FOR SUMS AND PRODUCTS OF NUMBERS THE FOLLOWING THEOREM HAS MANY IMPORTANT APPLICATIONS THEOREM 2 (DE MORGAN’S DUALITY LAWS6) GIVEN A SET E AND ANY FAMILY OF SETS {AI} (WHERE I RANGES OVER SOME INDEX SET I), WE ALWAYS HAVE (I) E ? [ I AI = \ I (E ?AJ); (II) E ? \ I AI = [ I (E ?AI) VERBALLY, THIS READS AS FOLLOWS: (I) THE COMPLEMENT (IN E) OF THE UNION OF A FAMILY OF SETS EQUALS THE INTER- SECTION OF THEIR COMPLEMENTS (IN E) (II) THE COMPLEMENT (IN E) OF THE INTERSECTION OF A FAMILY OF SETS EQUALS THE UNION OF THEIR COMPLEMENTS (IN E) PROOF OF (I) WE HAVE TO SHOW THAT THE SET E ?S I AI CONSISTS OF EXACTLY THE SAME ELEMENTS AS THE SET T I(E ?AI), I E , THAT WE HAVE X ?E ? [ I AI I?X ? \ I (E ?AI) THIS FOLLOWS FROM THE EQUIVALENCE OF THE FOLLOWING STATEMENTS (WE INDICATE LOG- 6 AUGUSTUS DE MORGAN, INDIAN-BORN ENGLISH MATHEMATICIAN AND LOGICIAN (1806–1871)