Practice Work

2.1

Let $A=\{a,b,c,d\}$, $B=\{a,b,e\}$, $C=\{a,c,e,f\}$. Describe each by listing elements.

a. $(A\cap B)-C$

$$\{b\}$$

b. $A\times (B\cup C)$

$$\{a,b,c,d\}\times \{a,b,e,c,f\}$$

$\{(a,a),(a,b),(a,e),(a,c),(a,f),$ $(b,a),(b,b),(b,e),(b,c),(b,f),$ $(c,a),(c,b),(c,e),(c,c),(c,f),$ $(d,a),(d,b),(d,e),(d,c),(d,f)\}$

c. $P(A)\cap P(B)$

$$P(A)=\{\{a\},\{b\},\{c\},\{d\},\{a,b\},..\}$$ $$\{\{a\},\{b\},\{c\},\{d\},\{a,b\},\{b,a\}\}$$

2.2

Prove by induction that if $A$ is a finite set with $n$ elements, where $n$ is a positive integer, then $A$ has $2^n$ subsets.

If $A$ is a finite set with $n$ elements, where $n$ is a positive integer, then $A$ has $2^n$ subsets.

Basis Step: Test that this holds for $n=1$.

$$\begin{array}{rl}P(\{1\})& =\{\{\},\{1\}\}\\ P(\{1,2\})& =\{\{\},\{1\},\{2\},\{1,2\}\}\\ P(\{1,2,3\})& =\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}\end{array}$$

Assume it works for any $n=k$.

Inductive Step: Test for when $n=k+1$.

We know when $n=k$, $A$ has $k$ elements and that $P(A)$ has $2^k$ elements. When $n=k+1$, lets say we have the set $B$ which has $k+1$ elements. Since this our set $A$ with one extra element, say $x$, we know that $P(B)$ will include $P(A)$, it will also include a new set where each element corresponds to the elements in $P(A)$ but also include the new element $x$.

For example:

$$\begin{array}{rl}A& =\{y\}\\ P(A)& =\{\varnothing ,\{y\}\}\\ & \\ B& =\{x,y\}\\ P(B)& =\{\varnothing ,\{x\},\{y\},\{x,y\}\}\\ & =P(A)+\text{{{x}, {x, y}}}\end{array}$$

Since we know $P(A)$ has $2^k$ elements, $P(B)$ must have $2\times 2^k$ elements. But also, $2\times 2^k=2^{(k+1)}$, this is our IH with $k+1$. Hence by M.I., the statement holds for all $n$, where $n$ is a positive integer.

Formal Proof

https://www.youtube.com/watch?v=3CWhQBcOhvs

Prove that for some finite set $N:\underset{\mathcal{P}(n)}{\underbrace{|N|=n\Rightarrow |P(n)|=2^n}}$.

Basis Step: Let $n$ = 0.

$$\begin{array}{l}N=\varnothing \\ \mathcal{P}(0):|N|=0\\ \\ P(\varnothing )=\{\varnothing \}\\ |P(\varnothing )|=1=2^0\end{array}$$

Assume: This works for $n=k$.

$$\begin{array}{l}\mathcal{P}(k):|N|=k\Rightarrow |P(k)|=2^k\end{array}$$

Inductive Step: Then test $n=k+1$:

$$\begin{array}{l}\mathcal{P}(k+1):\\ |N|=k+1\\ \\ N^{\prime }=N\text{textbackslash}\{a\}⟺|N^{\prime }|=k\Rightarrow |P(N^{\prime })|=2^k\end{array}$$

So now we form $P(N)$ from $P(N^{\prime })$ and $P(N^{\prime })$ with $a$ included in each subset. This gives us the total number of subsets as $|P(N)|=2\times 2^k=2^{k+1}$. This is our induction hypothesis.

2.3

Show that if $A$, $B$ and $C$ are sets, then $A\times (B\cup C)=(A\times B)\cup (A\times C)$ always holds.

Let $s\in A\times (B\cup C)$. By $\times$ then $s=(x,y)$. So, $x\in A$ and $y\in B\cup C$.

If $y\in B$, then $(x,y)\in A\times B$ and similarly when $y\in C$, we find $(x,y)\in A\times C$. Thus, by $\cup$, we find that $(x,y)\in (A\times B)\cup (A\times C)$.

there is more stuff that needs to be here

2.4

Describe ‘div’ relation on the set $\{1,2,3,7,11,22,66\}$

$(1,1),(1,2),(1,3),(1,7),(1,11),(1,22),(1,66),$ $(2,22),(2,66)$ $(3,66)$ $(11,22)$ $(11,66)$

graph A {
	66--22,3
	22--11,2
	11--1
	7--1
	3--1
	2--1
}