Re: Can we have Second Order Logic expressibility in FOL?

From: Leonid Portnoy (lp178_at_columbia.edu)
Date: 01/24/05 

Date: Mon, 24 Jan 2005 05:24:25 GMT

>In sci.logic Leonid Portnoy <lp178@columbia.edu> wrote:
>> If we can axiomatize set theory in FOL using ZFC, then it seems we can
>> quantify over sets, and thus over relations and functions since they
>> are sets. But isn't this the domain of second order logic - to be able
>> to quantify over predicates (i.e. relations)?
>
>> [ snipped example from graph theory ]
>
>> Or, why can't we represent mathematical induction:
>
>> Ap (P(0) ^ Am P(m)->P(m+1)) -> AnP(n)
>
>> where again p ranges over all functions [which are sets defined in FOL
>> via ZFC].
>
>Because that's just passing the buck. First let's rewrite your
>induction principle in set notation,
>
> AP (0\in P ^ Am (m\in P -> (m+1)\in P)) -> N \subset P
>
>This is a single sentence in set theory, but to apply it to specific
>cases where you prove that every natural number has some property,
>you first have to prove the existence of the set P of of all things
>that have the property. To do this, you have to rely on axioms
>and axiom schemas formulated in first-order logic and this is where
>the limitations come back.

Can you give a specific example (that shows how the limitations come
back)?

For simple applications it seems we can easily formalize the
properties of P in our first-order theory. For instance, we can
formalize the following { x \in P : Sum(1 to x) = x*(x+1)/2 }
and then use the induction sentence to prove N \subset P.
Are you saying that we can not prove the existence of P
i.e. "Es (IsSet(s) ^ s=P)" in our theory? Then how do we develop
mathematics based on ZFC, where we (I assume) have to prove the
properties and existence of many different sets.

>A more subtle phenomenon occurs if you try to use the above as a
>second-order-ish definition of the natural numbers ("N is the
>smallest set containing zero and closed under successor"). The
>quantifier on P looks right, but it is weaker than intended because
>your set theory based on first-order logic does not "see" all the
>sets. As a result, your theory (if consistent, blah blah blah)
>has nonstandard models with hyperfinite natural numbers.

Will that mean that certain sentences about N won't be provable (since
they will be valid under the standard model but invalid under the
nonstandard one)?

Leonid Portnoy

Relevant Pages

  • Re: extending ZFC
    ... > can be a good framework for working with set theory, ... We quantify over all ... since we are only talking about their truth in ...
    (sci.math)
  • Re: Aleph One Sets
    ... >> except to set theory specialists. ... you're explaining the TRUTH to some IDIOT: ... The axioms of ZFC were not handed down by God. ...
    (sci.logic)
  • Re: Countable models of ZFC
    ... Might not some set be the domain of a model of ZFC? ... I thought you were talking about the intended model. ... underpinnings of your mathematics. ... think they can understand the first-order language of set theory. ...
    (sci.logic)
  • Russels Revenge
    ... (axiomatic set theory might be accepted better) ... although it is ofcourse my own revenge, in the spirit of Russel. ... no name calling, just an overview of the foundations, axiomatic systems or whatever you want to call them. ... ZFC was ' suppose to ' resolve russels paradox. ...
    (sci.math)
  • Re: lets turn the tables
    ... ZFC goes ... NFU+~Infinity contradicts Aatu's classical philosophy. ... basic principles of set theory compelling and evident. ... feel the same way about their respective theories as Aatu ...
    (sci.math)