alexanderknop/i2dm

The lecture notes for my discrete mathematics classes.

i2dm's Issues

chapter 2 typo

On page 9, the last paragraph, it should be "divides" rather than "devises"

3.2 Changing the Base Case errors

In section 3.2 "Changing the Base Case" there is an error that occurs twice. The textbook states 2k^2 + 8k + 32 = 2(k+4)^2 when this should in fact be 2k^2 + 16k + 32 = 2(k+4)^2

Page 101 Fixes

I focused on one page and included reasons for grammatical changes. There is context around the change to make it easy to search and replace.

Spelling:
"not that difficult but very technicall" -> "technical"
" if a propositional formula is a tautlogy" -> "tautology"
" Consider a tautlogy" -> "tautology"
"The proof of this tautology" -> "tautology"
"consider casess using" -> "cases"

Grammar:
"So the proof simply bruteforce all the values of the variables of a formula and check that the formula is indeed true" -> "brute-forces" and "checks"
Third-person singular noun "proof" needs pluralized verb

" First we derive A ∨ ¬ A and B ∨ ¬ B, we use these" -> "B, and we use these"
Independent clauses require ", and", ";", or "." (or any other cordinating conjunction)

"After that we consider" -> "After that, we consider"
"Thus we just need" -> "Thus, we just need"
"After that we consider" -> "After that, we consider"
" In this case the assumption" -> "In this case, the assumption"
Introductory phrases need a comma

"the case when A is true but and B is false" -> "A is true and B is false"
This is a compound subordinate clause, which makes things a little tricky. No comma is necessary even though "A is true" and "B is false" are complete sentences.

" is also false, thus the proof" -> "is also false; thus, the proof"
"Thus" is a conjunctive adverb, not a coordinating conjunction. Something else must be used to join the independent clauses, the semicolon in this case.

Cheers,
Bryan Hatton
Contact me if you need more identifying information, like student ID

typo found in list of symbols

explanation for (m)n is written as :denotes the number of ways to choose an subset of n
elements from a fixed set of n elements, page 75, but should be denotes the number of ways to choose an subset of n elements from a fixed set of m elements, page 75

exercise 11.9 Hint typo

should be number of ways to select k+1 elements

possible theorem 12.6 typo

n+k-1 choose n should be n+k-1 choose k-1

Notation page

Page before page 4.

The first one says... choose subset of n elements from fixed size of n. One of them should be a m.

11.2. Counting subsets.. what is K?

Page 80

Should the K be an N, or should the N be a K?

Typo/Mistake Suggestions

These are some suggestions I found in I2DM pdf:
(pg3) 1. The three statements about salmon to be written as three sentences, w/ a capital letter and a
period. ex) If a salmon has scales, it has fins.
(pg4) 2. consider explaining what iff means ex) if and only if(iff)
3. in exercise 1.1 - 1 the question asks "if n^2 is positive implies n is not equal to 0" while the
solution only reach the conclusion that "we prove that if n doesn't equal to 0, then n^2>0"
consider switching the order of the two parts in the question
4. exercise 1.1 -2 isn't answered while the solution to 1.1-1 is put under 1.1-2, consider moving it
before 1.1 -2
(pg5) 5. header(1.2.........) is visible on this page but not on other pages
6. the first P in sec 1.2 line 2, add by before starting----->"is to try to prove (by) starting...."
7. 2nd P in line 2. add a comma after For example(,)
8. bottom paragraph line 3----> By applying axiom 3 twice
(pg6)10. 1st line, "in this paragraph"? should it be "in this section" or "in the previous section"
11. the last line of the 1st paragraph, considering adding chapter numbers to show what "second
part of this book" is

William Hsu([email protected])

chapter 8 more explanation

On page 50, under Theorem 8.2, surjection and injection are used without defining them (the definition do not appear until page 52).

chapter 6 typos

On page 36, instead of four functions being all f1, I think it would be better to denote each function as f1 f2 f3 f4.

Typos

1. in part 11.1 the proof of Theorem 11.1, "ovbious" should be "obvious"
2. in the proof for the Binomial theorem in page 75, "Asume" should be "Assume"
3. in the last part of the proof for the binomial theorem, in the sum. shouldn't it be
   (n+1)+(n+1)
   ( k-1 ) ( k )
