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.

  • 1
    $\begingroup$ 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. $\endgroup$ Jul 27 '16 at 14:02
  • $\begingroup$ @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 $\endgroup$
    – Nethesis
    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$.

  • $\begingroup$ Is there any way to do this proof syntactically? $\endgroup$
    – Nethesis
    Jul 27 '16 at 14:17
  • 1
    $\begingroup$ @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." $\endgroup$ Jul 27 '16 at 14:30
  • $\begingroup$ 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? $\endgroup$
    – Nethesis
    Jul 27 '16 at 14:37
  • 1
    $\begingroup$ @Nethesis - exactly. $\endgroup$ Jul 27 '16 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.