Math notesfuyhgjnyihgjbnm PDF

Preview

Summary

yg5d7tuf8yuf6u...

Description

Math notes Econschool October 26, 2020

Contents 1 Logic 1.1 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 3

2

2 Sets 2.1 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4

3 Relations 3.1 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 6

4 Open and Closed sets 4.1 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7

5 Sequences and series 5.1 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 9 11

4

5

7

8

6 Proofs

12

7 Answers

16

1

Econschool

1

1

LOGIC

Logic

1.1

Notes

A set is a well-defined collection of unique objects. Some examples of sets are • N = {1, 2, 3, . . . }: the set of natural numbers • Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . . }: the set of all integers • Q: the set of all rational numbers • R: the set of of all real numbers

Suppose U is a set. Assertions that are true or false are called sentences. A proposition is a statement, possible involving variables, which may be true or false depending on the particular values of the variables. Propositions may be formed from simpler propositions using logical operations. Suppose P (x), Q(x) are propositions which may be true or false depending on x ∈ U . Then • NOT: ¬P is true if P is not true

• OR: P ∨ Q is true if at least one of P or Q is true • AND: P ∧ Q is true if both P and Q are true • IMPLIES: P =⇒ Q is true except when P is true and Q is false. • EQUIVALENT: P ⇐⇒ Q is true if P and Q take the same value

The following truth table describes these operations where a proposition is said to take value 1 if it is true and 0 if it is false. P

Q

0 0 1 1

0 1 0 1

P∨Q 0 1 1 1

P∧Q

P =⇒ Q

0 0 0 1

1 1 0 1

P ⇐⇒ Q 1 0 0 1

A tautology is a proposition that is always true. Propositions can also come with quantifiers. The two main quantifiers are: • Universal quantifier: the sentence ∀xP (x) is true if the proposition P (x) is true for all x ∈ U • Existential quantifier: the sentence ∃xP (x) is true if there is at least one value of x ∈ U that makes proposition P (x) true Propositions with quantifiers can also involve negations. The following equivalences will be useful in thinking about such propositions: • ¬∀xP (x): is true if it is not the case that P (x) is true for all x. That is, there exists x for which P (x) is not true. Symbolically, ∃x¬P (x). • ¬∃xQ(x): is true if it is not the case that there exists x for which Q(x) is true. That is, for all x, Q(x) is false. Symbolically, ∀x¬Q(x). A proposition may also involve multiple quantifiers.

• ∀x∀yP (x, y ) is true when P (x, y ) is true for all x and all y. • ∃x∃yP (x, y ) is true when there exists a pair (x, y ) for which P (x, y) is true. • ∀x∃yP (x, y) is true if for every x, there exists a y for which P (x, y) is true • ∃x∀yP (x, y ) is true if there exists an x such that for all y, P (x, y ) is true.

It helps to read propositions involving multiple quantifiers like ∀x∀yP (x, y) as ∀xQ(x) where Q(x) is the proposition ∀yP (x, y) and depends only on the variable x. 2

Econschool

1.2

1

LOGIC

Problems

Ex. 1.1 — Prove the following are tautologies: 1.(P ⇐⇒ Q) ⇐⇒ ((P =⇒ Q) ∧ (Q =⇒ P )) 2.(P =⇒ Q) ⇐⇒ (¬Q =⇒ ¬P )

Ex. 1.2 — Let U = N and suppose •P (x) is the proposition that x is prime

•Q(x) is the proposition that x + 1 is prime

•R(x) is the proposition that x + 7 is prime What can you say about the propositions: 1.∃x(P (x) ∧ Q(x)),

2.∀x(P (x) =⇒ ¬R(x))

3.∀x(¬R(x) =⇒ P (x)) Ex. 1.3 — Answer the following saying whether the propositions are True or False 1.∀x ∈ (0, 1), ∃y ∈ (0, 1), x < y

2.∃y ∈ (0, 1), ∀x ∈ (0, 1), x < y

3.∃y ∈ [0, 1], ∀x ∈ (0, 1), x < y

4.∃y ∈ {0, 1}, ∀x ∈ {0, 2}, x = 6 y

5.∀x ∈ {0, 2}, ∃y ∈ {0, 1, 2}, x = y

