Higher-Order Logic : Philosophy Forums

Philosophy Forums » Logic and Philosophy of Math » Higher-Order Logic » Higher-Order Logic

Higher-Order Logic

TecnoTut
Tenured Poster

Usergroup: Sponsors
Joined: Jul 09, 2002
Location: Florida
Total Topics: 187
Total Posts: 4418

Posted 04/10/08 - 10:45 AM: Subject: Higher-Order Logic	#1
First-order predicate calculus allows quantification only over individuals. Higher-order logic also permits quantification over predicate (property) positions. Natural languages seem to permit such quantification: 'Mary has every quality that John admires'. Mathematics, moreover, may be expressed in higher-order logic. Peano arithmetic and Zermelo-Fraenkel set theory, e.g., require infinite axiom sets in first-order logic but are finitely axiomatizable -- and categorical, determining their models up to isomorphism -- in second-order logic. Because they quantify over properties and relations, higher-order logics seem committed to Platonism: Mathematics reduces to higher-order logic. W.V. Quine argued the latter is not logic because properties and relations are too obscure for rigorous foundational study (See Quine's hostile view towards properties in 'Word & Object'?), while sets and functions are in the domain of mathematics; logic should not have an ontology of its own. Its most natural semantics seems to presuppose a prior understanding of properties and relations. Also, on this semantics, it differs greatly from first-order logic. Like set theory, it is incomplete, but not compact. This raises questions about the boundaries of logic: 1) Must logic be axiomatizable? 2) Must it be possible, i.e., to develop a logical system powerful enough to prove every valid argument valid? 3) Could there be valid arguments with infinitely many premises, any finite fragment of which would be invalid?
He that dies pays all debts - Shakespeare's Stephano from The Tempest Truth is its own measure - Spinoza, Ethics IIp43s Those who deny [Aristotle's] first principle should be flogged or burned until they admit that it is not the same thing to be burned and not burned, or whipped and not whipped. - Ibn Sina (Avicenna)

Beeboo
Student

Usergroup: Members
Joined: Feb 17, 2007
Total Topics: 14
Total Posts: 81

Posted 04/11/08 - 09:07 AM:	#2
I don't know much about those interesting questions. But according to Godel's theorem, there are no extensions of Q (Robinson arithmetic) which are complete, consistent and axiomatizable. Now for a positive test for validity: first, if the test classify a statement as valid then the statement is really valid. Secondly, if the statement is valid then the mechanical test says it is valid. (soudness and completeness). This is a positive test for validity. But for first order logic there is no negative test for validity: fol is undecidable. Also it is known that there are no positive test for the validity of second-order sentences. The proof is something like that : Take a first order sentence A of the language L. We have Q->A valid if we have Q\|-A thus this means if we have A true in the model N (natural numbers). This means that not(A) is not true in N and again that we don't have Q\|-not(A) and that Q->not(A) is not valid. Now if a positive test existed for second order logic existed then we would have a positive test for validity in N. To check the truth of the sentence A apply the positive test to Q->A and to Q->not(A). One of those must be valid and the test would identify precisely which one is valid. However there is no decision procedure for truth in N, hence no positive test for second order logic. You are right that second-order logic has a stronger expressive power than fol. Many notions such as well-foundeness, finiteness can be expressed in HOL and not in FOL. It is true too that Peano's arithmetic is categorical in HOL but has non-standard models in FOL. Also, there are great papers of Boolos about second-order logic and his answers to Quine about HOL not being logic. Quine says we can't quantify things that are not names. a first order variable is a name of something in the domain. Concepts, for instance, are not names. But Boolos answers that nothing forbids us to quantify on things that are not names. Instead of saying x names b, one could say x belongs to concept X. Boolos points out that formulas like "There exist a set X such that for all x we have Xx" are valid in second order logic. We would like to say things like that. But we impose that second order logic can't speak about totalities. This means we have to restrict the quantification on subsets of the domain of first order variables. This was the first solution Boolos adopted. In the famous ariticle "to be is to be the value of a variable" Boolos changes his mind and adopts plural quantification. Also there is that argument that answers Quine about HOL being set theory: The sentence "There exist a set F such that for all x we have Fx" is valid. However "there exist an a such that for all x, x€a" is not valid (€ means belongs to). So HOL (second order logic) doesn't assert the same thing as ZF. Our sentence here only says that there exist a subset of the domain such that everything of the domain belongs to it. Here are the references of both Boolos's articles: On Second-order Logic (Logic, Logic, and Logic) and To Be is To Be a Value of a variable" also in Logic, Logic, and Logic. Edited by Beeboo on 04/11/08 - 12:45 PM

The Bearded Monkey
Professor

Usergroup: Members
Joined: May 02, 2003
Total Topics: 100
Total Posts: 641

