Midterm 1 Notes:Math 360, Fall 2013

Math 360 Midterm 1 Notes

Please excuse the weird informal tone of these notes. That's just how I write to myself.

Basics

Brief review:

Very Basic Logic

Just here as a reminder.

• \(\lnot P\) means not \(P\)
• \(P \wedge Q\) means \(P\) and \(Q\)
• \(P \vee Q\) means \(P\) or \(Q\)
• \(P \rightarrow Q\) means \(P\) implies \(Q\)
• \(P \leftrightarrow Q\) means \(P\) if and only if \(Q\).
• \(\forall x\) means for all \(x\)
• \(\exists x\) means there exist an \(x\)
• s.t. means such that. Often represented with a colon.
• \(!\exists x\) means there does not an \(x\)

Sets

A set is a collection of things. We say something is in a set or an element of a set.
A set is defined either by listing the elements in the set or by giving a rule that defines those elements.
So the set of MA360, MA361, would be written: $$ \{ \text{MA}360,\text{MA} 361 \} $$ If we want to get the set of all even numbers, we can't list all the elements, so we give a rule: $$ \{e | e \text{ is a multiple of 2.} $$ If a thing is in a set, we write: $$ \text{thing} \in \text{set} $$ So for the first example it would be: $$ \text{MA}360 \in \{\text{MA}360,\text{MA}361\} $$ And of course we can assign variable names to sets.
Also - sets don't care about order or about the number of times an element appears. The sets \(\{2,2,2,3\}\) and \(\{2,3\}\) are exactly the same. (If we do care about repetitions, it's a multiset. If we care about order, it's a tuple).

Union of Two Sets

\(A\) and \(B\) are sets. The union of these two sets is also a set, written: $$ A \cup B $$ The union of \(A\) and \(B\) is the set of all things in at least one of \(A\) and \(B\).
\(A = \{1,2,3\}, B = \{3,4,5\}\). Then: $$ a \cup B = \{1,2,3,4,5\} $$

Intersection of Two Sets

\(A\) and \(B\) are sets. The intersection of these two sets is also a set, written: $$ A \cap B $$ The intersection of \(A\) and \(B\) is the set of all things in both \(A\) and \(B\).
\(A = \{1,2,3\}, B = \{3,4,5\}\). Then: $$ A \cap B = \{3\} $$

Cartesian Product of Two Sets

\(A\) and \(B\) are sets. Their Cartesian product is also a set. It's written: $$ A \times B $$ The Cartesian product is hard to explain. Basically it's the set of all the matchings between \(A\) and \(B\). Better explained through example:
\(A = \{1,2,3\}, B = \{3,2\}\). Then: $$ A \times B = \{(1,3),(1,2),(2,3)(2,2),(3,2),(3,3)\} $$

Equality

Two sets are equal if and only if they have all the same elements.
\(A=\{1,2,3\}\). \(B=\{1,3,2,2\}\). Order and repetitions don't matter for sets, so both sets contain the same elements, so: $$ A = B $$

Subset

We have a set \(A\). Another set \(B\) is a subset of \(A\) if all the things in \(B\) are also in \(A\) (all the elements of \(B\) are elements of \(A\).) We write this relationship as: $$ B \subseteq A $$
\(A = \{1,2,3\}\), \(B=\{2,3\}\). Well, \(2\in A\) and \(3 \in A\), so every element of \(B\) is in \(A\), so \(B\subseteq A\).
Also, \(1\in A\). So every element of \(A\) is in \(A\), and \(A\) is a subset of itself. Subsets are like less than or equal too, not less than.
If \(B \subseteq A\), and \(B\) is not equal to \(A\), then

Cardinality

The cardinality of a set is its "size". For finite sets, this is the number of elements in the set. For infinite sets, it's more complicated.
Two sets have the same cardinality (are equipotent) if there is a bijection between them.

Relation

A relation between two sets \(A\) and \(B\) is a subset of their Cartesian product. That's a lie, of course. Relations are actually normal things like equals and less than and greater than or equal to, and this is just a way of making that concept general.
Equality of real numbers is a relation. \(\mathbb{R}\times\mathbb{R}\) is the set of all tuples of real numbers. The relation, "=", is defined as: $$ = : \{(x,x)|x\in \mathbb{R}\} $$ Technically the ":" should be an "=", but that would be confusing.

Equivalence Relation

An equivalence relation is a relation that is symmetric, transitive, and reflexive. If the relation symbol is \(\cong\), then: $$ x\cong x\\ x \cong y \leftrightarrow y\cong x\\ x\cong y \wedge y\cong z \rightarrow x\cong z $$ It's a relation that acts like equality, kind of.

