mad3105 asgn1

MAD3105 Asgn1 - Relations and Their Properties

Ex. Let n be a positive integer. How many binary relations are there on A x A if |A| = n?
- |A X A| = |A| x |A| = n x n = n^2

Properties:
reflexive - if every element in the set A is related to itself, relation R is reflexive
irreflexive - if no element in the set A is related to itself, relation R is irreflexive
symmetric - if for every pair of elements, the relation contains a swapped version of that pair, relation R is symmetric
antisymmetric - if a pair of elements (a,b) exists, a = b && (b,a) cannot exist in the relation
asymmetric - if a pair of elements (a,b) exists, (b,a) cannot be in the relation
transitive - if a pair of elements (a,b) exists and a pair of elements (b,c) exists, (a,c) must also exist

Def.
R1 XOR R2 = (R1 UNION R2) - (R1 INTERSECT R2)

Ex. If R = {(1,1), (1,2), (2,4), (3,1), (3,0)}, S = {(1,2), (2,0), (3,1), (0,0), (4,3)}, find S o R.
- S o R = {(1,2), (1,0), (2,3), (3,2), (3,0)}
- If something exists in R, such as (3,1), find all things in S that are related to 1, such as (1,2). This means that
(3,2) must exist in S o R.
			  __________________
Ex. If M_R = |  1  |  0  |  0  |
             |  1  |  1  |  1  |
             |__0__|__1__|__0__|

					   __________________
- M_R^-1 (inverse) =  |  1  |  1  |  0  |
                      |  0  |  1  |  1  |
                      |__0__|__1__|__0__|

- inverse of a relation in matrix form is just the transpose of the original matrix

- M_R-comp (complement of R) =    __________________
                                 |  0  |  1  |  1  |
                                 |  0  |  0  |  0  |
                                 |__1__|__0__|__1__|

- complement of a relation in matrix form, just swap zeroes and ones out to show pairs

								   __________________			     __________________  	         __________________
- M_(R o R) (R composed with R) = |  1  |  0  |  0  |               |  1  |  0  |  0  |             |  1  |  0  |  0  |
                                  |  1  |  1  |  1  |       x       |  1  |  1  |  1  |      =      |  1  |  1  |  1  |
                                  |__0__|__1__|__0__|               |__0__|__1__|__0__|             |__1__|__1__|__1__|

- just matrix multiplication

Ex. If a relation R = {(1,1), (2,1), (2,2), (2,3), (3,2)} is given in a matrix, identify if it is reflexive, (anti)symmetric, or transitive.

- If reflexive, main diagonal is all 1
- If symmetric, everything on either side of main diagonal is equal
- If antisymmetric, nothing outside of main diagonal is hit
- If transitive...