Language of Relations and Functions Flashcards
Notations in relations
Element x in A is related to element y in B if x < y.
Lead to relations like 0 R 1 if R was representing x is related to y. Using Cartesian Product, that would lead to (let A = {0,1,2} and B = {1,2,3}):
{(0,1),(0,2),(0,3),(1,2)(1,3)(2,3)} in ordered pairs
Relations and Domains
R (relation) between A and B is a subnet of A x B, since A x B contains all numbers whilst R represents some of those numbers which can be paired up with the right combination.
A pair is represented by (x, y), so if x is related to y by R, it is written as x R y if (x, y) is in R. Set A in this instance is called the domain, with set B being it’s co-domain.
Notations for the relation R
x R y = (x, y) ∈ R
R is a subnet, (x, y) is what you get from all the pairs. That is why the singular pair (x, y) is in the subnet of R, consisting of multiple pairs.
Functions
Definition: put something it, gives something out
x+1 -> x is the input, the result is the output
f : A -> B
A is the domain of f, B is the codomain of f.
g 0 f(x)
f : X -> Y and g : Y -> Z, then their composition g o f is a function from X to Z given by (g o f)(x) = g(f(x)) (x being element, X being group)
f(x) -> what is in Y from X (f is the connection, A is the main domain and f shows the elements that the inputs of A go to B, the codomain)
Injective
Different values depending on same inputs (2x compared to x^2, since f(2) is the same as f(-2)).
|A| <= |B|
Surjective
Surjective if the range of f coincides with the codomain of f. Every b exists in B there exists a in A with b=f(a). Every element in codomain is in a.
Every input has an output.
|A| => |B|
Bijective
Surjective and Injective
|A| = |B| (same cardinality)
F(A)
f(A) = f : A -> B, but we could write f : A -> C with c being all the elements that A relates to inside of B.
Pigeonhole Principle
If |A| > |B| then at least one value of f occurs more than once.
Relations
Connection between items
a < c, b divides e
Cartesian Product
A x B of sets A and B is the set consisting of all pairs (a,b) with a exists in A and b exists in B:
A x B = {(a,b) | a exists in A and b exists in B}
Binary Relation
Subset of the Cartesian product of two sets
Inverse
change the order of the elements
R = (a, b) -> becomes R^-1 = (b, a)
Compositional
deriving relations by other relations
(a, b) -> (b,c), you can then derive (a, c)
(paul, john) which is relation R-> (john, spain) which is relation S, then you can derive that paul knows a friend who went to spain
S o R = the two connections, backwards order (S(R(x)), since R is applied first)
Matrix Representation:
S = {1,2,3,4}
Matrix would be 1 in every element that s contains.
Composition of Relations
Representation of ID o Salary, specifically S o R
Let’s say ID and Grade are one, which is 3 by 5, and Grade and Salary are another represented by 5, 5.
Dimension of ID and Salary would be 3x5, represented by ID.Salary
Binary Relation
In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain.
Reflexive Relation
xRx for all x exists in A
Each element in the set is related to itself.
(a,a),(a,b),(b,b) would be reflexive.
Symmetry Relation
xRy implies yRx for all x, y exists in A
All elements are reversed in some sort of way.
if (a,b) exists then (b,a) exists.
Antisymmetric Relation
xRy and yRx imply x = y for all x, y exists in A
Symmetric, but x and y are equal to each other.
if x <= y then y<=x
Transitive Relation
xRy and yRz imply xRz for all x, y for all x,y,z exists in A
x has to be in y and z, and y has to be in z
Ana, Banana, Lambanana
Transitive Closure
Adding all possible transitive options, represented by R*
Equivalence Relation
A binary relation which contains reflexive, symmetric and transitive
Partition
Collection of non-empty subsets of set …
Equivalence Class
Any x exists in A -> Ex = {y exists in A | yRx}
Partial Order / Poset
Every relation is Reflexive, Transitive, Antisymmetric (this is the relation).
Represented by the set and the relation (S, R), and defining it as a poset.
Total Order
Every relation is Reflexive, Transitive, Antisymmetric, as well as comparable with every other element.
Immediate Predecessor and Predecessor
What comes directly before and before.
Unary Relations
Subsets of a set.
Hasse Diagram
A way of representing a partial order.
Range of f
Set of values that did come out instead of what could have come out.
For example, f : A -> B
A contains 1+1, B contains 2 and 4.
2 would be the range.
Functional relation
All second elements are unique.
For instance, we could have {(3,1), (3,2), (4,3)} since all of the second elements don’t appear second again with another relation.
