[FOM] SOL vs. ZFC
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
http://www.math.helsinki.fi/logic/people/juliette.kennedy/
More information about the FOM
mailing list