Skip to content

0x002 Number

1. N

One approach to consruct natural number from real number is to take intersection of all inductive subsets of \(\mathbb{R}\)

\[Z_{+} = \cap_{A \in \mathcal{A}} A\]

Theorem (well-ordering property) every nonempty subset of \(Z_{+}\) has a smallest element

1.1. Peano Axioms

1.2. Arithmetic Functions

Definition (Euler's totient) for \(n \in Z^+\) let \(\varphi(n)\) be the number of positive integers \(a \leq n\) with \(a\) relatively prime to \(n\) (e.g: \(\varphi(12)=4\) since 1,5,7,11 satisfies the condition).

In particular, \(\varphi(p) = p-1\) for primes, more generally, we have the formula

\[\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)\]

Additionally, it is multiplicative when \(gcd(a,b)=1\)

\[\varphi(a,b) = \varphi(a)\varphi(b)\]

This can be proved by the Chinese Remainder Theorem.

If \(n = p_1^{a_1}p_2^{a_2} ... p_s^{a_s}\), then

\[\varphi(n) = \prod_i \varphi(p_i^{a_i}) = n\prod_i (1-\frac{1}{p_i})\]

Theorem (Euler) If \(n,a\) are coprime, then

\[a^{\varphi(n)} = 1 \mod n\]

This is of course an entension of the Fermat Little Theorem, and this can be further generalized to the Carmichael's theorem

Proof from group theory is to consider the multiplicative group of integer module \(n\), whose order is \(\varphi(n)\). Suppose \(a, a^2, ..., a^k\) forms a subgroup then \(a^k \equiv 1\). Lagrange Theorem says \(k\) should divide \(\varphi(n)\), then

\[a^{\varphi(n)} \equiv a^{kM} \equiv 1\]

Definition (Möbius function) For any positive integer n, define \(μ(n)\) as the sum of the primitive nth roots of unity. It has values in \({−1, 0, 1}\) depending on the factorization of n into prime factors.

  • It is 0 if it has a square prime factor
  • Otherwise it is \((-1)^k\) where \(k\) is the number of prime factor

It is also a multiplicative function when arguments are coprime

\[\mu(m, n) = \mu(m)\mu(n)\]

If \(m,n\) are not coprime, \(\mu(m,n)=0\)

Proposition (Möbius inversion formula) the following two are equivalent

\[g(n) = \sum_{d | n}f(d)\]
\[f(n) = \sum_{d | n}g(d)\mu(n/d)\]

Intuitively, this is expanding the formula of inclusion-exclusion principle. \(g(n)\) is the count of all elements in the set of \(n\), \(f(n)\) contains the elements unique to the set of \(n\).

In combinatorics, \(g(n)\) is usually easy to compute while \(f(n)\) is diffcult, if the target is too compute \(f(n)\), we can use the inversion formula to compute \(f(n)\) with \(g(n)\).

easy case

Consider \(n=6\), we know

\[g(1) = f(1), g(2) = f(1) + f(2), g(3) = f(1) + f(3), g(6) = f(1) + f(2) + f(3) + f(6)\]

With a bit algebra, it is easy to show

\[g(6) = f(1) - f(2) - f(3) + f(6)\]

which follows the previous inversion formula

2. Z

Theorem (Division theorem) For any integer \(a\) and any positive integer \(n\), there exist unique integers \(q, r\) such that \(0 \leq r < n\) and

\[a = qn + r\]

Theorem (Fundamental Theorem of Arithmetic, unique factorization) There is exactly one way to write any composite integer \(a\) as a product of the form

\[a = p_1^{e_1} p_2^{e_2} ... p_r^{e_r}\]

where \(p_i\) are prime, \(p_1 < p_2 ... < p_r\) and \(e_i\) are positive integers.

3. Q

Proposition (cardinality) Q is countable

Proof Set \(A_1 = \{ 0 \}\) and \(A_n\) where \(n \geq 2\) be the set

\[A_{n} = \{ \pm \frac{p}{q} \text{ where } p,q \in N \text{ are in lowest terms with } p+q=n \}\]

