0
$\begingroup$

Let $L$ be a formal language. Let $\Gamma$ be a set of formulas of $L$. Let also $\rho: \{c_i\} \to \{c_i\}$ be a function defined by $\rho(c_i) = c_{2i}$. That is, a function which takes each constant to an even constant. Extend the definition of $\rho$ to terms and formulas in the most obvious manner so that if $\tau$ is a term, $\rho(\tau)$ is the same term with all constants changed to even ones. Similarly for $\rho(\phi)$ when $\phi$ is a formula and let $\rho(\Gamma) = \{\rho(\phi) \mid \phi \in \Gamma\}$.

Question: Show that if $\Gamma$ is consistent, then $\rho(\Gamma)$ is consistent.

My (partial) Proof: Suppose towards contradiction that $\Gamma$ is consistent but $\rho(\Gamma)$ is inconsistent. Then $\rho(\Gamma) \vdash (\phi \wedge \neg\phi)$ for some $\phi$. This means there is a sequence $\langle \sigma_1,...,\sigma_n \rangle$ such that $\sigma_n \equiv (\phi \wedge \neg\phi)$. I would like to claim that something like $\langle e(\sigma_1),...,e(\sigma_n) \rangle $ is a proof of $e(\phi \wedge \neg\phi)$ from $\Gamma$ and thus a contradiction. The question is which function $e$ to use.

The most obvious candidate is $\rho^{-1}$. However, this can only be defined for even constants but $\sigma_i$ could be an instance of an axiom or MP and thus contain odd constants as well. If I define a new function $e$ which behaves as $\rho^{-1}$ only for even constants, I am still going to have some problem in telling it how to behave on odd ones. In particular, it will most likely override constants already used. How could I go around this problem?

$\endgroup$
6
  • $\begingroup$ Since $\rho(\Gamma)$ does not mention odd constants at all, you can show (if you want to be formal, induct on the length of proof) that any proof from $\rho(\Gamma)$ is still valid if you just replace all odd constants with basically anything else - even constants or variables, say. So after that you get a proof of a contradiction from $\rho(\Gamma)$ which never mentions any odd constant. Now just apply $\rho^{-1}$. $\endgroup$
    – David Gao
    Commented Aug 14 at 9:13
  • $\begingroup$ @DavidGao If I convert a proof of $\phi$ from $\rho(\Gamma)$, that is $\langle \sigma_1,...,\sigma_n \rangle$ to a proof involving only even constants, I will have to apply some function to the $\sigma_i$. Presumably $\rho$. However, if $\sigma_i$ was originally in $\Gamma$, then $\rho(\sigma_i)$ will no longer be in $\rho(\Gamma)$, but $\rho(\rho(\Gamma))$ which is not the same. $\endgroup$
    – Promethèus
    Commented Aug 14 at 9:58
  • $\begingroup$ I’m not sure I understand what you meant. What I said is the following: if a set of formula $\Omega$ does not mention a constant $c$, then a proof $\langle \sigma_1, \cdots, \sigma_n \rangle$ from $\Omega$ is still valid if you replace all instances of $c$ in $\sigma_i$ to some other constant $d$, or some variable $x$ (that does not already occur boundedly in any $\sigma_i$). $\endgroup$
    – David Gao
    Commented Aug 14 at 10:07
  • 1
    $\begingroup$ Ah, I suppose I see what you meant. No, you’re not supposed to apply $\rho$. Instead, apply a function that sends even constants to themselves and odd constants to some even constants (for concreteness, say $c_0$). $\endgroup$
    – David Gao
    Commented Aug 14 at 10:15
  • $\begingroup$ Yes I think I understand. What I said was that if I replace all odd constants appearing in $\langle \sigma_1,...,\sigma_n\rangle$ with some even ones, I am worried I might be using again some of the constants already been used and thus disrupt the proof. Whereas you are saying this is not an issue. If I use some function $e$ which changes only odd constants to even ones, and leaves even ones unchanged, then it should work right? $\endgroup$
    – Promethèus
    Commented Aug 14 at 10:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .