more math proofs | Chelsea Zou

Groups (G, *)

A group is a set \( G \) together with operation \( * \colon G \times G \to G \) (takes two elements and returns one) satisfying the following axioms:

1. Associativity:
\( (a * b) * c = a * (b * c) \quad \quad \forall a,b,c \in G\)

2. Identity:
\(\exists e \) such that \(a * e = a \quad \quad \forall a,e \in G) \)

3. Inverse:
\(\exists a^{-1}\) such that \( a * a^{-1} = e \quad \quad \forall a, a^{-1}, e \in G \)

**4. Commutative (Abelian Group):
\(a * b = b * a \quad \quad \forall a,b \in G\)

Fields (F, +, \( \cdot \))

A field is a set \( F \) with two operations
\( + \colon F \times F \to F \)
\( \cdot \colon F \times F \to F \)

1. \((F, +)\) is an abelian group:
\( a + b = b + a \), associativity, identity \(0\), and additive inverse \( -a \quad \forall a, b \in F \)

2. \((F \setminus \{0\}, \cdot)\) is an abelian group:
\( a \cdot b = b \cdot a \), associativity, identity \(1\), and multiplicative inverse \( a^{-1} \quad \forall a \neq 0 \)

3. Distributivity:
\( a \cdot (b + c) = a \cdot b + a \cdot c \quad \quad \forall a, b, c \in F \)

Vector Spaces (V)

A vector space over a field \( F \) is a set \( V \) equipped with:

• Closed under Addition \( + \colon V \times V \to V \), where \( u + v \in V \) for all \( u, v \in V \).
• Closed under Scalar multiplication \( \cdot \colon F \times V \to V \), where \( \lambda v \in V \) for each \( \lambda \in F \), \( v \in V \).

1. Commutativity:
\( u + v = v + u \quad \forall u, v \in V \)

2. Associativity:
\( (u + v) + w = u + (v + w) \quad \forall u, v, w \in V \)
\( (ab)v = a(bv) \quad \forall a, b \in F, \, v \in V \)

3. Additive Identity:
\( \exists 0 \in V \) such that \( v + 0 = v \quad \forall v \in V \)

4. Additive Inverse:
\( \forall v \in V, \, \exists w \in V \) such that \( v + w = 0 \)

5. Multiplicative Identity:
\( 1v = v \quad \forall v \in V \)

6. Distributivity:
\( a(u + v) = au + av \quad \forall a \in F, \, u, v \in V \)
\( (a + b)v = av + bv \quad \forall a, b \in F, \, v \in V \)

Subspaces (\(U \subseteq V\))

A subspace \( U \) of a vector space \( V \) (over a field \( F \)) is a non-empty subset of \( V \) that is itself a vector space under the same operations.

• Contains the zero vector   \( 0 \in U \).
• Closed under Addition   \( u_1 + u_2 \in U \quad \forall\, u_1,u_2 \in U \).
• Closed under Scalar Multiplication   \( \lambda u \in U \quad \forall\, \lambda \in F,\; u \in U \).

1. Non-emptiness (Zero Vector):
\( 0 \in U \Longrightarrow U \neq \varnothing \)

2. Additive Closure:
\( u + v \in U \quad \forall\, u,v \in U \)

3. Scalar Closure:
\( \alpha u \in U \quad \forall\, \alpha \in F,\; u \in U \)

Dimensionality of a Subspace

The dimension of a subspace \( U \) is the number of vectors in any basis of \( U \).

• Basis of \(U\)   A set \( \{u_1,\dots,u_k\} \subset U \) is a basis if it is linearly independent and spans \( U \). Then \( \dim U = k \).
• Sum of Subspaces   For subspaces \( U, W \subseteq V \):
    \( \dim(U + W) = \dim U + \dim W - \dim(U \cap W) \).

Linear Maps \( T: U \to V \)

Let \( U \) and \( V \) be vector spaces, and let \( T \in L(U, V) \) be a linear map from \( U \) to \( V \).

1. Pick a basis for \( U \): (think of it like building blocks for a space U)
\[ \{ u_1, u_2, \dots, u_n \} \]

2. Write any vector \( x \in U \) as a linear combination of the basis: (build a new vector x using those building blocks)
\[ x = a_1 u_1 + a_2 u_2 + \dots + a_n u_n \]

