Probability - Exercise 21 in Chapter 1

Two players take turns removing a ball from a jar that initially contains $m$ white and $n$ black balls. The first player to remove white ball wins. Develop a recursive formula that allows the convenient computation of the probability that the starting player wins.

Solution

Let $p(m,k)$ indicates the winning probability when there is $m$ white balls and $k$ black balls.

Let event $A = $ the starting player wins at the first move and $B=$ the starting player lost the first move but its opponent is doomed to lose. Let $C$ = the starting player will win when there is $m$ white balls and $k$ black balls.

Then, $P(C) = P(A) + P(B)$. Let $p(m,k)$ indicate the winning probability when there are $m$ white balls and $k$ black balls. We have

$P(A) = \frac{m}{m+k}$, $P(B) = \frac{k}{m+k} \times (1-p(m,k-1))$, $p(m,k) = \frac{m}{m+k} + \frac{k}{m+k} \times (1 - p(m,k-1))$.

The initial statement is $p(m,0) = 1$.

Tips about Probability Problems 2(a), 9, 10

2.a Show that $A^C = (A^C \cap B) \cup (A^C \cap B^C)$.

Observe that

$(A^C \cap B) \cup (A^C \cap B^C) = ( (A^C \cap B) \cup (A^C) ) \cap ((A^C \cap B) \cup B^C)$

and

$( (A^C \cap B) \cup A^C ) = A^C$, $(A^C \cap B) \cup B^C = A^C \cup B^C$.

Therefore, $(A^C \cap B) \cup (A^C \cap B^C) = A^C \cap (A^C \cup B^C) = A^C$.

9. (a) The key point is noticing the sets $A \cup S_i$ are disjoint, therefore, the additive axiom is applicable.

(b) $P(A) = P(A \cap B \cap C) + P(A \cap B \cap C^C) + P(A \cap B^C \cap C) + P(A \cap B^C \cap C^C)$ and using $P(A \cap B) = P(A \cap B \cap C^C) + P(A \cap B \cap C)$, $P(A \cap C) = P(A \cap B \cap C) + P(A \cap B^C \cap C)$.

10.

$P((A \cap B^C) \cup (A^C \cap B) ) = P(A) + P(B) - 2P(A \cap B)$ is a equation that compute either event $A$ or event $B$ happen, but not both. Comparing to $P(A \cup B) = P(A) + P(B) - P(A \cap B)$, the latter formula gives a way for computing "at least one event in $A$ and $B$ happens".

A tips about inequality

If $a \leq x \leq y \leq b$ and $a = b$ then $x = y = a = b$.

A tip about series.

A series $\sum a_n$ can be seen as a sequence, where $s_n = \sum_{k=T}^n a_k $, $T \in \mathbb{T}$. If $(a_n) > 0$, it's an increasing sequence, if $(a_n) \leq 0$, it's a decreasing sequence.

Exercise 15.8 A sketch of the proof

Suppose $f(x)$ is defined on $[M, +\infty)$ decreasingly and $f(x) \geq 0$. For each $n \in \mathbb{N}$, we have $f(n) = a_n$. We are going to prove that $\int_M^{+\infty} f(x)$ and $\sum a_n$ converge or diverge jointly.

Proof.

Observe that $f(x)$ is a decreasing function. For $x \geq n$, $f(x) \leq f(n)$ and for $x \leq n$, $f(x) \geq f(n)$. Consider two intervals, namely, $[n-1,n]$ and $[n+1, n]$ where $n-1 \geq M$. 

Then, $\int_{n-1}^n f(x) dx \geq \int_{n-1}^{n} f(n) dx \geq \int_{n}^{n+1} f(x)dx$.

Because $\int_{n-1}^{n} f(n) dx = n - (n-1) f(n) = f(n)$, therefore $\int_{n-1}^{n} f(x)dx \geq f(n) \geq \int_{n}^{n+1} f(x)dx$.

Hence, we have

$\sum_{n=M+1}^{+\infty} \int_{n-1}^{n} f(x)dx \geq \sum_{n=M+1}^{+\infty} f(n) \geq \sum_{n=M+1}^{+\infty} \int_{n}^{n+1}f(x)dx$

$\int_{M}^{+\infty} f(x)dx \geq \sum_{n=M+1}^{+\infty} f(n) \geq \int_{M+1}^{+\infty} f(x)dx$.

