Correctness proof

algorithm reverse_string is
    input: a string s
    output: the string s reversed

    if s = "" (base case)
        return ""
    else (recursive case)
        let s' be a copy of s
        remove the last character t from s'
        return t + reverse_string(s')

Theorem: reverse_string correctly returns the reverse of \(s\), for every string \(s.\)
Proof by induction: Let's perform induction on \(n\), the length of the string \(s.\)
Base case:
\(n = 0 :\) reverse_string("") returns "" \(\checkmark\)
Inductive step:
Assume reverse_string correctly returns the reverse of a string for strings of length \(k \geq 0.\) We want to show reverse_string correctly returns the reverse of a string for strings of length \(k + 1.\) Since \(k + 1 \geq 1\), reverse_string will enter its recursive case when given a string of length \(k + 1\), that is, a string of the form: $$c_1 c_2 ... c_k c_{k+1}$$ Then, it takes the last character off the string and prepends it to what the call on a string of length \(k\) returns. This looks like: \(c_{k+1}\) + reverse_string(c_1 c_2 ... c_k) According to the inductive hypothesis, this call will correctly return the reverse of a string of length \(k.\) Therefore, concatenating the last character of the string to the front of its reverse without that last character will result in the reverse of that entire string: $$c_{k+1} + (c_k ... c_2 c_1)$$ $$c_{k+1} c_k ... c_2 c_1$$ Thus, it can be concluded that if reverse_string correctly returns the reverse of a string for strings of length \(k \geq 0\), then reverse_string correctly returns the reverse of a string for strings of length \(k + 1.\) By the principle of mathematical induction, reverse_string correctly returns the reverse of a string for strings of length \(n \geq 0.\) This range encompasses every string \(s\) that could be given to reverse_string. \(■\)

algorithm power_set is
    input: a set S
    output: the power set of S

    if S = {} (base case)
        return {{}}
    else (recursive case)
        let S' be a copy of S
        remove an element e from S'
        P ← power_set(S')
        let P' be a copy of P
        for each set A in P'
            add A ∪ {e} to P
        return P

Theorem: power_set correctly returns the power set of \(S\) for every finite set \(S.\)
Proof by induction: Let's perform induction on \(n\), the size of the set \(S.\)
Base case:
\(n = 0 :\) power_set({}) returns {{}} \(\checkmark\)
Inductive step:
Assume power_set correctly returns the power set of a set for sets of size \(k \geq 0.\) We want to show power_set correctly returns the power set of a set for sets of size \(k + 1.\) Since \(k + 1 \geq 1\), power_set will enter its recursive case when given a set of size \(k + 1.\) Then, it makes a call to itself to find the power set of \(S'\), which is just the given set \(S\) with \(1\) element, \(e\), removed. \(S'\) is therefore of size \(k\) since it has \(1\) fewer element. According to the inductive hypothesis, this call will correctly return the power set of a set of size \(k\): $$\mathcal{P}(S') = \set{\set{}, \set{s_1}, ... \set{s_1, ... s_k}}$$ Note that the element \(e\) is missing in all the sets in \(\mathcal{P}(S').\) What the algorithm ends up returning is a set that is effectively a union of \(\mathcal{P}(S')\) and a duplicate of \(\mathcal{P}(S')\) whose sets all include \(e\): $$\set{\set{}, \set{s_1}, ... \set{s_1, ... s_k}} \cup \set{\set{} \cup \set{e}, \set{s_1} \cup \set{e}, ... \set{s_1, ... s_k} \cup \set{e}}$$ To show this is equal to \(\mathcal{P}(S)\), we need to prove that any arbitrary subset of \(S\) is in \(\mathcal{P}(S)\) and that any arbitrary set in \(\mathcal{P}(S)\) is a subset of \(S.\)

1. Let's begin with proving the former. It is a fact that any arbitrary subset \(X\) of \(S\) either includes \(e\) or it does not.
   • If \(e \notin X\), then the subset can be found in \(\mathcal{P}(S').\) Since \(\mathcal{P}(S)\) is created by adding elements to \(\mathcal{P}(S')\), it includes every element in \(\mathcal{P}(S')\), so our arbitrary subset will show up in \(\mathcal{P}(S).\)
   • If \(e \in X\), then there is a corresponding version of that arbitrary subset that does not include \(e\), \(X - \set{e}\), which can be found in \(\mathcal{P}(S').\) Since the algorithm operates by duplicating \(\mathcal{P}(S')\) and adding \(e\) to every set in it, our arbitrary set will show up in the final \(\mathcal{P}(S)\) as \(X - \set{e} \cup \set{e} = X.\)
   Therefore, if \(X \subseteq S\), then \(X \in \mathcal{P}(S)\), as was computed by the algorithm.
2. Let's prove the latter. This'll be quick. Any arbitrary set \(Y\) in \(\mathcal{P}(S)\) is a subset of \(S'\), which itself is a subset of \(S\), or, it is one of the duplicated subsets that have the element \(e\), which is an element from \(S.\) There is no way for \(\mathcal{P}(S)\) to include anything not already in \(S\), as it is completely derived from \(S.\) Therefore, if \(X \in \mathcal{P}(S)\), then \(X \subseteq S.\)
3. Having proven both ways, we can now state: \(X \subseteq S\) if and only if \(X \in \mathcal{P}(S)\), indicating that the computed power set for \(S\) is correct.

Thus, it can be concluded that if power_set correctly returns the power set of a set for sets of size \(k \geq 0\), then power_set correctly returns the power set of a set for sets of size \(k + 1.\) By the principle of mathematical induction, power_set correctly returns the power set of a set for sets of size \(n \geq 0.\) This range encompasses every set \(S\) that could be given to power_set. \(■\)