# Lecture Notes

PHIL 402

## Table of contents

- Week 1 Wednesday: A Fancier Version of Long Division
- Week 1 Friday: Division
- Week 2 Monday: Fundamental Theorem of Arithmetic
- Weed 2 Wednesday: Congruence Classes
- Week 2 Friday: Arithmetic Over Congruence Classes
- Week 3 Monday: The Structure of \(\mathbb{Z}_p\)
- Week 4 Monday: Rings
- Week 4 Wednesday: More on Rings
- Week 4 Friday: Even More on Rings
- Week 5 Monday: Ismorphisms and Homomorphisms
- Week 6 Monday – Polynomial Rings
- Week 6 Wednesday – Polynomial Rings
- Week 6 Friday – Factorization, Polynomials
- Week 8 Monday – Congruence Class Polynomial Rings

## Week 1 Wednesday: A Fancier Version of Long Division

- Division Algorithm / Theorem: given integers \(a, b\), with \(b > 0\), there exist unique integers \(q, r\) such that \(a = bq + r\) and \(0 \leq r < b\)
- Rings where the division theorem holds – Euclidean rings
- \(\mathbb{Z}\) is a Euclidean ring

Non-constructive Existence Proof

- Consider the set \(S\) which is all things you can write in the form \(a - bx\), where \(x \in \mathbb{Z}\) and \(a - bx \ge 0\)
- \(S\) is a non-empty set of non-negative integers
- Use the well-ordering principle (every non-empty set of non-negative integers has a least element) to conclude that \(S\) has a least element, call it \(r\)
- \(r\) by definition is non-negative.
- Show \(r < b\)
- Uniqueness (show by contradiction)

- You can have sets of real numbers which do not follow the well-ordering principle

## Week 1 Friday: Division

- Three equivalent conditions of the GCD of \(a,b\)
- Greatest in the usual ordering of \(a\) and \(b\)
- Maximal (by divisibility) divisor of \(a, b\)
- integral linear combination of \(a, b\) (Theorem 1.2) – it is the smallest positive integral linear combination
- Any integral combination is not necessarily the GCD; if you know it is the smallest positive one, then you know it is the GCD

- A divisor: the numerator is the central player rather than the denominator
- 0 is not a divisor of anything / you can’t divide by 0
- \(GCD(a, b)\) is often written as \((a, b)\)
- Ideals are represents in parentheses and GCDs are the ideal generated by \(a\) and \(b\)

## Week 2 Monday: Fundamental Theorem of Arithmetic

- Main landmark theorem of arithmetic: Fundamental Theorem of Arithmetic (unique factorization): every nonzero integer is either a unit or can be written as a product of primes of prime integers uniquely
- Uniquely: up to reordering and plus/minus

- A unit (in the integers): something such that there exists some other integer where their product is 1. In the integers, these are \(\pm 1\)
- The set of integers you can get from the multiples of \(n\) are the same as \(-n\); they behave very similarly in general.
- You cannot tell the difference between \(n\) and \(-n\) with divisibility relationships
**Theorem 1.5.**Let \(n\) be a nonzero integer which is not a unit. Then \(n\) is prime iff (if \(n \nmid b\) and \(n \nmid c\), then \(n \nmid bc\)).- The only divisors of \(n\) are the units and itself. (weaker)
- The modern algebra definition is more general / stronger.
- Rewrite as \(n \vert bc \implies n \vert b \text{ or } n \vert c\)

- In 2.1: congruence classes are sets (infinite subsets of the numbers)

## Weed 2 Wednesday: Congruence Classes

- Given some integer \(a\), the congruence class \([a]\) is the set of all integers congruent to \(a\) modulo \(n\)
- Given \(a, c \in \mathbb{Z}\), TFAE

\(c \in [ a]\) \(c \equiv_n a\) \(n \vert a-c\) \([ a] = [ c]\) \(a, c \text{ have the same remainder when divided by } n\) \(a \in [ c]\) \([ a] \cap [ c] \neq \emptyset\)

- Corollary 2.4: no. 4 and no. 7 are equivalent
- Equivalence classes form a partition of any set.
- Congruence is an equivalence class.
- Given any \(a \in \mathbb{Z}, \exists 0 \le r < n\) s.t. \([a] = [r]\)
- Theorem 2: you can substitute with representatives. If \(a \equiv_n b\) and \(c \equiv_n d\), then \(a + c \equiv_n b + d\)
- If you want to do addition or multiplication, you can do whatever representative you want in your class.