$\int_{M}^{+\infty} f(x) dx + \int_{M}^{M+1} f(M)dx ( = f(M) ) \geq \sum_{n=M}^{+\infty} f(n) \geq \int_{M}^{+\infty} f(x)dx$.

and finally we got

$\int_{M}^{+\infty} f(x)dx + f(M) \geq \sum_{n=M}^{+\infty} f(n) \geq \int_M^{+\infty}f(x)dx$.

By the squeeze theorem, obviously $f(x)$ and $(a_n)$ diverge or converge jointly.

Exercise 13.14

I just solved this problem without using any deeper knowledge in topology. I guess you saw this problem from Prof. Ross's book, "Elementary Analysis: The Theory of Calculus", 2nd Edition.

Here's the proof, but somehow I feel there's a pitfall about the $S(x)$ without reason. So if anyone could help making it more strict I would very appreciate. I think the procedure of the proof is somehow obscure. so please I'll explain the "idea" behind that following proof here. The idea is, we decomposite the set $D$ as a union of sets in which one point $x \in E$ is fixed, and the other point $y$ is taken from $E$. We try to prove that at least one of these sets having the same supremum as the $\sup D$, then we can build a sequence of points $(x_n) \in E$ so that $(x_n)$ converges to a point $x_0 \in \mathbb{R}^n$. Since $E$ is compact, it's closed and bounded and contains every limit of the convergent sequence whose elements are in $E$, then we are done.

Notation:

$d(x,y)$ means the distance function.

$(s_n)$ means a sequence.

Proof:

If $D$ is a finite set, it's trivial that there exists $x,y \in E$ such that $d(x,y) = \sup D = \max D$. Let's consider the condition where $D$ is an infinite set. From the definition of $D$ we can tell that

$D = \cup_{x \in E} S(x)$

where $S(x)$ is a "function" of $x \in E$, defined as:

$S(x) = \{d(x,y): y \in E\}$

Since $S(x) \subseteq D$ for all $x \in E$, $\sup S(x) \leq \sup D$ and there is at least one $x_0 \in E$ such that $\sup S(x_0) = \sup D$. [1]

If that $S(x_0)$ is finite, because $x_0 \in E$, $\sup S(x_0) = \max S(x_0) = \sup D$ and $S(x_0) = \{ d(x_0, y) : y \in E \}$, we have $x_0, y \in E$ such that $d(x_0,y) = \sup D$.

If $S(x_0)$ is infinite, then $S(x_0)$ is bounded, because $\inf S_0 \geq 0$ and $\sup S_0 = \sup D$. Hence, there exists a monotonic sequence $(d_n)$ converging to $\sup S_0 = \sup D$. [2]

