?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
theorist.
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
argument.
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