My Journal

Professor: Thea Pignataro

Read Ross secs 13, 21 & 22.

Review linear algebra: Subspace, spanning set, linear independence, dimension, basis, kernel, range, std. basis, affine subspace.

Prof's notes on http://1drv.ms/1KlFihR, mirror: link1

Sec. 1.6

Def: a normed real vect. space. (Theorem 1.6.6)

Generalization of vector length

Inner product space (theorem 1.6.6 I)

Remark: Every inner product induces a norm, but not every norm can be represented as an inner product. Nor does every metric arises from a norm.

Sec. 1.7 Matrices, etc.

Def. 1. 7.1 A metric space.

Check example 1.7.2 (discrete methods), many set, d(x, y) = 0 if x=y and d(x,y) = 1 if x != y. Check that this is a metric.

Professor: Benjamin Steinberg

Syllabus

HW must be from 8th edition of textbook.

Set-builder notation.

Empty set is contained in all sets.

A = B, if

{a,b,c} = {a,a,b,b,c,c,c}

Theorems and Definitions of the text: (variables are generally assumed to be integers unless stated otherwise)

Chapter 1 Fundamentals

Section 1.1 Sets

Section 1.2 Mappings

Section 1.3 Properties of Composite Mappings (Optional)

Section 1.4 Binary Operations

Section 1.5 Permutations and Inverses

Section 1.6 Matrices

Section 1.7 Relations

Chapter 2 The Integers

Section 2.1 Postulates for the Integers (Optional)

Section 2.2 Mathematical Induction

Section 2.3 Divisibility

Section 2.4 Prime Factors and GCD

Definition 2.11 Greatest Common Divisor: gcd(a,b) = d
1. d > 0
2. d|a & d|b
3. c|a & c|b => c|d

Theorem 2.12 Greatest Common Divisor
A method to find gcd: Euclidean Algorithm

Definition 2.13 Relatively Prime Integers: gcd(a,b) = 1

Theorem 2.14 If gcd(a,b) = 1 & a|bc => a|c

Definition 2.15 Prime Integer (p)
1. p > 1
2. the only divisors of p: ± 1 and ±p

Theorem 2.16 Euclid's Lemma
prime p |ab,
=> either p|a or p|b

Corollary 2.17 prime p|

Theorem 2.18 Unique Factorization Theorem = Fundamental Theorem of Arithmetic
n > 0,
=> n=1 or ..., where are unique primes
Terms: = multiplicity of => standard form for ...

Definition 2.19 Least Common Multiple: lcm(a,b) = m where a, b != 0
1. m > 0
2. a|m & b|m
3. a|c & b|c => m|c

Theorem 2.20 Euclid's Theorem: The number of primes is infinite

Section 2.5 Congruence of Integers

Definition 2.21 Congruence modulo n
n > 1, x ≡ y (mod n)

Theorem 2.22 Congruence modulo n is an equivalence relation on Z.
Congruence classes = residue classes

Theorem 2.23 Addition and Multiplication Properties
a ≡ b (mod n),
=> a+x ≡ b+x (mod n) & ax ≡ bx (mod n)

Theorem 2.24 Substitution Properties
a ≡ b (mod n) & c ≡ d (mod n),
=> a+c ≡ b+d (mod n) & ac ≡ bd (mod n)

Theorem 2.25 Cancellation Law
gcd(a,n) = 1 & ax ≡ ay (mod n),
=> x ≡ y (mod n)

Theorem 2.26 Linear Congruences
gcd(a,n) = 1,
∃x =>ax = b (mod n)
=> (mod n)

Theorem 2.27 System of Congruences
gcd(m,n) = 1,
∃x => x ≡ a (mod m), x ≡ b (mod n),
=> (mod mn)

Theorem 2.28 Chinese Remainder Theorem
expands theorem 2.27

Section 2.6 Congruence Classes: = {[0],[1],...,[n-1]}

Theorem 2.29 Addition in : [a] + [b] = [a+b]
1. Associative & commutative in
2. [0] = additive identity
3. [-a] is additive inverse of [a], where [-a],[a]

Theorem 2.30 Multiplication in : [a][b] = [ab]
1. Associative & Commutative in
2. [1] = multiplicative identity
3. Theorem 2.31 [a] has multiplicative inverse in IFF gcd(a,n) = 1