Let $(p_n)$ be a sequence that $(p_n \in E : d(x_0, p_n) = d_n)$. As $d_n$ converges to $\sup S_0 = \sup D$, $(p_n)$ converges to a point $p_0$. [3] Since $(p_n) \in E$, $E$ is compact (so it's closed), then $E$ contains all limts of the sequences whose elements are in $E$. Therefore, we proved that there exists $x_0, p_0 \in E$ such that $d(x_0, p_0) = \sup D$.

Some Details

[1] Otherwise, for every $x \in E$, $\sup \{d(x,y) : y\in E\} \neq \sup{D}$ and $D = \{d(x,y) : x,y \in E \} $ we reach a contradiction.

[2] See Prof. Ross's book, Page 72 Bolzano-Weierstrass Theorem and Theorem 10.2.

[3] Since $(d_n)$ converges to $\sup D$, for any $\sigma > 0$, there exists a $N$ such that $n > N \implies |d_n - \sup D| < \sigma$, i.e. $\sup D - \sigma < d_n < \sup D + \sigma$. Because $d_n = d(p_n, x_0)$, and only $x_0, p_n \in S(x_0)$, there is a $p_0 \in \mathbb{R}^n$ such that $d(x_0, p_0) = \sup D$ and $d(x_0, p_n) + d(p_n,p_0) = d(x_0, p_0)$. Then, because $d(p_n,p_0) = d(x_0, p_0) - d(x_0, p_n) = \sup D - d_n$, so for any $\sigma_1 > 0$, there exists $N_1 \in \mathbb{N}$ such that $n > N_1 \implies |\sup D - d_n| = |d(p_n,p_0)| = d(p_n,p_0) < \sigma_1$, hence $(p_n)$ converges to $p_0$.

Prove that the interior of the set of rational numbers is empty set.

We'll prove that the interior $\mathbb{Q}^{\circ}$ of the set of rational numbers $\mathbb{Q}$ is an empty set.

If $q \in \mathbb{Q}^{\circ}$, then there exists $r_q > 0$ s.t. $\{y: |q - y| < r_q\} \subset \mathbb{Q}$. Therefore, $ q - r_q < y < q + r_q$. If we can prove that, between any two real numbers $a,b \in \mathbb{R}:  0 < a < b$, there must exist an irrational number, then we are done. By the symmetry we can easily prove the proposition under condition $a < b < 0$.

Because $q + \sqrt{2}$ is not an rational number (otherwise \sqrt{2} would be an rational number, which is obviously a wrong proposition), therefore $q + \frac{\sqrt{2}}{n}, n \in \mathbb{N}$ is an irrational number.

We will prove that, pick up an rational number $q \in (a,b)$ [1] , there is an proper $n$ s.t. $a < q + \frac{\sqrt{2}}{n} < b$. Because $a < q$ and $\frac{\sqrt{2}}{n} > 0$, hence $ q + \frac{\sqrt{2}}{n} > a$. Thus, the only requirement for us is proving that there is an $n \in \mathbb{N}$ s.t. $q + \frac{\sqrt{2}}{n} < b$. Transform this inequality we got the requirement for $n$:

$n > \frac{\sqrt{2}}{b-p}$

According to the Archimedean property, for any $a,b > 0$, there must an $n \in \mathbb{N}$ such that $na > b$. Hence, we can always find a $n \in \mathbb{N}$ s.t. $ 0 < a < q + \frac{\sqrt{2}}{n} < b$. Therefore, for any two $a,b \in \mathbb{R}$ and $a,b > 0$, there must be an irrational number $i \in (a,b)$. Hence, if $q \in \mathbb{Q}^{\circ}$, then there exists $r_q > 0$ s.t. $\{y: |q - y| < r_q\} \subset \mathbb{Q}$. Therefore, $ q - r_q < y < q + r_q$. However, we know that between $q - r_q$ and $q + r_q$ there is always an irrational number $i$, $i \in \{y: |q - y| < r_q\} \subset \mathbb{Q}$ but since $i$ is an irrational number, $i \notin \mathbb{Q}$. We reach a contradicition. Therefore, $\mathbb{Q}^{\circ} = \emptyset$.


[1]: By the Denseness of $\mathbb{Q}$, there is always an rational number $q$ between two different real numbers.

Prove the closure of $\{\frac{1}{n}, n \in \mathbb{N}\}$ is $\{ \frac{1}{n}, n \in \mathbb{N}\} \cup \{0\}$. Exercise 13.9 (a).

Notations:

 1. $A^C$ means the complement of $A$, i.e. $A \cup A^C = U$. In
    general, $U = \mathbb{R}$ unless there is a specific explanation.
 
 2. $(s_n)$ means a sequence. For example, $(\frac{1}{n})$ means the
        sequence $(1, 1/2,1/3, 1/4, 1/5, 1/6,...)$, i.e. $s_n = \frac{1}{n}$
        where $n \in \mathbb{N}$.

Proof:

Let $A = \{\frac{1}{n}: n \in \mathbb{N}\} \cup \{0\}$. For proving $A$ is a closed set, it equals to prove $A^C$ is an open set. Observing that the sequence $s_n = \frac{1}{n}$ ($n \in \mathbb{N}$) forming a strictly decreasing sequence, hence, we could construct a bunches of sets such that for set $S_n$: $\sup{S_n}=s_n=\frac{1}{n}$ and $\inf S_n = s_{n+1} = \frac{1}{n+1}$, $\sup S_n \notin S_n$ and $\inf S_n \notin S_n$, then no element from the sequence $s_n$ would be in the sets $S_n$.

Therefore, $A^C = \cup_{n=1}^{+\infty} (s_{n+1},s_n) \cup (-\infty,0) $.

Because the union of ***any*** collection of open sets is an open set, clearly, each $S_n$ is an open set and $(-\infty,0)$ is an open set. Therefore $A^C$ is open [1] (Contrastively, the *intersection* of ***finitely*** many open sets is an open set). Since $A = \mathbb{R} - A^C$ and $A^C$ is an open set, we proved that $A$ is a closed set by the definition of closed set.

Reference:

[1] Elementary Analysis: The Theory of Calculus, 2nd Edition. Kenneth A. Ross. Page 87, discussion 13.7, Springer, 2013.

Exercise 13.7

The problem is very abstract so it may be a bit confusing when one starts trying to solve it. Here is my solution.

Proof: Let consider an open set $U \subset \mathbb{R}$. Notice that, $U$ may be a union of infinite open sets, which is also an open set. Now, let consider $A = (U \cap \mathbb{Q})$, i.e. $A$ is the set of all rational numbers in $U$. Let $a_n = \inf \{ a \in \mathbb{R} : (a, q_n] \subset U \}$ and $b_n = \sup \{ b \in \mathbb{R} : [q_n, b) \subset U   \}$ where $q_n \in A$. Then $\cup_{i=1}^{\infty} (a_n, b_n) = U$.
We will prove $(a_n, b_n) \cap (a_m, b_m) \neq \emptyset \implies (a_n, b_n) = (a_m, b_m)$ as follows.

Suppose $(a_n, b_n) \cap (a_m, b_m) \neq \emptyset$, Let $k \in (a_n, b_n) \cap (a_m, b_m)$. Because $k \in (a_n, b_n) \cap (a_m, b_m)$ and $ (a_n, b_n) \subset U$, $(a_m, b_m) \subset U$. By completeness axiom, $\inf \{ a \in \mathbb{R} : (a, k] \subset U \}$ is unique, therefore $a_n = a_m$. Analogously, $\sup \{ b \in \mathbb{R}: [k,b) \subset U \}$ is unique, therefore $b_n = b_m$ and we are done.

A bit more about the last sentence: $\{ a \in \mathbb{R} : (a, k] \subset U \} \subset \mathbb{R}$ is either bounded below or unbounded below. If it is bounded below, then by the completeness axiom, it has a unique infimum. Otherwise, its "infimum" is $-\infty$. Similarly, $\{ b \in \mathbb{R} : [k,b) \subset U \} \subset \mathbb{R}$ and it is either bounded above or unbounded above. If it's bounded above, then it has a unique supremum, otherwise, its "supremum" would be $+\infty$. No matter which condition we are on, the "supremum" and "infimum" are two unique numbers or $+\infty$ and $-\infty$, respectively. Therefore, $\sup \{ b \in \mathbb{R} : [k,b) \subset U \} $ is unique and so is the $\inf \{ a \in \mathbb{R} : (a, k] \subset U \}$.

13.6 (b) Solution

The solution is available here.

Exercise 12.12 and what I've learned from that

I got stuck on the Exercise 12.12 about 4 hours. A solution is on here.

In the hint of part (a), the author claimed that we can show $M > N$ implies ... but, why?

Because, if $\inf(s_n: n > N)$ and $N \rightarrow +\infty$, because $n > N$, therefore $n \rightarrow +\infty$. The idea is, we fixed a positive number $N > 0$, and for $M>N$ we have

$\sup \{\sigma_{n} : n > M \} \leq \frac{1}{M} (s_1 + s_2 + ... + s_N) + \sup \{s_n : n > N \} $.

then we implicitly proved that for every $N > 0$ we have a $M > N$ such that $\sup \{ \sigma_{n} : n > M \} \leq \frac{1}{M} (s_1 + s_2 + ... + s_N) + \sup \{ s_n : n > N \}$. Because, if $N \rightarrow +\infty$, then $M \rightarrow +\infty$, hence $\lim \sup \sigma_{n} > \lim \sup s_n$. Uh, a kind of obscure so it may need sometime to figure out.

Inequality revisit and a substitution solution for Exercise 12.11

The inverse of the proposition $a > b$ is $a \leq b$, i.e. $a < b$ OR $a = b$. In other words, a relation $a > b$ is not true iif $a = b$ or $a < b$. Analogously, if we say $a < b$ is not true, then either $a = b$ or $a > b$.

Hence, we conclude if we want to prove $a \geq b$, we can prove that for any $b_1 < b$, we have $a \geq b_1$. This trick is useful for Exercise 12.11.

Besides, there's another substitution solution for Exercise 12.11 based on the definition of $\lim \inf (s_n)$.

Suppose $\lim \inf |s_n|^{\frac{1}{n}} = \alpha$ and $\lim \inf | \frac{s_{n+1}}{s_n} | = \beta$, by the same arithematic procedure we conclude that $|s_n|^{\frac{1}{n}} \geq c^{\frac{1}{n}} \beta$ for a constant $c, c>0$. Because $\lim \inf |s_n|^{\frac{1}{n}}$ is the limit of sequences $(u_t)$ where $u_1 = \inf {|s_n|^\frac{1}{n}}$ for $n > N_1$, etc. and $\inf (s_n)$ is the largest lower bound of a sequence $(s_n)$, we conclude that $(u_t) \geq c^{\frac{1}{n}} \beta$ for all $t$ and by Exercise 9.9(c) we got $\lim (u_t) = \lim \inf |s_t|^{\frac{1}{t}} \geq \beta$.

Books and learning path

Books and learning path. These following books are NOT listed in learning order.

Math:

1. Elementary Analysis by Ross ( Marked with Analysis(Ross) )
2. Linear Algebra by Lang (Marked with Linear Algebra)
3. The principle of mathematical analysis by Rudin
4. Real and Complex Analysis by Rudin
5. Functional Analysis by Rudin
* 6. Algebra by Artin
* 7. Algebra by Lang (GTM 211)
8. Introduction to Probability

*: One from two, or maybe both.

Research Topic:

1. The Elements of Statistical Learning
2. Convex Optimization
3. Deep Learning
4. Probabilistic Graphical Model
5. Speech and Natural Language Processing
6. Artificial Intelligence: A Modern Approach
7. Reinforcement Learning
8. Machine Learning A Probability Perspective
9. Pattern Recognition and Machine Learning
10. Manifold Learning Theory and Applications
11. Information Geometry Theory and Applications

Others:

1. Statistical Mechanics by Landau

Some tips about $\lim \inf s_n$, $\lim \sup s_n$ and subsequences

According to its definition, we know $\lim \sup s_n$ means

$\lim \sup s_n = \sup\{s_n : n > N\}$ when $N \rightarrow +\infty$

To me, this definition, at the first glance, is wired and caused some difficulties to understand it. Here is the understanding I finally got.

For any given $N$, $\sup \{s_n : n > N\} \geq t$ and  for all $\epsilon > 0$, there exits a $N_1$ s.t. $\sup \{s_n : n > N_1\} < t + \epsilon$. Because $\lim \sup s_n$ is defined by the limit of sequence $(u_n)$ where $u_k = \sup {s_n : n > N_k}$ and $(N_k)$ is a strictly increasing sequence, i.e. $n < m \implies N_n < N_m$. Exercise 12.1 would improve the understanding of $\lim \sup s_n$ and $\lim \inf s_n$.

Besides, $\{s_n: s_n < \lim \sup \{s_n\} \}$ could be an empty set.

Recall the sequence $s_n = 1/n$, $\lim s_n = 0$, therefore $\lim \sup s_n = \lim \inf s_n = \lim s_n = 0$ and all $s_n > 0$. See page 61, $\lim \sup s_n$ is the largest value that infinitely many $s_n$'s can approach to.

Extra tip

If $(s_{n_k})$ is a subsequence of $(s_n)$, we have

$\{s_{n_k}: k > N\} \subseteq \{s_n : n > N\}$ 

and therefore

$\lim \inf s_n \leq \lim \inf s_{n_k}$ and $\lim \sup s_{n_k} \leq \lim \sup s_n$

See page 74. Besides, $n_k \geq k$ because when $k=1$, $n_1 \geq 1$ and $n_{k} > n_{k-1}$.

Exercise 11.8

$\lim \inf s_n = - \lim \sup (-s_n)$

Exercise 12.4 and Exercise 12.5

If $(t_n)$ and $(s_n)$ are bounded sequences, then

$\lim \inf s_n + \lim \inf t_n \leq \lim \inf (s_n + t_n) \leq \lim \sup (s_n + t_n) \leq \lim \sup s_n + \lim \sup t_n$

Exercise 12.6

Let $(s_n)$ be a bounded sequence, and let $k$ be a nonnegative real number.

1. $\lim \sup (ks_n) = k \cdot \lim \sup s_n$.

2. $\lim \inf (ks_n) = k \lim \inf (s_n)$.

If $k < 0$, then $k \lim \sup s_n = \lim \inf (ks_n) $ and $\lim \sup (ks_n) = k \lim \inf (s_n)$

A conclusion used in Exercise 12.9 but not directly given by the text

$ \inf \{s_n : n \in \mathbb{N}\} \leq \lim \inf s_n \leq \lim \sup s_n \leq \sup \{ s_n: n \in \mathbb{N} \}$

Def. of $\lim \sup s_n$ and $\lim \inf s_n$ on Page 60

If $(s_n)$ is not bounded above, $\lim \sup (s_n) = + \infty$. If $(s_n)$ is not bounded below, $\lim \inf (s_n) = - \infty$.

Combining Theorem 11.8 and the first paragraph of section 12, we can conclude that, for any sequence $(s_n)$, $\lim \inf s_n$ and $\lim \sup s_n$ always make sense, regardless of whether $\lim (s_n)$ exists or not.

3.5 Note

Let $v,u$ be elements of $V$. The line segment between $v$ and $v+u$ is the set of all points

$v+tu$, $t \in [0,1]$.

If $v,w$ are elements of $V$, the line segment between $v$ and $w$ is

$t_1v + t_2w$, subject to $t_1, t_2 \geq 0$ and $t_1 + t_2 = 1$.

The parallelogram spanned by $v,w$ is

$t_1 v + t_2 w$, $0 \leq t_i \leq 1$ for $i=1,2$]