6.∃y ∈ {0, 1, 2}, ∀x ∈ {0, 2}, x = y

Here, (x, y) is the set of real numbers between x and y excluding x and y; [x, y] is the set of real numbers between x and y including x and y . Ex. 1.4 — Let U = {1, 2, . . . , 100}. Give a sentence P (n) depending on n ∈ U , such that P (1), P (2), · · · , P (99) are all true but P (100) is false. Ex. 1.5 — Show that ¬∀x(P (x) =⇒ Q(x)) and ∃x(P (x) ∧ ¬Q(x)) are equivalent. Ex. 1.6 — Suppose the domain of propositional function P (x, y) consists of x ∈ {1, 2, 3} and y ∈ {1, 2, 3}. Write the propositions i)∀x∀yP (x, y), ii)∀x∃yP (x, y), iii)∃x∀yP (x, y), iv)∃x∃yP (x, y) using ∧ and ∨ logical operations. Ex. 1.7 — Assuming x ∈ R, y ∈ R, evaluate the four propositions in problem 6 for the following cases: 1.P (x, y) : x + y = 0

2.P (x, y) : x ∗ y = 0

3.P (x, y) : x2 + y ≥ 25

4.P (x, y) : y 2 + x ≥ 25

Ex. 1.8 — Show that the ¬∀x∃y(xy = 1) can be expressed as ∃x∀y(xy 6= 1)

3

Econschool

2

2

SETS

Sets

2.1

Notes

A set A is a subset of B if ∀x, x ∈ A =⇒ x ∈ B. If we want to define a subset of U consisting only the elements that satisfy formula P (x), we can write it as {x ∈ U : P (x)}. For instance, the set of even numbers is given by {x ∈ N : ∃n such that x = 2n} and the set of non-negative real numbers is given by R+ = {x ∈ R : x ≥ 0}. Some useful set operations and definitions are: • Complement: AC = {x : x ∈ / A} • Union: A ∪ B = {x : x ∈ A or x ∈ B } • Intersect: A ∩ B = {x : x ∈ A and x ∈ B} • Difference: A \ B = {x : x ∈ A and x ∈ / B} • Symmetric difference: A∆B = {x : (x ∈ A and x ∈ / B) or (x ∈ B and x ∈ / A)} • Cartesian Product: A × B = {(x, y) : x ∈ A, y ∈ B} • Power set: P (A) contains all subsets of A • Cardinality: |A| represents the number of elements in the set If sets A, B have no elements in common, then they are said to be disjoint and we say that A ∩ B = φ where φ is the empty set. A collection of non-empty subsets of a set A such that they are disjoint and their union is A is called a partition of A.

2.2

Problems

Ex. 2.1 — Prove De Morgan’s laws 1.(A ∪ B)C = AC ∩ B C

2.(A ∩ B)C = AC ∪ B C

Ex. 2.2 — Which well-known set is this? {n ∈ N : (n > 1) ∧ (∀x, y ∈ N, ((xy = n) =⇒ (x = 1 ∨ y = 1)))} Ex. 2.3 — Prove the following: 1.(A∆Y = B∆Y ) ⇐⇒ (A = B) 2.(A∆B )∆C = A∆(B∆C ) Ex. 2.4 — Which of the below statements are correct? •A∆B = B =⇒ A ⊂ B

•A∆B = φ =⇒ A = B

•A∆B = A ∪ B =⇒ A ∩ B = φ Ex. 2.5 — Let An = {(n + 1)k : k ∈ N}. Then A1 ∩ A2 equals? Ex. 2.6 — Let An = {1, 2, . . . , n}. Let B1 = A1 and Bn+1 = An+1 ∆Bn for n ≥ 1. Then what is |B2k |? Ex. 2.7 — Let A and B be sets such that |A ∩ B| = m. Then what is |(A × B) ∩ (B × A)|? Ex. 2.8 — Suppose A, B, C are sets such that (A \ B)∆(B \ C) = A∆B. Which of the following must be true? a) A = C b) A ∩ B = B ∩ C c) A ∪ B = B ∪ C d) None 4

Econschool

3

3

RELATIONS

Relations

3.1

Notes

