[proofplan] The language $L$ is built inductively as $L = \bigcup_{n=0}^\infty L_n$, where $L_0 = P \cup \{\bot\}$ and $L_{n+1} = L_n \cup \{(p \Rightarrow q) : p, q \in L_n\}$. A valuation is, by definition, a map $v: L \to \{0,1\}$ satisfying $v(\bot) = 0$ and the implication rule $v(p \Rightarrow q) = 0 \iff (v(p) = 1 \text{ and } v(q) = 0)$. Part (1) (uniqueness) follows by induction on $n$: agreement on $L_n$ propagates to $L_{n+1}$ because the value on an implication is forced by the values of its subformulas. Part (2) (existence) constructs the valuation level by level, starting from $w$ on $P$ and $v(\bot) = 0$, and extending at each stage using the implication rule; uniqueness is then part (1). [/proofplan] [step:Recall the inductive construction of $L$ and the definition of a valuation] The language $L$ is defined as the union $L = \bigcup_{n=0}^\infty L_n$, where \begin{align*} L_0 &= P \cup \{\bot\}, \\ L_{n+1} &= L_n \cup \{(p \Rightarrow q) : p, q \in L_n\}. \end{align*} A **valuation** is, by definition, a map \begin{align*} v: L &\to \{0, 1\} \end{align*} satisfying \begin{align*} v(\bot) &= 0, \\ v(p \Rightarrow q) &= \begin{cases} 0 & \text{if } v(p) = 1 \text{ and } v(q) = 0, \\ 1 & \text{otherwise,} \end{cases} \end{align*} for all $p, q \in L$. In particular, the value of $v$ on $(p \Rightarrow q)$ is a deterministic function of the pair $(v(p), v(q))$. [/step] [step:Prove part (1) — uniqueness — by induction on the level $n$] Let $v, v'$ be valuations with $v(p) = v'(p)$ for all $p \in P$. We prove by induction on $n \ge 0$ that $v(r) = v'(r)$ for every $r \in L_n$. **Base case ($n = 0$).** Since $L_0 = P \cup \{\bot\}$, a formula $r \in L_0$ is either a propositional variable $p \in P$, in which case $v(r) = v(p) = v'(p) = v'(r)$ by hypothesis, or $r = \bot$, in which case $v(\bot) = 0 = v'(\bot)$ by the definition of a valuation. **Inductive step.** Assume $v = v'$ on $L_n$. Let $r \in L_{n+1}$. Either $r \in L_n$, in which case $v(r) = v'(r)$ by the induction hypothesis, or $r = (p \Rightarrow q)$ with $p, q \in L_n$. In the latter case, the induction hypothesis gives $v(p) = v'(p)$ and $v(q) = v'(q)$. By the implication rule, \begin{align*} v(p \Rightarrow q) &= \begin{cases} 0 & \text{if } v(p) = 1 \text{ and } v(q) = 0, \\ 1 & \text{otherwise,} \end{cases} \end{align*} and identically for $v'$. Since $(v(p), v(q)) = (v'(p), v'(q))$, the two case-splits produce the same output: $v(p \Rightarrow q) = v'(p \Rightarrow q)$. Hence $v = v'$ on $L_{n+1}$, completing the induction. Since every $r \in L$ lies in some $L_n$, we conclude $v = v'$ on $L$. [guided] Let $v, v'$ be valuations agreeing on the set $P$ of propositional variables. We wish to show they agree on all of $L$. Since $L$ is built up level by level from $P \cup \{\bot\}$ by iterated application of the implication constructor, the natural strategy is **induction on the level** $n$. The key observation is that the valuation rule \begin{align*} v(p \Rightarrow q) &= \begin{cases} 0 & \text{if } v(p) = 1 \text{ and } v(q) = 0, \\ 1 & \text{otherwise,} \end{cases} \end{align*} expresses $v(p \Rightarrow q)$ as a *deterministic function* of the two values $v(p)$ and $v(q)$. Therefore, if $v$ and $v'$ agree on $p$ and $q$, they are *forced* to agree on $(p \Rightarrow q)$. **Base case ($n = 0$).** We have $L_0 = P \cup \{\bot\}$. For $r = p \in P$, $v(p) = v'(p)$ by hypothesis. For $r = \bot$, $v(\bot) = 0 = v'(\bot)$, since every valuation is required (by definition) to send $\bot$ to $0$. Thus $v = v'$ on $L_0$. **Inductive step.** Suppose $v = v'$ on $L_n$. Take any $r \in L_{n+1}$. There are two possibilities from the definition of $L_{n+1}$: either $r$ already lies in $L_n$ (nothing new to check — the induction hypothesis applies), or $r$ is a *new* formula of the form $(p \Rightarrow q)$ with $p, q \in L_n$. In the latter case, the induction hypothesis gives $v(p) = v'(p)$ and $v(q) = v'(q)$. Applying the implication rule to both $v$ and $v'$ with the same inputs yields the same output: \begin{align*} v(p \Rightarrow q) &= v'(p \Rightarrow q). \end{align*} Thus $v = v'$ on $L_{n+1}$. By induction, $v = v'$ on every $L_n$, and since $L = \bigcup_{n=0}^\infty L_n$, we have $v = v'$ on $L$. Why does this argument work? Because the valuation rule leaves *no choice* once the values on subformulas are fixed. Compare with the *parsing* of formulas: a formula $r \in L_{n+1} \setminus L_n$ has a unique decomposition $r = (p \Rightarrow q)$ (this is part of the well-formed-formula definition of $L$), so there is exactly one pair $(p, q)$ whose values determine $v(r)$. [/guided] [/step] [step:Prove part (2) — existence — by constructing $v$ level by level] Let $w: P \to \{0, 1\}$ be an arbitrary function. We construct a valuation $v: L \to \{0, 1\}$ extending $w$ by defining $v$ on $L_n$ inductively and verifying the valuation axioms at each stage. **Stage $n = 0$.** Define $v: L_0 \to \{0,1\}$ by \begin{align*} v(r) &= \begin{cases} w(r) & \text{if } r \in P, \\ 0 & \text{if } r = \bot. \end{cases} \end{align*} In particular, $v(\bot) = 0$, which is the required value. **Stage $n + 1$.** Suppose $v$ has been defined on $L_n$ and satisfies the implication rule for all $(p \Rightarrow q) \in L_n$ (vacuously at $n = 0$, since $L_0$ contains no implications). Extend $v$ to $L_{n+1}$ by keeping its previous values on $L_n$ and setting, for each new formula $(p \Rightarrow q) \in L_{n+1} \setminus L_n$ with $p, q \in L_n$, \begin{align*} v(p \Rightarrow q) &:= \begin{cases} 0 & \text{if } v(p) = 1 \text{ and } v(q) = 0, \\ 1 & \text{otherwise.} \end{cases} \end{align*} This is well-defined because $L_{n+1} \setminus L_n$ consists of formulas of the form $(p \Rightarrow q)$ with uniquely determined subformulas $p, q \in L_n$, on which $v$ has already been defined. **Taking the union.** Define $v: L \to \{0,1\}$ by setting $v(r) := v(r)$ where $r \in L_n$ for the smallest $n$ with $r \in L_n$; since the stages extend one another consistently, this is well-defined on $L = \bigcup_{n} L_n$. **Verification that $v$ is a valuation.** We must verify: (i) $v(\bot) = 0$, which holds by construction at stage $0$; and (ii) for all $p, q \in L$, the implication rule holds for $(p \Rightarrow q)$. Given $p, q \in L$, choose $n$ with $p, q \in L_n$; then $(p \Rightarrow q) \in L_{n+1}$, and by definition of $v$ on $L_{n+1}$, \begin{align*} v(p \Rightarrow q) &= \begin{cases} 0 & \text{if } v(p) = 1 \text{ and } v(q) = 0, \\ 1 & \text{otherwise.} \end{cases} \end{align*} So the implication rule holds. **Extension of $w$.** By the base case, $v(p) = w(p)$ for all $p \in P$. **Uniqueness.** Uniqueness is exactly part (1), applied to any two valuations extending $w$. [/step]