4. in exercise 11.3, shouldn't the summation start at i=0
5. in exercise 11.4,it should be "show" instead of "shwo"

Zhiqiang Pi ([email protected])

Exercise 12.1

The exercise appears to have a typo. What does the sum of l1 to lK equal?

Possible typos

1. in part 6.3 the definition of a graph, I believe the second property should be (x,y1) is in D and (x,y2) is in D. (Sorry I don't know LaTex)
2. in part 6.4 before definition 6.2, I think "f: X -> Y" might be better than "f: X to Y"
3. in definition 6.2 before theorem 6.2, I don't think the last sentence of the first bullet point in clear
4. on the bottom of page 51, in the set of the second last line, I think the brackets are off
5. in the proof of theorem 8.4 I think |Y| = n instead of m

Zhiqiang Pi ([email protected])

Chapter 6 more explanation

On page 33, is every element in Y being used? I know that every element in X has been assigned an element in Y.
On page 34, what does it mean "there are, however, less direct methods such as use of the counting arguments"?

Figure 5.1 "Euler Diagrams"

For part a) of the Euler Diagrams, you might have the circles flipped (if A is a subset of B, should circle A not be the smaller circle inside circle B?)

-Jason Vega
[email protected]

Possible typo

1. in exercise 4.4, I think "A==>B is the same as (A==>B)/(B==>A)" should be changed to "A<==>B is the same as (A==>B)/(B==>A)"

2. is the page ordering of Chapter 5 wrong?

Zhiqiang Pi ([email protected])

Spelling Fixes

Page 3 typo

(m)n "denotes the number of ways to choose "an" subset" should be "a" subset.

Some issues on Page 4 of I2DM.pdf

Note: This does not cover all of the issues on the 4th page of I2DM.pdf

Exercise 1.1:

"But in order to prove it we need to know something again, it is a problem!" --> "But in order to prove it , we need to know something again, which is a problem!"

Also, make the "it" more clear. Do you mean proving a "statement" in this case?

"But what it means to know something?" --> "But what does it mean to know something?"

"An axiom is a statement that believed to be true" --> "An axiom is a statement that is believed to be true"

Make sure to change all of your iff on the page to if. (unless if I am misunderstood)

Overall, you are on a good path to publishing a Discrete Mathematics textbook in the future. 👍

• Alex Guo (Username: aguo)

some typos and suggestions throughout the book

On page 29, the symbol after C is never introduced. (the one looks like [ ])
On page 40, it would be better to also include graph for B\A to denote the difference.
On the bottom of page 50, f is used without defining it. Also, "( f ◦ i) : A → X" should be "( f ◦ i) : A → Y"
On page 63, I am not sure why there are three functions: h, h’ and h’’. Aren’t h and h’ the same function?
On the top of page 67, there should be another “)” on for both generalized union and intersection of sets.
On the bottom of page 69, "finish" is misspelled "finitsh"
On page 70, under Corollary 9.2, "|Xi|" should be "|Ai|" Also, under theorem 9.3, "|X|" should be "X".
On page 74, under theorem 10.3, "Then for any function f : |X| → |Y|” should be "Then for any function f : X → Y”. Also, "|X| > |Y|" should be mentioned since not any function can be applied to pigeonhole principle. Also, the symbol "⌈ ⌉" is not introduced.
On page 75, under theorem 10.4, the symbol on the top of summation sign should be “m” for both since we are adding from 1 to m.
On the bottom of page 79, "First, let us try to do this informally. Assume that X = [n] ” should be "First, let us try to do this informally. Assume that X = |n|"
On the bottom of page 80, in the parentheses, it should be X and n instead of X and k.
Side Note: there is never a page number for the first page of all chapters.

Issue with Chapter 2 End of The Chapter Exercise 2.4

Line #91 Missing statement

Exercise 2.4 only lists the axioms, and is missing the statement(s) that need to be proven.

chapter 5 more explanation on notation [l]

On page 29, does [l] means all integers from 1 to l?
For the notation [ ], is there any constraint on its usage?

Chapter 4 more explanations

Hi, for 6 examples listed on page 23, could please state whether statements 3 and 4 are propositions, and whether 5 and 6 are true or false?

Typos