Any subset R of A × B is called a relation from the set A into the set B. Another way to write ordered pair (x, y) ∈ R is xRy. A relation R from A to A itself is called a binary relation in A and is a subset of A × A. The following are some important properties a binary relation R defined in A might have: • Reflexivity: ∀x ∈ A : xRx • Completeness: ∀x, y ∈ A : x 6= y ⇒ xRy or yRx • Transitivity: ∀x, y, z ∈ A : (xRy and yRz) ⇒ xRz • Symmetry: ∀x, y ∈ A : xRy ⇒ y Rx • Anti-symmetry: ∀x, y ∈ A : (xRy and yRx) ⇒ x = y • Asymmetry: ∀x, y ∈ A : xRy ⇒ ¬yRx • Negative transitivity: ∀x, y, z ∈ A : (¬xRy and ¬yRz) ⇒ ¬xRz The binary relation R is called: • a weak ordering if it is transitive and complete (TC) • a partial ordering if it reflexive, transitive, and antisymmetric (RTA) • a linear ordering if it is reflexive, transitive, antisymmetric and complete (RTAC) • an equivalence relation if it is reflexive, transitive and symmetric (RTS) The equivalence class of an element a ∈ A under the equivalence relation R is denoted by [a] = {x ∈ A : aRx} Note: An equivalence relation R partitions the set A into equivalence classes and for any partition of the set A, we can define a equivalence relation on the set A. Suppose  is a partial ordering on a set A and B ⊂ A. • An element a ∈ A is called an upper bound (lower bound) for B if a  b (b  a) for every b ∈ B. Let U (B) = {a ∈ A : a  b∀b ∈ B} denote the set of upper bounds of B and similarly L(B) denote the set of lower bounds. If U (B) 6= φ, the set B is bounded from above and if L(B) 6= φ, the set B is bounded from below. • If B ∩ U (B) 6= φ, then |B ∩ U (B)| = 1 and the element x ∈ B ∩ U (B) is called the maximum element of B denoted by max B. Similarly, x ∈ B ∩ L(B) is called the minimum element of B and is denoted by min B. • When min U(B) exists, it is called the least upper bound (or supremum) of B and is denoted by sup B. When max L(B) exists, it is called the greatest lower bound (or infimum) of B and is denoted by inf B. A relation R from A to B is called a function if for every a ∈ A, there is a unique b ∈ B such that aRb. Such a relation R is denoted by f : A → B and we write f (a) = b for aRb. For a function f : A → B, the set A is called the domain of the function and B is called the codomain of the function. Note that there might be elements in the codomain which f is never mapped to. A function f : A → B is called • injective (or one-to-one) if f (x) = f (y) =⇒ x = y • surjective (or onto) if ∀b ∈ B, ∃a ∈ A such that f (a) = b • bijective if it is both injective and surjective 5

Econschool

3

RELATIONS

If f : A → B is bijective, it is said to be invertible and it has an inverse function g : B → A which is defined by g(f (a)) = a for all a ∈ A. Returning to the notion of of cardinality of a set, we say that two sets A and B have the same size if there exists a bijection from A to B. A set A is said to be • finite if it is empty or if there exists a bijection from A to {1, 2, . . . , n} for some n ∈ N • Countably infinite if there exists a bijection from A to N. For example, the set of even natural numbers, integers, rational numbers are all countably infinite sets. • uncountable if there exists no injection from A to N. For example, the set real numbers, [0, 1] are uncountable sets. Sets which are finite or countably infinite are also said to be countable.

3.2

Problems

Ex. 3.1 — Suppose |A| = n. Find •number of relations on A

•number of reflexive relations on A

•number of symmetric relations on A

•number of complete and reflexive relations on A

•number of equivalence relations on A when n = 4

•number of functions from A to A

•number of functions from A to A which are not bijective

Ex. 3.2 — Check if the following relations on set of real numbers R satisfy reflexivity, transitivity, completeness and symmetry : •{(x, y) ∈ R × R : y ≤ x2 }

•{(x, y) ∈ R × R : xy 6= 0}

•{(x, y) ∈ R × R : x + y < 4}

•R+ × R+

Ex. 3.3 — Check if the following relations are a weak ordering, partial ordering, linear ordering or an equivalence relation. Note that a relation might satisfy more than one of these definitions. •xRy if |x| = |y| where x, y ∈ R •xRy if x ≤ y where x, y ∈ R •xRy if x < y where x, y ∈ R