The triangle spanned by $O,v,w$ is

$t_1 v + t_2 w$, $0 \leq t_i$ and $t_1 + t_2 \leq 1$.

or

$t_1v_1 + t_2v_2 + t_3v_3$, $t_i \geq 0$ for $i=1,2,3$ and $t_1 + t_2 +t_3 = 1$

where $v = v_1 - v_3$ and $w = v_2 - v_3$

Corollary from Exercise 6

Let $L: V \rightarrow W$ be a linear map. Let $S'$ be a convex set in $W$. Let $S$ be the set of all elements $P$ in $V$ s.t. $L(P)$ is in $S'$, then $S$ is convex.

A brief summary of some basic but important properties about linear map and vector space.

 A linear map is a map $F: V \rightarrow U$ that satisfies those following properties:

1. $F(cA) = cF(A)$

2. $F(A+B) = F(A) + F(B)$.

In the above equations, $A,B \in V$. $V$ is called the domain of the linear map $F$ and $U$ is called the image of $L$.

$F$ is said to be injective if for $u,v \in V$, we have $F(u) = F(v)$ iff $u = v$. If $F$ is injective, then $\ker F = \{O\}$ and vice versa.

$F$ is said to be surjective if, for any $u \in U$, we have at least one element $v \in V$ s.t. $F(v) = u$.

