24 - Functions

!Screenshot 2023-11-06 at 12.27.16 PM.png
!Screenshot 2023-11-06 at 12.28.15 PM.png

In class Practice

$f:A⟹B$ is a function if

1. $f\subseteq A\times B$
2. $\mathrm{\forall }a\in A,a$ is the first coordinate of exactly one ordered pair in $f$ thought of as a subset of $A\times B$.

Not well-defined means it's not a function.

HW 24

Ben Finch

E 24.1
a) Yes, it is a function
b) No, it's not a function since $(4,6)\notin A\times B$.
c) Not a function, doesn't have $(3,b)$
d) Not a function, 1 is assigned to two items in $B$
e) Not a function, doesn't have $(3,b)$
f) Yes, it is a function.

E 24.2
a) $\mathbb{R}$
b) $\mathbb{R}-\{\frac{\pi }{2}+k\pi :k\in \mathbb{Z}\}$
c) $\{x\in \mathbb{R}:x>0\}$
d) $\{n\in \mathbb{R}:n\le 1\}$
e) $\mathbb{R}-\{-2\}$

E 24.3
Let $A$ be a finite set and let $B$ be any set. Let $f:A\to B$ be a function. Considering $f$ as a set of ordered pairs, prove that $|f|=|A|$.

Proof. Let $A$ be a finite set and let $B$ be any set. Let $f:A\to B$ be a function. By definition 24.1, each $a\in A$ must be the first coordinate of exactly one element in $f$. Also, $f$ cannot have some element $(m,n)$ where $m\notin A$. Thus if each $a\in A$ is the first element of one element in $f$, we know that $|A|=|f|$. $◻$

E 24.4
a) The function is well defined
Proof.
Let $X\in {\mathbb{Z}}_8$. Let $a,b\in X$. Then $a\equiv b\mathrm{mod}8$. Then $a-b=8k$ for some $k\in \mathbb{Z}$. Now $f(\bar{a})=[a]$. Thus $a-b=2(4k)$. Thus $a\equiv b\mathrm{mod}4$. So $[a]=[b]$. Thus $f(\bar{a})=f(\bar{b})$. $◻$

b) $[0]$ and $[4]$ are the same in ${\mathbb{Z}}_4$ but $g([0])=\bar{0}$ and $g([4])=\bar{4}$ are different in ${\mathbb{Z}}_8$. So the function is not well defined.

c) The function is well defined.
Proof.
Let $X\in {\mathbb{Z}}_4$. Let $a,b\in X$. Then $a\equiv b\mathrm{mod}4$. Then $a-b=4k$ for some $k\in \mathbb{Z}$. Now $h([a])=\overline{2a}$. Thus $a-b=2(4k)=8k$. Thus $a\equiv b\mathrm{mod}8$. So $[a]=[b]$.Thus $h([a])=h([b])$. $◻$

d) $[1]$ and $[5]$ are the same in ${\mathbb{Z}}_4$, but $j([1])=\bar{3}$ and $g([5])=\overline{15}=\bar{7}$. So the function is not well defined

E 24.5
Define $f:{\mathbb{Z}}_5\to {\mathbb{Z}}_5$ by $f(\bar{a})={\bar{a}}^5$. Define $g:{\mathbb{Z}}_5\to {\mathbb{Z}}_5$ by $g(\bar{a})=\bar{a}$. You may assume that f and g are both well-defined (which they are). Are f and g equal?

Proof.
We can check if $f$ and $g$ are equal by checking every element in ${\mathbb{Z}}_5$:

