6
$\begingroup$

There is this quote by Hermann Weyl:

"… classical logic was abstracted from the mathematics of finite sets and their subsets …. Forgetful of this limited origin, one afterwards mistook that logic for something above and prior to all mathematics, and finally applied it, without justification, to the mathematics of infinite sets. This is the Fall and original sin of [Cantor's] set theory …." (Weyl, 1946)

Does this imply that at the invention of quantifiers "$\exists, \forall$", they were merely used for finite domains of discourse?

In that case, I think that would mean they can be viewed as merely abbreviating the connectives "$\land$, $\lor$". For example, if the domain conists of $3$ elements $a,b,c$, then merely

$\exists x\ \phi(x)\equiv\phi(a)\lor\phi(b)\lor\phi(c)$

and

$\forall x\ \phi(x)\equiv\phi(a)\land\phi(b)\land\phi(c).$

A motivation is to understand if I can think of quantifier rules as just induced by rules for connectives. For example, for finde domains, I figured that using only De Morgan's laws

$\neg\exists x\ \phi(x)=\neg((\phi(a)\lor\phi(b))\lor\phi(c))=\neg(\phi(a)\lor\phi(b))\land\neg\phi(c)=(\neg\phi(a)\land\neg\phi(b))\land\neg\phi(c)=\forall x\ \neg\phi(x).$

At a time were people haven't come up with the quantifiers, I guess they didn't even think about things like finitely axiomatizing arithmetic yet.

Since I came across the quote in the article discussing the controversy behind cardinalities:

Once we got quantifier for infinite domains (like the natural numbers), is there an additional obstacle for accepting uncountable domains?

