?Forcing is fancy diagonalization? (was: Reply: FOM:Natural Examples)

William Calhoun wcalhoun at planetx.bloomu.edu
Wed Sep 1 21:18:31 EDT 1999

On Mon, 23 Aug 1999, Bart Kastermans wrote:

> I know Cantor diagonalization and I am learning forcing (I am reading the
> book by Kunen).  I do not at all see how forcing can be seen as a form
> of diagonalization, can someone explain?
> [...]
> BK
> -- 
> Bart Kastermans, Engelandstraat 68, 1966 NJ Heemskerk, The Netherlands
> tel./fax.: +31-(0)251-239 832, Time Zone: GMT + 01:00
> Home-Page: http://www.cs.vu.nl/~bkaster/
First, I'll repeat my disclaimer that I am not a set

I was using "diagonalization" to mean a construction
in which an omega-list of conditions are met in an
omega-sequence of steps.  

In forcing, we may construct a generic filter G for
a countable poset P in an omega-sequence of steps.
At each step add an element from one of the dense 
subsets of P to the set of generators for G.  (See
Kunen Chapter VII, Lemma 2.3)     

In the historical remarks at the end of Chapter VII
Kunen says:

   In recursion theory, many classical results may
   be viewed, in hindsight, as forcing arguments.  
   Consider, for example, the Kleene-Post theorem 
   that there are incomparable Turing degrees.

He goes on to show how that argument, usually called
a diagonal argument, may be viewed as a simple forcing

So if diagonalization is "simple forcing" I think it's
fair to say that forcing is "fancy diagonalization."

-Bill Calhoun
-Math, CS, and Stats 		wcalhoun at plantex.bloomu.edu	
-Bloomsburg University		Telephone: 570-389-4507  
-Bloomsburg, PA 17815		FAX: 570-389-3599
Position: Assistant Professor	Research Interest: Computability

More information about the FOM mailing list