Functions/Sets Flashcards
Preimage
‘a’ is a preimage of f(a)
Domain
If f(x) maps A to B, A is the domain of function f(x).
Codomain
If f(x) maps A to B, B is the codomain of function f(x).
Image
If f(a) is b, b is the image of ‘a’ under function f(x).
Range
The range of f(x) is the set of all images for elements in A.
Function equality
Two functions are equal if:
- they have the same domain
- they have the same codomain
- they map the same element of domain to the same element of codomain
Injective
One to one:
Each element in domain is mapped to at most one element in codomain
Surjective
For each element in B, there exists an element in A such that f(a) = b.
Bijective
Both Injective and Surjective;
both one to one and onto.
There is no element in B that is not mapped to from A.
Composition
ie: f(g(x))
Countably infinite set
A set that has a Bijection
(One-to-One Correspondence) with the Z domain
Countable set
A set that is either Finite OR a set
that is Countably Infinite.
Uncountable set
A set that is NOT a Countable
Set.
Alphabet
A set of symbols
String
A sequence of symbols based on an alphabet
Language
A set of strings over some alphabet(s)
Congruence Relation
‘a’ is congruent to ‘b mod m’ if:
m | a - b
m | a & m | b with same remainder
IF
a ≡ b (mod m)
and c ≡ d (mod m)
THEN
a + c ≡ b + d (mod m)
a · c ≡ b · d (mod m)
IF
a ≡ b (mod m) holds
THEN
c + a ≡ c + b (mod
m)
TRUE or FALSE:
Dividing a valid congruence by an integer, c ∈ Z, preserves its validity
FALSE
TRUE or FALSE:
Multiplying both sides of a valid congruence by an
integer, c ∈ Z, preserves its validity.
TRUE
TRUE or FALSE:
Adding an integer to both sides of a valid congruence by an
integer, c ∈ Z, preserves its validity.
TRUE
a + (b mod m) =
(a + b) mod m
a x (b mod m) =
(a x b) mod m
(a + (b mod m)) + (c mod m) =
(a x (b mod m)) x (c mod m) =
a + (b + (c mod m)) mod m)
a x (b x (c mod m)) mod m)
a + (b mod m) =
a x (b mod m) =
b + (a mod m)
b x (a mod m)
(a + (b mod m)) x (c mod m) =
(a x (c mod m)) + ((b x (c mod m)) mod m)
a x ((b + (c mod m) mod m)
(a x (b mod m)) + ((a x (c mod m) mod m)