If $F$ is both injective and surjective, then $F$ is bijective and has an inverse map $F^{-1}$ which is a linear map too.

If a linear map $F$ maps a vector space $V$ to itself, i.e. $F: V \rightarrow V$, then $F$ is called an operator sometime.

If a linear map $F: V \rightarrow U$ has an inverse map $F^{-1}: U \rightarrow V$, then we say $F$ is an isomorphism.

$\text{Im} F \subseteq U$, $\ker F \subseteq V$. If $\ker F = V$, then $F$ is a zero mapping.

Specially, if $F: V \rightarrow V$ and $\ker F = \{O\}$, then $F$ is invertible, i.e. $F$ is isomorphism. Because $\dim V = \dim \text{im}F + \dim \ker F$, since $\ker F = 0$, $\dim V = \dim \text{im} F$. Therefore, $V = \text{im}F$ and $F$ is surjective. Because $\ker F = \{O\}$, $F$ is injective, thus $F$ has an inverse linear map.

Useful corollaries in exercises of Chapter 3 Section 5

10. Let $V$ be a vector space. Let $P: V \rightarrow V$ be a linear map s.t. $P^2 = P$. Then

$V = \ker P + \text{im} P$ and $\ker P \cap \text{im}P = \{O\}$.

Check Chapter 1 Section 4 Theorem 4.1 for more details about the direct sum.

