Herewith a bit of fun. I daresay my understanding has evolved since publication.
Someone has my gratitude for preserving this "lost" piece on Archive, where I discovered it recently.
Also please see
'Vacuous truth' step by step
http://madmathzera.blogspot.com/2017/10/vacuous-truth-step-by-step.html
Welcome to N-fold, a [now defunct] web site for oft-eccentric thoughts on math and science.
Often in mathematics, we hear that a statement is vacuously true. Just what is vacuous truth?
An email discussion on vacuous truth took place in May 2001 among Amherst logician Dan Velleman, who wrote the introductory logic text, How to Prove It (Cambridge 1994), math columnist John Paulos, of Temple University, who has written professionally on logic, Cornell topologist Jim Conant, and Conant's dad, math student Paul Conant.
The discussion arose after Jim pointed out that statements of the form "all a e A P(a)" are always true if A is empty [the letter "e" is the element symbol], prompting Paul to attempt a general definition of "vacuous truth."
[Paul's idea for an alternative set theory axiom stating that no set with an infinite number of elements exists, which appears near the bottom of this webpage, was not discussed by the professional mathematicians, nor did they discuss his remarks on 'nebulous' prime conjectures.]
Jim's point arose in a discussion of vacuously true relations in which Dan noted that, if A is empty, then
all a e A((a,a) e R) and all a e A((a,a) ~e R)
are both true statements.
Paul then proposed that a vacuously true statement be defined as one in which modus ponens (and modus tollens) does not hold, but Dan objected.
Paul:
" [If] p-->q and p is known to be false [and so] modus ponens can't be used to infer q [then] p-->q is vacuously true."
Dan:
"Well, it depends on what you mean by this. Of course, to apply modus ponens you have to have both p and p-->q. It might be argued that if p-->q is vacuously true, then a situation in which you might try to use modus ponens to infer q from p and p-->q will never arise: if p is known to be false, then we would never be in a situation of knowing that both p and p-->q are true, so we would never want to apply modus ponens.
But sometimes we assume something, for the sake of argument, that turns out later to have been false. (For example, proof by contradiction.)
If we have assumed p, and we know p-->q, then we should be allowed to infer q, even if we find out later that p was actually false.
Otherwise, we'd really be handicapped when doing proof by contradiction.
So it might be dangerous to impose some sort of ban on uses of modus ponens with vacuously true implications.
In fact, there is no need for such a ban, because the following statement is true.
If p is true and p-->q is vacuously true, then q is true.
Of course, the reason that this statement is true is that it is vacuously true!"
Paul:
"But, personally, I feel more comfortable with a definition of vacuous truth.
For example, when you say in your text (page 271), 'But because there are no natural numbers smaller than 0, the statement all k<0 P(k) is vacuously true,' I want to know the definition of vacuous truth.
And when we conclude that, if A is empty, the statement all a e A P(a) is vacuously true, I want justification (perhaps I overlooked such a justification or implicit justification in your book).
"So, avoiding the terms 'modus ponens' and 'modus tollens,' we can still define vacuous truth in accord with [an] email I sent you.
That is, a statement is vacuously true with respect to p if (p-->q) & ~p (which equals ~p v q).
It is nonvacuously true if (p-->q) & p (which equals p & q).
A statement (~q-->~p) & q (which equals q v ~p) is vacuously true with respect to q.
A statement (~q-->~p) & ~q (which equals ~p & ~q) is nonvacuously true.
So, when you say
if p and (p-->q) is vacuously true
I'm not sure what that means.
That is, if p is true and p-->q is true, I would hold that p-->q is perforce nonvacuously true."
[The above email has been lightly edited and minor corrections have been made.]
Dan:
"Right. And therefore the statement 'p is true and p-->q is vacuously true' is always false. And therefore the statement "If p is true and p-->q is vacuously true, then q is true' is vacuously true.
I.e., it has the form A-->B (where A is the false statement 'p is true and p-->q is vacuously true' and B is the statement 'q is true'), and it is vacuously true because A is false."
Paul:
"That's a good one. Does that mean my last definition of vacuous truth is already commonly accepted among logicians?"
John:
"I don't know if your definition is the commonly accepted one of 'vacuously true' or indeed if there is a commonly accepted one."
John also wrote:
"There may indeed be a technical definition such as yours for 'vacuous truth.' More commonly, however, the term is used roughly to mean 'empty,' 'devoid of content,' or even simply 'tautological'."
Paul:
"John's assertion that there is lack of clarity among mathematicians on the meaning of vacuous truth demonstrates a need for general agreement on a specific definition.
Clearly, Dan's definition of vacuous truth--which is implied in his clever "(p & (p-->q is vacuously true) requires that q is true)--is the same as the definition I suggest.
Dan:
"I think the term 'vacuously true' is usually used for a statement of the form 'for all x in A, P(x),' where A is the empty set. For example, 'All unicorns are purple' is vacuously true. If you paraphrase this as, 'If something is a unicorn, then it is purple,' then it fits your definition.
But probably most mathematicians would be more likely to recognize the term as appropriate in the case of a statement written using 'for all,' rather than 'if ... then.'
Replying to Dan, Paul:
"I now recall something about 'purple unicorns' in your text.
This exchange has proved helpful to me because I can see that a vacuously true statement is [equivalent to a statement] composed of two statements linked by the 'or' connective and a nonvacuously true statement is [equivalent to a statement] composed of two statements linked by the 'and' connective. And [I see that] the negation of a vacuously true statement is nonvacuously true, and the converse.
"So if I run across two statements that at first glance appear contradictory, as in
a e A --> (a,a) e R and a e A --> (a,a) ~e R, I should check for the possibility of vacuous truth."
Paul adds:
"And the tautology p is both vacuously true and nonvacuously true since
p --> p & p = p = p v p = p & p
The same holds for ~p."
Jim suggested that mathematicians would understand the term 'vacuous truth' from the context in which it was used.
"But, as an often dull student, I prefer exactness.
For example, I had long been under the impression that the fundamental of set theory that states that the empty set is a subset of every set was an axiom. But in fact it is a derivable theorem.
That is, if A is a subset of B, the definition of A is:
x e A --> x e B
or,
(x ~e A) v (x e B)
Since x ~e A is true for the null set, the statement above is vacuously true, as is the statement (x ~e A) v (x ~e B).
We know that if p --> q is vacuously true, then the statement p --> ~q is also vacuously true. Curiously, these statements are, in a sense, equivalent. That is, in a vacuously true statement of this form it is irrelevant whether q is true or not. In fact, by vacuously true, we are saying ~p is true and q is undetermined.
I have seen the term 'vacuous implication' loosely used to describe this state of affairs. That is, if the statement p-->q is vacuously true, then q is not implied by p because ~p is true."
Paul wondered about the meaningfulness of the concept 'power set of the reals':
"If R is nodenumerable, then P(R) is nondenumerable, meaning perhaps that it exists in a 'vacuous' sense."
Jim:
"I don't know what you mean. P(R) is nondenumerable but why does that make its existence 'vacuous'? I would on the contrary say that it is highly nonvacuous since it has so many elements. Perhaps you mean that nondenumerable sets are 'fishy,' and only exist as a mathematical abstraction."
Paul remarks:
"If we accept John's point that a 'vacuously true' statement may be interpreted as one that is empty of meaning, then it is possible to argue that the power set of an infinite number of elements doesn't exist in totality, or that perhaps it 'exists' courtesy of a vacuous definition.
If P(R) is held to exist, then (let [_ be the general subset symbol):
x e P(R) <--> x [_ R
but if P(R) is held to not exist, then
x e P(R) --> x [_ R
is vacuously true
though
x [_ R --> x e P(R) is false
This brings us to Cantor's paradox. That is cardU < cardP(U) and cardP(U) < cardU are both statements that can be proved.
If we say that
at least one x but not all x [_ U <--> at least one x but not all x e P(U)
is true, we can then assert that when "all" elements of P(U) are considered collectively, the elements vanish and P(U) becomes empty. Likewise, when considering "all" the subsets of U.
In that case
all x e P(U)(x [_ U <--> x e P(U))
is vacuously true in both directions.
but
at least one but not all x e P(U)(x [_ U <--> P(U))
is nonvacuously true.
This is analagous to
Sn = {the set of straight line segments in a symmetrical n-gon.}
at lim n-> inf., Sn becomes empty.
We can take this approach to Russell's paradox, which can be stated:
R = {A e U|A ~e A}, meaning
A e R <--> A ~e A,
giving rise to
R e R <--> R ~e R
Letting S = U\R, we can write (with u the union symbol)
all x e U(x e U <--> x e RuS)
and say that U and RuS become empty at the limit. Hence, at the limit, the statement is vacuously true in both directions, but
at least one x but not all x e U(x e U <--> x e RuS)
Russell's paradox however can be found in a set of one element."
PAUL ADDS (June 2001):
"I have found it conceptually important to be aware of this lemma of vacuous truth:
lemma: if p --> q is vacuously true, then p --> ~q is vacuously true.
Another way to see this is: p --> q v ~q and restate the lemma:
p --> q is vacuously true iff q --> ~(p & q).
For example, in the case of the infinite symmetrical n-gon, let us say Sn = { f | f is a facet which has more than one point}. Taking n to infinity means Sn is empty.
If we say
~some f e Sn(f has more than one point),
we can translate this as
all f e Sn ~(f has more than one point)
or
all f e Sn(f has less than two points)
or
f e Sn --> f has less than two points.
This is 'counterintuitive' because the consequent is false.
We can also write:
~all f e Sn(f has more than one point)
or
some f e Sn(f has fewer than two points)
Since f ~e Sn, the predicate is false for both the universal and existential quantifiers, meaning it is irrelevant whether the subject is true or false. In this case, we know it is false. In other cases, we may not know the truth value; in other cases we may get true as a value.
That is, I think that writing that p --> q is vacuously true only if q --> ~(p & q), is better than saying simply that if p --> q is vacuously true, then ~p v q holds.
It may seem silly, but to me the lemma has psychological value. The lemma means that if the predicate is false, then it is irrelevant whether the subject is true or false."
A THREE-PART SET THEORY AXIOM
So perhaps we may consider an alternative set theory axiom:
'(i.) A class is a statement defining the elements of a set.
'(ii.) Any set has a finite number of elements.
'(iii.) For any set S, the statements "S e S" is undefined.'
Suppose X = {x|x = 1}. In that case, X is a set; x means an arbitrary element of X; and 1 is a distinct, or identified, element of X. The statement (x = 1) is a class.
You may say that there are sets which are members of themselves.
For example, without our axiom, one can write:
S = {s e S| s is a set identified by the letter S}. In that case S e S. Our axiom simply says that S e S is roughly equivalent to division by zero. Clearly, this sub-axiom is equivalent to Zermelo-Fraenkel axiom which asserts that a set is always disjoint from at least one of its elements.
Russell's paradox stems from:
R = {A e U|A ~e A}
By (ii.), R is not a set because the definition does not require n elements.
If R contains no elements, then r e R <--> a ~e A is vacuously true in both directions and there is no paradox.
Suppose R = {R e U|R ~e R}, or r e R <--> R ~e R. Then, if r = R, in that case R e R and we have a contradiction -- even if R contains only one element.
Though (iii) forbids the question R e R, we are entitled to ask whether R ~e R. Since R ~e R --> R e R, which is undefined, we can then agree that R ~e R tells us there is at least one case where A ~e A is undefined.
Speaking of classes covering infinitudes, the statement 'r is a number equal to p/q or not equal to p/q' does not here imply r e R. R is not the set but the statement, or, that is, the class. Even so, R can be an element of a finite set. (The notation r e R would need to be revised; perhaps r d. R, for 'any case r as defined by R.')
If X is a class, x e X is untrue and x ~e X is always true. Hence X is logically equivalent to the empty set. However, X does not equal the empty set because the empty set exists.
Yet the equivalence is meaningful because we can say that X is equinumerous with the empty set, or cardN = cardP(N) = cardR = cardP(R) = card0.
This axiom does not mean we cannot loosely use a phrase such as "all reals." Nor does it necessarily nullify various limit proofs.
We handle a concept such as "the infinitude of primes" like this:
There is a class of objects (we don't define 'object' other than by saying that it is a "case" defined by the condition of the class) such that between n/2 and n, at least one prime occurs for ANY n.
We might express the statement:
Any n d. N( [n/2,n] --> prime)
(Here N is a statement defining the object of natural number.)
In other words, if a statement is inductively true -- i.e., a nonstop recursion algorithm holds -- we need not then say that an infinite set exists. It is sufficient to know that the statement is true for any defined object. (Yes, but precisely what is an algorithm? you say. My page of that title may be reached via the N-fold link. Let me insert that I am under the impression that Alonzo Church invented the lamda calculus in order to circumvent classical set theory.)
Of course, the perception of infinite set arose from the notion of "actual infinity" associated with an irrational number. The seemingly contrasting notion of "potential inifinity" simply reinforces the concept of actual infinity because in an absolute, platonic or timeless sense, if an object potentially exists, then it already exists, or exists beyond time.
So here we are not arguing for infinity, potential or actual, which requires the universal quantifier to read "all." Rather, with this axiom we are arguing that when the upside down A is applied to nonstop recursion statements, it is to be read "any."
Addressing irrationals, we introduce the term 'not-object': an object that is defined by what it is not.
Not-objects can also be used for rationals, as we explain:
We write a nonstop recursion formula that builds nested intervals, with any interval a finite length shorter than the previous interval and with endpoint a measurable distance from origin.
So the not-object in this formula is a nested interval of 0 length. It is defined as, for any step n, not any previous interval, though within the interval at step n.
Does the not-object exist? Well, it sure is handy to have such a limit point. So why not agree that it exists? But to agree that it exists does not mean that the infinite set N exists.
After all, we can't fundamentally prove most such points exist since we can only use approximations to "measure" their distance from origin.
Such nonstop recursion functions can be used to obtain rationals and irrationals. But most irrationals are not subject to measure by ruler and compass or other finite step algorithms (square and cube roots are an exception).
In fact, a way to define a class of irrationals is to say that such an irrational's so-called limiting value can be defined only by nonstop recursion algorithm.
In the same vein, a circle, rather than being construed as a so-called limit of n-gon approximations, is agreed to exist because there is a non-stop recursion algorithm which inductively means that as n increases, the approximation of a circle is 'closer.' Any such symmetrical n-gon is finite. The circle does not exist as an n-gon but is an axiomatic form.
We would not then say that a circle perimeter contains an infinite set of points. Rather, it is possible to devise a nonstop recursion algorithm to divide a circle perimeter into ever smaller arcs through intersection by rays. A circle then can have any finite number of arcs.
The same kind of reasoning holds for a line, also an axiomatic form.
So to say that we can map the set N onto a unit length line would be recast: We know that a nonstop recursion algorithm exists for dividing a line segment into ever shorter lengths. That is, n d. N(1/n --> number of subdivisions).
A line, really, is a not-object, because it can't be drawn. Having 0 width, it may be said, perhaps, to be an edge or boundary between plane parts, a plane being another axiomatic object. The line exists as not-part A and not-part B.
In a like manner, the curve f(x) -- which could be a line of course -- is a not-object. One can't see the curve f(x). It is invisible. It may, for example, be defined by the area beneath a part of it or by the length of an arc for a portion of it.
But f(x) between a and b is said to exist because there exists at least one algorithm where, the higher step n, the closer to a limiting value. So, we say any x d. R(f(x)--> z < L) or, depending on the algorithm and the curve, any x d. R(f(x)--> z > L) rather than all x e R(f(x)-->(z<L) v z>L)).
That is, the integral of f(x) means that we can find at least one algorithm where the step m area < the step n area < L, or the step m area > the step n area > L.
Does the area L exist? In a platonic sense, yes. But it is sufficient for us to know that such an algorithm exists. That knowledge is equivalent to the assertion that such an area exists.
Though our alternative axiom might be construed as in the intuitionist camp, I'm really a fan of Cantor. However, it seems useful to look at non-Cantorian possibilities.
At some future point, I hope to discuss on another N-fold page quasi-Cantorian ideas about irrationals.
++++++
Vacuous truth in the sense that John mentions can be seen from tautologies such as all x e X(x e X) and E!x e X(x' e X) [where E is the existential quantifier and x' means a unique element].
Suppose the writer says that all x e X(x e X) is vacuously true. Does he mean the tautology x e X --> x e X or does he mean the specific case of x ~e X?
We define an element as x = (y,z), where y is the general condition, held constant for X, pertaining to all x, and z is the condition that makes an element unique. (In passing, we note that x = (y,y) means z' = y. Because y is a general property, there can be no property to distinguish elements. Hence x = (y,y) means either X is empty or X has one element. And (z,z) = (y,y).)
So every element of X has the general property of being an element of X. But we take this for granted unless it is specified that y means x e X.
I actually introduced this notation in order to get another insight into Russell's paradox.
Russell's paradox can be seen as stemming from one of those annoying infinitely recursive [nested] definitions: rob Peter to pay Paul and then rob Paul to pay Peter, ad infinitum.
Let the general property of x = (y,z) be y = (s' = S), or
x = ((s'=S),z).
If X e X, then let x' = X and z' = (x'=X), giving,
X = x' = ((s'=S),(x'=X))
The dog-chasing-its-tail effect of this definition is apparent. This is also true for x'=/=X, even though this inequality is usually true (or always true by our axiom).
That is, the issue stems from the need to define a set by its elements and an element by its set.
Another thought on Russell's paradox: We know that for sets A and B, A<-->B means A = B. The same is not necessarily true for statements p and q. That is, p<-->q does not necessarily mean p=q. For example, if p means x<y<z and q means y>x, p=/=q but p<-->q.
Now if we transform R = {a e A|A ~e A} to r e R <--> A ~e A, we may regard r e R as a statement p. As long as we don't "observe" the meaning of the statement, we can be satisfied that equalities don't necessarily result from biconditional statements.
ELUSIVE PRIME CONJECTURES
Vacuousness in the general sense also seems to arise from such prime conjectures as the twin prime and Mersenne prime posers. Is there an infinitude of twin primes of form p+2 (where p is an arbitrary prime)? Is there an infinitude of Mersenne primes of form 2^p - 1?
The probability that any integer n is prime approaches 0 as n approaches infinity. Yet, the probability is never 0 for an arbitrary integer n.
But what about the probability that there is an infinitude of twin primes? Primes occur pseudorandomly (that is, can only be reliably predicted by recursive algorithm). The condition that p+2 is not prime (where p is a prime) cannot so far be proved nonrecursively, nor inductively.
So, though the probable occurrence of primes decreases with n, the probability that p+2 will occur at least once after some arbitrary m, rises with n. Hence the probability that there is an infinitude of twin (or Mersenne) primes equals 1 at infinity.
Hold up, you say. Something's wrong here. We do not accept this probability as valid because the conclusion is not arrived at inductively. Perhaps circular reasoning is the culprit.
Yet the question is, 'Is there an infinitude of twin primes'?
So what is meant by infinite set of twin primes? If, at the limit, the probability is 1 that the twin and Mersenne prime conjectures hold, why do we suspect the truthfulness or reliability of this probability? It is after all only valid for an infinitude.
We don't like it perhaps because of Euclid's proof of the infinitude of primes. Suppose we forget Euclid. What is the probability that there is an infinitude of primes? Again after some arbitrary m, the probability rises with n, reaching 1 at lim n->inf. Why would we not accept that the statistical truth is truth, since we cannot examine every element of N?
Yes, but perhaps someone will prove that one of the conjectures is false. We cannot, so far, prove that someone will not prove such a conjecture false.
Even so, the case for undecidability is strong. Primes cannot be infallibly forecast by algebraic formula, nor can composites be infallibly forecast by algebraic formula. This means that at infinity there is no algebraic description of a prime.
And both twin primes and Mersenne primes decrease faster than the primes decrease, so no proof can cite increasing density.
Now if it is someday proved that the conjectures are undecidable in a nonstatistical sense, would we then be willing to accept the statistical probability as truth?
All this may seem like flogging a dead horse, but, dull student that I often am, I need the extra detail sometimes. For example, It took me an embarrassingly long time to see the right answer to the Monty Hall problem." For more on that, hit the N-fold link until reaching a 'Monty Hall' link.
A discussion of the ZF infinity axiom and euclidean space can [no longer] be found via the N-fold link.
No comments:
Post a Comment