FOM: Re: Query on first-order logic

[Joe Shipman]

Answering my second question below:

T(S) is finite iff the following game is a first-player win:

Player 1 selects a pair of contradictory sentences {P1, ~P1}
Player 2 chooses one sentence S1 from {P1,~P1}
Player 1 selects a pair of contradictory sentences {P2, ~P2}
Player 2 chooses one sentence S2 from {P2,~P2}
etc.
Player 1 wins if at some stage he gets complete information from Player 2
-- that is, the conjunction S&S1&...&Sn is inconsistent or axiomatizes a
complete theory.  Player 2 wins if he can avoid giving complete
information at any finite stage.

This is an interesting formalization of the "20 questions" game, where 20
is replaced by omega.

If T(S) is countably infinite Player 1 wins the modification of the game
where it has omega+1 stages instead of omega stages; but I can think of an
example where T(S) has cardinality 2^aleph_0 which is also a player 1 win
at the omegath stage, so this doesn't go in the other direction.


Joe Shipman wrote:

> Given: a sentence S of first-order logic (may include function symbols
> and relation symbols of arbitrary arity, constants, and the equality
> symbol).
>
> Consider the set T(S) = {complete, consistent theories in the language
> of S which include S}.  |T(S)|=0 iff S is inconsistent; |T(S)|=1 iff S
> axiomatizes a complete theory.
>
> Is it provable that the only possible cardinalities for T are
> {0,1,2,...,aleph_0, 2^aleph_0}?
>
> Is there a nice characterization of the S for which T(S) is finite?
>
> -- Joe Shipman