Relations and Functions

Let the set $A=\{0,1,2,3\}$. Is the relation $T=\{(0,1),(2,3)\}$ on $A$

1. reflexive?

2. symmetric?

3. transitive?

Is the less-than-or-equal-to relation, $\leq$, an equivalence relation on $\mathbb{Z}$?

Let the function $f:\{1,2,3\}\to\{1,4,9,16,25\}$ be such that $f(x)=x^{2}$.

1. Use arrow notation to write a definition for $f$.

2. State the domain, codomain, and range of $f$.

3. What is the image of 2 under $f$?

4. Is $g:\{1,2,3\}\to\{1,8\},x\mapsto x^{3}$ a valid function?

Is $f:\mathbb{Q}\to\mathbb{Z},\;\frac{p}{q}\mapsto p+q$ a well-defined function?

Let the functions $f:\mathbb{R}\to\mathbb{R}$ and $g:\mathbb{R}\to\mathbb{R}$. Write down the rule of the function $fg$ if $f(x)=x^{2}-x+1$ and $g(y)=\frac{1}{y^{2}+1}$.

Define the function $f:\mathbb{N}\to\mathbb{Z}$ such that

By considering $f$, prove that $|\mathbb{N}|=|\mathbb{Z}|$.

Let the set $A=\{1,2,3,4\}$. Find a function $f:A\to A$ that is bijective but is not equal to the function $g:A\to A,x\mapsto x$.

Let the set $S=\{1,2,3\}$. Which of the following sets is/are relations on $S$? If the set is a relation on $S$, is it an equivalence relation?

1. $A=\varnothing$

2. $B=\{(1,1),(2,2),(3,3)\}$

3. $C=\{(1,1),(1,2),(2,2),(3,3)\}$

4. $D=\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)\}$

Let the functions

1. Which of the given function(s) are injective? If they are, prove it. If not, explain why.

2. Does the composite function $hf$ exist? If so, give a definition of $hf$ using arrow notation and state its image. Otherwise, explain why.

3. Does the composite function $fg$ exist? If so, give a definition of $fg$ using arrow notation and state its image. Otherwise, explain why.

Let $\sim$ be an equivalence relation on a set $A$ and let $x,y\in A$. Prove that

1. if $[x]=[y]$ then $[x]\cap[y]\neq\varnothing$;

2. if $[x]\cap[y]\neq\varnothing$ then $x\mathrel{\sim}y$; and

3. if $x\mathrel{\sim}y$ then $[x]=[y]$.

Let $X$ be any set, and let $f:X\to X$, $g:X\to X$, and $h:X\to X$ be functions. Suppose $h$ is injective. Prove or disprove the following statements.

1. If $hf=hg$ then $f=g$.

2. If $fh=gh$ then $f=g$.

The McCarthy 91 function $M:\mathbb{Z}\to\mathbb{Z}$ is a recursive function created by computer scientist John McCarthy to test formal verification in computer science. It is defined as follows.

1. Show $M(101)=91$.

2. Show $M(n)=M(n+1)$ for all $90\leq n\leq 100$.

3. Deduce that $M(n)=91$ for all $90\leq n\leq 100$.

4. Hence prove that $M(n)=91$ for all $n\leq 100$.

Let the function $f:\mathbb{N}^{2}\to\mathbb{N}$ be defined such that

Prove that

1. $f(n,2)=n-1$ for all integers $n>1$;

2. $f(n+1,n)=2$ for all positive integers $n$; and

3. $f(n,4)=2$ for all integers $n>1$.

Let $X$ be a non-empty finite set of cardinality $n$ and let $f:X\to X$ be a injective function. Prove that $f$ is bijective.(Hint: consider strong induction on $n$.)