Transcript Math 3121 Lecture 2 Sections 0-1 Sets and Complex Numbers

Math 3121
Abstract Algebra I
Lecture 2
Sections 0-1: Sets and Complex
Numbers
Questions on HW (not to be handed in)
• HW: pages 8-10: 12, 16, 19, 25, 29, 30
Finish Section 0: Sets and Relations
• Correction to slide on functions
• Equivalence Relations and Partitions
Corrected Slide: Functions
• Definition: A function f mapping a set X into a set
Y is a relation between X and Y with the
properties:
1) For each x in X, there is a y in Y such that (x, y) is in f
2) (x, y1) ∊ f and (x, y2) ∊ f implies that y1 = y2.
• When f is a function from X to Y, we write
f: X Y, and we write “(x, y) in f” as “f(x) = y”.
Functions (Corrected Version)
• Definition: A function f mapping a set X into a set Y is a
relation between X and Y with the property that each x
in X appears exactly once as the first element of an
ordered pair (x, y) in f. In that case we write f: X Y.
• This means that
1) For each x in X, there is a y in Y such that (x, y) is in f
2) (x, y1) ∊ f and (x, y2) ∊ f implies that y1 = y2.
• When f is a function, we write “(x, y) in f” as “f(x) = y”.
Recall: Equivalence Relation
• Definition: An equivalence relation R on a set
S is a relation on S that satisfies the following
properties for all x, y, z in S.
1. Reflexive: x R x
2. Symmetric: If x R y, then y R x.
3. Transitive: If x R y and y R z, then x R z.
Equivalence Classes
• Definition: Suppose ~ is an equivalence
relation on a nonempty set S. For each a in S,
let a̅ = {x∊S | x~a}. This is called the
equivalence class of a ∊ S with respect to ~.
Notes about Equivalence
1) By definition of a̅ = {x ∊ S | x ~ a}:
x ∊ a̅ ⇔ x ~ a.
2) By symmetry, a ~ a. Thus:
a ∊ a̅
Functions and Equivalence Relations
Theorem: Suppose f: X  Y is a function from a
set X to a set Y. Define a relation ~ by (x ~ y)⇔
(f(x) = f(y)). Then ~ is an equivalence
relation on X.
Proof: Left to the reader.
Theorem
• Theorem: Let ~ be an equivalence relation on
a set S, and let a̅ denote the equivalence class
of a with respect to ~. Then
x ~ y ⇔ x̅ = y̅ .
Proof
Proof: We show each direction of the implication separately
x ~ y ⇒ x̅ = y̅ :
We will show that x ~ y implies that x̅ and y̅ have the same elements.
1) Start with transitivity of ~: x ~ y and y ~ z ⇒ x ~ z
2) Rewrite 1) as: x ~ y ⇒ (y ~ z ⇒ x ~ z) (Note: P and Q ⇒ R is equivalent to P ⇒ (Q ⇒ R ))
3) By symmetry of ~, replace y ~ z by z ~ y and x ~ z by z ~ x in 2):
x ~ y ⇒ (z ~ y ⇒ z ~ x)
4) Reversing x and y in 3) gives: y ~ x ⇒ (z ~ x ⇒ z ~ y).
5) By symmetry of ~, replace y ~ x by x ~ y in 4):
x ~ y ⇒ (z ~ x ⇒ z ~ y).
6) Combining 5) and 3):
x ~ y ⇒ (z ~ x ⇔ z ~ y).
7) By definition of equivalence class
x ~ y ⇒ (z ∊ x̅ ⇔ z ∊ y̅ ).
Thus x ~ y ⇒ x̅ = y̅
x̅ = y̅ ⇒ x ~ y :
Suppose x̅ = y̅ . Since x ∊ x̅ , equality of sets implies that x ∊ y̅ . Thus x ~ y.
Thus x ~ y ⇔x̅ = y̅ .
QED
Partitions
• Definition: A partition of a set S is a set P of nonempty subsets of S
such that every element of S is in exactly one of the subsets of P.
The subsets (elements of P) are called cells.
• Note that a subset P of the power set of S is a partition whenever
1) ∀ x ∊ S, x is in some member of P
2) ∀ X, Y ∊ P, (X⋂Y ≠ Ø) ⇒ X=Y.
• Note that 1) is equivalent to:
1’) The union of all members of P is equal to S:
• ∪(P) = S
and 2) is equivalent to:
2’) The intersection of any two different members of P is empty.
• ∀ X, Y ∊ P, X ≠ Y ⇒ X Y =Ø
Theorem
• Theorem (Equivalence Relations and
Partitions): Let S be a nonempty set and let ~
be an equivalence relation on S. Then ~
corresponds to a partition of S whose
members are the equivalence classes a̅ = {x ∊
S | x ~ a}.
Proof
Proof: Let P = {a̅ | a ∊ S}
We show that P is a partition of S. We must show
that P is a collection of nonempty subsets of S
such that each element of S is in exactly one
member of P.
We will show that 1) for each x in S, x ∊ x̅ , 2) for any
x, y in S, (x̅ ⋂y̅ ≠ Ø) ⇒ (x̅ =y̅ ). From 1) we
conclude that each member of P is nonempty,
and that each member of S is in at least one
member of P. From 2) we conclude that each
element of S is in at most one member of P.
Proof of 1)
Proof of 1) For each a ∊ S, a ∊ a̅ :
Let a ∊ S.
Because ~ is reflexive, a ~ a
Thus a ∊ a̅ = {x ∊ S |x~a} .
Proof of 2)
Proof of 2) for any x, y in S, (x̅ ⋂y̅ ≠ Ø)⇒ (x̅ =y̅ ):
Assume x̅ ⋂y̅ ≠ Ø. Then there is an element z
in x̅ ⋂ y̅ . Then z ~ x and z ~ y. Applying
symmetry to the first and then transitivity to
the pair, we get x ~ y. By the previous
theorem x̅ = y̅ .
Thus (x̅ ⋂y̅ ≠ Ø)⇒ (x̅ =y̅ ).
Section 1: Complex Numbers
• This section covers complex numbers. It summarizes:
– Definition: ℂ = { a + b i | a, b ∊ ℝ}, where i2 = -1
– Addition and multiplication of complex numbers:
• (a + b i)+(c + d i) = (a + c) + (b + d) i
• (a + b i)(c + d i) = a c + a d i + b i c + b i d i
= (a c – bd) + (a d + b c) i
Note: follows from distributive and commutative laws.
– Absolute value: |a + b i | = sqrt (a2 + b2)
– Euler’s formula: e i ϑ = cos ϑ + i sin ϑ.
– Polar coordinates in the complex plane.
r e i ϑ =r cos ϑ + i r sin ϑ.
– Solving for roots using polar coordinates.
– The unit circle in the complex plane.
– Roots of unity: e i 2π/n = cos (2π/n) + i sin (2π/n)
More on the Complex Unit Circle
• Let U is the unit circle on the complex plane.
U = {z ∊ ℂ | |z| = 1}
• U is closed under multiplication of complex numbers.
• The function f(ϑ) = e i ϑ maps the real numbers into
the complex circle. It wraps the real line around the
circle.
• Note the addition formula: f(a+b) = f(a) f(b). Expand
this in terms of Euler and get the addition formulas for
sine and cosine (in class).
• Note that a ~ b ⇔ f(a) = f(b) defines an equivalence
relation on ℝ.
HW – not to hand in
• Pages 19-20: 1, 3, 5, 13, 17, 23, 38, 41