•XRY if X ⊂ Y where X, Y ⊂ A

Ex. 3.4 — For each of the following functions with domain R+ , and co-domain R, check if it is injective, surjective or bijective? •f1 (x) = [2x] where [a] is the greatest integer less than or equal to a

•f2 (x) = x + 1

•f3 (x) = |x − 1| •f4 (x) = x2

•f5 (x) = max(x, x2 )

•f6 (x) = − min(x, x2 ) 6

Econschool

4

4 OPEN AND CLOSED SETS

Open and Closed sets

4.1

Notes

Let X be a nonempty set. A function d : X × X → R+ is a metric (distance function) if, for any x, y, and z in X, it satisfies the following three conditions: 1. (Properness) d(x, y) = 0 if and only if x = y , 2. (Symmetry) d(x, y) = d(y, x), and 3. (Triangle Inequality) d(x, y) ≤ d(x, z) + d(z, y). A nonempty set X equipped with a metric d constitutes a metric space (X, d). We will focus on the Euclidean Pn 1 2 2 space where X = Rn and the distance metric d(x, y) = for any x, y ∈ Rn . i=1 |xi − yi |

• For any x ∈ X and ǫ > 0, Nǫ (x) = {y ∈ X : d(x, y) < ǫ} is the ǫ-neighborhood of x. In the simplest case where X = R and d(x, y) = |x − y|, we get Nǫ (x) = (x − ǫ, x + ǫ).

• A set Y ⊆ X is open in X if for each y ∈ Y , there exists ǫ > 0 such that Nǫ (y) ⊆ Y . • A set Y ⊆ X is closed in X if X \ Y is open in X. • A set Y ⊆ X is bounded if there exists r > 0 such that for all x, y ∈ Y , d(x, y) < r . For any a, b ∈ R with a < b, the open interval (a, b) = {x ∈ R : a < x < b} is an open set and the closed interval [a, b] = {x ∈ R : a ≤ x ≤ b} is a closed set. Note that there exist sets which are neither open nor closed such as (0, 1] and sets which are both open and closed such as φ and R. Let (Yi )i∈A be a collection of sets such that Yi ⊂ Rn for all i ∈ A. Then, the union of the collection is given by ∪i∈A Yi = {x ∈ Rn : x ∈ Yi for some i ∈ A} and the intersection of the collection is given by ∩i∈A Yi = {x ∈ Rn : x ∈ Yi for all i ∈ A} Proposition 4.1. (Arbitrary union of open is open) Suppose (Yi ) ⊂ Rn is an open set for all i ∈ A. Then ∪i∈A Yi is open. Proposition 4.2. (Arbitrary intersection of closed is closed) Suppose (Yi ) ⊂ Rn is a closed set for all i ∈ A. Then ∩i∈A Yi is closed Proposition 4.3. (Finite intersection of open is open) Suppose (Yi ) ⊂ Rn is an open set for all i ∈ A. where A is finite. Then ∩i∈A Yi is open. Proposition 4.4. (Finite union of closed is closed) Suppose (Yi ) ⊂ Rn is a closed set for all i ∈ A. where A is finite. Then ∪i∈A Yi is closed. The following examples illustrate why finiteness of A is important in the last two propositions. Let Yi = (0, 1 + 1i ) for i ∈ N. Then ∩i∈N Yi = (0, 1] which is not open. Let Yi = [0, 1 − 1i ] for i ∈ N. Then ∪i∈N Yi = [0, 1) which is not closed.

4.2

Problems

Ex. 4.1 — Replace A by union or intersection and B be finite or infinite in the below propositions so that they are true. •The set (0, 1) can be expressed as A of B family of closed intervals. •The set [0, 1] can be expressed as A of B family of open intervals.

7

Econschool

5

5 SEQUENCES AND SERIES

Sequences and series

5.1

Sequences

