Math 330: Number Systems
Announcements
Section 3, Zaslavsky
Main class page | Schedule and homework | Announcements | Term Project | Syllabus
Contents
Midterm Test (Thurs., Oct. 20 Mon., Oct. 24)
The midterm will cover Chapter 1 through Section 6.2 (HW 1-18).
The format will be open-book, open-notes: you can have your textbook and notes, but no electronic devices (obviously?!).
There will be some questions everyone should answer and some questions you can choose from. (For instance, there might be 2 required questions and 5 other questions of which you choose 3 to answer—these may or may not be the actual numbers.)
Grading guidelines:
A B C D F
86-100 69-85 52-68 47-52 0-46
Final Exam (Tues., Dec. 13)
The final exam will cover the entire course. That is Chapters 1-6, 8-11, and 13 except Sect. 13.5.
Grading guidelines:
A B C D F
80-120 61-79 43-60 38-42 0-37
I gave 10 points per problem in part I, for 60 points, and 30 points per solution in part II, for 60 points. That's not what it said on the final exam itself; this is a better allocation of points.
Project
The project has Part I (verify validity or invalidity of your operations; 30 pts.) and Part II (a) identity element (10 pts.), (b) cancellation (10 pts.), (c) inverses (10 pts.): total of 60 points, which will be converted to 15% of the final grade (the same as the midterm exam).
A B C D F
32-60 22-31 12-21 10-11 0-9
Anyone who did the entire project gets a big boost in grade; that is intentional.
Quiz 1 (10/19).
Negate the following statement:
Jan plays the trumpet if and only if Joe organizes a parade.
Solution (to appear).
Quiz 2 (11/10).
The quiz concerns sets X = {1,2,3,4} and Y = {1,2,...,16} and the function f: A → Y defined by f(x) = x2.
- Is f injective?
- Is f surjective?
- Is f bijective?
Solution: Yes, no, no.
Quiz 3 (11/10).
The quiz concerns the function f from Quiz 2.
- Find a left inverse of f.
- Find a right inverse of f.
- Find a two-sided inverse of f.
Solution:
(a) g(y) = √y if y = 1, 4, 9, 16 and = 10 (or any values) otherwise.
(b) None.
(c) None.
- In math, "unique" has a very precise meaning: "only one". It never means "different". If you mean "different", say "different", or "distinct" to mean "different from each other.
We often use "unique" as part of a phrase like "There is a unique ...". That means "There is one and only one ...".
- "Therefore" and non-synonyms.
- "So" means "therefore". Throwing in random "so"s here and there will confuse your reader and get a lower grade.
- If you do mean "therefore", don't say "and". "And" does not mean "therefore". Good synonyms for "therefore" are "thus", "consequently", and so on.
- The symbol ⇒ means "implies". The symbol ∴ means "therefore". They don't mean the same thing.
"A ⇒ B" means "If A is true, then B is true." It doesn't assert that A is true and it doesn't assert that B is true.
"A, therefore B", also written "A ∴ B", means "A is true, and therefore B is true." It does assert that A is true and it also asserts that B is true.
- "Assume" means "suppose for this discussion". It does not mean "I'm going to prove" or "This is a known fact".
- Pay attention to the difference between a subset and an element of a set. Can you explain the difference? If not, think about it carefully.
Pay attention also to the difference between the notations for a subset of a set, ⊆, and for an element of the set, ∈. (These symbols may not show correctly in all browsers.)
Main class page | Schedule and homework | Announcements | Term Project | Syllabus
- 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.
- 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 =(def) {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.)
- Section 2.3, Induction should probably 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 in a later chapter.
- 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. I explained that in class. However, that's not the definition to use in this book.
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.
- 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").
- 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 (∃).
- The second part is the property of that variable. For instance, "x is even", or "x2 ≤ 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 ([n1 has property P] AND [n2 has property P]), then (n1 = n2) }.
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:
- P AND P is logically equivalent to P.
- P OR P is logically equivalent to P.
- P AND Q is logically equivalent to Q AND P.
- P OR Q is logically equivalent to Q OR P.
- (P AND Q) OR R is logically equivalent to (P OR R) AND (Q OR R).
- (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.
- 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 (xj)j=a∞ and (yj)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.)
- In Project 4.26 it should be stated that m, n ∈ Z.
- 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}.
- Um = {my: y ∈ Z and my > 0}.
- V = {2y: y ∈ Z and 2y > 0}.
- Wm = {my: y ∈ Z and y > 0}.
Now we state the pairs of sets to think about:
- S, and T where n ∈ N.
- R, and Um where m ∈ N.
- Um and Wm, where m ∈ Z.
- W2, and Wm with m = 2.
- V, and Um 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.
- There are (at least) two methods for showing two sets equal.
- The two-way comparison method.
- Transform the defining equations or properties of X until you get the description of Y.
- There are two ways to show two sets are not equal.
- Find an element in one that isn't in the other.
- Restate them both in comparable ways (as in A2) that make the answer obvious.
- Two ways to find the intersection of two sets:
- Combine the defining properties and (as in A2) simplify.
- 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 Vm and Wm? What is the range of m supposed to be?
The problem is not stated clearly enough. (It's my fault, not the authors'.) 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:
"Vm and Wm for a specified m ∈ Z."
See the presentation above, at "set definition".
- The definition of a partition on page 57 is missing an essential condition: No subset P ∈ Π can be empty.
- Instead of not defining the degree of the zero polynomial (as the book does on page 59), I prefer to give it degree −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.
- In Proposition 6.18 the polynomials must be real (or at least rational, i.e., the coefficients are rational numbers). Otherwise, q(x) and r(x) may not exist with the stated properties. We'll assume the polynomials in the Division Algorithm for Polynomials are real.
- 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 are some extra propositions that are interesting. They should not be used in proving propositions from the book.
- 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.
(I proved this in class.)
- Proposition 6.A. 1 is odd.
In class I gave a proof using the Division Algorithm for integers (Theorem 6.13), to show how powerful the Division Algorithm is.
I claim there's another proof (simpler). Can you find it?
- Proposition 6.B. Suppose n ∈ N. If c ∈ Z and 0 < c < n, then c is not divisible by n.
Main class page | Schedule and homework | Announcements | Term Project | Syllabus
- In class we proved Proposition 8.45½. If u is an upper bound for A, and u' > u, then u' is also an upper bound for A.
We don't have this proposition officially so you should not use it in proofs. The purpose is to help you visualize the set of all upper bounds.
- On pages 80, line 4 up, and 81, line 1, Proposition 8.32(ii) should be 8.32(iii).
- 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.
- 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).
- Example 9.5: See Section 5.4 for the definition of the graph of f.
- 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 xk+1 > xk 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 (xk) is an increasing sequence, then i < j implies xi ≤ xj.
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)2 and u2" is not u2 − (u−h)2, it is |u2 − (u−h)2|. Thus, to prove the distance is < δ, they ought to prove u2 − (u−h)2 > 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)2 < u2. (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)2 < u2.
- 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".
- 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? I showed a proof in class, using Proposition 13.6, and gave the idea of a different proof using a bijection N → Z.)
Main class page | Schedule and homework | Announcements | Term Project | Syllabus