7
$\begingroup$

It feels like a dumb question, but is it always the case that a false statement has a counterexample? Is there a proof of it (or of the contrapositive, if it has no counterexample it must be true)?

$\endgroup$
16
  • 2
    $\begingroup$ The statement $0=1$ has no counterexample in my opinion but is clearly False. $\endgroup$ Aug 28 '19 at 18:42
  • 3
    $\begingroup$ Does "counterexample" always make sense for any statement? For example, if "My name is Bill" is false, what exactly is a counterexample? One usually speaks of counterexamples for statements of the form "if A then B", so a counterexample would be a specific A and B for which the statement is false. $\endgroup$
    – MPW
    Aug 28 '19 at 18:43
  • 11
    $\begingroup$ Only false universal statements (statements that assert that something occurs "for all" things) are suceptible to counterexamples. $\endgroup$ Aug 28 '19 at 18:43
  • 6
    $\begingroup$ @ArturoMagidin That's not quite true - or rather, universality (and counterexample-ness) isn't entirely clear-cut. For example, take a statement of the form "For some $x$, every $y$ makes $P(x,y)$ hold" (for some property $P$). This statement is false iff the statement "for every function $f$ (of appropriate type) there is some $x$ such that $\neg P(x, f(x))$ holds" is true. Via this translation, we can view such a function $f$ as a counterexample to the original statement. Moreover, this is nontrivial - e.g. it's often interesting to ask how complicated such an $f$ must be (if it exists). $\endgroup$ Aug 28 '19 at 18:47
  • 1
    $\begingroup$ Well, if its false there must be false. I suppose we can wax philosophical as to what a "statement" and "example" mean. I suppose "unicorns exist" doesn't have a counterexample because the true statement "there are no such things as unicorns" isn't a positive statement about things but an absence of a things. Then again one could argue the universe itself, and the lack of unicorns,, therein is a counterexample. $\endgroup$
    – fleablood
    Aug 28 '19 at 18:48
8
$\begingroup$

The idea of counterexample makes sense only for statements that claim that a certain property is held by all members of a given class of objects.

That is, if we have some false claim

For all $m\in S,$ property $p$ holds,

then because it is false it is certain that there is at least some $m\in S$ for which $p$ fails to hold. There's not much more than this to prove. It follows immediately from the conditions.

$\endgroup$
14
  • $\begingroup$ The idea of a counterexample makes sense for any logical statement: a counterexample is a structure in which the statement fails to hold. E.g., the integers provide a counterexample for the statement $\forall x.x + x = 0$ in the language of abelian groups. $\endgroup$
    – Rob Arthan
    Aug 28 '19 at 21:57
  • $\begingroup$ @RobArthan I don't see how your example does not support my answer or buttresses your own point. As for your claim, what would you call a counterexample to the statement, $0=1,$ where $0,1\in\mathrm Z$? $\endgroup$
    – Allawonder
    Aug 28 '19 at 22:02
  • $\begingroup$ The structure comprising the integers provides a counterexample. $\endgroup$
    – Rob Arthan
    Aug 28 '19 at 23:32
  • $\begingroup$ @RobArthan That's a counterexample to the statement being semantically true. But we generally care about truth within some fixed context/model: e.g. when we say "$0=1$ is false" we don't mean "there is a structure not satisfying $0=1$," we mean "the standard model of arithmetic does not satisfy $0=1$." So I don't think that appropriately translates the question. $\endgroup$ Aug 29 '19 at 1:44
  • $\begingroup$ @NoahSchweber: I don't understand your comment: truth is a semantic concept so it is tautologous (in the English language sense of that term) to say "semantically true". What we mean when we say "$0 = 1$" is context-dependent: it is false in the context of integral domains as usually defined but neither true nor false in the context of rings. In the case of the theory of a specific structure like $\Bbb{N}$ in which $0 = 1$ fails to hold, that specific structure is the counter-example. $\endgroup$
    – Rob Arthan
    Aug 29 '19 at 22:45