Consider the set of real numbers R with the linear ordering of less than or equal to (≤) and d(x, y) = |x − y| for x, y ∈ R. Then, • A sequence of real numbers is a function x : N → R and is usually written as (xn ). • A sequence (xn ) converges to a limit x ∈ R if for any ǫ > 0, ∃M ∈ N such that |xn − x| < ǫ for all n ≥ M . In this case, we say the sequence converges or is convergent and we write xn → x or limn→∞ xn = x. If it does not converge, we say the sequence diverges. • A sequence (xn ) is bounded from above (below) if there exists a real number K with xn ≤ K (xn ≥ K ) for all n = 1, 2, . . .. It is said to be bounded if it is bounded from below and above. • A sequence (xn ) is said to be increasing (decreasing) if xn ≤ xn+1 (xn ≥ xn+1 ) for all n = 1, 2, . . .. It is said to be monotonic if it is increasing or decreasing. Using these definitions, we obtain the following results: Proposition 5.1. Let (xn ) be a convergent sequence. Then the sequence is bounded and the limit x is unique. Proposition 5.2. (Monotone convergence theorem) Every increasing (decreasing) real sequence that is bounded from above (below) converges. Proposition 5.3. (Limit laws) Let (xn ) and (yn ) be two real sequences such that xn → x and yn → y for some real numbers x and y. Then: 1. |xn | → |x| 2. xn + yn → x + y 3. cxn → cx 4. xn − yn → x − y 5. xn yn → xy 6.

xn yn

→

x , y

provided that y, yn 6= 0 for each n.

7. xn ≤ yn for all n =⇒ x ≤ y Proposition 5.4. (Squeeze Theorem): Let (xn ) and (yn ) and (zn ) be sequences in R and xn ≤ yn ≤ zn for all n. If lim xn = lim zn = a, then (yn ) converges to a. Proposition 5.5. Let (xn ) be a sequence in R. We define lim sup xn = lim sup{xn : n > N } N →∞

and lim inf xn = lim inf{xn : n > N } N →∞

Then, lim xn exists if and only if lim sup xn = lim inf xn . Proposition 5.6. Let (xn ) be a sequence such that xn > 0 for all n and lim xn → 0 and if λ > 1, xn → ∞1 . 1 This

means that the sequence diverges to ∞

8

xn+1 = λ. Then, if λ < 1, xn

Econschool

5 SEQUENCES AND SERIES

Proposition 5.7. If p(x) = an xn + an−1 xn−1 + . . . a0 with an 6= 0 and q(x) = bm xm + bm−1 xm−1 + . . . b0 p(n) is with bm 6= 0, then limn→∞ q(n) • 0 if n < m • ∞ or −∞ if n > m •

an if n = m bm

Proposition 5.8. Some special sequences and their convergence properties are as follows: • The power sequence xn = an converges if −1 < a ≤ 1 and diverges otherwise. • The exponent sequence xn = na converges if a ≤ 0 and diverges otherwise. 1

• The nth root sequence xn = an converges to 1 if a > 0. 1

• The sequence n n converges to 1. • The exponential sequence xn = (1 + na )n converges to ea . We considered convergence of sequences in R. We can similarly define convergence of sequences in Rm Pm 1 2 2 with the distance metric: d(x, y) = for any x, y ∈ Rm . i=1 |xi − yi | m A sequence (xn ) converges to a limit x ∈ R if for any ǫ > 0, ∃M ∈ N such that d(xn , x) < ǫ for all n ≥ M. The following result provides an equivalent definition of convergence in Rm . Proposition 5.9. Let (Rm , d) be the Euclidean metric space, and (xn ) a sequence in Rm . We have: xn → x ⇐⇒ xin → xi in R for each i = 1, 2, . . . , m Recall the definition of a closed set in the previous section: In the metric space (X, d) where X = Rm Pm 1 and d(x, y) = ( i=1 |xi − yi |2 ) 2 , a set Y ⊂ X is closed if X \ Y is open. The following result provides an equivalent definition of closed sets in terms of convergence of sequences: Proposition 5.10. A set Y ⊂ Rm is closed if and only if for all sequences (xn ), if xn ∈ Y for all n and xn → x, then x ∈ Y .

5.2

Series

• Given a sequence (xn ) of real numbers,

P∞

xi is called an infinite series. Pn • For any n, the nth partial sum of the series is defined by Sn = i=1 xi P∞ • If lim Sn exists and is finite, the infinite series i=1 xi is said to be convergent. Otherwise, the series is said to be divergent. P P • The series xn is said to converge absolut...