MAT102 Lecture 20

• When you want to prove that something is true for all $n\in \mathbb{N}$.

  • You can use an arbitrary $x$ and prove for $x$.
  • To prove with induction and two variables, use both methods.
  • Fix an arbitrary string length $s$.

• 2

  • a
    • Let $\mathbb{R}$ be a universe of discourse. Think of $\{0,1\}\subseteq \mathbb{R}$.
    • $\chi A:U\to \{0,1\}$
    • $\chi A(x)=\{\begin{array}{ll}0& x\notin A\\ 1& x\in A\end{array}$
    • 1
      • $A=\mathbb{Z}$

        	left=-2; right=2;
        	top=10; bottom=-10;
        	---
        	(-2,1)
        	(-1,1)
        	(0,1)
        	(1,1)
        	(2,1)
        	y=0| -2<x<-1
        	y=0| -1<x<0
        	y=0| 0<x<1
        	y=0| 1<x<2
        

    • 2
      • $A=[-2,0]\cup [1,2]$

        	left=-2; right=2;
        	top=10; bottom=-10;
        	---
        	y=1| -\infty<x<0
        	y=0| 0<x<1
        	y=1| 1<x<\infty
        

    • 3
      • $A=\mathbb{Q}$

        	left=-2; right=2;
        	top=10; bottom=-10;
        	---
        	y=1|dashed|
        	y=0|dashed|
        

  • b
    • If $\chi A$ is the function of some set $A\subseteq U$, what is ${\chi }_A^{-1}(\{1\})$?
    • It should be anything that is in $A$
    • The definition of a preimage is:
      • $f^{-1}(V)=\{x\in A:f(x)\in V\}$
      • $f^{-1}(B)=A$
      • ${\chi }_A:U\to \{0,1\}$
      • ${\chi }_A:A\to \{0,1\}$
      • ${\chi }_a^{-1}(\{1\})=A$

    ---

    • Any element that's in $A$.
  • c
    • If $A$ is a set, the powerset of $A$ is $P(A)$ is all the subsets.
    • $P(a)=\{\{1\},\{1,2\},\{1,2,3\},\{2\},\{2,3\},\{3\},\{1,3\},\mathrm{\varnothing }\}$
    • $8$ including $\mathrm{\varnothing }$
  • d
    • Let $U$ be a universe of discourse. Let $F(U)=\{f:U\to \{0,1\}\}$ be the set of all functions on $U$ that map into $\{0,1\}$.
    • So this is any function that is part of the $U$.

    ---

    • Takes a set and outputs a characteristic function
    • $p:F(U)\to P(U)$
    • $f\mapsto f^{-1}(\{1\})$
    • The preimage of $\{1\}$, is the function by part 2b
    • So get a set, then we get out a function. The preimage is the set.
    • $p^{-1}(p(A))=p^{-1}({\chi }_a)={\chi }_a^{-1}(\{1\})=A$
    • $p(p^{-1}(f))=p(f^{-1}(\{1\}))={\chi }_{f^{-1}(\{1\})}$
    • $${\chi }_{f^{-1}(\{1\})}=\{\begin{array}{ll}0& x\end{array}$$