Substitutions as mappings from the set of Propositional Variables to the set of Formulas

Question

Rautenberg defines substitutions in propositional calculus as follows:

" A (propositional) substitution is a mapping σ : PV →F that is extended in a natural way to a mapping σ : F → F "

PV: set of propositional variables
F = set of formulae

In my understanding, substitution is a function with three arguments:

1 - The formula "f" in which the substitution takes place, an element of F
2 - The variable "a" in f which is replaced, an element of PV
3 - The variable "b" which replaces "A", an element of PV

In other words, a triple defined as: {f,a,b} $\rightarrow$ F

The mapping would then be described by F $\cup$ PV $\to$ F

Am I wrong?

Answer 1

Your understanding is not wrong (though you really ought to view substitution at least as something that can swap in an entire formula for your chosen variable, and writing $F\cup PV$ is a mistake since every propositional variable is in particular a formula), but it is a different angle on things than Rautenberg's (slightly more general) definition.

In your view "substitution" is one particular mapping $$ \operatorname{subst}: PV\times F\times F\to F $$ but only that one mapping. Not everything that is $PV\times F\times F\to F$ is substitution.

On the other hand, to Rautenberg every map of the form $PV\to F$ is a substitution, and there are many different substitutions. Once some $\sigma:PV\to F$ is given we can define $\sigma^*: F\to F$ recursively: $$\begin{align} \sigma^*(X) &= \sigma(X) \\ \sigma^*(P\Rightarrow Q) &= \sigma^*(P) \Rightarrow \sigma^*(Q) \\ \sigma^*(P\land Q) &= \sigma^*(P) \land \sigma^*(Q) \\ \sigma^*(P\lor Q) &= \sigma^*(P) \lor \sigma^*(Q) \\ \sigma^*(\neg P) &= \neg\sigma^*(P) \end{align} $$ (this is what is meant by "extended in a natural way to $F\to F$" except Rautenberg doesn't write the $*$ superscript; I'm inserting it here for clarity).

The connection between the two notions is the following: Your $\operatorname{subst}(X,P,Q)$ is the same as $[X\mapsto P]^*(Q)$ where $[X\mapsto P]$ is the map $PV\to F$ defined by $$ [X\mapsto P](Y) =\begin{cases} P & \text{when }Y=X \\ Y &\text{otherwise} \end{cases} $$

You should be able to convince yourself that this works out to be the same as your preferred notion of substitution.

The formalism you quote from Rautenberg is slightly more general, because there is, for example, a $\sigma$ that corresponds to interchanging two propositional variables $X$ and $Y$, something that is not easy to write down using a $PV\times F\times F\to F$ substitution operation.

Answer 2

In Rautenberg's approach, a substitution is a function $\sigma : PV \to \mathcal F$ defined on the set $PV = \{ p_0, p_1, \ldots \}$ of propositional variables (see page 4).

Thus, the function is defined for all variables; assume, e.g. :

$\sigma(p_0)=\alpha$ and $\sigma(p_i)=p_i$, for $i > 0$.

Then, we have to apply the substituion $\sigma$ to a formula, e.g. $p_0 \lor \lnot p_0$. The result will be :

$(p_0 \lor \lnot p_0)^{\sigma}= \alpha \lor \lnot \alpha$.

With another formula, like : $p_0 \land p_1$, the result (for the same substitution $\sigma$) will be :

$(p_0 \land p_1)^{\sigma}= \alpha \land p_1$.