# CMPUT272 Lecture Notes - Lecture 18: Binary Relation, Cross Product, Injective Function

For unlimited access to Class Notes, a Class+ subscription is required.

Novemebr 5 2014

ETLC 2-001

Relations

Recall:

A1 ... ai i w = y B) A C)

((a, b), c)

An n-ary relation on the cross product of n sets is a

subset of A1 An

A binary relation on A B

Examples of binary relations:

R +)^2 R = {(x, y) | x R, 1R5, 1 N

{a, b}

R ) R

A binary relation from A to B is a funcion a!bf

(a1, _)

(a2, _)

... (there is no other (a2, _) )

(an, _)

f: A -> B

(a, b) f}

Examples of functions:

f: {1, 2, 3} -> {p, q}

f = {(1,q), (2,q), (3,q)} (ok)

f = {(1,p), (2,p), (3,p)} (ok)

f = -> -> a1,a2 a1 = a2

aka, A, a1 f(a1) a1,a2 a1 = a2

|A| ba |B|

A function f: A -> B is one-to-one

correspondance (aka, bijection, bijective) if