1
$\begingroup$

I was learning mathematical logic in the context of (some) model theory and FOL using the language of L-structures (or just structures). Recall the definition of an L-structure. Its a set together with a language $L$ and way to interpret formulas and sentences formed from those symbols, usually denoted as (page 25 these notes):

$$ \mathcal A = ( A; L ) = (A; (R^{\mathcal A})_{R \in L^R,} (F^{\mathcal A})_{F \in L^F} )$$

L-structures make things completely unambiguous and was trying to arrive to a formulation to understand why in "standard logic" (informally speaking about mathematics/meta-logic) we consider statements of the form:

" all elements of the empty set have property P(x)"

to be true. After reading the wikipedia article of vacuous truth it became clear to me that for vacuous truths (which I will define it as when "the set $A$ is empty") of the informal form:

$$ \forall x \in A : Q(x)$$

must be equivalent to:

$$ \forall x (\varphi^A(x) \to Q(x)) $$

for some definable set (i.e. $\varphi^A = \{ a \in A : \mathcal A \models \varphi( \underline a) \}$ where $\underline a$ is the name of $a$) using L-formula $\varphi^A$. This is the only way for this to make sense since if the definable set $\varphi^A$ is empty (or \varphi^A) is always False, then it would make sense that whole L-sentence to be True (from the definition of material implication, since nothing is an element of the empty set). In other words if one takes such an $\varphi^A$ and defines the short hand $x \in \varphi^A =\emptyset $ just to be $\varphi^A(x) = False$ then one can express the above "vacuous truth" as follows:

$$ \forall x (x \in \emptyset \to Q(x)) $$

and its clear that the statement is true.

However, for me the natural interpretation was that:

$$ \forall x \in A : Q(x)$$

should be the L-sentence:

$$ \forall x Q(x)$$

under the L-structure $\mathcal A = (A ; L)$ (and allow $A$ to be empty of course). If one takes that interpretation then intuitively it becomes clear that since no element exists that can never be true, so the L-sentence should be False. So my question is:

  1. why are vacuous truths not defined that way but instead favour the material implication definition?
  2. Is the main reason that its defined with the material implication definition because L-structures cannot be empty for some reason? (why can't they be empty?)

I think its interesting to bring up also the informal notion of:

$$ \exists x \in A : Q(x)$$

(as well as the one considered originally in the question $ \forall x \in A : Q(a)$)). The reason is because how would we interpret $ \exists x \in A : Q(a)$? If we interpret it as:

$$ \exists x ( \varphi^A(x) \to Q(x) ) $$

then it would seem to be that this would also should evaluate to true vacuously. Is this correct?


If we accept that the right interpretation of

$$ \forall x \in A : Q(x)$$

is:

$$ \forall x Q(x)$$

in some empty L-structure then it does make sense that its true if we accept the following:

$$ \forall x Q(x) = \land_{a \in A} Q(a)$$

i.e. that the for all is a conjunction as large as we might need it. If we accept this as the definition/model for fall statement then that would be an empty conjunction, which are defined to be True. This is because we can always tac on an empty conjunction the same way we can add 0 and for the proposition to remain unchanged under conjunction an empty conjunction must be true. In other words:

$$ P \land (\land_{a \in \emptyset } Q(a) ) = P \land True = P$$

similarly for exists we must have an "infinite disjunction":

$$ \exists x Q(x) = \lor_{a \in A} Q(a)$$

and when its empty be defined to be zero (since tacking on a empty disjunction and let things unchanged, then the disjunction must be originally have been False):

$$ P \lor (\lor_{a \in \emptyset } Q(a) ) = P \lor False = P$$

honestly, this is the only definition that seems consistent to me and makes sense and doesn't randomly introduce material implication out of the blue and then doesn't explain if we should add material implication also out of the blue to exists. So I think this is the one that makes most sense to me. I hope its correct, but really only care to know the truth.