2
$\begingroup$

As the comments have indicated, this isn't a very clear question. The problem lies in what "false" means or what "example" in "counterexample" means or, possibly, what "statement" means? Or I should say what they mean to you.

As others have pointed out, it's not clear what a "counterexample" to a statement like $0=1$ should mean. Most likely, you really mean counterexamples to universal statements like $\forall x.P(x)$ (e.g. $\forall x.x = 0$). Now there's a question of what "example" and, relatedly, what "false" should mean.

Before I go into a more precise and technical perspective, I'll give a kind of "pragmatic" answer. Assuming you mean universal statements like the above, it is not the case that you will be able to write down an explicit counterexample even if you prove that the statement is "false", in the sense that you prove its negation.

Now for the various perspectives that arise from being precise. First, if we define "false" as the negation is provable, so $P$ is "false" iff $\vdash\neg P$ and we define "example" as a term, then the answer is "no". To be precise, we have a formula $\forall x.P(x)$ and we have $\vdash\neg\forall x.P(x)$. Classically, this is equivalent to $\vdash\exists x.\neg P(x)$, but, classically, it does not need to be the case that there exists a term, $t$, in our language such that $\vdash\neg P(t)$ even when we know $\vdash\exists x.\neg P(x)$. This is different for constructive logic where we have the existence property which guarantees that if we can prove a (closed) existential formula, then there is some term that witnesses it. However, the answer to your question is still "no" for constructive logic because $\neg\forall x.P(x)$ is not equivalent to $\exists x.\neg P(x)$ in constructive logic.

Round two. Let's define "false" as semantically false with respect to some model $\mathfrak M$. We then would talk about $\mathfrak M\vDash P$ which states that when we interpret the closed formula $P$ with respect to the model $\mathfrak M$, which I'll write as $[\![P]\!]_\mathfrak M$, then it is interpreted as a "true" value. In general, for an open formula $[\![P]\!]_\mathfrak M$ is the set of (tuples of) elements of the domain that satisfy the interperation of $P$. Given this, it is the case that if $\mathfrak M\vDash\neg \forall x.P(x)$, then there is an element, $c$, of the domain of $\mathfrak M$ such that $c\in[\![\neg P(x)]\!]_\mathfrak M$. To relate this to the first case, it may be the case that there exists no term $t$ such that $[\![t]\!]=c$. With this definition, the answer to your question is "yes" by the definition of the semantics of existential quantification.

Round three. If we define "false" to mean the negation is semantically valid, written $\vDash\neg P$ which is shorthand for $\mathfrak M\vDash\neg P$ for all models $\mathfrak M$, then we can talk about countermodels which is basically a counterexample in the first sense of this meta-theoretic universal statement. That is, we find a model $\mathfrak M$ such that $\mathfrak M\vdash\neg P$ is false (in the sense of the second definition). Now $P$ doesn't itself need to be a universal statement. We can talk about countermodels to the formula $0=1$. This would be a model $\mathfrak M$ such that $[\![0]\!]_\mathfrak M\neq[\![1]\!]_\mathfrak M$. With this definition, the answer to your question is "no" but it's almost "yes". We do have a countermodel to $P$ when we know $\vDash\neg P$, any model will do, except if there are no models at all which will happen when your theory is inconsistent.

As a kind of Round two-and-a-half, we could consider defining "false" as $\nvDash P$ which states that $P$ isn't true in every model. It may be true in some but not others. The analysis of this just recapitulates the analysis we just did only at the meta-level. The meta-theory thinks that a countermodel exists in this case, but from a meta-meta-perspective whether we can write down a term to describe that countermodel is not given.

$\endgroup$
1
$\begingroup$

If by 'counter-example' you mean a world in which the statement is false, then yes: it would be the very world (or situation or context) in which you evaluated the statement to be false.

$\endgroup$

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.