## Week 2 Friday: Arithmetic Over Congruence Classes

- Arithmetic across congruence classes looks a lot lot arithmetic over the naturals.
- How do you define addition across two congruence classes? You could just add every element across the set: e.g. \(S + T = \{s + t \vert s \in S, t \in T\}\), and the same for multiplication: \(ST = \{st \vert s \in S, t \in T\}\)
- Or you could union
- Consider the set 0 \(Z\), the set of units \(U\), and the set of everything else \(R\)
- \(Z * Z = Z\).
- \(Z * U = Z\).
- \(Z * R = Z\).
- \(U * R = R\).
- \(U * U = U\).
- \(R * R =\) natural numbers without the primes.
- \(U + U = \{ 0, -2, 2 \}\).
- You can define set addition / multiplication, but it’s poorly behaved

- Congruence classes behave well under addition and multiplication – which is a miracle, that you can define addition and multiplication on sets. You can define arithmetic on them.
- For all \(a \in \mathbb{Z}\), \([a] = [0] + a\) (translation). Different elements in the equivalence class must be shifted over.

## Week 3 Monday: The Structure of \(\mathbb{Z}_p\)

- Brackets vs. no brackets (default, but only when working in \(\mathbb{Z}_p\))
- No-brackets is a label representing the congruence class
- Zero divisor: a non-zero number / class such that multiplying it by an existing number/class gives zero.
- Existence of zero divisors: things can behave very weirdly; no zero divisors in the integers, rationals, reals, etc.
- One example of zero divisors in linear algebra: \(AB = 0\), but \(A \neq 0\) and \(B \neq 0\)
- Let \(a \in \mathbb{Z}_n\) be such that \(a^2 = 1 \iff a^2 -1 = 0 \iff (a - 1)(a + 1) = 0\)
- When you have zero divisors, it doesn’t mean that either \((a-1)\) or \((a+1)\) equal zero.
- e.g. in \(\mathbb{Z}_{15}\) we get \(a \in \{ -1, 1, -4, 4 \}\)

- Polynomials over systems with zero divisors are very different from polynomials over systems without zero divisors.

## Week 4 Monday: Rings

- A ring: mathematical set / object where you can add & multiply with the usual conventions
- You need associativity and distributivity under addition and multiplication
- Commutativity requried fo addition but not nec for multiplication
- But lots of other systems do not have multiplicative commutativity, yet we want rings to include for instance matrices

- A lot of mathematical structures fall under the context of ring theory, and we can save work by studying them all together
- The ring must contain an additive identity and inverses
- A lot of systems have multiplicative identities
- You can bootstrap basically all claims about associativity and distributivity from the fact that \(+, \times\) in \(\mathbb{C}\) and \(M_N(C)\) satisfy associativity and distributivity
- Additive identities are unique
- When in a table:
- Additive inverses – “Sudoku” rule, no repeats in rows or columns
- Commutativity is checkable by symmetry across the diagonal

Hierarchy of rings

- Commutative rings (polynomial rings)
- No zero divisor rings
- Integral domains – commutative and no zero divisors (integers)
- Fields – no zero divisors, commutative, and every nonzero element has a multiplicative inverse
- Division ring – no zero divisors, and every nonzero element is a unit

## Week 4 Wednesday: More on Rings

- Ring: a set with \(\plus\) and \(\times\) and associativity, distributivity, additive identity, and additive inverses
- Suppose you have a subset. Is it a subring? What is inherited?
- You need to check closure of addition and multiplication still holds.
- Associativity and distributivity come for free
- Need to check additive identity and inverses still hold

- Addition in rings are surjective because of additive identity
- You have to check closure under multiplication, but Theorem 3.6 shows that closed under addition, closed under additvie inverses, and containing zero is equivalent to checking closed under subtraction (assuming set is nonempty)
- Multiplication is generalizable to non-integer rings due to distributivity across multiplication
- For non-commutative rings, divisors don’t have to go both ways
- Units and zero divisors need to be commutative
- Multiplicative inverses of units need to be equal
- Every finite integral domain is a field (Theorem 3.9). Being able to cancel implies multiplication by \(a\) is injective
- For finite sets, injection implies surjection, implying every element has a multiplicative inverse, which is the condition for a field
- e.g. the integral domain of integrals is not a field.

