?Forcing is fancy diagonalization? (was: Reply: FOM:Natural Examples)
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?
> 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
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."
-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