Partition

A partition of a set \(A\) is a set of pairwise disjoint subsets of \(A\) whose union is \(A\). A bunch of subsets \(B_1, B_2,\ldots,B_n\), that don't have any elements in common, and every element of \(A\) is in one of them.
Partitions generate equivalence relations, and vice versa.

Functions

A function \(f:A\rightarrow B\) is a subset of \(A\times B\) where no element of \(A\) appears more than once. This is another weird definition that generalizes the normal idea of a function.
\(A\) is the domain. \(B\) is the codomain. The set of actual outputs is the image.

Injective Function

\(f:A\rightarrow B\) is injective if: $$ f(x)=f(y) \rightarrow x=y $$ Same output implies same input.

Surjective Function

\(f:A\rightarrow B\) is surjective if: $$ \forall y\in B: \exists x\in A: f(x)=y $$ The function covers the entire set.

Bijective Function

A function is bijective if it's injective or surjective. Bijectivity is equivalent to being invertible.

Algebraic Structures

An algebraic structure is a set \(A\) and at least one function \(f:A^n \rightarrow A\). A binary structure is a set \(A\) and a function \(f:A\times A \rightarrow A\).
Usually the functions are called operations. A function \(f:A^n \rightarrow A\) is called an \(n\)-ary operation. If our operation is binary, and its symbol was \(*\), then the operation would be written: $$ x*y $$ instead of \(*(x,y)\).

Properties

There are properties that algebraic structures can have. These are some of the most important.

Associativity

A binary structure is associative if: $$ x*(y*z) = (x*y)*z $$
Subtraction and division are not associative. Vector multiplication is not associative.

Existence of an Identity

A binary structure has an identity if there is an element \(e\) such that: $$ x*e = x = e*x $$
So integer addition has an identity - 0.

Existence of Inverses

A binary structure with an identity has inverses if, for every \(x\), there is an element \(x^{-1}\) such that: $$ x*x^{-1} = e = x^{-1}*x $$
So integer addition has inverses - if \(x\) is an integer, then \(-x\) is its inverse, because \(-x + x = 0\).

Commutativity

A binary structure is commutative if: $$ x*y = y*x $$
Integer addition is also commutative.

Isomorphisms

We've got two binary structures, \((A,*)\) and \((B,\circ)\). These two structures are isomorphic if there is a bijective function \(\phi:A\rightarrow B\) such that: $$ \phi(x*y) = \phi(x) \circ \phi(y) $$ Two structures that are isomorphic can be considered the same for many purposes.

Structural Properties

A structural property is a property that is "closed" under isomorphisms. Meaning if structure \(A\) has the property, and \(A\) is isomorphic to \(B\), then \(B\) also has the property.
Structural properties include:

• Associativity
• Identity
• Inverses
• Commutativity

Binary Structures

A binary structure is a structure with a 2-ary operation. So integers with addition, real numbers with division, matrices with matrix subtraction - all binary structures.

Groups

A group is a binary structure that is associative, has an identity, and has inverses. So if \(x,y,z\in G\), and \(G\) is our group, then: $$ x*(y*z) = (x*y)*z\\ 1*x = x = x*1\\ x*1/x = 1 = 1/x*x $$ Additionally, if the operation is commutative, i.e. $$ x*y = y*x $$ then the group is called abelian.

Examples

The integers are a group under addition:

• Addition is associative. 4+(5+6) = 15 = (4+5)+6
• Addition has an identity - 0. 5+0 = 5 = 0+5.
• Addition has inverses - the negative number. 10 + (-10) = 0 = (-10)+10

