[FOM] Poker/First/Second Order

[Harvey Friedman]

Reply to Buckner 8:41PM 5/19/03 and 7:49PM.

>
>
>Logically, we can do without cardinal numbers altogether.

Tell us how you want to express and prove the following without 
numbers. Ultimately you have to express it in a form that you can 
then prove it. What axioms are you going to use to prove it? Tell us 
how you want to express the relevant axioms without numbers.

###There are more straights than flushes in 5 card poker.###

Here is the background. A deck of cards consists of cards in four 
suits (clubs, diamonds, hearts, spades), and there are 13 cards in 
each suit, 2,3,4,5,6,7,8,9,10,J,Q,K,A. There are a total of 52 cards 
in the deck.

A poker hand consists of 5 distinct cards from the deck.

A straight is a poker hand whose five cards are consecutive, but the 
cards can be of any unrelated suits. It is required that not all 
cards be of the same suit (that would be instead a straight flush). 
The consecutive orders allow A to be  used as a 1, so that A2345 is a 
straight (provided not all of the same suit).

A flush is a poker hand whose five cards are all of the same suit, 
and the five cards do not form a straight flush.

>
>Well, what is the one most important issue that you feel philosophers (if
>they are the culprits) have misunderstood?  I don't actually have a problem
>with quantifying over properties.  I have a problem, as I said before, with
>carving "Socrates is bald" into two bits ("Socrates", "is bald") plus a
>relation between the referents of the two parts.

They sometimes don't take into account the extreme difference between 
semantic implication from first order systems, and semantic 
implication from second order systems.  One is known to be directly 
related to models of mathematical practice, whereas the order is 
known not to be directly related to models of mathematical practice. 
Here by model, I don't mean model as in "relational structure", but 
rather in "scientific model".

For example, it is well known that the continuum hypothesis, CH, or 
its negation, not CH, is semantically implied by ZFC as a second 
order system.

But does it follow that mathematicians are either able to establish 
CH from ZFC or able to establish not CH from ZFC, in some relevant 
sense of "establish" that is relevant to mathematical practice? I.e., 
prove and submit to a Journal for publication that uses ZFC as their 
standard?

Certainly not.

On the other hand, suppose it were the case that CH or its negation 
is semantically implied by ZFC, as a first order system.

It would then follow that CH is provable in ZFC or not CH is provable in ZFC.

This would mean that, at least in principle, we could publish a proof 
of CH or publish a proof of not CH in a Journal that uses ZFC as 
their standard.

That is why

1) the establishing in 1938-40 and 1962-63 that CH and not CH are not 
semantically implied by ZFC as a first order system, (assuming ZFC is 
consistent), was a great event in scientific history; and

2) the establishing in ???? that CH  or not CH is semantically 
implied by ZFC as a second order system was a nonevent, where few 
people know who to credit with it and where an original reference 
would be. It is also (essentially) trivial.

To add to the confusion, there are some perfectly standard formal 
systems associated with second order systems. Of course they are not 
complete with respect to the usual second order semantics. But they 
are syntactically "ordinary", in that proofs are strings of symbols, 
and there is a decision procedure for testing whether or not a string 
of symbols is a proof.

Now if ZFC is couched in terms of such a standard formal system for 
second order logic, then we get a variant of ZFC - depending on the 
exact setup, perhaps something very close to MKC (Morse Kelly class 
theory with axiom of choice).

Then the results about CH work almost without any change whatsoever, for MKC.

So as a model of mathematical practice, second order logic behaves 
almost identically to first order logic but with certain 
comprehension axioms taken for free.

Using second order logic as a model of mathematical practice is the 
same as using first order logic as a model of mathematical practice 
but with the boundary between what is logic and what is mathematics 
shifted to the "right".

I should add that the use of second order logic mentally may be, in 
some contexts, a very good idea because of the previous paragraph. 
E.g., I have been keeping an eye open to using this aspect of it for 
some ambitious projects.

>
>>There is no difficulty, as there is a huge literature on various
>>logics" in between first and second order "logic". If you are
>>familiar with this literature, then the efficiency of communication
>>would greatly increase.
>
>If you or any other competent FOM member could suggest some sample
>literature, I'll read it.  Preferably something available over the internet,
>or via online journal, or in collection that is in print, or in book that is
>in print.
>
>Or in book/collection/offprint owned by FOM member who is prepared to sell
>to me.  I will pay good prices (within reason).

I have a collection in very good condition I will sell to you for $2,000,000.

If that's too much money, first  start by doing a search on "weak 
second order logic". Also "generalized quantifiers".

>
>>By thinking through what an interpretation is, you will clearly see
>>the great power of f.o.m. in clarifying and addressing a huge range
>>of issues including the ones that you raise. Do you agree with this?
>
>Perhaps when I understand what an interpretation is!  I read some papers by
>Feferman on his site, they suggest the notion is more difficult than your
>previous summaries.

This is vital. See below. 

>
>I read your VIGRE Foundations lecture, but the idea appears to be introduced
>on p.10 without ceremony, where you write
>
>"A relational structure consists of a non-empty set D called the domain,
>together with interpretations of all constant, function, and relation
>symbols"

This is the beginning of the study of first order predicate calculus.

FOM subscribers: what are the good elementary texts nowadays for 
philosophers that have the semantics and syntactic stuff done pretty 
thoroughly? And also discusses, decently, interpretations?