Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Right off the bat, I want to make clear that my logic lecturer has adopted a rather non-standard form of the predicate calculus in which structures can be empty. Normally, structures are required to be non-empty in order to prevent this sort of thing from coming up, but it is in fact possible to allow empty structures if you adjust the modus ponens rule a bit.

I'm going to quote the following bit from my lecture notes and then explain what I don't understand about it ($\phi$ and $\psi$ refer to formulae throughout):

We don't always have $\{\phi,(\phi\Rightarrow\psi)\}\models\psi$: if $\phi$ has a free variable and $\psi$ doesn't, then $\phi$ and $(\phi\Rightarrow\psi)$ are always valid in the empty structure, even if $\psi$ is $\bot$.

Here's what I don't understand: since $\phi$ has a free variable, neither $\phi$ nor $(\phi\Rightarrow\psi)$ is a sentence. Therefore, to make any sense of the statement $\{\phi,(\phi\Rightarrow\psi)\}\models\psi$ we have to add constants to the language and substitute them for the free variables occuring in $\phi$ and $(\phi\Rightarrow\psi)$. But if the language contains constants then we cannot use the empty set as a structure. This seems to invalidate the above quotation. How am I wrong?

About $\Rightarrow$:

I am used to using $\Rightarrow$ as a symbol with the following special properties:

  • If $\phi$ and $\psi$ are formulae then $(\phi\Rightarrow\psi$) is a formula (Note - here, $\Rightarrow$ is just a symbol).
  • Let $A$ be a structure - i.e., a set $A$ equipped with a function $\omega_A:A^{\alpha(\omega)}\to A$ for each operation symbol $\omega$ and a function $\pi_A:A^{\alpha(\pi)}\to\{0,1\}$ for each predicate symbol $\pi$, the $n$-ary interpretation of the formula $(\phi\Rightarrow\psi)$ in $A$ is the function $(\phi\Rightarrow\psi)_A^{(n)}:A^n\to\{0,1\}$ which, given some element $(a_1,a_2,\dots,a_n)$ of $A^n$, takes the value $0$ if and only if $\phi_A^{(n)}(a_1,a_2,\dots,a_n)=1$ and $\psi_A^{(n)}(a_1,a_2,\dots,a_n)=0$.

You might be more used to using the symbol $\to$ in this way. If this is the case, then you have my apologies.

Definition of $\models$:

Given a formula $\phi$ and a structure $A$, we say that $\phi$ is satisfied in $A$ if the $n$-ary interpretation $\phi_A^{(n)}:A^n\to\{0,1\}$ of $\phi$ in $A$ is the constant function with value $1$. Given a set $T$ of sentences - formulae with no free variables - we define a model of $T$ to be a structure $A$ such that every member of $T$ is satisfied in $A$. If $\phi$ is a formula with no free variables, we say $T$ semantically entails $\phi$ and write $T\models\phi$ if $\phi$ is satisfied in every model of $T$.

If $\phi$ or some member of $T$ has a free variable, then we say $T\models\phi$ if $T'\models\phi'$, where $T'$ and $\phi'$ are formed from $T$ and $\phi$ by adding new variables to the language and substituting them in for the free variables in question. It was this that provoked my confusion: $\{\phi,(\phi\Rightarrow\psi)\}$ has free variables, so we must add constants to the language to make sense of $\{\phi,(\phi\Rightarrow\psi)\}\models\psi$. But if the language has constants, then the structure must be non-empty!

(Given the disparity between my lecturer's treatment of the subject and that of others, I can only assume that there is a parallel disparity between the vocabulary I have used and that you might be used to - I don't myself know any other words for formula, structure and so on, but if there's a term you don't recognize, I'll do my best to explain what it means, and maybe then you'll recognize what it is that I'm talking about.)

share|cite|improve this question
Most of your quote from the lecture notes seems to make sense if we assume the convention that a non-closed formula $\phi$ is true in a structure iff its universal closure is. Under this convention every formula with free variables would count as valid in the empty structure. What doesn't make sense is the final "... even is $\phi$ is $\bot$, because $\bot$ does not have a free variable. Probably that is a typo for "... even if $\psi$ is $\bot$". – Henning Makholm Apr 19 '12 at 16:08
Could you edit the question to rephrase and emphasize what exactly you're asking? Also, could you give the definition of $\models$ from your instructor's notes? You have defined a satisfaction function that takes a variable assignment but have not defined what $M \models \phi$ means. – Carl Mummert Apr 19 '12 at 18:43
As an aside, if $x = x$ is valid but $(\exists x)[x = x]$ is not, then more has to be changed in the deductive system than just modus ponens. – Carl Mummert Apr 19 '12 at 18:52
@Donkey_2009: thank you for adding those definitions to the question. I don't see how they match up, either. But given the way that a "structure" is defined there, I am curious how the truth value for a formula $t = s$ is obtained, given that if $A$ is empty then it seems like the "interpretation" of a constant symbol is the empty function. – Carl Mummert Apr 19 '12 at 21:27
(Are you at Cambridge by any chance?) – Clive Newstead Apr 19 '12 at 21:54
up vote 3 down vote accepted

You don't need constants: the structure could have a predicate $P$ with arity 1. Then we have $\{P(x), (P(x)\rightarrow\bot)\} \not\models \bot$ since in the (unique) model $A$ such that $P_A: \emptyset \rightarrow \{0,1\}$, $P(x)$ and $(P(x)\rightarrow\bot)$ are satisfied: there is a unique function from $\emptyset$ to $\{0,1\}$, so their interpretations are equal to the constant function 1.

The reason is that, as Henning pointed out, your definition of $\models$ adds universal quantifiers, so this simply says that $\forall x\ P(x)$ and $\forall x\ (P(x)\rightarrow\bot)$ are trivially true in the empty structure. And because of the quantifiers, you can't apply the modus ponens to derive a contradiction from that.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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