jkennedy at mappi.helsinki.fi jkennedy at mappi.helsinki.fi
Tue Jun 4 11:43:37 EDT 2013

 From Jouko Vaananen:

The set of validities in second order logic is not Pi^1_2-complete,  
not even Pi^m_n-complete for any m and n, but it is Pi_2-complete in  
the Levy hierarchy (see Vaananen: "Second order logic and foundations  
of mathematics", Bulletin of Symbolic Logic, Volume 7, Issue 4,  
December, 2001).

Concerning your questions:

1) The only commonly used axiom system for second order logic that I  
know is the one given in Hilbert-Ackermann (1928) based on axioms of  
(impredicative) comprehension. The Soundness Theorem of this system is  
provable in ZFC, so anything that is valid in that system is provably  
valid in ZFC. One can easily formulate such new axioms for second  
order logic that cannot be proved valid in ZFC, for example the V=L,  
Continuum Hypothesis, etc. The question is then, is V=L a commonly  
used axiom of second order logic, I think not.

2) The obvious example is the following: Let A be the Hilber-Ackermann  
axiomatization of second order logic. Let B be the second order Peano.  
Let C be the number theoretic statement of consistency of A+B. Now ZFC  
proves the validity of the second order statement "B implies C". By  
Goedel's theorem we cannot prove in A+B the statement C, and hence not  
the statement "B implies C" in A.  (See also Vaananen: "Second order  
logic or set theory?" Bulletin of Symbolic Logic, 18(1), 91-121, 2012.)

Best Wishes

Quoting Joe Shipman <JoeShipman at aol.com>:

> The set of validities in Second Order Logic with standard semantics  
> is Pi^1_2 complete, so we can't give a complete axiomatization. My  
> question has two parts:
> 1) is there any commonly used system of axioms for second order  
> logic that includes sentences which ZFC does not prove are validities?
> 2) is there any sentence which ZFC proves is a validity of second  
> order logic, but which is not a consequence of any commonly used  
> system of axioms for second order logic other than the system  
> "enumerate sentences with ZFC-proofs of their validity"?
> -- JS
> Sent from my iPhone
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom

Department of Mathematics and Statistics
P.O. Box 68 (Gustaf Hällströmin katu 2b)
FI-00014 University of Helsinki, Finland
tel. (+358-9)-191-51446, fax (+358-9)-191-51400

More information about the FOM mailing list