Re: Negating Quantifiers

On 2009-08-22 13:12:00 -0400, RussellE <reasterly@xxxxxxxxx> said:

On Aug 20, 8:17 pm, Owen Jacobson <angrybald...@xxxxxxxxx> wrote:
On 2009-08-20 16:23:50 -0400, RussellE <reaste...@xxxxxxxxx> said:

I've reordered this a bit, to put the part related to the ostensible topic (the negation of quantifiers) first.

  Ax (Ey (P(x, y) OR ~P(x, y)))
   <=> Ax (~Ay (P(x, y) AND ~P(x, y)))

(Without the outer quantifier, your sentence has an unbound variable,
making it a predicate. None of your other sentences are predicates.)

Substituting this into the expression:
Ax(~Ay(P AND ~P))

Distributing over the inner ~Ay:
Ax(~Ay(P) AND ~Ay(~P))

Doesn't follow. The former is equivalent to

  Ax (~(Ay (P(x, y) AND ~P(x, y))))

(This is just a more thorough use of parentheses.)  You can distribu
te
the Ay quantifier thus:

  Ax (~((Ay P(x, y)) AND (Ay ~P(x, y))))

Ay P(x, y) <=> ~Ey ~P(x,y)
Ay ~P(x, y) <=> ~Ey P(x,y)

Substituting we get:

Ax (~((~Ey P(x, y)) AND (~Ey ~P(x, y))))

True, but uninteresting and excessively noisy: this follows intuitively
from the law of excluded middle. As a style point, transposng the sides
of the AND was unnecessarily distracting.

However, you can't distribute the ~ the same way, since

  ~(a AND b) <=> (~a OR ~b)

While this statement is true, it is completely irrelevant.
Next, you will be saying I can't distribute
~~(Ay (P(x, y) AND ~P(x, y))) because of the
double negation.

You can do anything you like from that, since a contradiction implies anything. However, that predicate isn't implied by any non-contradictory sentences, and (correcting the missing quantifier - you really are very sloppy about them):

∀x ¬¬(∀y (P(x, y) ∧ ¬P(x, y)))
⇔ ∀x ∀y P(x, y) ∧ ¬P(x, y)

is definitey not implied by the sentence you started with.

Ax ((Ay P(x, y)) OR (Ay ~P(x, y)))

This is a very interesting statement. It says for all x,
either x <= all y or x > all y. The statement is true
for x=0. Is it true for all x > 0?

It would perhaps be more interesting if it arose from something.
However, the statement

  Ax ((Ay P(x, y)) OR (Ay ~P(x, y)))

does not follow from anything above.

It follows from substitution and ~(a AND b) <=> (~a OR ~b).

In
∀x ¬(∀y (P(x, y) ∧ ¬P(x, y)))
? Surely not, since

∀x ¬(∀y (P(x, y) ∧ ¬P(x, y)))
⇔ ∀x ¬((∀y P(x, y)) ∧ (∀y ¬P(x, y)))
⇔ ∀x (¬∀y P(x, y)) ∨ (¬∀y ¬P(x, y)))

You've dropped two negations from yours, before each of the '∀y' quantifiers. If you think you can drop those, show your work. Continuing on:

∀x (¬∀y P(x, y)) ∨ (¬∀y ¬P(x, y)))
⇔ ∀x (∃y ¬P(x, y)) ∨ (∃y P(x, y))

Which is...

Distributing the outer negation in

  Ax (~((~Ey P(x, y)) AND (~Ey ~P(x, y))))

gives

  Ax (~~Ey P(x, y)) OR (~~Ey ~P(x, y))
 <=> Ax (Ey P(x, y)) OR (Ey ~P(x, y))

.... reassuringly equivalent to what we can derive from your original sentence by other means.

The remainder is my opinion of your effort to prove that Peano arithmetic is inconsistent, which doesn't directly relate to the subject line but seems to come up in every one of your threads sooner or later. Skip it, or don't, as you see fit.

-o

 - You did a tolerable job of showing that, if there is a number
