CRN 12107: HW 4

Latest revision as of 00:34, 9 October 2013

Problem 16. Exercise 2.5 #1a.

Problem 17.

1. Show that every positive integer can be written as the sum of (one or more) distinct powers of 2. (Examples: $8=2^3$, $25=2^4+2^3+2^0$.)
2. Can every positive integer be written as the sum of (one or more) distinct powers of 3?

It is quite obvious that statements and their connectives on the one hand, and sets and set connectives 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$\quad for all elements $A$ in $\cal B$.
   2. $A\sqcup O=O$ and $A\sqcup N=A$\quad 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 18. 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$) naturally 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 19. Find the Boolean Algebra ${\cal S}_2$ generated by two free statements $P$ and $Q$.

For a natural number $n$, let ${\cal D}_n$ denote the set of the divisors of $n$. For example, ${\cal D}_{42}=\{1,2,3,6,7,14,21,42\}$ and ${\cal D}_{12}=\{1,2,3,4,6,12\}$. For $m,n\in\mathbb{N}$ let $m\sqcap n$ denote the greatest common divisor of $n$ and $m$, and $m\sqcup n$ their least common multiple. For instance $6\sqcap 4=2$ and $6\sqcup 4=12$. It turns out that ${\cal D}_{42}$ with these two operations $\sqcap$ and $\sqcup$ forms a Boolean Algebra, while ${\cal D}_{12}$ does not.

Problem 20.

1. Verify Boolean Algebra Law 7 for ${\cal D}_{42}$.
2. Show that ${\cal D}_{12}$ does not form a Boolean Algebra.
3. Conjecture for which values of $n$ the set ${\cal D}_{n}$ forms a Boolean Algebra.