21495: HW 4

Latest revision as of 11:11, 2 March 2017

Problem 16. Prove for all natural numbers $n\geq 5$: $2^n>n^2$.

Problem 17. Let $n\in\mathbb{N}$. Conjecture a formula for the expression \[a_n=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{3\cdot 4}+\cdots +\frac{1}{n\cdot (n+1)}\] and prove your conjecture by induction.

Problem 18. Use Problem 15 and induction to show that ${\cal P}(A)$ has $2^n$ elements, when $A$ has $n$ elements.

Mathematical statements and their connectives "and" and "or" on the one hand, and sets and set connectives "intersection" and "union" on the other hand behave somewhat analogously. The English mathematician George Boole (1815--1864) made this idea precise by describing what he called "algebra of logic". Today we use the name "Boolean Algebra" in his honor instead:

A Boolean Algebra is a set ${\cal B}$ together with two "connectives" $\sqcap$ and $\sqcup$ satisfying the following properties:

1. Closure Laws:
   1. If A and B are two elements in ${\cal B}$, then $A\sqcap B$ is also an element in ${\cal B}$.
   2. If A and B are two elements in ${\cal B}$, then $A\sqcup B$ is also an element in ${\cal B}$.
2. Commutative Laws:
   1. $A\sqcap B=B\sqcap A$ for all elements $A$ and $B$ in $\cal B$.
   2. $A\sqcup B=B\sqcup A$ for all elements $A$ and $B$ in $\cal B$.
3. Associative Laws:
   1. $(A\sqcap B)\sqcap C=A\sqcap (B\sqcap C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
   2. $(A\sqcup B)\sqcup C=A\sqcup (B\sqcup C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
4. Absorption Laws:
   1. $A\sqcap (A\sqcup B)=A$ for all elements $A$ and $B$ in $\cal B$.
   2. $A\sqcup (A\sqcap B)=A$ for all elements $A$ and $B$ in $\cal B$.
5. Distributive Laws:
   1. $A\sqcap (B\sqcup C)=(A\sqcap B)\sqcup (A\sqcap C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
   2. $A\sqcup (B\sqcap C)=(A\sqcup B)\sqcap (A\sqcup C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
6. There are elements $N\in{\cal B}$ (called the null element) and $O\in{\cal B}$ (the one element) such that
   1. $A\sqcap N=N$ and $A\sqcap O=A$ for all elements $A$ in $\cal B$.
   2. $A\sqcup O=O$ and $A\sqcup N=A$ for all elements $A$ in $\cal B$.
7. For every element $A$ in $\cal B$ there is an element $B$ in $\cal B$ such that $A\sqcap B=N$ and $A\sqcup B=O$.

Let $X$ be an arbitrary set. Then ${\cal P}(X)$ with the connectives $\cap$ (in the role of $\sqcap$) and $\cup$ (in the role of $\sqcup$) forms a Boolean Algebra. Highlights of the proof are the subject of the problem below:

Problem 19. Let $X$ be an arbitrary set.

1. Show that the Absorption Laws hold for ${\cal P}(X)$.
2. Which elements in ${\cal P}(X)$ play the role of the null element, and the one element, respectively?
3. For a given element $A$ in ${\cal P}(X)$, how does one choose the element $B$ mentioned in Law 7?

Similarly certain sets of statements with connectives $\wedge$ (in the role of $\sqcap$) and $\vee$ (in the role of $\sqcup$) form Boolean Algebras.

What is meant by "certain" sets of statements? Our task at hand is to identify what sets of statements correspond to power sets.

Let us consider an example and start with one "generic" statement $P$. How many distinct propositional forms can we form involving this statement? A little bit of reflection will lead us on the following path: Every propositional form has a truth table, so the number of distinct propositional forms is limited by the number of distinct truth tables. Since a truth table involving the statement $P$ has two rows, and since we have two choices for each row entry (T or F), there are at most 4 distinct truth tables, and therefore there are at most 4 distinct propositional forms. On the other hand it is easy to see that $P$, $\neg P$, $P\vee \neg P$ and $P\wedge \neg P$ are 4 distinct propositional forms contained in each Boolean Algebra containing $P$.

It is now boring to check that the following 4-element set indeed forms a Boolean Algebra: \[{\cal S}_1=\{P\wedge\neg P;\ P,\ \neg P;\ P\vee \neg P\}\] ${\cal S}_1$ is called the "Boolean Algebra generated by the free statement $P$".

Problem 20. Find the Boolean Algebra ${\cal S}_2$ generated by two free statements $P$ and $Q$.