1. in exercise 11.5, shouldn't the summation start from 1?
2. in the list of symbols, "denotes the number of ways to choose a subset of n elements from a fixed set of n elements" should be "denotes the number of ways to choose a subset of n elements from a fixed set of m elements"
3. Suggestion, in the list of symbols, when explaining the multiplication sign, maybe use * rather than the dot.
4. in the Logical Notation part, for the first two statements, maybe be consistent on the use of alpha and a.
5. in the set notations, (B)A should be the number of injections from A to B instead of infunctions
6. in theorem 11.3, is the third theorem wrong since there is no m in the right-hand side?
7. in the practice final, the solution for question 5, in the last sentence, you misspelled "answer"

Zhiqiang Pi ([email protected])

Possibly the typo suggestion for lecture 3 notes

I think in line 73, the sentence "Let $P(n)$ be some statement about an integer $n$." Here might be "some statements" or " a statement" instead of "some statement".

Page 90 Issue

Corollary 12.1 states for all positive integers n and k, the number of compositions of n into k is equal to n choose k. The textbook notes that the number of compositions of n into k parts is (n-1) choose (k-1), which is in line with the statement that the number of compositions of n is equal to 2^{n-1}

Problem 2: Page 90 Definition 12.3, "If, in addition, all the numbers are positive, the sequence is called composition" should read "the sequence is called a composition"

Ch. 8 Typos and Suggestions

• Page 52. Proof of Theorem 8.1 "Let z∈Z; we need to find x∈X such that (g◦f)(x) = y" We actually need to find x∈X such that (g◦f)(x) = z.

• Page 53. Proof of Theorem 8.3 "Let us consider the inverse g^(−1) of g. Note that h=f◦g^(−1) is a bijection from [n] to [m]."

1. h=f◦g^(−1) is not a bijection from [n] to [m]. Rather, h=g^(−1)◦f is a bijection from [n] to [m].

2. We can only apply Theorem 8.1 here if g^(-1) is invertible. Although it may be clear to some, consider adding a clarification note that if g is invertible, then g^(-1) is also invertible (perhaps in addition to Theorem 8.2 text).

• Page 53. Corollary 8.1 "cardianlity" is a misspelling of "cardinality."

-Jason Vega ([email protected])

Few suggestions chapter_1_proofs.tex

Found a few places to consider changes in chapter_1_proofs.tex:

Line 27: should be “each of them is true”
Line 30: change “whether” to “when”
Line 68: change to “But what does it mean to know something?”
Line 70: may want to add “so” before “it”
Line 72: add “is” before “believed”
Line 160: add “a” before “statement”
Line 166: change “to” to “too”
Suggestion: The sentence beginning with “Add problem arising…” on line 165 is a little bit confusing.
Line 168: Change to “we are going to discuss one approach to this in the second part of this book.”

Found by Kartik Nighojkar

Chapter 12 Page 88: S(n, n-2)

Under definition 12.1: Let us find the value in a more complicated setting, we claim that S(n, n − 2) = (n2).
I believe the claim should be S(n, n − 1) = (n2) because this is the actual claim that is proved in the next sentence. Also because S(n, n − 2) = (n2) is not true.

chapter 5 typo

On page 31, 2^A should have the empty set

Chapter 12 Page 88

"We are going to study the question in all these modes. The Table ?? summarizes the results we are going to prove for the cases when all the boxes are not empty."

The name of the Table is shown as "??".

End of chapter exercises

For exercise 1.7 ("Prove that 0 divides an integer a iff a = 0"), is the question actually intending to ask us to prove that 0 is divisible by an integer a iff a does not equal 0?

Jason Vega ([email protected])

chapter 6 typos

On page 34 in the warning box, in the second paragraph, it should be ∃a∈ R a^2 < 0 and ∃a∈ R a^2 = 1 instead of only ∃a a^2 < 0 and ∃a a^2 = 1
In the third paragraph, there are four typos.

1. it should be ∃a∈Z a ≥1 instead of ∃a∈R a^2 ≥1
2. it should ask “Is a >= 1 for any integer a” instead of “Is a > 1 for any integer a”
3. it should be ∃a ∈ Z a ≥ 1 instead of ∃a ∈ Z z ≥ 1
4. the last Z( the set of all integers) is typed incorrectly.

