Department of Mathematical Sciences
Binghamton University

Math 330: Number Systems
Advice

Section 7, Zaslavsky · Fall 2018

Contents

• Mathematical Writing
• Mathematical Language
• Additions and Corrections to the Textbook
    for Chapter 1 2 3 4 5 6 8 9 10 11 12 13

Mathematical Writing

Mathematical Language

Additions and Corrections to the Textbook

Chapter 1

• The distributive law is really two laws: one for the left and one for the right. The full name of Axiom 1.1(iii) is left distributivity. Proposition 1.6 is right distributivity.


• The minus sign "−" is used in two different ways. −x means the negative (the additive inverse) of x; that is a unary operation (it acts on one number). y − x means y + (−x); this is a binary operation (it acts on two numbers). Don't confuse them. Even though they use the same symbol (and they are somewhat similar), they are not the same thing.

Chapter 2

• (Opinion) Natural numbers vs. positive integers (page 14). I disagree with the book on the best definitions. The set of natural numbers is N, as in the book. A positive integer should be defined to be an integer that's > 0 (because positive means > 0).
      Here's how I think we should do the definitions. We should define a set P := {m ∈ Z : m > 0}. This is the set of positive integers. Then Proposition 2.3 says: P = N. (After this proposition we don't need the symbol P any more, because by the proposition, P is just another name for N.)