Corollary 2.32 [a] in has multiplicative inverse IFF n is a prime

Section 2.7 Introduction to Coding Theory (Optional) - skipped

Section 2.8 Introduction to Cryptography (Optional)

Theorem 2.33 RSA Public Key Cryptosystem

Chapter 3 Groups

Section 3.1 Definition of Group

Definition 3.1 Group, G
1. G is Closed under *
2. * is associative
3. G has identity element e
4. all elements of G has inverses in G

Definition 3.2 Abelian Group (=Commutative group)

Definition 3.3 Finite, Infinite groups, Order of Group (|G|)

Section 3.2 Properties of Group Elements

Theorem 3.4 Properties of Group Elements
1. e in G is unique
2. All inverses of elements in G are in G and unique
3.
4. Reverse order law
5. ax = ay or xa = ya imples x = y: Cancellation law

Theorem 3.5 Equivalent Conditions for a Group
G is nonempty set, closed under associative multiplication.
G is a group IFF ax = b and ya = b s.t. x and y in G, for all a and b in G.

Definition 3.6 Product Notation
for

Theorem 3.7 Generalized Associative Law

Definition 3.8 Integral Exponents
Compare Multiplicative and Additive Notations

Theorem 3.9 Laws of Exponents
1.
2.
3.
4.
Can be translated to Laws of Multiples for additive groups.

Section 3.3 Subgroups

Definition 3.10
Theorem 3.11 Subgroup, H G is a subgroup IFF:
1.) identity e is in H (H is nonempty)
2.) H is closed under *
3.) , closed under inverse
Notation: is a subgroup of G

Theorem 3.12 Equivalent Set of Conditions for a Subgroup (Summarized Theorem 3.11)
H is subgroup of IFF:
1. H is nonempty (I think this can be ignored)
2. a, b in H implies

Definition 3.13 The center of a Group
Z(G) = {}
Meaning all g which commute with every element of G

Theorem 3.14 The center of a group G is an abelian subgroup of G

Definition 3.15 The Centralizer of a Group Element

Theorem 3.16 The centralizer of a in G is a subgroup of G

Definition 3.17 Cyclic Subgroup
For any a in group G, <a> = subgroup generated by a = = H = cyclic subgroup of G. The element a is called a generator of H.

Section 3.4 Cyclic Groups

Definition 3.18 Generator (repeated from last section)

Theorem 3.19 Infinite Cyclic Group
If whenever and <a> is an infinite cyclic group

Corollary 3.20 If G is a finite group, then for some positive integer n.

Theorem 3.21 Finite Cyclic Group
If m is the least positive integer s.t. a^m = e, then
1. <a> has order m
2. IFF (mod m)

Definition 3.22 Order of an Element: o(a) = |a| = |<a>|
Order of Subgroup of G generated by a in G

Corollary 3.23 Finite Order of an Element
If |a| is finite, then m = |a| is the least positive integer s.t.

Theorem 3.24 Subgroup of a Cyclic Group
If H is a subgroup of cyclic group G with generator a, then
, where k is the least positive integer s.t.

Corollary 3.25 Any subgroup of a cyclic group is cyclic

Theorem 3.26 Generators of Subgroups
Subgroup (generated by ) of cyclic group of order n generated by a = subgroup generated by , where d = gcd(m,n)

Corollary 3.27 Distinct Subgroups of a Finite Cyclic Group, G
where d is a positive divisor of n.

Theorem 3.28 Generators of a Finite Cyclic Group <a>:
is a generator of <a> of order n IFF gcd(m,n) = 1

Section 3.5 Isomorphisms

Definition 3.29 Isomorphism, Automorphism
is an isomorphism from G to G' if:
1. is a bijection from G to G'
2.
Notation
Automorphism: An isomorphism from G to G

Theorem 3.30 Images of Identities and Inverses
1. and
2.

Section 3.6 Homomorphisms

Definition 3.31 Groups G, & G'',, Homomorphism: s.t. or

1. Endomorphism: G = G'
2. Epimorphism: is onto, G' is homomorphic image of G.
3. Monomorphism: is one-to-one

Theorem 3.32 Images of Identities and Inverses ()
1.
2.