1. When $\bar{a}=\bar{0}$, $f(\bar{0})={\bar{0}}^5=\bar{0}$ and $g(\bar{0})=\bar{0}$, so $f(\bar{0})=g(\bar{0})$.
2. When $\bar{a}=\bar{1}$, $f(\bar{1})={\bar{1}}^5=\bar{1}$ and $g(\bar{1})=\bar{1}$, so $f(\bar{1})=g(\bar{1})$.
3. When $\bar{a}=\bar{2}$, $f(\bar{2})={\bar{2}}^5=({\bar{2}}^4)\bar{2}=\bar{1}\bar{2}=\bar{2}$ and $g(\bar{2})=\bar{2}$, so $f(\bar{2})=g(\bar{2})$.
4. When $\bar{a}=\bar{3}$, $f(\bar{3})={\bar{3}}^5=({\bar{3}}^4)\bar{3}=\bar{1}\bar{3}=\bar{3}$ and $g(\bar{3})=\bar{3}$, so $f(\bar{3})=g(\bar{3})$.
5. When $\bar{a}=\bar{4}$, $f(\bar{4})={\bar{4}}^5=({\bar{4}}^4)\bar{4}=\bar{1}\bar{4}=\bar{4}$ and $g(\bar{4})=\bar{4}$, so $f(\bar{4})=g(\bar{4})$.

Since $f(\bar{a})=g(\bar{a})$ for every $\bar{a}\in {\mathbb{Z}}_5$, the functions $f$ and $g$ are indeed equal. $◻$

E 24.6
A is a set.
$S_1,S_2\subseteq A$
$\chi$ - characteristic function

a) If $T=S_1\cup S_2$ and $S_1\cap S_2=\mathrm{\varnothing }$, then ${\chi }_T(a)={\chi }_{S1}(a)+{\chi }_{S2}(a)$.

Let $a\in A$ and consider the value of ${\chi }_T(a)$. There are two cases:

1. If $a\in S_1$, then $a\notin S_2$ because $S_1\cap S_2=\mathrm{\varnothing }$. Thus, ${\chi }_{S1}(a)=1$ and ${\chi }_{S2}(a)=0$. The sum ${\chi }_{S1}(a)+{\chi }_{S2}(a)=1+0=1$, which is equal to ${\chi }_T(a)$ because $a$ is in the union $T$.

2. If $a\in S_2$, a similar argument shows that ${\chi }_{S1}(a)=0$ and ${\chi }_{S2}(a)=1$. Again, ${\chi }_{S1}(a)+{\chi }_{S2}(a)=0+1=1$, which equals ${\chi }_T(a)$ because $a$ is in the union $T$.

3. If $a\notin S_1$ and $a\notin S_2$, then ${\chi }_{S1}(a)=0$ and ${\chi }_{S2}(a)=0$. Therefore, ${\chi }_{S1}(a)+{\chi }_{S2}(a)=0+0=0$, which matches ${\chi }_T(a)$ because $a$ is not in $T$.

In all cases, ${\chi }_T(a)={\chi }_{S1}(a)+{\chi }_{S2}(a)$. $◻$

b)

If $T=S_1\cap S_2$, then ${\chi }_T(a)={\chi }_{S1}(a)\cdot {\chi }_{S2}(a)$

Proof.
Let $a\in A$. There are 4 cases:

Case 1. $a\in S_1\cap S_2$
Note that ${\chi }_T(a)=1$ because $a$ is in both $S_1$ and $S_2$.
${\chi }_{S1}(a)=1,$ and ${\chi }_{S2}(a)=1$. Thus ${\chi }_T(a)=1\cdot 1={\chi }_{S1}(a)\cdot {\chi }_{S2}(a)$.

Case 2. $a\in S_1-S_2$
Here, ${\chi }_T(a)=0$ because $a$ is not in $S_2$, hence not in the intersection $T$.
${\chi }_{S1}(a)=1,$ and ${\chi }_{S2}(a)=0$. Thus ${\chi }_T(a)=1\cdot 0={\chi }_{S1}(a)\cdot {\chi }_{S2}(a)$.

Case 3. $a\in S_2-S_1$.
Here, ${\chi }_T(a)=0$ because $a$ is not in $S_1$, hence not in the intersection $T$.
${\chi }_{S1}(a)=0,$ and ${\chi }_{S2}(a)=1$. Thus ${\chi }_T(a)=0\cdot 1={\chi }_{S1}(a)\cdot {\chi }_{S2}(a)$.