Two vector spaces $V$ and $U$ are isomorphic if there exists a bijective linear map s.t. $F: V \rightarrow U$.

Some important facts about composition of linear maps.

Suppose we have three linear mapping $F,G,H$ s.t. $F: V \rightarrow U$ and $G: U \rightarrow W$ and $H: W \rightarrow Z$.

We have

$F \circ ( G \circ H) $ = $ (F \circ G) \circ H$, i.e. the associative law. This property is on the textbook (Serge Lang, Linear Algebra 3rd edition) page 47

and

$F \circ (G + H ) = F \circ G + F \circ H$, i.e. the distributive law. See page 67 for more details.

However, the commutative law does not apply in general. In some special cases, it is applicable, though. For example, $F \circ F = F \circ F = F^2$.

Problems withheld due to lacking of prerequisite knowledge.

Linear Algebra:

Exercise 7, 8 in Chapter 3 Section 3.

Analysis:

Probability:

Differential Equations:

A specific solution to Exercise 1 in Serge Lang Linear Algebra, Chapter 3 Section 3.

The answer given by the solution manual is somehow vague, therefore I wrote down my answer there for future reviewing.

Exercise 1. Let $A, B$ be two vectors in $\mathbb{R}^2$ forming a basis of $\mathbb{R}^2$. Let $F: \mathbb{R}^2 \rightarrow \mathbb{R}^n$ be a linear map. Show that either $F(A), F(B)$ are linearly independent, or the image of $F$ has dimension 1, or the image of $F$ is $\{O\}$.