The integers are really an abelian group, because addition is commutative. But that just makes them a type of group.
The real numbers, without 0 (written \(\mathbb{R}^{*}\) are a group under multiplication:

• Multiplication is associative
• 1 is an identity.
• 1/x is the inverse of x

As before, this is also an abelian group, because multiplication is commutative.

Writing Conventions

There are a couple of shorthands that make writing about groups easier. They are confusing shorthands.
We have a group \((G,*)\). First off, this gets shortened to \(G\). Basically, if the operation is clear from context, it's not going to be written.
So if "\(G\)" is written, and a few words later "\(x*y\) with \(x\) and \(y\) in \(G\)", then it should be clear that \(G\) is actually \((G,*)\).
So we have \(G\). We have \(a\in G\). I want to talk about the element: $$ a*a*a*a*a*a*a*a $$ That's a pain. So instead, I'm going to pretend that operation is syntactically like multiplication, meaning: $$ a^8 = a*a*a*a*a*a*a*a $$ If the operation was \(+\), then I would write: $$ 8a = a+a+a+a+a+a+a+a $$ instead. These operations still have nothing to do with addition or multiplication. It's just an easier way of writing things. (You'd think mathematicians would have come up with a different but still easy way to write things, but apparently they can't be bothered.)

Subgroups

We have a group \((G,*)\). \(H\) is a subset of \(G\). We say \(H\) is a subgroup of \(G\) if:

• \(H\) is closed under \(*\).
• \(H\) contains the identity of \(G\).
• \(H\) contains the inverses of all its elements.

Another way of saying this is that \(H\) is a group under the operation restricted to \(H\).
This means that \(G\) is a subgroup of itself.
\(G\) is the improper subgroup of itself. The set consisting of just the identity element is always a subgroup of \(G\), and is called the trivial subgroups. If a subgroup is not the improper subgroup, then it is as proper subgroup.

Examples

The even integers are a subgroup of the integers, under addition.

• The even integers are closed under addition - if you add two even integers, you always get an even integer.
• 0 is even, so the even integers contain the identity.
• The inverse of every even integer is even - 4 and -4 are both even. So all the inverses are in the even integers.

Cyclic Subgroup

Pick an element \(a\) in a group \(G\). If we take the set: $$ \langle a \rangle = \{a^n|n\in \mathbb{Z}\} $$ Then this set is a subgroup of \(G\), called the cyclic subgroup generated by \(a\). This is also the smallest subgroup of \(G\) that contains \(a\) (where the ordering is given by containment).
If the cyclic subgroup generated by \(a\), i.e. \(a\), is of finite order \(n\), then we say that the order of \(a\) is also \(n\).
\(a^n=e\), if \(n\) is the order of \(a\).
Otherwise, the order of \(a\) is infinite.

Cyclic Groups

\((G,*)\) is a group. \(G\) is cyclic if there is an element of \(G\), let's call it \(a\), such that every element of \(G\) can be produced from \(a\). So if \(g\in G\), then: $$ \exists b\in \mathbb{Z}: a^n = g $$ this is the same as saying \(g=a*a*a\ldots*a\) for \(n\) \(a\)'s.

Theorems

• Every cyclic group is abelian.
• If the order of a cyclic group is \(n\), then the group is isomorphic to \(\mathbb{Z}_n\).
• If the order of the group is infinite, then the group is isomorphic to \(\mathbb{Z}\).
• There are no uncountable cyclic groups.
• Every subgroup of a cyclic group is cyclic.
• The subgroups of \(\mathbb{Z}\) are the groups \(n\mathbb{Z}\) - the multiples of \(n\) in the integers.

Division Algorithm

Not actually an algorithm. In any case, for any two integers \(m\) and \(n\), there are two other integers \(q\) and \(r\), with \(0\leq r \lt m\), such that: $$ m = qn+r $$

Greatest Common Divisor

If \(r\) and \(s\) are two integers, and they generate: $$ H = \{nr+ms|n,m\in\mathbb{Z}\} $$ then the generator of \(H\) is the \(gcd(r,s)\). This is the same as the arithmetic gcd of \(r\) and \(s\).
If the gcd of two integers is 1, the integers are relatively prime.

Structure of Cyclic Groups and Subgroups

Cyclic groups are all isomorphic to \(\mathbb{Z}\) or \(\mathbb{Z}_n\). Specifically, if \(G\) is cyclic and of finite order \(n\), then \(G\simeq \mathbb{Z}_n\), and if \(G\) is infinite (meaning countably infinite - there are no uncountable cyclic groups) then \(G\simeq \mathbb{Z}\).
So only \(\mathbb{Z}\) and \(\mathbb{Z}_n\) really matter.
All the subgroups of \(\mathbb{Z}\) are of the form \(n\mathbb{Z}\) - the set of all integer multiples of \(n\). There are no subgroups of \(\mathbb{Z}\) that aren't generated in this way, and every \(n\) generates a cyclic subgroup like this.
The subgroups of \(\mathbb{Z}_n\) are the sets \(\langle d \rangle\), where \(d\) is a divisor of \(n\). If \(s\) is not a divisor of \(n\), then \(\langle s \rangle\) is actually \(\langle gcd(s,n)\rangle\).

Subgroup Generated by a Set

For a group \(G\) and a subset \(S\subseteq G\), the subgroup generated by \(S\) is the smallest subgroup of \(G\) that contains \(S\). This is the same as the intersection of all the subgroups that contain \(S\).
For cyclic groups, at least, this is equivalent to the subgroup generated by the greatest common divisor of all the elements of \(S\). So the subgroup generated by \(\{3,6\}\) is just \(\langle 3 \rangle\).

Proof Techniques

Proving Two Sets Are Equal:

We have two sets \(A\) and \(B\). Show that \(A\subseteq B\) and \(B\subseteq A\).

Proving Two Sets Have Equal Cardinality:

We have two sets \(A\) and \(B\). Find a bijective function between the two sets. Alternatively, find a surjective function from \(A\rightarrow B\) and another from \(B\rightarrow A\).

Proving a Function is Surjective:

We have a function \(F:A\rightarrow B\). Pick an arbitrary element of \(B\). Show that there is an element of \(A\) that maps to that element.

Proving a Function is Injective:

We have a function \(f:A\rightarrow B\). Pick two elements \(x\) and \(y\) in \(A\). Assume \(f(x) = f(y)\). Show that therefore, \(x=y\).

Proving a Function is an Isomorphism:

We have a function \(\phi:A\rightarrow B\). Show that \(\phi\) is one to one, and onto. Show it's well-defined. Show that \(\phi(a*b) = \phi(a) * \phi(b).</dd> <dt>Proving Two Structures Are Not Isomorphic <dd>This is in general difficult. Just check as many structural properties as you can. (In graph theory this problem is intractable. I suspect, but do not know, that the same is true here.)</dd> <dt>Proving an Operation is Associative: <dd>We have an operation \(*:F\rightarrow F\). Pick three arbitrary elements and show that \(x*(y*z) = (x*y)*z\).

Proving an Operation has An Identity:

Do a constructive proof. Find the identity, and show it has the right properties.

Proving an Operation has Inverses:

Take an arbitrary member of the set, show it must have an inverse.

Proving an Operation is Commutative:

Take two arbitrary members of the set, prove they commute.

Proving a Structure is a Group:

Given set \(G\) and operation \(*:G\rightarrow G\). Show that the set is closed under the operation. Show the operation is associative. Show that an identity exists (possibly from definition of operation). Show that there are inverses.

Important Examples

Group Examples

• The set of integers under addition
• The rational number under addition
• The real numbers under addition.
• The complex numbers under addition
• The non-zero rational numbers under multiplication.
• The non-zero real numbers under multiplication.
• The non-zero complex numbers under multiplication.
• The invertible \(n\times n\) matrices under matrix multiplication.
• The \(n\times n\) matrices under matrix addition.
• The integers modulo \(n\) under addition. (Equivalence classes modulo \(n\).
• The \(n\)-th roots of unity.
• The symmetries of an equilateral triangle.
• Invertible, diagonal \(n\times n\) matrices.

Group Non-Examples

• The real numbers with multiplication (0 has no inverse).
• Complex numbers with multiplication.
• Rational numbers with multiplication.
• Square matrices with multiplication.

Other Binary Structures

Monoids:

• Real numbers with multiplication.

Most Important Theorems

Associativity of Composition

Composition of functions is associative.

Partitions = Equivalence Relations

Every partition generates an equivalence relation (the relation is - are these elements in the same partition?) and every equivalence relation generates a partition (the partitions are - these things are in the same partition if they are equivalent).

Uniqueness of Identity Element

An operation on a set has at most one identity element. It is impossible to have more than one.

Cancellation Laws

In a group \(G\), if \(x*y=x*z\), then \(y=z\), and if \(y*z = z*x\), then \(y=z\). This is not true for \(y*x=x*z\).

Integer Division

Given two integers \(m\) and \(n\), there are two other integers \(q\) and \(r\) such that: $$ n = mq +r $$ and \(0\leq r \lt m\).

Classification of Cyclic Groups

Every cyclic group is isomorphic to \(\mathbb{Z}\) or \(\mathbb{Z}_n\). If \(G\) is a group of order \(n\), then \(G \simeq \mathbb{Z}_n\), otherwise (if \(G\) is infinite), then \(G\simeq \mathbb{Z}\).

Subgroups of \(\mathbb{Z}\)

Every subgroup of \(\mathbb{Z}\) is of the form \(n\mathbb{Z}\) - the set of all multiples of \(n\), i.e. $$ n\mathbb{Z} = \{nm|m\in \mathbb{Z}\} $$

Subgroups of \(\mathbb{Z}_n\)

Every factor of \(n\) generates a subgroup of \(\mathbb{Z}_n\), and these are the only subgroups of \(\mathbb{Z}_n\). The subgroup generated by \(m\) is actually the subgroup generated by \(gcd(m,n)\).