Definition 3.33 Kernel: ker
is a homomorphism from group G to G'

Chapter 4 More on Groups

Section 4.1 Finite Permutation Groups

Definition 4.1 Cycle

This statement is not unique.
Disjoint subsets which define cycles, are called orbits

Theorem 4.2 Partition of A

Definition 4.3 Orbit
Let , the orbit of
The orbits form a partition of {1,...,n}
Note: All permutations can be written as a product of transpositions:

Lemma 4.4 t(P) = (-1)P
t is any transposition (r,s) on {1,2,...,n} and

Theorem 4.5 Products of Transpositions (Either all even or all odd transpositions)

Definition 4.6 Even Permutation vs. Odd Permutation (based on number of transpositions)
Even Permutation if r in r-cycle is odd
Odd Permutation if r in r-cycle is even

Definition 4.7 Alternating Group
is the subgroup of that consists all even permutations in

Definition 4.8 Conjugate Elements
1. The Conjugate of a by b is the element
2. c is a conjugate of a IFF for some b in G

Section 4.2 Cayley's Theorem

Definition 4.9 Cayley's Theorem
Every group is isomorphic to a group of permutations.

Section 4.4 Cosets of a Subgroup

Definition 4.10 Product of Subsets
Let

Theorem 4.11 Properties of the Product of Subsets
1. Associative
2. not commutative
3. B = C AB = AC & BA = CA
4. AB = AC  B = C
5. gA = gB A = B

Definition 4.12 Cosets, H < G,
Left coset of H in G: aH = { | x = ah for some }
Right coset of H in G: Ha
Left & right cosets are never disjoint, but they may be different sets.

Lemma 4.13 Left Coset Partition
The distinct left cosets of H form a partition of G.

Definition 4.14 Index: [G:H]
The total number of distinct left cosets of H in G.

Theorem 4.15 Lagrange's Theorem
If G is a finite group,

Corollary 4.16 |a| divides |G|

Section 4.5 Normal Subgroups

Definition 4.17 Normal (Invariant) Subgroup
H is a normal subgroup of G if xH = Hx for all x in G (left coset = right coset)
Note that it does not mean xh = hx

Theorem 4.18 A special coset H: hH = Hh = H

Corollary 4.19 The square of a subgroup

Theorem 4.20 Normal Subgroups and Conjugates
H is a normal subgroup of G IFF

Definition 4.21 Set Generated by A

Theorem 4.22 Subgroup Generated by A: <A> is a subgroup of G generated by A

Section 4.6 Quotient Groups

Theorem 4.23 Group of Cosets
If H is normal subgroup of G, then cosets of H form a group with respect to the product of subsets

Definition 4.24 Quotient (Factor) Group of G by H
If H is normal subgroup of G, the group G/H consists of the cosets of H in G is the quotient group of G by H

Theorem 4.25 Quotient Group => Homomorphic Image
(a) = aH is an epimorphism from G to G/H

Theorem 4.26 Kernel of a Homomorphism
If f is a homomorphism from G to G', ker f is a normal subgroup of G

Theorem 4.27 Homomorphic Image => Quotient Group
Let G and G' be groups with G' a homomorphic image of G. Then G' is isomorphic to aquotient group of G

Theorem 4.28 Fundamental Theorem of Homomorphisms
If is an epimorphism from the group G to the group G', then G' is isomorphic to G/ker

Skipped

Chapter 5 Rings, Integral Domains and Fields

Section 5.1 Definition of a Ring

Definition 5.1a A set R is a ring it has all 6 properties:
a) closed under + and .
b) associative under + and .
c) commutative under +
d) contains additive identity = zero = 0
e) contains additive inverses = -a = negative (opposite) of a, applies in subtraction
f) two distributive laws hold

Definition 5.1b Alternative Definition of a Ring:
a) R forms an abelian group under +
b) R is closed under associative multiplication
c) two distributive laws hold

Definition 5.2 Subring, analogous to subgroup

Theorem 5.3 Equivalent set of conditions for a subring
a) S is nonempty
b) x, y in S implies x+y and xy are in S
c) x in S implies -x in S

Theorem 5.4 Characterization of a subring
a) S is nonempty
b) x, y in S implies x-y and xy are in S
S = {0} and S = R are trivial subrings