Posted 04/13/08 - 07:09 AM:	#3
for question three I think you need to check for infinitary logic, I myself don't know much about this field.
i shall take the whichpath to quantum catastrophe theory.

moonlight
Lunatic

Usergroup: Members
Joined: Oct 09, 2005
Location: stuck on earth
Total Topics: 17
Total Posts: 510

Posted 04/15/08 - 12:24 AM:	#4
Hi TechnoTut, Very interesting post. I think the main difference between the higher order quantification we use in maths and in natural language is one of semantics. In my opinion, it is possible to use the higher order quantification we use in natural language without arriving at the problems we face when we use the same in mathematics for the following reason: Suppose John knows a number of things (say 'm' things). Then 'm' is finite, since John is finite. So there can only be a finite number of properties John considers since the powerset of the set of 'm' things he knows, P(m) is finite. Consequently, the higher order quantification used in such natural language should be first-orderizable, since we never deal with infinite domains of knowledge. We can list every possible thing John knows, and then assign a name to every possible property on that domain, and make the higher order quantifiers range over these explicitly (or implicitly) finite number of properties. Thus the sentence 'John admires every one of Mary's properties' can be turned into a first order sentence. A very long one, but it could be done. In mathematics of course the problem is different, and the semantics aren't reducible to the first order as easily. A domain containing all the natural numbers, will have an uncountably infinite number of properties, i.e. the powerset of such a domain could be too large to ever be able to count through. I never quite understood fully Quine's objections on this issue. Without such a 'full' higher order quantification we can't discuss infinities in maths and spell out the difference between countable and uncountable ones. He criticises this 'ontological problem' with HOL but doesn't propose anything in replacement. Anyways to answer your questions: 1) Must logic be axiomatizable? I don't see any law about it, but ideally: yes. It is very practical to be able to 'pack up' entire theories in just a few axioms. It helps when examining the theory. 2) Must it be possible, i.e., to develop a logical system powerful enough to prove every valid argument valid? No, not necessarily. A theory may contain more than a countable number of valid arguments, and not all of them would then be derivable even given infinite time, speed, etc. (resources generally speaking). 3) Could there be valid arguments with infinitely many premises, any finite fragment of which would be invalid? I can't see how this would be possible, although I'm not sure. If the infinite premises are each invalid, then suppose they would be conjoined, put in PNF, and then the resulting quantifier free matrix be put in canonical disjunctive normal form. There would be an uncountably infinite number of conjunctions, each containing every atom listed in the premises, either negated or not. Every such conjunction would be connected in the matrix by an 'OR'. If every one of the original premises was invalid, then every premise must have contained its own contradiction(s). Thus all the conjunctions derived in the matrix in this way must contain contradictions. But how would the conjunction of 2 contradictions result in a tautology then? I think it is possible to see that even if we can't check them all one by one, we can intuitively guess that no number of contradictions conjoined together, would result in a tautology. I amy be missing something here of course. Cordially, moonlight.
All are lunatics, but he who can analyze his delusion is called a philosopher. - Ambrose Bierce -

TecnoTut
Tenured Poster

Usergroup: Sponsors
Joined: Jul 09, 2002
Location: Florida
Total Topics: 187
Total Posts: 4418

Posted 04/15/08 - 12:22 PM:	#5
I personally do not know the answers to the first two questions, but I the answer to the third question is "yes". Let {Q} be an infinite set of premises defined as follows for all statements P, where P is a member of {Q}, there exists a statement P' such that P' is also a member of {Q}, and it is not the case that P or P' imply each other. Now, let C be defined as follows. For all T, if T is a member of {Q}, then T is a part of a conjunction on C. (Thus if {Q} = {P, P'}, then C = (P ^ P')) Now, since C is an infinitely long conjunction of every member of Q, Q :- C. However there exists no R, where R is a subset of Q, such that R :- C. Here we an infinitary language (since the conjunction is infinitely long), and it is known that such languages are not compact.
He that dies pays all debts - Shakespeare's Stephano from The Tempest Truth is its own measure - Spinoza, Ethics IIp43s Those who deny [Aristotle's] first principle should be flogged or burned until they admit that it is not the same thing to be burned and not burned, or whipped and not whipped. - Ibn Sina (Avicenna)

MoeBlee
aka I. Kabruob

Usergroup: Members
Joined: May 19, 2005
Total Topics: 9
Total Posts: 1041

Posted 04/16/08 - 11:59 AM:	#6
TecnoTut wrote: Let {Q} be an infinite set of premises Impossible. {Q} is a singleton. No singleton is infinite.

muxol
yuletide

Usergroup: Members
Joined: Dec 07, 2003
Total Topics: 1
Total Posts: 1836

Posted 04/16/08 - 03:12 PM:	#7
Yes, that is very bizarre notation. Clearly there is something brilliant going on in the background that we are missing. What is a logic? At least, what are some necessary conditions for being one?

You don't have permission to post.

Please login or register.