Would like to know which version of inductive formula is better

Question

In a 4-valued logic with values 0, 1/2, 2/3 and 1, three connectives are defined:

$V(\varphi \wedge \psi)$ = min $V((\varphi), V(\psi))$
$V(\varphi \vee \psi)$ = max $V((\varphi), V(\psi))$
$V(\diamond \varphi) = 1$ if $V(\varphi) \geq 2/3$, else 0

On formulas in the language composed of proposition letters and these three connectives we define a function $C$ that places the connective $\diamond$ in front of every proposition letter in the formula.

E.g.: $C((p \vee \diamond q) \vee q) = ((\diamond p \vee \diamond \diamond q)\vee \diamond q)$

The question:

Give an inductive definition of $C$

Inductive definitions have always given me troubles! I have the following versions of this inductive definition, and I just can't decide which version is better.:

Version 1:

base case:

$C(p) = \diamond p$

I never know what to write here, I got a plethora of possibilities and I never know which one I should take:

• If $\varphi$ is an atomic formula, then $C(\varphi) = \diamond \varphi$
• for all atomic formulas $\varphi$, $C(\varphi) = \diamond \varphi$
• for all atoms $\varphi$, $C(\varphi) = \diamond \varphi$
• If $p$ is an atomic formula, then $C(p) = \diamond p$
• For all atomic formulas $p$, $C(p) = \diamond p$
• For all atoms $p$, $C(p) = \diamond p$

Inductive step:

$C(\varphi \wedge \psi) = (C(\varphi) \wedge C(\psi))$
$C(\varphi \vee \psi) = (C(\varphi) \vee C(\psi))$
$C(\diamond \varphi) = \diamond (C(\varphi))$

Version 2:

With this one, I moved a step in the base case.

base case:

$C(p) = \diamond p$ and $C(\diamond p) = \diamond \diamond C(p)$

And the same trouble of which version to write like in version one

Inductive step:

$C(\varphi \wedge \psi) = (C(\varphi) \wedge C(\psi))$
$C(\varphi \vee \psi) = (C(\varphi) \vee C(\psi))$

Answer 1

Your first version looks fine. Here is one, albeit not very explicit (because the language details are implicit) way of presenting the definition. $C(\phi)$ is defined by induction on the structure of $\phi$:

• If $\phi \in \mathsf{Props}$, then $C(\phi) = \diamond\phi$;

• If $\phi$ is of form $\psi \circ \chi$ and $\circ \in \mathsf{Cons_2}$, then $C(\phi) = C(\psi) \circ C(\chi)$;

• If $\phi$ is of form $\diamond \psi$, then $C(\phi) = \diamond C(\psi)$;

where $\mathsf{Prop}$ and $\mathsf{Cons_2}$ are the sets of propositional letters and binary connectives respectively.

Answer 2

I also think your first version is perfectly fine. Note that as a definition by recursion on the complexity of $\phi$ (which is the more appropriate term) your second candidate is ill-defined.

The base clause of a recursive definition of some function $f: \mathcal{F} \rightarrow A$ (where $\mathcal{F}$ is the set of formulas and $A$ some set) says that $f(\phi) = f_{At}(\phi)$, where $f_{At}$ is some function from $At$ (the set of atoms from $\mathcal{F}$) to $A$ and $\phi \in At$.

The base clause of your second version, however, uses a function defined on the set $At \cup \lbrace \diamond \phi : \phi \in At \rbrace \not = At$. In other words, the base clause must be specified independently of the values of $f$.

One might try to repair your second version by putting $C(\diamond \phi) = \diamond \diamond C(\phi)$ to the recursive clauses, where $\phi \in \mathcal{F}$. But this repaired version yields wrong results. According to that definition $C((p∨\diamond q)∨q) = ((\diamond p \lor \diamond \diamond C(q)) \lor \diamond p) = ((\diamond p \lor \diamond \diamond \diamond q) \lor \diamond p) \not = ((\diamond p \lor \diamond \diamond q) \lor \diamond p)$.