Solution:

Because $\dim V = \dim \ker F + \dim \text{im} F$, $\dim V = 2$.

1. If $F(A)$ and $F(B)$ are linearly independent, then $F(A)$ and $F(B)$ forming a basis of $\text{im} F$. The $\text{im}F = 2$ and $\ker F = 0$.

2. If $F(A)$ and $F(B)$ are linearly dependent, i.e. $F(A) = k_1 F(B)$. then $t_1 F(A) + t_2 F(B) = t_1 k_1 F(B) + F(B) = (t_2 + t_1 k_1) F(B)$.

2-1. If $t_1F(A) + t_2F(B) = O$, then $(t_2 + t_1 k_1) F(B) = O$.  Because $t_1 F(A) + t_2 F(B) = F(t_1 A + t_2 B)$ and $A,B$ are a basis of $\mathbb{R}^2$, therefore for all $ v \in \mathbb{R}^2$, $F(v) = O$, that is, $\text{im}F = 0$, i.e. $\ker F = 2$.

2-2. If $t_1F(A) + t_2F(B) \neq O$, then $(t_2 + t_1 k_1)F(B) \neq O$. Because $t_1 F(A) + t_2 F(B) = F(t_1 A + t_2 B) = (t_2 + t_1 k_1)F(B) \neq O$, therefore $F(B)$ is a basis of $\text{im}F$. That is, $\dim \text{im}F = 1$ and $\dim \ker F = 1$.

An interesting corollary about a line under the linear mapping.

Suppose we have a linear mapping $F: V \rightarrow U$. By simple geometry knowledge, we know that for two points $x,y \in V$, the segment between points $x,y$ are

$x+(1-t)y$, where $t \in [0,1]$.

Because $F$ is a linear mapping, we have $F(x + (1-t)y) = F(x) + F( (1-t)y ) = F(x) + (1-t)F(y)$, where $t \in [0,1]$.

If $y \in V$ lying in the $\ker F$, i.e. $F(y) = O$, then $F(x + (1-t)y) = F(x)$. Therefore, the image of the segment $x + (1-t)y$ in $V$ under the linear mapping $F$ in $U$ is a point $F(x)$.

Otherwise, we have two different points $F(x), F(y) \in U$.

The following part needs verifying once more.

We'll prove that if $x,y \notin \ker F$, then $F(x) = F(y)$ iff $x=y$ as follows.

Suppose we have $x,y \in V$ and $x \neq y$, $x,y \notin \ker F$ and $F(x) = F(y)$, we have

$F(x) - F(y) = O$. Because $F$ is a linear mapping, we got $F(x)-F(y) = F(x) + -F(y) = F(x) + F(-y) = F(x-y)$. However, because $F(x) = F(y)$ in our assumption, we have $O = F(x-y)$. Because $x,y \notin \ker F$ and $x-y \in \ker F$, we have $x-y = O$, i.e. $x=y$. Hence, we reached an contradiction, showing that if $x,y \notin \ker F$ and $F(x) = F(y)$, then $x=y$. Q.E.D.

Intuitively, $x \in V$ is a linear combination of the basis of $V$ and $y \in V$ is a linear combination of the basis of $V$. If $F(x) = F(y)$, we got $F(t_1 v_1 + t_2 v_2 + ... + t_n v_n ) = F(k_1 v_1 + k_2 v_2 + k_3 v_3 + ... + k_n v_n)$ and $F( (t_1 - k_1)v_1 + (t_2 - k_2)v_2 + ... (t_n - k_n) v_n) = O$. Because $v_1, v_2, ..., v_n$ are the basis, and $x,y \notin \ker F$, the linear combination of $x,y$ are not in $\ker F$, and therefore we have $t_i = k_i$ for $i = 1,...,n$ thus $x=y$.

