MATH2020 (Lec 03) - Functions and Relations

Functions and Relations

Relations:

Def 1:

• a binary relation R consists
  • set A: domain of R
  • set B: codomain of R
  • subset of A x B: graph of R
• example:
  • A = {1,2}
  • B = {a,b,c},
  • R = {(1,a),(1,b),(2,c)} is a relation from A to B, or a subset of A x B
• note:
  • $R:A->B$: R is a relation from A to B
  • "$aRb$": the pair (a, b) in the graph of R
• confusing example:
  • eg1

Relation Types:

Def 2 (Reflexitivity, symmetry, transitivity)

• A relation R on set S is:
• Reflexive:
  • every element in S is related to itself
  • if $(x,x)\in R$ for all $x\in S$
  • eg: the “equal” relation is reflexive, as every number is equal to itself
  • tips: is x “the relation” to x correct
• Symmetric:
  • order of elements in the pair don’t matter
  • $(x,y)\in R$, then $(y,x)\in R$
  • eg. the “is sibling of relation is symmetric” as if x is sibling of y, then y is also sibling of x
• Transitive: (suy ra)
  • if x related to y, y related to z, then x is also related to z
  • if $(x,y)\in R$, and $(y,z)\in R$, then $(x,z)\in R$

Def 3 (Functions) ❓❓❓

• a function $f:S\to T$ is a mapping from set S to elements in set T, to which each element in 1 set (domain set) is mapped to exactly 1 element in another set (codomain set)
• $f:S\to T$
  • f: function
  • S: domain
  • T: codomain
  • f is a relation between S and T. For each $s$ in S there is a unique element $t$ in T so that $(s,t)\in R$
  • image / range of $f$ is set of all values $f$ can produce
• note:
  • image: set of output that the function actually produce for a particular input
  • range: set of output that the function could produced, eh

Def 4 (Injection / One-to-one)

• a function $f:S\to T$ is “injective” if for every $t\in T$, there exists AT MOST one $s\in S$ such that $f(s)=t$
• one output is mapped to AT MOST one input
• prove:
  • assume $f(x_1)=f(x_2)$ for $x_1,x_2$ in S
  • show that this implies $x_1=x_2$

Def 5 (Surjection / Onto) ❓❓❓

• a function $f:S\to T$ is “surjective” (onto) if the image of f equals its range, or for each $t\in T$, there is AT LEAST one $s\in S$ such that $f(s)=t$
• prove:
  • let f(s) = t ⇒ s = …
  • as $t\in T$, if $s\in S$ → surjective

Def 6 (Bijection / One to one correspondence)

• a function $f:S\to T$ is “bijective” if it is injective and surjective
• every element of the codomain corresponds to exactly one element of the domain

Function Composition & Inverse

Def 7 (Composition)

• for $f:A\to B$ and $g:B\to C$
• $g\circ f=g(f(x))$
• $f\circ g=f(g(x))$
• $g\circ f\ne f\circ g$, if well defined

Inverse relation

• $R^{-1}$ of $R:A\to B$ is the relation from B to A defined by $(b{R}^{-1}a)IFF(aRb)$
• change the position & reverse arrow sign: $A\to B$ into $B\to A$

Def 9: identity function

• identity function is a function returning the same output as its input
• $i{d}_A:A\to A$ - a function maps set A to itself
• eg
  • A is set of real numbers
  • $x\in A$, $id(x)=x$; for eg $x=5$, then $id(5)=5$
• prove
  • for every x in domain f, $f(x)=x$

Def 10: left / right inverse

• $f\circ g=id$ ⇒ f is left inverse of g, g is right inverse of f

Def 10: two-sided inverse

• f is both left and right inverse of g → f and g are two sided inverses of each other

Def 12:

• f from A to B is total when f(x) exists for all $x\in A$

Claim 13, 14, 15: work for both sides

• f is injective and total ⇐> f has left inverse
• f is surjective ⇐> f has right inverse
• f is bijective ⇐> f has a two-sided inverse

Set cardinality

• review definition in lec 1
• set cardinality: number of elements in a set, either finite or infinite
• Two sets $A$ and $B$ have the same cardinality (written as $|A|=|B|$) IFF there exists a bijection $f:A\to B$
• Set $A$ has cardinality $\ge$ set $B$ (written as $|A|\ge |B|$ ) IFF there exists
  • an injection $g:A\to B$
  • a surjection $g^{\prime }:B\to A$

Set countability

Countable & Uncountable Set

• countable if it has same number of elements as some subset of ${\mathbb{N}}^{+}$ or ${\mathbb{N}}^{+}$ itself
• include finite and infinite set that is bijective with ${\mathbb{N}}^{+}$
• a set is countable IFF $|S|\le |N^{+}|$
• eg:
  • set $\mathbb{Z}$ is also countable: alternating between non-negative and negative numbers → here
• prove S is countable set:
  • find a bijection between the set S and ${\mathbb{N}}^{+}$
• a set not countable is uncountable
  • Proposition 2: eg. set of (0, 1); $\mathbb{R}$ is uncountable

Cantor-Bernstein-Schroeder

• if $f:S\to T$ is injective (or $|S|\le |T|$) and $g:T\to S$ (or $|T|\le |S|$) is injective ⇒ there is a bijective $h:S\to T$

Theorem 18

• if A and B are countable sets, $A\cup B$ is also countable

Rational and irrational numbers

• rational numbers: any number expressed as the fraction $\frac{p}{q}$ with p, q are integers
• irrational numbers: real number that cannot be expressed as fraction of 2 int (eg. pi, e, sqrt(2))