term 1 key definitions Flashcards
what are the set of numbers
N - the natural - integers from 0 up
Z - integers - all integers
Q - rational numbers - any number that can be produced with a fraction
R - the real numbers
I - imaginary numbers
What are all algebraic properties
commutativity - x +y = y +x
associativity - (x+y)+z = x + (y+z)
identity - doesnt affect value
inverse - reverse funtion application
what is a subset
a subset of A is a set B such that every element of B is an element of B.
The empty set is a subset of every set.
To prove two sets are equal prove they are both subsets of each other
What are set operations
U - union - or
n - intersection - and
\ - difference - A\B = in A but not B
What is the cartesian product
the set of all ordered pairs between two sets.
What is a proposition
a statement that is either True or False
What is a predicate
a statement that becomes a proposition when we specify a value for one or more free variables
What are the universal Quantifiers
∀ - all
∃ - there exists
¬ - not
the operations that exist are
∧ - and
∨ - or
what are propositional identities
P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)
de morgans law
¬(P ∧ Q) = (¬P) ∨ (¬Q).
¬(P ∨ Q) = (¬P) ∧ (¬Q).
P ⇒ Q = (¬P) ∨ Q.
when are two functions equal?
9 Let f : A → B and g : C → D be functions. Then
f and g are equal (written f = g) if A = C and B = D and
f(x) = g(x) for all x ∈ A.
What are surjective injective and bijective functions?
Surjective - if for each element in B, theres at least one element in A that can produce it
injective - one to one
biijective - both surjective and injective
when can a function have an inverse
if and only if its a bijection
what is a one sided inverse?
For a function f : A → B, we say:
(i) g : B → A is a left inverse to f if g ◦ f = idA;
(ii) h : B → A is a right inverse to f if f ◦ h = idB.
how do you find the inverse of a permutation
reverse the elements in the cycle but put the smallest item first
What is the order of a permutation
the smallest m such that the permutation to the power = the identity
order of π = lcm(m1, . . . , mt).
A permutation cannot be expressed as both a product of an even number of transpositions and of an odd number of
transpositions
A permutation cannot be expressed as both a product of an even number of transpositions and of an odd number of
transpositions
The sign of σ ∈ Sn is denoted sgn(σ) and is defined by
+1 if it has an even number of transpositions
-1 if it has an odd number
what is the fundamental theorem of arithmetic
let n have the prime factorizations
n = p1…pr = q1…qs
then every prime occurs equally often in both factorisations
what is congruence
a-b/n = an integer or
a = b + kn
what is the congruence class of a number
the set of numbers congruent modulus [c]n
= {c, c + n, c + 2n…}
a]n + [b]n = [a + b]n, [a]n − [b]n = [a − b]n, [a]n[b]n = [ab]n.
a]n + [b]n = [a + b]n, [a]n − [b]n = [a − b]n, [a]n[b]n = [ab]n.
1 If some number d divides both a and n, and d > 1,
then [a] is not invertible in Zn.
1 If some number d divides both a and n, and d > 1,
then [a] is not invertible in Zn.
what is a binary operation on a group
a rule assigning each a and b to an element
What makes a set a group
if a(bC) = (ab)c
there is an identity element and an inverse element
Let G be a group (written multiplicatively) and let
g ∈ G. The order of g, written o(g) is the least positive integer r
with g
r = e, if such an r exists. Otherwise, we write o(g) = ∞
and say that g has infinite order.
Let G be a group (written multiplicatively) and let
g ∈ G. The order of g, written o(g) is the least positive integer r
with g
r = e, if such an r exists. Otherwise, we write o(g) = ∞
and say that g has infinite order.
if a group G with operation * then a subset H of G is a subgroup of G if
- a * b is in H when a and b are in H
- the identity element of G is an element of H
- every inverse element in H is in H
