# Confused by a step in the 'Rule C' proof in Mendelson's Logic Textbook

I've been working through 'Introduction to Mathematical Logic, 5th Ed' by Mendelson, and I've found a step in the proof of proposition 2.10 (Rule C) that I cannot understand.

In the proof of this proposition, on what is to me the fifth line, Mendelson writes:

'We replace $d_k$ everywhere by a variable $z$ that does not occur in the proof.'

I do not understand how Mendelson is justified in doing this step, it doesn't seem valid.

• I suggest to edit your post to be self-contained. This way, you enable people to help you that don't have access to a copy of Mendelson's book - like me. Jul 27 '16 at 14:02
• @Stefan The problem is that I believe an actual justification would require his book on hand, nevertheless I'll try in a bit to add the prior lines and the theorem statement Jul 27 '16 at 14:03

The step is valid.

Simplifying a little bit the case, we have to show that:

if $\Gamma \vDash \mathcal C(d) \to \mathcal B$, then $\Gamma \vDash \mathcal C(z) \to \mathcal B$,

provided that we have proved $\exists x \mathcal \ C(x)$.

Assume not, i.e. that we have an interpretation $M$ with domain $D$ and a sequence $s$ such that :

$M \vDash \Gamma, M,s \vDash \mathcal C(z)$ and $M \nvDash \mathcal B$.

But we have proved $\exists x \mathcal \ C(x)$ and this means that, in every interpretation $M$: $M \vDash \exists x \mathcal \ C(x)$.

This means that there is a sequence $s'$ such that $s'^*(x) \in D$ that satisfies $\mathcal C(x)$.

By Rule C, we have assigned to this element the "name" $d$, where $d$ is the new individual constant introduce with the rule.

Thus, we have that:

$M \vDash \Gamma, M \vDash \mathcal C(d)$ and $M \nvDash \mathcal B$

contradicting the fact that: $\Gamma \vDash \mathcal C(d) \to \mathcal B$.

• Is there any way to do this proof syntactically? Jul 27 '16 at 14:17
• @Nethesis - yes by induction; see van Dalen: "Let $x$ be a variable not occurring in $Γ$ or $\varphi$. If $Γ \vdash \varphi$, then $Γ[x/c] \vdash \varphi[x/c]$. Comment: "Although variables and constants are basically different, they share some properties. A variable can take the place of a constant in a derivation but in general not vice versa.Observe that the result is rather obvious, changing $c$ to $x$ is just as harmless as coloring $c$ red—the derivation remains intact." Jul 27 '16 at 14:30
• Okay, so as far as I can tell, the argument is that the only way one can introduce constants is via Axiom Schema (A4) in Mendelson, or by a proper axiom (not relevant as $d_k$ is new). If one introduces the constant by (A4), however, then one may also instead introduce a new variable $z$ in the same way, and every other rule for manipulating a formula containing $d_k$ also applies to that formula with $z$ used, instead? Jul 27 '16 at 14:37
• @Nethesis - exactly. Jul 27 '16 at 15:19