I wonder about this point because if you introduce the quantifier, because you can't write down an infinitely long sentence, for example a $\forall$-claim about the element of $\mathbb Z$, then there is not so much difference anymore to the problem which arises with $\mathbb R$. Sure, they are not countable - but you can still name many of it's elements (even if you can't even specify some). You can only handle all of them via $\forall$, and that is true not matter what infinite cardinality you speak about.

$\endgroup$
  • $\begingroup$ That sort of makes them operators on Hilbert space, too, if $\Bbb{F}_2$ had an inner product. I can see people having the same difficulty accepting infinitely iterated quantifiers as I have accepting Hilbert spaces. $\endgroup$ – Loki Clock Jun 18 '13 at 14:56
  • $\begingroup$ @LokiClock: I wouldn't have expected this comment. Different propositions as basis and $\pm 1$ sign as truth value? Do you add them via $\land$ or via $\lor$? What does a normale form correspond to? Is this necessary if you got Boolean algebra? And what's your problem with hilber spaces? Iterated quantifiers? $\endgroup$ – Nikolaj-K Jun 18 '13 at 15:00
  • $\begingroup$ The domain in bijection with the basis vectors, different propositions as vectors whose coordinates are the truth value of the proposition at each element of the domain, the quantification of either of those over the whole set/basis as an operator from the space $\Bbb{Z}_2^{Dom}$ to $\Bbb{Z}_2$. $\endgroup$ – Loki Clock Jun 18 '13 at 15:06
  • $\begingroup$ I don't know about normal forms, though it looks interesting. It's not necessary to think of it that way, but it's natural, in that it's just treating the boolean algebra on the whole set as a vector space over the boolean algebra on a singleton. Wikipedia calls this treating subsets as bit vectors. $\endgroup$ – Loki Clock Jun 18 '13 at 15:18
  • $\begingroup$ My problem isn't so much with Hilbert spaces as with infinite-dimensional vector spaces. They depend on the axiom of choice to have a unique dimension, they break duality, and moreover the isomorphism of direct product and direct sum. They're a tempting conceptual frame, but they act more like topological objects than algebraic ones. $\endgroup$ – Loki Clock Jun 18 '13 at 15:28
5
$\begingroup$

Several things should be mentioned here. First, the replacement of quantifiers by conjunctions and disjunctions requires not only that the domain of discourse be finite but that its size and in fact all its elements be explicitly known. For example, a law saying "all serfs must give their feudal lord a quarter of all the grain they grow" can be stated in this generality only by using quantifiers, not as a conjunction of separate laws for each serf (and each kernel of grain). A conjunction formulation would have to be rewritten every time the lord acquired a new serf.

Now concerning Weyl's statement, I don't think he was claiming that the mere use of quantifiers originated in finite situations and is inappropriately extended to the infinite. Rather, he objected to some of the logical laws governing statements involving quantifiers (and connectives). A typical example would be the law of classical logic that $$ (\forall x\,\phi(x))\lor(\exists x\,\neg\phi(x)). $$ If $x$ ranges over a finite set, this law is (relatively) unproblematic. Either all the $x$'s satisfy $\phi$ or we can (in principle) go through all the possible values of $x$, one after another, and eventually find one that doesn't satisfy $\phi$. With infinitely many (or, worse, uncountably many) possible values for $x$, the idea of going through them all is no longer so convincing.

At this point, it becomes important to be clear about the intended meaning of the existential quantifier. Weyl and other constructivists advocate reading $\exists x$ as meaning that we can (at least in principle) find an appropriate value for $x$. Classical mathematics interprets $\exists x$ as merely asserting existence of an $x$, with no claim about our ability to find anything. This disagreement about what $\exists$ should mean will obviously lead to disagreement about the validity of formulas like the one displayed above. Classical mathematicians will say it's obviously correct; constructivists will say it's an arrogant statement about our omniscience; and extremists on each side will think the other side is crazy.

Let me also comment on your question whether uncountable domains are worse than countably infinite ones. Some of the issues, like those I described above, are the same in both cases. Nevertheless, there are differences, which, as far as I understand them, seem to boil down to the following idea. Even though we cannot "go through" all elements of a countable domain, they way we can with a finite domain, we can at least envision a process which, if continued forever, would go through the whole domain. In the case of uncountable domains, even that "potential exhaustion" of the domain is unavailable. There is a book, by Gregory Moore, on the history of the Axiom of Choice, in which he reproduces some correspondence between leading French mathematicians, from just after the Axiom of Choice was proposed, in which they discuss to what extent it is acceptable. If I remember correctly, Hadamard found the full Axiom of Choice acceptable, while the others, including Lebesgue and Baire, argued for accepting only versions that permit countably many choices. A cynic would say that's because they had proved theorems that depend on the countable axiom of choice, but the reasons they give in these letters suggest a genuine intuitive difference between the countable and uncountable cases.

$\endgroup$
  • $\begingroup$ Thanks for your answer! You make a stronger destinction between the quantifier and the connectives than I expected. Isn't the the possiblitiy to replace the quantifies with connectives that which makes quantifier elimination possible? $\endgroup$ – Nikolaj-K Jun 20 '13 at 12:16
  • $\begingroup$ @NickKidman No, quantifier-elimination is not based on replacing quantifiers with connectives in the way you outlined. The process of eliminating quantifiers varies from one theory to another and in general requires quite detailed knowledge of these theories. $\endgroup$ – Andreas Blass Jun 22 '13 at 1:30
2
$\begingroup$

In Logic, quantifiers are undefined, i.e., primitive concepts. They have to satisfy axioms. But their interpretation is as open and variable as the interpretation of the primitives of Boolean algebra.

Henkin quantifiers are an example of non-standard interpretations of quantifiers that obey all the usual axioms for quantifiers, but disagree with our intuition of there exists or for all. See Alonzo Church, Mathematical Logic, in my opinion the only satisfactory introductory textbook.

Historically, Hilbert and his pupils had a lot of trouble axiomatising the quantifier. Several of their first publications were wrong: this history is explained in Church.

There is a difference in esprit between logicians and mathematicians. Set theory is a branch of mathematics, and shares the same esprit. Goedel never really understood Russell. For Russell, there could only be one logic, and it was about the real world, Russell's interest in logic grew out of his own attempt to axiomatise Physics. That is why when Relativity and later Quantum Theory came, he and Whitehead abandoned the Principia unfinished and he wrote about Relativity instead, and Whitehead developed a rival gravitational theory to Einstein's (for quite a while there were rivals to the Einsteinians: the Whiteheadians, of which there still remained at Queen's Univ., when I was there, a 90 year old professor in the Physics Dept. ... still lecturing and doing research...). When Whitehead retired he threw out his copy of Principia and it was picked up by a grad student from the hallway....

That said, I will now rest some, since it should be obvious that one's motivation for introducing quantifiers will depend on whether one comes from Physics or Logic or Mathematics. I suppose Cauchy with his definition of limit was early: clearly this answers your question «yes, uncountable». R was his universe. Frege, even more so: his motivation was to define a cardinal number as an equivalence class of sets. But with the theory of types, things finally get interesting: Physics will tell us whether there are uncountably many, countably many, or finitely many objects. There are no sets, and so there are only countably many propositions or formulas built on top of the objects (higher type), so second-order quantifiers only deal with countably many instantiations. Furthermore, how many proper names can there be in a formal language? Only countably many..... people seem to have lost interest in this problem.

$\endgroup$
  • $\begingroup$ Thanks for the response. Some part of it is difficult to read for me. Like the section with "...when I was there a 90 year old follower in the Physics Dept..." Are you saying you are 90+ ?? $\endgroup$ – Nikolaj-K Nov 22 '13 at 10:03

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.