A common trick for proving $\text{Im} F = C$ where $C$ is a geometric shape's analytic equation.

From Linear Algebra, Serge Lang 3rd Ed. Chapter 3 Section 1.

Suppose we have a linear mapping $F = V \rightarrow W$, and suppose we have a coordinate $(u,v) \in V$. After mapping, it became $(x,y) \in W$ and satisfy an equation $E:F(x,y) = 0$.
We want to prove that: (1) $\text{Im}F \subseteq E$ and $E \subseteq \text{Im} F$ so that we can conclude $E = \text{Im}F$.
Here's the trick. We firstly pick up an arbitrary coordinate $(u,v)$ from $V$, and follow the mapping $F$ so that we can get an coordinate after mapping, say $(x,y)$, and that $(x,y)$ satisfies an equation $E:F(x,y) = 0$. This proved $\text{Im} F \subseteq E$, i.e. the image of $F$ is some points satisfies the equation $E$.

Secondly, we pick up an arbitrary coordinate $(x,y)$ from the equation $E$, and find out a coordinate $(u,v)$ in V so that $F(u,v)=(x,y)$. This proved that each point on that equation, $E$, is an element of the $\text{Im}F$, i.e. every point satisfies $E$ is an element of $\text{Im}F$. Eventually we got $E \subseteq \text{Im}F$.

Because $E \subseteq \text{Im}F$ and $\text{Im}F \subseteq E$, we conclude that $E = \text{Im}F$.

Example (Exercise 12 from the Chapter 3 Section 1):

Let $F$ be the mapping defined by $F(x,y) = (x/3,y/4)$. (Errata: in the printing version I have, there's a typo stating $F(x,y) = (x/3, x/4)$ rather than $(x/3,y/4$).) What is the image under $F$ of the ellipse

$\frac{x^2}{9} + \frac{y^2}{16} = 1$?

We'll solve this problem by the procedure mentioned above.

1. We pick up an arbitrary coordinate $(u,v)$ in $V$, where $V$ is the ellipse $\frac{x^2}{9} + \frac{y^2}{16} = 1$ and substitute it into the mapping $F$, we got $F(u,v) = (u/3, v/4)$. Let $(x,y) = (u/3,v/4)$ (Notice here, $(x,y) \in W$, where $W$ is the image of $F$. ) Then $3x=u$ and $4y=v$. Because $\frac{u^2}{9} + \frac{v^2}{16} = 1$, we have $\frac{(3x)^2}{9} + \frac{(4y)^2}{16} = 1$. After using some arithmetic tricks, we found $x^2 + y^2 = 1$, that is a unit circle and we proved $\text{Im}F \subseteq E$, where $E$ is the equation of the unit circle $x^2 + y^2 = 1$.

2. In the second step, our aim is proving $E \subseteq \text{Im}F$. We pick an arbitrary coordinate from $E$ satisfying $x^2 + y^2 = 1$, say, $(x,y)$. Then, we need to find out a coordinate $(u,v) \in V$ s.t. $F(u,v) = (x,y)$.  Take an arbitrary coordinate $(u,v)$ that may belong or not belong to $V$, we have $F(u,v) = (u/3, v/4) = (x,y)$. Therefore, $x = u/3$ and $y = v/4$. Substitute $(x,y) = (u/3,v/4)$ into the unit circle equation, we have

$x^2 + y^2 = \frac{u^2}{9} + \frac{v^2}{16} = 1$

This proved that $(u,v) \in V$ (recall that $V$ is the ellipse equation) and every point on the unit circle $x^2 + y^2 = 1$ is in $\text{Im}F$. Therefore we got $E \subseteq \text{Im} F$. Thus, $\text{Im} F = E$ Q.E.D.

Addtional Tips:

1. Because for any $v \in V$ we proved that there is at least a image of $F$ at $v$ in $V$, namely, $F(v)$, so we implicitly proved that $F$ is surjective.

2. However, we didn't implicitly prove that $F$ is injective, because we didn't show that there is only an unique $v \in V$ s.t. $F(v)=w$ .