greater than any natural number, and if that number (let's call it h)
is a natural number, then Peano arithmetic is inconsistent. This is not
a new result, so it did not generate much discussion.
 - You failed to demonstrate that h is not a number. That's also not a
new result; there are lots of non-natural numbers that are larger than
any natural number.

No one has ever suggested a "non-natural" natural number is
a contradiction? Maybe someone did make such a suggestion
and was burned at the stake.

Good grief. Where did I say "non-natural natural number"? I said "non-natural number."

 - You sketched out your reasons for believing that h is a *natural*
number, but did not prove it.

I have to prove a TM writes one position at a time?
I proved the set of blank positions is empty using induction.
Of course, you prove the set of blank positions is never
empty using induction.

This again? Look, there is no such "the set" of blank positions. There's the set of positions that are blank at all steps (which is empty), and for each natural number n, there is a set of positions that is blank at step n, which is not empty for any step n. Formally:

Given

T(0, 0)
∀s ∀i T(s, i) → T(s + 1, i)
∀s ∀i T(s, i) → T(s + 1, i + 1)

defining a binary predicate T(s, i) that is true if the i'th cell of your TM's tape is non-blank after the transition indexed by s. ('i'ndex, and 's'tep, for mnemonic purposes.) By induction, we can prove from the above that

∀s ∀i (i ≤ s ⇔ T(s, i))

is also true, and that

∀s ∀i (i > s ⇔ ¬T(s, i))

is also true.

Then we have a set B, which is (informally) the set of cells that are always blank:

∀i (i ∈ B ⇔ ¬∃s T(s, i))
⇔ ∀i (i ∈ B ⇔ ¬∃s (s ≤ i))

Because ∀i 0 ≤ i, therefore ∀i ∃s (s ≤ i), so B must be the empty set. It's not the most intuitive proof ever, but it's equivalent to the informal statement that "the n'th cell is written to at the n'th set, so no cells are never written to". (Double negative intentional, here, but if you really want to dispute this, stick to the proof, not the informal descriptions.)

We also have a family of sets B_t, each of which is the set of positions that is blank after the t'th transition:

∀i (i ∈ B_t ⇔ ¬T(t, i))
⇔ ∀i (i ∈ B_t ⇔ i > s)

Because ∀s (s + 1) > s, therefore ∀s ∃i i > s, so B_t must be non-empty (B_t contains at least t + 1 - proving that it has aleph-null elements left as an exercise). Therefore, there is also no step t such that B = B_t.

You've incorrectly assumed in your "proof" that B, the set of cells that are never written to, and some set B_t, are interchangable. If they were, you'd be right - that would allow proofs of all sorts of things that aren't true.

I can see why you prefer inconsistent formal system.
You can prove anything you want to prove and refute
anything you don't like.

On the contrary. I rather wish I could refute, for example, the halting problem, since much of static program analysis is limited by it[0]. Or the pigeonhole principle, so that I could prove the existence of a "perfect" compression algorithm. Or that I could simply make up and declare valid a proof of the Riemann hypothesis.

What I can and cannot prove is restricted by the necessary implications of whatever set of axioms I build my proofs on. As it happens, for this discussion I'm assuming first-order logic, and that Peano arithmetic describes the natural numbers, and that T(s, i) above accurately models your Turing machine. (I didn't actually prove that one, but if T doesn't match your machine, that should be easy to show.)

When pressed, you resorted to rhetoric
and ambiguity. At no point did you even attempt a formal proof.

It si a waste of time to try to prove a contradiction in
a formal system that assumes its own consistency.

Indeed. In such a system, you can resort to Gödel's argument and prove the system inconsistent very quickly. It's only in systems like Peano arithmetic and first-order logic that you have to demonstrate an inconsistency the hard way: by proving from the axioms of the system both halves of P and ¬P, for some statement P.

Unless the consistency of a system is one of the axioms of that system or is implied by one of the axioms, you can't resort to Gödel's incompleteness proofs. To the best of my knowledge, none of the axioms of Peano arithmetic or first-order logic amount to "Peano arithmetic is consistent." So you have to prove your inconsistency the hard way.

Your
argument that, in PA,

  Ex Ay (x >= y)

relied heavily on a rhetorical trick that isn't supported either by
first-order logic, or by Peano's axioms, or by Turing's axioms.

Neither FOL nor PA can prove ExAy (x>=y) is true for
finite, orderd sets? We both know this is true.

Where did I say "finite, ordered sets?" Peano arithmetic implies an *infinite* set, and you can impose a fairly natural ordering on it. There are inductive definitions of < that give 0 < S(0) < S(S(0)) < ... .. Once you've done that, you can prove that all finite subsets of N have a greatest element, and that every non-empty subset (finite or infinite) of N has a least element, and that *no* infinite subset of N (including N itself) has a greatest element.

This "Axiom of Deniability" nonsense is pretty insulting and completely
unnecessary. It only paints you as more of a prat. You'd do better if
you focussed on the technical parts of the arguments presented to you.

I know you vehemently deny you are assuming the formal system
is consistent. You don't have to assume the formal system is
consistent. This assumption is built into your "allowable" deduction
rules. Contradictions aren't allowed in "valid" proofs.

*sigh* Look, before you continue off down this line, read up on the history of Frege's set theory and Russell's paradox. That's a good example of how to show an inconsistency in a formal system. Russell's paradox doesn't rely on assuming that Frege's theory was either consistent or inconsistent: it works out with either starting assumption, and so would any proof that Peano arithmetic is inconsistent.

Yes, we can prove anything we want in an inconsistent
system. How is your proof relevant to the validity of
my proof? Do you still think you can use proof by
refutation without assuming the consistency of
the formal system?

Do you think you can use "assume the system is inconsistent" to prove inconsistency? Note that nowhere have I claimed to be proving Peano arithmetic is consistent, or even that your proof is wrong. I've only claimed that you *have not offered a complete proof*: you're still missing the crucial step of proving some sentence P, and also some sentence ¬P.

The closest thing you've offered is this "set of blank cells is both empty and non-empty" noise, and it's fairly easy to show that the set shown to be empty does not describe the same part of your Turing machine as any of the sets shown to be non-empty. While it's surprising the first time you run into it, it's not an inconsistency.

-o

[0] For example, http://www.perlmonks.org/?node_id=663393

.

Relevant Pages
Quantcast