I also want to emphasize that the two interpretations are not logically equivalent (in a fixed large L-structure $\mathcal A'$ where $A \subseteq A$) since:

$$ \forall x Q(x) \not \equiv \forall x ( \varphi^A(x) \to Q(x) )$$

one can see this by writing $\varphi^A(x) \to Q(x)$ as $ \neg \varphi^A(x) \lor Q(x)$. Thus, for them to be equivalent we need:

$$ \neg \varphi^A(x) \lor Q(x) \equiv Q(x) $$

which are only equivalent when $\neg \varphi^A(x) = False $ so when $\varphi^A(x) = True$. So if $A$ is empty and thus $\varphi^A(x)$ always true, means that the implication interpretation of the statement $\forall x \in A: Q(x)$ is NOT equivalent to $\forall x Q(x)$. Intuitively it should be obvious because $\forall x Q(x)$ requires some property of every element in the L-structure (the universe in question) while $\forall x (\varphi^A(x) \to Q(x))$ only requires it for things in $A$ (not that for things not in $A$ play no role in determining the truth of the for all statement because they are always true since $\varphi^A(x)$ is false so the implication is true. I see it as the "trick" of how material implications invoke the identity of conjunctions to make things that play no rule in determining the consequent affect the truth value of the whole implication).


I've also read somewhere that some inference rules are NOT valid when the structure is empty (some inference rules having to do with quantifiers). What are they and why are they not valid?

$\endgroup$
9
  • 2
    $\begingroup$ The prohibition on empty structures is mainly just a ridiculous historical artifact. It makes some definitions and statements a little more convenient, makes others less convenient, and confuses lots of people into thinking there is actually something wrong with empty structures when there isn't anything wrong with them at all. $\endgroup$ Commented Nov 15, 2018 at 5:35
  • 2
    $\begingroup$ The rules of inference $P \vdash \exists x~.~P$ and $\forall x~.~ Q \vdash Q$ don't hold in empty structures (take $P = \top$ and $Q = \bot$), that is the reason for excluding empty structures afaik. $\endgroup$
    – DanielV
    Commented Nov 15, 2018 at 5:40
  • 2
    $\begingroup$ @DanielV: I would say that that is a reason to reject those rules of inference, not to reject empty models. Indeed, in ordinary informal mathematical reasoning, those are not valid rules of inference since there is typically no guarantee that our domain of discourse is nonempty. $\endgroup$ Commented Nov 15, 2018 at 5:42
  • 2
    $\begingroup$ vacuous truth is only a "nickname" and not a formal definition. According to the rules for connectives, $\forall x (Px \to Qx)$ is True in an interpretattion with domain $D$ if there are no $P$s in $D$, simply because for every $a \in D$ $Pa$ does not hold and thus $Pa \to Qa$ is True. $\endgroup$ Commented Nov 15, 2018 at 7:07
  • 2
    $\begingroup$ And this is not a definition but a fact. We like (?) to call this fact : "vacuous truth". $\endgroup$ Commented Nov 15, 2018 at 7:08

1 Answer 1

1
$\begingroup$

As I was writing this I realized one interesting thing. If we take my interpretation of:

$$ \forall x \in A : Q(a)$$

to be:

$$ \forall x Q(x)$$

in the L-structure $\mathcal A = ( \emptyset; L)$ (assuming that empty L-structures are ok for a second) then we actually get a bit problem. For the above to take any truth value either $Q(a)$ must be always false for all $a \in A$ or some $a \in A$ must make $Q(a)$ true. Since the L-structure (which is basically the model or the "world" which things are either true or false) has an empty set, then we can actually never instantiate anything to check $Q(x)$, which is problematic. This operation is undefined or we need to define something strange like an "empty element" and then say what every logical statements returns when considered with the empty element. It probably isn't a big deal to do this because semantic truth is defined inductively so we can capture what to do with the empty element at the base case, but it seems not only inelegant but its unclear that we actually gain anything from doing this (unlike in programming which defining, say, the empty string actually does something). So we are faced with deciding what $Q(x)$ means when the L-structure has nothing. Since this seems useless, we disallow such things to avoid such definitions or because $Q(x)$ just isn't defined for empty sets.

Instead, it seems that a much more natural approach is that $A$ is much more likely to be a specific set in some larger universe of mathematics (the real L-structure in question). This is a lot more flexible because we can talk about sets that arise form a specific L-structure, instead of considering a new universe of mathematics where truth is defined every time we ask a question. Thus, we choose that the material implication definition (and assume some larger universe/L-structure implicitly that is none-empty) with the following L-sentence:

$$ \forall x (\phi^A(x) \to Q(a)) $$

or as a short hand for $\varphi^A(x)$ we adopt the notation:

$$ \forall x (x \in A \to Q(a)) $$

where we note that $x \in A$ is a short hand for the L-formula $\phi^A(x)$ thus is 100% rigorous (unlike $ \forall x \in A : Q(a)$ that is not rigorous).

$\endgroup$
10
  • $\begingroup$ comments on why this is wrong would be extremely helpful. My answer seems 100% reasonable and if its not I'd like to know what is actually mathematically correct. $\endgroup$ Commented Nov 15, 2018 at 5:38
  • 1
    $\begingroup$ There is absolutely no difficulty with defining the truth value of $\forall x Q(x)$ in $\mathcal{A}=(\emptyset; L)$. Following the definition on page 25 of the notes you linked, $\mathcal{A}\models \forall x Q(x)$ iff $\mathcal{A}\models Q(\underline{a})$ for all $a\in \emptyset$. The latter condition is true vacuously, and so $\mathcal{A}\models \forall x Q(x)$ is true. $\endgroup$ Commented Nov 15, 2018 at 5:40
  • 1
    $\begingroup$ In an empty domain every formula of the form $\forall x A(x)$ will be TRUE and every formula of the form $\exists x B(x)$ will be FALSE. $\endgroup$ Commented Nov 15, 2018 at 13:54
  • $\begingroup$ What Mauro wrote is correct, under the definitions in the notes that the OP linked. There is an alternative definition of truth, which includes along with each structure a valuation function from the set of variables to the domain of the model. Since the set of variables is nonempty, there is no such function, and so so depending on how the exact definition of $\vDash$ is phrased other things can happen. $\endgroup$ Commented Nov 15, 2018 at 14:58
  • 1
    $\begingroup$ @MauroALLEGRANZA no I disagree. If I write the formal statement $\forall x B(x)$ (in some L-structure $\mathcal A = (A;L)$) it means that and nothing else. If we informally say something else like $\forall x \in A : B(x)$ ok fine there might be different interpretations and thats what part of my confusion stems from. But if I write the statement $\forall x B(x)$ that is not equivalent to $\forall x (D(x) \to B(x))$. How can it? the original statement doesn't even talk about $D(x)$! As formal statements in FOL (from notes I posted) $\forall x B(x) \not \equiv \forall x (D(x) \to B(x))$. $\endgroup$ Commented Nov 16, 2018 at 17:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .