George M. Bergman Math H110, Fall 2008 Supplementary materialSome notes on sets, logic, and mathematical languageThese are ‘‘generic’’ notes, for use in Math 110, 113, 104 or 185.These pages do not develop in detail the definitions and concepts to be mentioned. That is done, tovarious degrees, in Math 55, Math 74, Math 125 and Math 135. I hope you will nevertheless find themuseful and thought-provoking. I recommend working the exercises for practice; but don’t hand them inunless they are listed in a homework assignment for the course.1. Set-theoretic symbolsSymbol. Meaning, usage, examples, discussion.∅ The empty set., Here denotes the set of all natural numbers, i.e., {0, 1, 2, 3, ... }, while (from ‘‘Zahl’’,German for ‘‘number’’) denotes the set of all integers, {... , –3, – 2, –1, 0, 1, 2, 3, ... }.(Many older authors started the natural numbers with 1, but it is preferable to start with 0, sincenatural numbers are used to count the elements of finite sets, and ∅ is a finite set.), , Of these, (for ‘‘quotient’’) denotes the set of all rational numbers, i.e., fractions that can bewritten with integer numerator and denominator, denotes the set of real numbers, and theset of complex numbers.(The five sets just named used to be, and often still are, denoted by bold-face letters N, Z, Q,R and C. The forms , ..., arose as quick ways to write these boldface letters on theblackboard. Since it is convenient to have distinctive symbols for these important sets, printedforms imitating the ‘‘blackboard bold’’ symbols were then designed, and are now frequently used,as shown.)∈ ‘‘Is a member of’’. E.g., 3 ∈.{ } ‘‘The set of all’’. This is often used together with ‘‘!’’ or ‘‘:’’ (different authors prefer the one orthe other), which stand for ‘‘such that’’. For instance, the set of positive integers can be written{1, 2, 3, ... } or {n∈!n>0} or {n : n∈ , n>0}. The set of all square integers can be written{0, 1, 4, 9, ... , n2, ... } or {n2!n∈ }. Note also that {n2!n∈ } = {m2!m∈ } ={m2+ 2m+ 1!m∈ }. (Why?)⊆‘‘Is a subset of’’. E.g., ∅⊆{1}⊆⊆ ⊆ ⊆. {n2!n∈ }⊆{n∈!n≥0}.⊆.⊂ or⊂≠‘‘Is a proper subset of’’; that is, a subset that is not the whole set. For instance,⊂≠. In fact,all the formulas used above to illustrate ‘‘⊆’’ remain true with⊂≠in place of⊆except for⊆. Since a proper subset is, in particular, a subset, one may use⊆even when⊂≠is true;and one generally does so, unless one wants to emphasize that a subset is proper. But beware:some authors (especially in Eastern Europe) use ⊂ for ‘‘is a subset of’’.⊇, ∈, etc. Obvious variants of the above symbols: A⊇B means B⊆A; x∈X means x is not a memberof X; A⊆B means A is not a subset of B; etc..Warning: The phrases ‘‘A lies in X’’ and ‘‘A is contained in X’’ can mean either A∈X orA⊆X. (The former phrase more often means A∈X and the latter A⊆X, but this is noguarantee.) So in your writing, if there is danger of ambiguity, either use the mathematicalsymbols, or use the unambiguous phrases ‘‘is a member of’’ and ‘‘is a subset of’’.∩ Intersection: A ∩B = {x!both x ∈A and x ∈B are true }. For instance,{x∈!x>9} ∩ {x∈!x≤12} = {10, 11, 12}.- 2 -∩ Intersection of an indexed family of sets. For instance, if A0, A1, ... are sets, then ∩n=0,1,...An,also written ∩n∈An, ∩∞n= 0Anand A0∩ A1∩... ∩ An∩... , means {x!x is a member ofall of A0, A1, etc.}.In an intersection ∩i∈IAi, I does not have to be a set of integers; it can be any set such thatAiis defined for each i∈I. When a set I is used in this way to index (i.e., list) other entities, itis called an index set.∪ Union: A ∪B = {x!x∈A or x∈B}. For instance, {x∈!x> 0} ∪ {x∈!x< 12} = . Notethat if A⊆B then A∪B = B and A ∩B = A.∪ Union of an indexed family of sets. Thus ∪n=0,1,...An= ∪n∈An= ∪∞n=0An=A0∪ A1∪... ∪ An∪... . Example: ∪n∈{i∈!i<n} = .Often, when the intent is clear from context, the above notations are abbreviated. For instance,if we know that we have one set Aifor each i in a certain index-set I, then instead of∪i∈IAi, we may write ∪IAior ∪iAior just ∪Ai. Likewise, if we have a set Xnforeach positive integer n, the intersection ∩∞n=1Xnmay be written ∩nXnor simply ∩Xn.c‘‘Complement of’’:cA means {x!x∈A}.But {x!x∈A} makes no sense if we don’t say what x’s are allowed! So the notationcA isused only when discussing subsets of a fixed set. For instance, if we are discussing subsets of theintegers, thenc{even integers} = {odd integers}, while if we are considering subsets of, thenc{even integers} denotes the set consisting of all odd integers and non-integer rationals. To bemore precise, we can use the next symbols:– or \ A –B (or A\B) means {x∈A!x∈B}. E.g., – {even integers} = {odd integers}. Note thatA –B is defined even if B is not a subset of A. For instance, – {negative real numbers} = .f: X → Y This indicates that f is a function (also called a ‘map’ or ‘mapping’) from the set X to the set Y.(In reading the symbol out loud, one can use words such as ‘‘the map f from X to Y’’, or ‘‘fsending X to Y’’.)Such an f is said to be one-to-one (or injective) if for every two distinct elements x1, x2∈X,the elements f(x1) and f(x2) of Y are also distinct. For instance, the operation of cubing aninteger is a one-to-one function→ ; but the squaring map is not one-to-one, because(–n)2= n2.The function f: X → Y is said to be onto Y if every element of Y equals f(x) for somex∈X. For instance, the squaring and cubing maps → are not onto, since not all integers aresquares or cubes. On the other hand, the cubing map → is both one-to-one and onto.Given f: X → Y, the set X is called the domain of f. What about the set at the other end ofthe arrow? A complication is that if f is not onto Y, then Y and { f(x)!x∈X} are differentsets. Traditionally, these were called the ‘‘range’’ and the ‘‘image’’ of f respectively, but theusage was not firm; ‘‘range’’ was often used as a synonym for ‘‘image’’. Hence nowadays, theunambiguous term ‘‘codomain’’ has been introduced to describe Y. A function is called onto if itis onto its codomain; a synonymous term is ‘‘surjective’’ (from