• Proposition 2.4 only covers <, but there is also ≤. Here are the "missing parts", or supplementary parts, of Proposition 2.4:
  • Proposition 2.4'. If a < b and b ≤ c, then a < c.
  • Proposition 2.4''. If a ≤ b and b < c, then a < c.
  • Proposition 2.4'''. If a ≤ b and b ≤ c, then a ≤ c.
  Use these freely, as if they were included in Proposition 2.4.
• Propositions 2.7 and 2.12. As with Proposition 2.4, feel free to use the supplementary parts (not stated in the book) with weak inequality, i.e., identities with ≤ instead of <, or both mixed in one identity.


• Section 2.3, Induction, could be called Mathematical Induction. That's the full name of what we're doing here. There are other kinds of reasoning outside mathematics that are called "induction", for instance in science. They are not axiomatic or deductive logic, like mathematical induction, so don't assume any time anyone says "induction" they mean our kind of induction—unless they're math people.


• If n is an integer, we call n+1 the successor of n. The reason is that there are no integers between n and n+1, as we'll prove later.


• An application of Axiom 2.15: How do we know there are no natural numbers other than 1, 2, 3, ...? Axiom 2.15 tells us that. Proof. Suppose we take A to be the set of all numbers you can get by taking 1, its successor 1+1 = 2, its successor 3, and so on all the way. Do we miss any natural numbers? No, because Axiom 2.15 tells us that set contains all of N.
      (We can deduce using Prop. 2.16 that A is equal to N, but that isn't necessary for what I'm saying here.)


• Digits (page 19). This is not entirely correct. A "digit" is not a number, it's a symbol for a number ? a single symbol, as contrasted with a multiple symbol like 10 or 209.
      In the decimal system, the digits are 0, 1, ..., 9. These are called decimal digits.
      In the binary system, they are only 0, 1. These are called binary digits or bits.
      In the hexadecimal system (base 16) they are 0, 1, ..., 9, A, B, C, D, E, F. If you're a computer hacker you probably know this. If not, can you figure out which numbers are meant by these 16 hexadecimal digits?
      (Etymology: Do you know where this use of the word "digit" comes from? Did you ever hear of "digital dexterity"?)


• Possibly the most important special case of Theorem 2.25 (Mathematical Induction) is where the induction starts at 0; that is, where m = 0. The special case where induction starts at 2 is also important.


• Warning about the Well Ordering Principle: It doesn't only say N has a smallest element. It applies to every subset of  N except the empty set.


• The definition of gcd(m, n) in the book (page 22) is not the customary definition. Normally, gcd means "greatest common divisor" and is defined in terms of divisibility. However, that's not the definition to use in this book. Be sure to use the book's definition.
      They want you to find the smallest element of the set S. Divisibility doesn't come into the statement of the problem or their definition of gcd.

Chapter 3

• At the beginning of Section 3.1, the book describes the structure of a quantified statement (that is, a statement that has a quantifier or quantifiers). It says the statement consists of "quantified segments" (where variables are quantified) and a "final statement" (after all the quantifiers). I recommend a slightly different analysis (which is equivalent to theirs).
  • The basic structure of a statement with a quantifier is that it has two parts ("segments").
    1. The first part is the quantification segment (or "range segment"). It states (a) the range of a variable, i.e., the set of possible values—for instance, "∀ x ∈ Z" or "∃ x ∈ Z" tells us x is an integer—and it also states (b) whether we are talking about all values (i.e., every value) of x (∀) or (at least) one value of x (∃).
    2. The second part is the property of that variable. For instance, "x is even", or "x² ≤ 4".
    
    For clarity we normally enclose the quantification segment in parentheses (or square brackets [] or curly brackets {}), and also (usually) enclose the property segment in parentheses. For instance, "(∀ x ∈ Z) (x is even)". (That happens to be false, but true or false, the structure of the statement is the same).
  • The property of x can be complicated. It may include a quantified statement about another variable. For instance,
                    "(∀ x ∈ Z) [ (∀ y ∈ N) (x > y) ]",
    or
                    "(∀ x ∈ Z) [ x < 1000 AND [(∃ y ∈ N) (x > y)] ]",
    but no matter how complicated, it is a property of x.
  • One reason quantification segments must be in order is that a statement with a quantifier should have one variable with one quantification segment and one property segment. The property segment may contain its own quantified statement, whose property can contain a third quantified statement, etc. These multiple statements are always nested within one another, so there's a natural order from inside to outside (or outside to inside, if you prefer).
  • As the book says, there's a simplification when two (or more) variables have the same quantifier (universal, or existential). Then the order of quantification doesn't affect the meaning, so the quantification segments can be combined. However, that's just to make it more convenient for us. It may still be helpful to rewrite the statement according to the basic structure, where only one variable is quantified at a time (especially when negating the statement).
  • Sometimes, it's possible to omit the brackets without causing confusion. If you're not sure how to interpret a quantified statement, you should start by figuring out where the brackets ought to be.


• Uniqueness in quantification requires care! This will be discussed in class. Summary: the correct format for the two parts (see top of page 28) is illustrated by this example:
          { (∃ n ∈ Z such that) (n has property P) } AND { if ([n₁ has property P] AND [n₂ has property P]), then (n₁ = n₂) }.
  Watch the bracketing very closely!


• For Section 3.2, let's define logical equivalence. Two statements A and B are called logically equivalent if they are always both true or both false, but it can never happen that one is true while the other is false. Note that these statements may involve variables, like the statements P(k) in induction, so they may not actually be always true, or always false; by "logical equivalence" we mean that whenever one is true, the other must be true also ? and similarly for falsehood.
      The book (page 28, margin) defines a different property, equivalence of statements A and B, symbolized by the two-headed double arrow ⇔ (read "if and only if"), as "A implies B and B implies A". That's our definition of ⇔. Whenever you use ⇔ as part of a statement, such as "A ⇔ B" ("A if and only if B"), the correct definition is "(A ⇒ B) AND (B ⇒ A)".
      We could, but we don't, have a theorem that:
          Theorem 3.2?. A and B are "logically equivalent" if and only if they are "equivalent".
  (We might have time to prove it in class, but I think not.)


• Properties of the logical operations AND and OR. In order to analyze set intersections and unions (Chapter 5) you have to know how to manipulate logical expressions that combine AND, OR, and NOT. NOT is adequately handled in the book (Project 3.7). For AND and OR you should know the following rules. P, Q, and R are any statements.
          Project 3.6?. Convince yourself that the following logical laws are correct:
  1.     P AND P is logically equivalent to P.
  2.     P OR P is logically equivalent to P.
  3.     P AND Q is logically equivalent to Q AND P.
  4.     P OR Q is logically equivalent to Q OR P.
  5.     (P AND Q) OR R is logically equivalent to (P OR R) AND (Q OR R).
  6.     (P OR Q) AND R is logically equivalent to (P AND R) OR (Q AND R).


• Proving an "OR" statement. Suppose you have two statements, P and Q. How can you prove the compound statement "P OR Q"? (You also have some assumptions given to you, which you're supposed to use in the proof.) There are (at least) two usual methods.
      Method 1. Go through your deduction, using the given assumptions, and at some points you'll have two alternative cases, in one of which you prove P is true, and in the other one of which you prove Q is true.
      Method 2. Assume P is false; add this hypothesis to the given assumptions. Then prove Q is true. (You could reverse the roles of P and Q.)


• Proving an "AND" statement is much simpler. To prove "P AND Q" you just prove P and also prove Q. That's two separate proofs.

Chapter 4

• Example 4.2, the "3x+1 problem", is very mysterious. It shows how much more harder it can be to understand a sequence with a recursive definition than a sequence with a simple formula for each term as in example 4.1.


• In Proposition 4.16 the sequences should be (x_j)_j=a^∞ and (y_j)_j=a^∞.


• In Proposition 4.17 it should be stated that a, a+r ≥ 1. (If not, then the summations are not both defined. Think about why not.)


• Expressions like the third display line on page 41 would be easier to read if the outer parentheses are replaced by square brackets, not the same parentheses in the same size used to denote binomial coefficients.


• In Project 4.26 it should be stated that m, n ∈ Z.

Chapter 5

• Pay attention to the difference between an element of a set and a subset of a set.
      Suppose you have a set S. A subset of S is a set, and it is not (except in very unusual cases) one of the things that is in the set S. An element or member of S is one of the things that is in the set S; it is not necessarily a set, although it can be (since sometimes the elements of S might be sets themselves).
      Pay attention also to the difference betweeen the notations for a subset of S, ⊆ (as in T ⊆ S), and for an element of S, ∈ (as x ∈ S).


• When reading or writing a set definition, pay attention to what is a variable inside the set definition and what is not a variable. As examples, how do the following pairs of sets differ? First, we define some sets:
  
  
  • R = {my: y ∈ Z, m ∈ N, and my > 0}.
  • S = {n: n ∈ N}.
  • T = {n}.
  • U_m = {my: y ∈ Z and my > 0}.
  • V = {2y: y ∈ Z and 2y > 0}.
  • W_m = {my: y ∈ Z and y > 0}.
  
  Now we state the pairs of sets to think about:
  
  
  1. S, and T where n ∈ N.
  2. R, and U_m where m ∈ N.
  3. U_m and W_m, where m ∈ Z.
  4. W₂, and W_m with m = 2.
  5. V, and U_m with m = 2.
  
  Now, find the simplest possible way of writing each of the sets in the preceding list.
      (The book used the previous version of these examples as the basis for Project 5.5.)


• In comparing sets X and Y for equality or containment, there is usually more than one method that may help.
  
  
  1. There are (at least) two methods for showing two sets equal.
     1. The two-way comparison method described in the "Template for proving A = B" on page 49.
     2. Transform the defining equations or properties of X until you get the description of Y.
  
  
  2. There are two ways to show two sets are not equal.
     1. Find an element in one that isn't in the other.
     2. Restate them both in comparable ways (as in A2) that make the answer obvious.
  
  
  3. Two ways to find the intersection of two sets:
     1. Combine the defining properties and (as in A2) simplify.
     2. Show the intersection is empty by proving that no element can be in both sets. (Of course, only if the intersection really is empty.)


• In Project 5.5(iii), do you think m is supposed to be the same m for both V_m and W_m? What is the range of m supposed to be?
      The problem is not stated clearly enough. (It's my fault; I wrote the problem for them.) The sets should be defined before the subproblem (i, ii, iii) statements. The range of m should appear within each subproblem statement. For instance, (iii) should read:
          "V_m and W_m for a specified m ∈ Z."
      See the discussion above on "set definition".

Chapter 6

• The definition of a partition on page 57 is missing an essential condition: No subset P ∈ Π can be empty.


• I like to define the degree of the zero polynomial as −1. Then I don't need to treat it as a special case in Proposition 6.18. Either my way or the book's way is acceptable.


• Proposition 6.18 is fine if the coefficients are real numbers or rational numbers. It is also fine if all coefficients are integers and the divisor n(x) is monic. If the coefficients are integers and n(x) is not monic, q(x) and r(x) do not exist with the stated properties. We'll assume the polynomials in the Division Algorithm for Polynomials have coefficients that are real or, if they are integral, the polynomials are monic.


• A root of a polynomial is also often called a zero of the polynomial, because it's a value of x that makes the polynomial take on the value 0.


• Here is an important extra proposition (that I proved in class).
  
  
  • Proposition 6.23'. Let n ∈ N and m, k ∈ Z. Write m = qn + r and k = pn + s using the division algorithm, so 0 ≤ r, s < n. Then m is congruent to k (mod n) if and only if r = s.


• Here are results regarding §6.4 that I discussed in class.
  
  
  • Definition. A natural number is composite if it is the product of two smaller natural numbers.
    
  • Proposition 6.28'. If n ∈ N, then n = 1 or n is prime or n is composite.
  
  
  • Used in the proof of Prop. 6.28': Lemma A. If p ≥ 2 and q ∈ N, then pq > q.
  
  
  • Used in the proof of Theorem 6.32: Lemma B. Suppose p is a prime number, and q₁, q₂, ..., q_k are primes as well. If p|q₁q₂...q_k, then p equals one of the q_i.

Chapter 8

• On pages 80, line 4 up, and 81, line 1, Proposition 8.32(ii) should be 8.32(iii) in two places.


• For Sect. 8.3, an instructive Example. Let
          S = { x in R : x is a rational number and x ≥ √2 }
  and let
          T = { x in R : x is a rational number and x ≤ √2 }.
  Then S has many lower bounds (think of one), but no infimum (greatest lower bound), in the rational numbers. Similarly, T has many upper bounds, but no supremum (least upper bound), in the rational numbers. The reason is that √2 is not a rational number (see the facts, below).
      In the real numbers, the facts change! In the real numbers, √2 = inf(S), i.e., it is the greatest lower bound of S in the real numbers. And, √2 = sup(T), i.e., it is the least upper bound of T in the real numbers.
      The purpose of this example is to show that Axioms 8.1 and 8.9 are not enough to specify the real numbers (since they're satisfied also by the rational numbers—and other systems). We need the Completeness Axiom, Axiom 8.32, to narrow down to the real numbers.
      Facts used in the preceding example, but not proved at this time (they would take us off the subject).
  • A rational number is a number that is the ratio (i.e., quotient) of two integers. (This is getting ahead of the logical development, but the rational numbers make a good example, so I'll just postpone all the proofs about them till later.)
  • √2 is not a rational number.


• There should be a
          Proposition 8.25A. Suppose x, y, z, w ∈ R and x, w ≠ 0. Then (y/x)(z/w) = (yz)/(xw).
  Use this freely. It is especially useful when dealing with rational numbers, where x, y, z, w are integers.


• Proposition 8.50 should be stated differently: Proposition 8.50'. If A ⊆ B, and if sup(A) and sup(B) exist, then sup(A) ≤ sup(B).

Chapter 9

• Example 9.5: See Section 5.4 for the definition of the graph of f.


• In Proposition 9.10(i), we need to assume A is not empty.


• There is one property of Z that hasn't been proved of e(Z) (what the book calls "Z as a subset of R"). That is the following:
  
  
  • Corollary 9.21. The Induction Axiom 2.15 is true for Z and N as subsets of R.
  
  
  (Stated more precisely: it is true for e(Z) and e(N), which are actually subsets of R.)

Chapter 10

• The proof of Theorem 10.1 could be simpler. We deduce the existence of a least upper bound u, as in the book. Now, u−1 is not an upper bound because u−1 < u, the least upper bound. Therefore, there exists a natural number n such that u−1 < n. Consequently, u < n+1. But then u is not an upper bound for N, which contradicts the definition of u. Therefore, the assumption that N has an upper bound in R must be false.


• What the book calls an increasing sequence (page 101) is usually called "weakly increasing" (or "non-decreasing"), while a sequence such that x_k+1 > x_k for all k is called "strictly increasing" (or "increasing").
      Similar terminology ("weakly" or "strictly") is used for decreasing sequences.


• There should be a Proposition 10.18'. If (x_k) is an increasing sequence, then i < j implies x_i ≤ x_j.
      We haven't proved it, but it's so useful in proofs like 10.19 that we should use it (as the book does, without comment, in proving 10.19).


• The proof of Theorem 10.25 (page 104) is a bit sloppy (not seriously so) in spots. Here is how I would modify it:
  • P. 104, line 5: "Thus every element in A is bounded above by 2." This has been proved only for x ∈ A such that x ≥ 1. We should also prove it for x < 1. Can you find an easy proof?
  • In (a), line 3, "the distance between (u−h)² and u²" is not u² − (u−h)², it is |u² − (u−h)²|. Thus, to prove the distance is < δ, they ought to prove u² − (u−h)² > 0. The book is assuming we know that. In fact, a few lines later at (a), lines 7-8, they prove u−h < u, which we can use to prove (u−h)² < u². (Can you provide that proof?) If they had proved it sooner, they would have fixed this oversight.
  • For (a), line 5, they again need the fact that (u−h)² < u².
  • In (a), last line, the reason we have a contradiction could be stated more precisely as "u−h < u and u−h is an upper bound for A, ...". The fact that h > 0 is not the exact reason; it's that u−h is an upper bound which is < u. (Of course you realized what they meant.)
  • P. 104, line 4 up: "By a similar argument as in" is bad English. Good English would be "By an argument similar to that in".


• The method of proof of Theorem 10.25 can be used to prove
  • Theorem 10.25A. Every real number r such that r > 1 has a square root.
  
  A different proof is needed for
  • Theorem 10.25B. Every real number r such that 0 < r < 1 has a square root.
  
  Problem 10.25C. Prove Theorem 10.25B, assuming that Theorem 10.25A has already been proved.
  

Chapter 11

• Proposition 11.2 should be an if-and-only-if statement: Proposition 11.2 (completed). x/y = z/w if and only if xw = zy.


• Project 11.26 should begin: "Use Proposition 11.25 to prove that ..."

Chapter 13

• The definition of [n] in §13.1 can be restated as follows:
          [n] := { i ∈ N : 1 ≤ i ≤ n }.
  Then [0] is well defined: it is the empty set. (Also, [1] = {1}, [2] = {1,2}, ..., so we get the book's sets for n > 0.) This is sometimes convenient since then [0] is not an exceptional case.


• Theorem 13.4 should be accompanied by a corollary: Theorem 13.4'. If a set X has the cardinality of [n] and also the cardinality of [m], where n, m ∈ Z_≥0, then m = n. (I think this helps to explain the meaning of Theorem 13.4.)


• Proposition 13.13 has the corollary (which I think is the main result):
      Proposition 13.13'. Z is countably infinite.
      (Why is it not finite? There are proofs (1) using Proposition 13.6 and (2) using a bijection N → Z.)


• The definition of an algebraic number on p. 125 should read "... of a nonzero polynomial ...".


• Theorem 13.25 should include the assumption that x < y. (Without that, it's false.)