Case 4. $a\in A-(S_1\cup S_2)$
Here, $a$ is in neither $S_1$ nor $S_2$, so it is not in their intersection.
${\chi }_{S1}(a)=0,$ and ${\chi }_{S2}(a)=0$. Thus ${\chi }_T(a)=0\cdot 0={\chi }_{S1}(a)\cdot {\chi }_{S2}(a)$.

In each case, ${\chi }_T(a)={\chi }_{S1}(a)\cdot {\chi }_{S2}(a)$. This completes the proof.

c)

If $T=S_1\cup S_2$, then ${\chi }_T(a)={\chi }_{S_1}(a)+{\chi }_{S_2}(a)-{\chi }_{S_1}(a)\cdot {\chi }_{S_2}(a)$

Proof.
Let $a\in A$. There are two cases for each set $S_1$ and $S_2$:

Case 1: $a\in S_1$
In this case, ${\chi }_{S_1}(a)=1$.

Case 1a: $a\in S_2$
Here, ${\chi }_{S_2}(a)=1$. Since $a$ is in both $S_1$ and $S_2$, it is also in their union $T$. Hence, ${\chi }_T(a)=1$.
The right-hand side of the equation becomes $1+1-1\cdot 1=1$, which is equal to ${\chi }_T(a)$.

Case 1b: $a\notin S_2$
Here, ${\chi }_{S_2}(a)=0$. Since $a$ is in $S_1$, it is in their union $T$. Hence, ${\chi }_T(a)=1$.
The right-hand side of the equation becomes $1+0-1\cdot 0=1$, which is equal to ${\chi }_T(a)$.

Case 2: $a\notin S_1$
In this case, ${\chi }_{S_1}(a)=0$.

Case 2a: $a\in S_2$
Here, ${\chi }_{S_2}(a)=1$. Since $a$ is in $S_2$, it is in their union $T$. Hence, ${\chi }_T(a)=1$.
The right-hand side of the equation becomes $0+1-0\cdot 1=1$, which is equal to ${\chi }_T(a)$.

Case 2b: $a\notin S_2$
Here, ${\chi }_{S_2}(a)=0$. Since $a$ is in neither $S_1$ nor $S_2$, it is not in their union $T$. Hence, ${\chi }_T(a)=0$.
The right-hand side of the equation becomes $0+0-0\cdot 0=0$, which is equal to ${\chi }_T(a)$.

In each case, ${\chi }_T(a)={\chi }_{S_1}(a)+{\chi }_{S_2}(a)-{\chi }_{S_1}(a)\cdot {\chi }_{S_2}(a)$. $◻$

E 24.7

Proof.
Since each $f_i$ is a function from $P_i$ to B, it is a subset of $P_i\times B$, and since each $P_i$ is a subset of A, it follows that each $f_i$ is a subset of $A\times B$. Thus, their union, $f$, is also a subset of $A\times B$, so $f$ is a relation from A to B.

To prove that $f$ is a function, we aim to demonstrate that for every element $a\in A$, there is exactly one ordered pair in $f$ with $a$ as its first coordinate. Consider an arbitrary element $a\in A$. Because {$P_i$: $i\in I$} is a partition of A, there exists a unique index $j\in I$ such that $a\in P_j$ and $a\notin P_i$ for all $i\ne j$. Therefore, $a$ is the first coordinate of exactly one ordered pair in $f_j$, namely $(a,f_j(a))$, because $f_j:P_j\to B$ is a function.

For all $i\ne j$, $a\notin P_i$, so $a$ is not the first coordinate of any ordered pair in $f_i$. This means that $(a,f_j(a))$ is the unique ordered pair in $f$ with first coordinate $a$. Hence, $f(a)=f_j(a)$ when $a\in P_j$ for some $j\in I$.

Since $a$ was an arbitrary element of A and we have shown that for each such $a$ there is exactly one ordered pair in $f$, it follows that $f$ is a function from A to B. $◻$