Then all Q can be enumerated

4. R

The reason to move from rational numbers to real numbers is when we encounter a sequence that looks as if it is converging to something, say \(\sqrt{2}\), then we can be assured that there is indeed a number there we can call the limit.

Technically, \(\mathbf{R}\) can be obtained by completing \(\mathbf{Q}\) with an additional axiom as follows.

Axiom (completeness) Every nonempty set of real numbers that is bounded above has a least upper bound.

The definition of upper bound and least upper bound is given by

Definition (upper bound) A set \(A \subseteq \mathbf{R}\) is bounded above if there exists a number \(b \in \mathbf{R}\) such that \(\forall{a \in A} a \leq b\). The number \(b\) is called an upper bound of \(A\).

Definition (least upper bound) A real number \(s\) is the least upper bound for a set \(A \subseteq \mathbf{R}\), denoted by \(s = \sup(A)\), if it meets the following two criteria:

  • \(s\) is an upper bound for \(A\) (upper bound condition)
  • if \(b\) is any upper bound for \(A\), then \(s \leq b\) (least condition)

\(\sup\) is a more general concept of \(\max\), while \(\max(A)\) might not exist, \(\sup(A)\) should always exists for bounded nonempty set \(A\) because of the axiom of compeleteness. An important difference between sup and max is that \(\sup(A)\) may or may not be an element of \(A\), but \(\max(A)\) is an element of \(A\) if exists.

Lemma (N and R, Archimedian property) Given any number \(x \in \mathbb{R}\), there exists an \(n \in \mathbb{N}\) satisfying \(n > x\). Given any real number \(y > 0\), there exists an \(n \in \mathbb{N}\) satisfying \(1/n < y\)

Lemma (N and Q, density) For every two real numbers \(a,b\), there exists a rational number \(r\) satisfying \(a < r < b\).

Proposition (cardinality) R is uncountable

proof Suppose \(R\) is countable, then \(R\) can be enumerated by

\[\{ x_1, x_2, ..., \}\]

We prepare a list of intervals \(I_n\) such that \(I_{n+1} \subseteq I_n\) and \(x_{n+1} \notin I_n\)

Then we know

\(\cap_n I_n\) contains such real number (by the Nested Interval Theorem), which is against the previous assumption.

4.1. Statements of Completeness

There are several equivalent statements about completeness. One of them can derive all the others.

Theorem (Nested Interval Theorem) Let \(I_n = [a_n, b_n]\) be a sequence of closed intervals, and suppose that these intervals are nested in the sense that \(I_1 \supset I_2 \supset I_3\) and \(b_n-a_n \to 0\) when \(n \to \infty\), then the result interval has a nonempty intersection.

\[\cap_{n=1}^{\infty} I_n \neq \emptyset\]

Proof: \(a_n\) is bounded by \(b_1\), so take \(s = \sup(a_n)\) and then show \(s >= a_n\) and \(s <= b_n\)

Theorem (Bolzano Weierstrass) Every bounded sequence contains a convergent subsequence

Theorem (Cauchy completeness) Every Cauchy sequnece of real numbers converges

Theorem (monotone convergence) every nondecreasing, bounded sequence of real numbers converges

4.2. Topology in R

Theorem A subset of R is open iff it is the union of a disjoint sequence of open intervals

proof <= is easy, to show =>, let the target open subset be \(A\), the basic idea is to take 'largest' open interval contained in \(A\) at each point, then show the intervals are disjoint and contains at least one rational, then enumerating every Q leads to the proof.

Stack exchanges have many proofs for this.

Theorem Every open subset \(O \subset R\) can be written uniquely as a countable union of disjoint open intervals

proof see Stein's real analysis Theorem 1.3

5. C

6. Reference

[1] Hofstadter, Douglas R. Gödel, escher, bach: ein endloses geflochtenes band. Klett-Cotta, 2006.

[2] Tao, Terence. Analysis. Vol. 1. Hindustan Book Agency, 2006.

[3] David S. Dummit, Richard M. Foote: Abstract Algebra