## Week 4 Friday: Even More on Rings

- Properties of matrices as linear transformations between real-valued spaces: \(T(v + w) = T(v) + T(w)\), \(T(cv) = cT(v)\)
- You often want maps to respect linear transformation structures.
- It helps to understand a ring \(R\) in relation to other rings
- We want to study maps which respect the ring structure.
- A ring is a set with multiplication/multiplication such that associativity, distributivity, additive commutativity, and additive inverses exist
- Map \(R \times R\) via \(\phi \times \phi\) to \(S \times S\), so \(R \times R \to_{\phi \times \phi} S \times S \to_{+} S\), and \(R \times R \to_{+} R \to_{\phi} S\)
- Ring homomorphism: mapping \(\phi: R \to S\) which satisfies \(\phi(a) + \phi(b) = \phi(a + b)\) and \(\phi(a)\phi(b) = \phi(ab)\), where \(a, b \in R\)
- We get additive commutativity and additive inverses for free

- Homomorphisms preserve the ring structure
- Isomorphism: a bijective homomorphism
- Generating sets

## Week 5 Monday: Ismorphisms and Homomorphisms

- \(R\) and \(S\) are isomorphic, or really the same
- If \(R\) and \(S\) are homomorphic… what does it mean?
- Homomorphisms do not go both ways
- \(R\) and \(S\) have pieces which are isomorphic

- Corollary 3.11: if \(\phi: R \to S\) is an injective homomorphism, \(R\) is isomorphic to the image of \(\phi\), which is a subring of \(S\)
- Given any two rings, you can always define a homomorphism which sends every element to \(0_S\). This satisfies the requirements for a homomorphism.
- Homomorphisms can lose a lot of information.
- Given two rings \(R\) and \(S\), can you determine if thye are isomorphic? This is a very difficult problem because you need to construct a map / guess a map
- No guaranteed way to show that two rings are not isomorphic

- Common rings can often be distinguished by isometric invariants, or properties presented under isomorphism
- \(R\) and \(S\) need to have the same cardinality
- Units must be preserved, cardinality of set of units needs to be preserved
- Commutativity preserved
- \(0_R \iff 0_S\) must be preserved
- \(-a_R \iff -\phi(a_S)\) must be preserved
- Rings with identity are preserved
- Integral domain – no zero divisors, so if \(ab = 0_R\), then \(a = 0_R\) or \(b = 0_R\).
- Zero divisors
- Cardinality of nipotents
- Cardinality of idempotents
- Characteristic of a ring
- Fields

- Almost anything you can define in terms of ring properties is going to be preserved by isomorphism, because it has to obey the ring structure

## Week 6 Monday – Polynomial Rings

- If your ring has zero divisors, then the sum/product of two polynomial rings can have a smaller degree than either.

## Week 6 Wednesday – Polynomial Rings

- Different interesting properties of systems:
- Does unique factorizatio nhold? Then the ring is a unique factorization domain. If a ring is a UFD, then if you take the polynomials over that ring, then the polynomial ring is also a unique factorization domain
- Does there exist a notion of GCD, where \(d = a \cdot x + b \cdot y\) for some \(x, y \in S\)? Theorem – this holds iff a ring is a principal ideal domain
- Does there exist an application of the division algorithm and a degree / complexity function? Then the ring is a Euclidean domain.
- Euclidean domain implies principal ideal domain implies unique factorization domain
- Unique factorization and irreducibility imply each other

- Polynomials over the integers are not PIDs.
- Other Euclidean domains: \(\mathbb{Z}[i] \subseteq \mathbb{C}\)

## Week 6 Friday – Factorization, Polynomials

- Standard interpretation in algebra II: roots are the intersection of \(y = 0\) with \(y = f(x)\) in \(\mathbb{R}^2\)
- In 402, \(x\) is not a variable, but an indeterminate, a placeholder to keep things sseparate
- Factor theorem: being a root is the same as \((x - a) \vert f(x)\)

## Week 8 Monday – Congruence Class Polynomial Rings

- Why is 5.7/5.8 interesting? – ring of polynomial congruence classes include the original field. The map from polynomial ring to congruence classes is not injective, so it’s interesting that you can have an isomorphic map overall