Set Theory Flashcards
What is a group?
A combination of a set and an operation (e.g. addition over the integers) that satisfies all four group axioms: closure, associativity, identity element, inverse element
What is the closure property?
For all x and y in G, x.y is also in G
∀ x, y ∈ G x.y ∈ G
What is the associativity property?
∀ x, y, z ∈ G . (x.y).z = x.(y.z)
What is the identity element?
There exists an element I, where x.I = I.x = x
∃ I ∈ G . ∀ x ∈ G . I.x = x.I = x
What is the inverse element?
For all x in G, there exists an inverse of x named y, where x.y = y.x = I
∀ x ∈ G ∃ I ∈ G . x.y = y.x = I
Meaning of ∃
there exists
Meaning of ∀
for all/for any
Meaning of .
such that
Meaning of ∈
is an element of/belongs to
What is meant by Z_n?
The set of integers modulo n (e.g. Z_4 = {0, 1, 2, 3})
2 + 3 = 1 (in Z it would be 5, but in Z_4 it’s 5 mod 4 = 1)
What does A \ B mean? (where A and B are both sets)
The set of numbers which are in A but not in B
{e : e ∈ A, e !∈ B}
What is a field?
A combination of a set and two operations, one with identity and an inverse, and another with identity and inverse for all except one element
What is P(A)?
The set of all subsets of A
What is A x B where A and B are sets?
Cartesian product of A and B, set of ordered pairs with first element from A and second element from B
A x B = {(a, b) . a ∈ A, b ∈ B}
What is [n]?
The set of all integers from 1 to n
What is an injective function?
A function f(x) where f(a) = f(b) implies a = b
What is the image of a function?
The set of all output values it can produce
What is the pre-image/inverse image of b under f(x)?
The set {a : f(a) = b}
What is a surjective function?
Every output has an input that results in it (there can be more than one)
What is a bijective function?
One which is injective and surjective
When do two sets have the same size?
When there is a bijection between them
How could you describe f(x) = sqrt(x)?
f : R>0 => R x R
f : R => C x C
What is a commutative group?
A group in which it doesn’t matter which way round you write the elements when doing the operation because you get the same result
Addition under the real integers is a commutative group
