[FOM] FOM Counterexample Theorems.

[John Corcoran]

FOM Counterexample Theorems.

A suitable first-order language L is interpreted in the set N of
[natural] numbers as universe of discourse.   Let n* be a numeral for n.
P(x) is an arbitrary formula with free x, as AyAz (x = (y + z))

Definition 1.   A number n is a counterexample for a universal sentence
Ax P(x) iff n satisfies not-P(x).  This definition makes it clear that
'is a counterexample for' expresses a semantic relation similar to
satisfaction. This means that counterexemplification is a relation from
individuals to interpreted sentences; just as satisfaction is a relation
from individuals to interpreted formulas. Beginners (and a few
non-beginners) need to be told (or reminded) that every sentence AxAy
R(x,y) is a sentence Ax P(x)-- with P(x) being Ay R(x,y). Thus this
definition is completely general. To be even more specific, the
definition implies that a number n is a counterexample for a universal
sentence AxAy R(x,y) iff n satisfies not-Ay R(x,y).

Q1.1. Where in the literature is this definition or an "equivalent"
explicitly stated or discussed?
Q1.2. Where in the literature can we find some theorems involving the
counterexample relation, the relation of an object being a
counterexample to a sentence (under an interpretation)?
Q1.3. What is known about the origin and history of the concept and the
word? Did its translations into other languages pre-date its coinage in
English or vice versa? What synonymous locutions have been used?

Definition 2. Two sentences are [logically] equivalent [LE] if each is a
consequence of the other.  In view of Goedel 1930, being LE is being
interdeducible.

Fact 1.  Not every two logically equivalent sentences have the same
counterexamples. 0 =1 is LE to Ax(x = 0 --> x = 1) which is LE to Ax(x =
1 --> x = 0).

Q2.1. Where in the literature is this fact explicitly stated,
exemplified or discussed?

Definition 3.  Let t be an ordered n-tuple. Let P be a formula with
exactly n free variables.  t is a countertuple for a universal closure
of P iff the assignment of the members of t to the variables of P in the
order of quantification satisfies not-P.  	

<0, 1> is a countertuple for AxAy(x>y); <1, 0> is a countertuple for
AyAx (x>y).

There are other ways of handling this.
Q3.1. Where in the literature is this definition or an alternative
explicitly stated or discussed?
Q3.2. What is know about the origin and history of the concept and the
word? Did its translations into other languages pre-date its coinage in
English or vice versa?


Fact 2.1.The ordered pair <n, m> is a countertuple for AxAy P(x,y) iff n
is a counterexample for AxAy P(x,y)  and m is a counterexample for Ay
P(n*,y). <0, 1> is a countertuple for AxAy(x>y), 0 is a counterexample
for AxAy(x>y and 1 is a counterexample for Ay(0>y). A countertuple is a
sequence of counterexamples.



Q4.1. Where in the literature is this fact explicitly stated,
exemplified, or discussed? 

FACT 3. Not every two logically equivalent sentences have the same
countertuples. 0 =1 is LE to AxAy(x = 0 --> (y = 1 --> x = y)) which is
LE to AxAy (x = 1 --> (y = 0 --> x = y)). And see fact 2.2 above.

Q5.1. Where in the literature is this fact explicitly stated or
discussed?

Question A: given two LE falsehoods Ax P(x) and Ax Q(x), how different
can their respective counterexample-sets be?
Q5.1. Where in the literature is this or a related question asked, even
implicitly?

Fact: There are LE falsehoods Ax P(x) and Ax Q(x) whose respective
counterexample sets are complements.

Question B: Does the phenomenon of being LE to a sentence having
different counterexamples apply only to "pathological" cases dreamed up
by logicians with time or is it of wide applicability?
Q6.1. Where in the literature is this or a related question asked, even
implicitly?

Numerical Counterexample-Set Theorem: given any falsehood F and any
non-empty definable set S of numbers, there is a false universal Ax P(x)
logically equivalent to F and having S as counterexample set.

Q6.1. Where in the literature is this or a related theorem proved, or
even stated, however implicitly?

General Counterexample-Set Theorem: Let L be any first-order language.
Let I be any interpretation of L.  Given any sentence F of L false in I
and any non-empty set S of individuals of I, there is a universal Ax
P(x) false in I, logically equivalent to the given sentence F, and
having S as counterexample set if and only if the set S is definable in
I by means of a formula Q(x) in L.

Q7.1. Where in the literature is this or a related theorem proved, or
even stated, however implicitly?

Definition 4. .   A number n is a proexample for an existential sentence
Ex P(x) iff n satisfies P(x).  This definition makes it clear that 'is a
proexample for' expresses a semantic relation similar to satisfaction. 

Q8.x. Ask all of the questions above substituting proexample for
counterexample.

Fact 5. 1. Classically, in order for AxP(x) to be false it is necessary
and sufficient for it to have some number as a counterexample.
Classically, in order for AxP(x) to be known to be false it is neither
necessary nor sufficient for some number to be known to be a
counterexample for it. 
Fact 5. 2. Classically, in order for ExP(x) to be true it is necessary
and sufficient for it to have some number as a proexample. Classically,
in order for ExP(x) to be known to be true it is neither necessary nor
sufficient for some number to be known to be a proexample for it.
NB: I am fully aware that non-classical thinkers disagree with these
claims. I do not need to be reminded of the question-begging "arguments"
against them. 
Fact 5.3: It is inappropriate to metaphorically substitute any of the
following for 'counterexample': 'prosecution witness', 'whistle-blower',
'disprover', 'disproof', etc. Counterexemplification is an objective
semantic relation just like satisfaction; it is not a subjective
epistemic relation. Likewise inappropriate is saying anything to the
effect that a counterexample disproves, refutes, destroys, contradicts,
or annihilates an interpreted universal sentence.
It is likewise inappropriate to metaphorically substitute any of the
following for 'proexample': 'defense witness', 'guarantor, 'prover',
'proof', etc. Proexemplification is also an objective semantic relation.
Likewise inappropriate is saying anything to the effect that a
proexample proves, establishes, demonstrates, or guarantees an
interpreted existential sentence.

Such inappropriate usage is at best misleading, at worst deceptive or
fallacious.	
Q9.x. Using the above as models ask suitable questions about these
facts.
NB: Of course, the words 'counterexample' and 'proexample' have been
used in other senses. Very few, if any, English words are unambiguous.

Thanks to M. Brown, R. Butrick, M. Davis, J. Miller, A. Urquhart, A.
Visser, and G. Weaver
-