3. Apply the linear map \( T \) to the vector \( x \): (feed this vector x into some machine T)
\[ T(x) = T(a_1 u_1 + \dots + a_n u_n) = a_1 T(u_1) + \dots + a_n T(u_n) \]

4. Each \( T(u_i) \in V \): (the transformed building blocks are now part of a new space V)

So you can write any vector \(x \in U\) as ( T(x) \) which is a linear combination of vectors in \( V \)

The kernel of \( T \):

The kernel of \( T \), denoted \( \text{Ker}(T) \), is the set of all vectors in \( U \) that map to the zero vector in \( V \): \[ \text{Ker}(T) = \{ x \in U \mid T(x) = 0 \} \] Then \( x \in \text{Ker}(T) \) if: \[ T(x) = a_1 T(u_1) + a_2 T(u_2) + \dots + a_n T(u_n) = 0 \] So the kernel is the set of all linear combinations of \( u_i \) that are destroyed (sent to zero) by \( T \).

3. Important facts:
• \( \text{Ker}(T) \) is always a subspace of \( U \).
• If \( \text{Ker}(T) = \{0\} \), then \( T \) is called injective (one-to-one).
• The dimension of the kernel is called the nullity of \( T \).

The range of \( T \):

The range (or image) of \( T \) is the set of all vectors in \( V \) that are outputs of \( T \): \[ \text{Range}(T) = \{ T(x) \mid x \in U \} \] \[ \text{Range}(T) = \text{span} \{ T(u_1), T(u_2), \dots, T(u_n) \} \subseteq V \]

• \( \text{Range}(T) \) is always a subspace of \( V \).
• If \( \text{Range}(T) = V \), then \( T \) is called surjective (onto).

Injective (one to one)

- Different inputs must produce different outputs (ex: x^2 is not injective because both -1 and 1 map to 1)
- If f(x) = f(y), then x = y

Surjective (onto)

- Every value in the output space (codomain) is hit

Modular Arithmetic

The set \( \mathbb{Z}/n\mathbb{Z} = \{0, 1, 2, \ldots , n-1\} \) where each element corresponds to the set of integers that when divided by n, has that remainder.
Think of each element in \( \mathbb{Z}/n\mathbb{Z} \) as being a "label" for some set of numbers:

For n = 3, we have \( \mathbb{Z}/3\mathbb{Z} = \{[0], [1], [2]\} \)
• \([0] = \{0,3,6,9, \ldots\}\)
• \([1] = \{1,4,7,10, \ldots\}\)
• \([2] = \{2,5,8,11, \ldots\}\)

Field Property:
If \( p \) is prime, then \( \mathbb{Z}/p\mathbb{Z} \) forms a field \( \mathbb{F} \): every nonzero element has a multiplicative inverse.

Proof by Induction

• Verify the base case \(n=1\).
• Assume the formula for \(n=k\) (inductive hypothesis).
• Show this assumption forces the formula for \(n=k+1\).
• Conclude the result holds for every integer \(n\ge1\).

We want to show for all integers \(n \ge 1\):

\[ 1 + 2 + \cdots + n \;=\;\frac{n(n+1)}2. \]

Base Case (\(n=1\)):
\[ 1 \;=\;\frac{1\cdot(1+1)}2 \;=\;1. \]

Inductive Step:
Assume for some \(k\ge1\): \[ 1 + 2 + \cdots + k \;=\;\frac{k(k+1)}2. \] Then \[ 1 + 2 + \cdots + k + (k+1) \;=\;\frac{k(k+1)}2 + (k+1) \;=\;(k+1)\Bigl(\tfrac{k}{2}+1\Bigr) \;=\;\frac{(k+1)(k+2)}2. \] Thus if it holds at \(k\), it holds at \(k+1\).

Conclusion:
By induction, the formula is true for all \(n\ge1\).

Proof by Contradiction

• Assume the opposite of the claim
• Reach a direct contradiction with the assumption
• Conclude the original claim must be true

Claim: There is no largest natural number.
1. Assume, for sake of contradiction, that there exists a largest natural number \(N\).

2. By definition of natural numbers, \(N + 1\) is also a natural number.
3. Notice then that \[ N + 1 \;>\; N, \] which contradicts our assumption that \(N\) was the largest.

4. Since the assumption leads to an impossibility, it must be false.

Conclusion:
Therefore, there is no largest natural number.