On page 35, under Disproving statements of the form, it should be ∀a ∈ A ¬P (a)

Chapter 8 typos

On bottom of page 56, both "X(g(i)" loses a ")" at the end

Page 3 (List of Symbols) typo

for the definition of (m) sub n, you wrote "... choose an subset ...", which should say " ... chose a subset ..."

chapter 3 typos

On page 14, under induction step, it should be "we may prove that 2n ≥ n^2 for n ≥ 4" instead of "we may prove that 2n ≥ n^2 for n ≥ 5"
On page 18, under base cases, it should be "the value of the arithmetic formula xi is equal to vi " rather than "the value of the arithmetic formula xi is equal to v1"

chapter 5 typo

On page 29, under Listing elements, there should be comma between 2 and π. And there should not be a comma after ...

chapter 6 typos

On page 36, "ever" should be "every" in the warning box
On page 38, there should be "∈D" after (x,y2)
On page 40, I am a little confused why it is "(f ◦ i) : A → X" instead of "(f ◦ i) : A → Y".
On page 40, I am a little unsure about the first statement of Theorem 6.2. If f, g, h are defined as in the notes, then shouldn't it be "h◦(g◦f)=(h◦g)◦f" since composition is not communicative?

Issue with the list of symbols

I believe that in the descriptions of the notation for (m)n and m choose n it says "denotes the number of ways to choose an subset of n elements from a fixed set of n elements"

where it should say "a" subset. AND it should say "from a fixed set of m elements" for both of the first 2 counting symbols.

Thanks!
Haley Dahlberg (A13433190)

Typo question for the word 'intresting' should be 'interesting'

https://github.com/aaknop/I2DM/blob/7e8587299345022912c6368921fb1b653915cb76/parts/part_2/chapter_8_bijections.tex#L193

Spelling Errors in chapter_1_proofs.tex

Line 191: Alnalyzis of Simple Algorithms --> Analysis of Simple Algorithms

• Alex Guo ([email protected])

possible typo in corollary 12.1

n choose k should be n-1 choose k-1

issue with exercise 3.24

I don't think the statement is true for the base case when n = 2 as n! = 2 and 2^2 = 4

Zhiqiang Pi ([email protected])

chapter 5 typo page 31

On page 31, it should be A = {n ∈ N: 2^n <= n} is non-empty or A = {n ∈ N: 2^n > n} is empty

typos

1. "(a + b)^2 = (a + b) · (a + b) (by axiom 5)" in the proof in part 1.2: this should be by axiom 6.
2. later on in the proof in part 1.2: "by axiom 1, it is enough to show that (a + b) · (a + b) = a + 2ab + b2.": a should be also squared
3. in the same proof: "by axiom 3 applied twice, (a + b)·(a + b) = a ·(a + b) + b ·(a + b)..." this is not by axiom 3 only, but by both axioms 3 and 4

Zhiqiang Pi ([email protected])

Spelling error in I2DM.pdf

1. In the first sentence of section 3.4, "analyzing" is misspelled as "analasing".

Typos in lecture notes chapter3

1. in part 3.6 on page 17. "in other words, the value of the arythmetic formula xi is equal to v1 when x1 = v1, ..., xn = vn." I think arythmetic should be changed to arithmetic.
   Zhiqiang Pi (email: [email protected])

Some typos found in Ch8

Student name: Gary Peng
PID: A15103364
Date of submission: 04/11/2019
Note: corrected parts are bolded.

Ch8, p.63:
In the proof of theorem 8.1, the construction of h'': [n] -> [m-1] should say
h''(i) = h'(i) if h'(i) < h'(n+1)
= h'(i) - 1 otherwise

Then, in proving h'' as a bijection, the first bullet point:
...If h'(i1), h'(i2) < h'(n+1) or h'(i1), h'(i2) >= h'(n+1), then ...
...without loss of generality we may assume that h'(i1) < h'(n+1) < h'(i2)...

Ch8, p.64:
In the proof of Corollary 8.1, the bijective function should map from
X to [n] instead of [n]->X because g1(Y)={ f(x): x E Y } has to be a subset of [n].

chapter 6 explanation

On page 39, I don't quite understand what it means for this sentence: "in other words.... Im f = { y : (x,y) belongs to d }"