HW1 Solutions Page

1. 1. `{4}` size `1`
   2. `{3,6}` size `2`
   3. `{1, 2, 4, 5, {1, 2, 4, 5}}` size `5`
   4. `{emptyset, {3}, {4}, {6}, {3,4}, {4,6}, {3,6}, {3,4,6}}` size `8`
   5. `{(1,3), (1,4), (1,6), (2,3), (2,4), (2,6), (4,3), (4,4), (4,6), (5,3), (5,4), (5,6)}` size `12`
2. The base case is `n=0`, I was assuming `n in NN`. For `n=0`, note `P(S^0(emptyset)) = P(emptyset) = {emptyset}` and this set has `1=2^0` elements. So the statement holds in the base case. For our induction hypothesis we assume `|P(S^n(emptyset))| = 2^n`. Next we try to show `|P(S^(n+1)(emptyset))| = 2^(n+1)`. Notice by the definition of successor set `S^(n+1)(emptyset) = S^(n)(emptyset) cup {S^(n)(emptyset)}`. `P(S^(n+1)(emptyset))` is the set of all subsets of `S^(n+1)(emptyset)`. Let `X=S^(n+1)(emptyset)`. A set `Z` that is a subset of `X` contains `0` or more elements of `S^(n)(emptyset)` and either contains `S^(n)(emptyset)` as an element or does not. The subsets of `X` of that don't contain `S^(n)(emptyset)`, are just elements of `P(S^(n)(emptyset))`, so by the induction hypothesis there are `2^n` of these. Let `Y` be a subset of `X` containing `S^(n)(emptyset)`. Consider the map from the subsets of `X` containing `S^(n)(emptyset)` to `P(S^(n)(emptyset))` given by `Y mapsto Y'= {v | v in Y ^^ v !=S^(n)(emptyset))}` it is not hard to see this is a bijection between these two sets. So by the induction hypothesis, this later set also has `2^n` elements. The total number of elements in `P(S^(n+1)(emptyset)))` is the sum of the number of elements in these two parts (subsets that don't contain `S^(n)(emptyset)` and those that do). The sum of these two part as we have just shown has `2^n + 2^n = 2cdot 2^n = 2^(n+1)` elements, thus, establishing the induction step and proving the statement.
3. `S^4(0) cdot S^5(0) = ` (by d)
   `S^4(0) cdot S^4(0) + S^4(0) =` (by d)
   `S^4(0) cdot S^3(0) + S^4(0) + S^4(0) = `(by d)
   `S^4(0) cdot S^2(0) + S^4(0) + S^4(0) + S^4(0)= `(by d)
   `S^4(0) cdot S^1(0) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= `(by d)
   `S^4(0) cdot 0 + S^4(0) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= `(by c)
   `0 + S^4(0) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S(0 + S^3(0)) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S^2(0 + S^2(0)) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S^3(0 + S^1(0)) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S^4(0 + 0) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= ` (by a)
   `S^4(0) + S^4(0) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S(S^4(0) + S^3(0)) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S^2(S^4(0) + S^2(0)) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S^3(S^4(0) + S^1(0)) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S^4(S^4(0) + 0) + S^4(0) + S^4(0) + S^4(0)= ` (by a)
   `S^8(0) + S^4(0) + S^4(0) + S^4(0)= ` (by b)
   `S(S^8(0) + S^3(0)) + S^4(0) + S^4(0)= ` (by b)
   `S^2(S^8(0) + S^2(0)) + S^4(0) + S^4(0)= ` (by b)
   `S^3(S^8(0) + S^1(0)) + S^4(0) + S^4(0)= ` (by b)
   `S^4(S^8(0) + 0) + S^4(0) + S^4(0)= ` (by a)
   `S^(12)(0) + S^4(0) + S^4(0)= ` (by b)
   `S(S^(12)(0) + S^3(0)) + S^4(0)= ` (by b)
   `S^2(S^(12)(0) + S^2(0)) + S^4(0)= ` (by b)
   `S^3(S^(12)(0) + S^1(0)) + S^4(0)= ` (by b)
   `S^4(S^(12)(0) + 0) + S^4(0)= ` (by a)
   `S^(16)(0) + S^4(0)= ` (by b)
   `S(S^(16)(0) + S^3(0))= ` (by b)
   `S^2(S^(16)(0) + S^2(0))= ` (by b)
   `S^3(S^(16)(0) + S(0))= ` (by b)
   `S^4(S^(16)(0) + 0)= ` (by a)
   `S^(20)(0) `
   
4. Let `A`, `B`, `C`, `D` be the inputs to the function. The formula is `(A wedge B wedge not C wedge not D) vv (not A wedge B wedge C wedge not D) vv (not A wedge not B wedge C wedge D) vv (A wedge not B wedge not C wedge D) vv (not A wedge B wedge not C wedge D) vv (A wedge not B wedge C wedge not D)`.
5. For machine `M_1'`
   
   1. `q_1`
   2. `{q_3}`
   3. `q_1`, `q_2`, `q_3`, `q_1`, `q_1`
   4. No
   5. No
   For machine `M_1'`
   
   1. `q_1`
   2. `{q_1, q_3, q_4}`
   3. `q_1`, `q_1`, `q_1`, `q_2`, `q_4`
   4. Yes
   5. Yes