1
$\begingroup$

I have studied set theory but I couldn't understand even the first line of the Godel's proof.

For instance, $\omega^n$ means the set of functions from $\omega$ to $n$ in my set theory, ZFC,

but the proof I got says;

" For $R\subset \omega^n$ a relation, $\chi_R:\omega^n \rightarrow \omega$ is given by

$\chi_R (\overline{a}) = 1$ if $\neg R(\overline{a})$

$\chi_R (\overline{a}) = 0$ if $R(\overline{a})$ "

To me, it has to be $\omega \times ... \times \omega$ ($n$ times) for $R$ to be a relation, not $\omega^n$. What's going on?

Why does this use $\overline{a}$ rather than $a$, if it designates arbitrary one? Any reason?

I am not even sure whether function here has the same meaning as function defined in ZFC.

And does $R(\overline{a})$ mean "$\overline{a} \notin R$" ?

I don't understand why it says $\Delta$, a set of sentences of our language. Why is it set, not just collection?

That is, why we cannot form a collection of sentences consist of $\exists, \forall$ and so on, which is not a set?

There are several terminologies i don't understand too.

Computable, $\mu$ and so on.

Since these theorems are provable in any axiomatic system, i don't know what in ZFC is true and what in ZFC is not true in arbitrary axiomatic system. In other words, what is always true in any axiomatic system?

Please recommend me a nice book to study this. I don't want to go any further in mathematical logic than to understand these theorems.

$\endgroup$
5
  • 1
    $\begingroup$ Actually, $\omega^n$ is the set of functions from $n$ to $\omega$, not the other way around. $\endgroup$
    – Thomas Andrews
    Oct 16, 2012 at 13:57
  • 1
    $\begingroup$ This question strikes me as very unfocused. The imcompleteness theorem, in particular, has lots of "popular" treatments out there of varying levels of detail. Forcing, on the other hand, is a deep tangle, a highly technical subject for which I have never seen an 'easy' introduction. The subject asks for references, the body asks specific questions about the text you are reading. $\endgroup$
    – Thomas Andrews
    Oct 16, 2012 at 14:01
  • $\begingroup$ @ThomasAndrews I'll change the title. Since those are only logic theorems i know, i typed it. $\endgroup$
    – Rubertos
    Oct 16, 2012 at 14:06
  • $\begingroup$ I found amazon.com/Incompleteness-Phenomenon-Martin-Goldstern/dp/… to be a very accessible introduction. I starts with basic logic, goes on to prove Gödel's Completeness Theorem, and then the Incompleteness Theorem. It also contains some model-theory (i.e., simply non-standard models of the integers), and also a proof of the model-theoretic version of the Completeness Theorem (the ultrafilter construction). $\endgroup$
    – fgp
    Oct 16, 2012 at 14:37
  • $\begingroup$ $\overline a$ stay for an $n$-uple. $R(\overline a)$ is an $n$-ary relation and $\chi_R$ is its characteristic function, i.e. a function that for each $n$-uple $\overline a$ returns $0$ if $R(\overline a)$ holds [i.e. $\overline a \in R$] and returns $1$ if $\lnot R(\overline a)$ holds [i.e. $\overline a \notin R$]. $\endgroup$
    – Mauro ALLEGRANZA
    Apr 4, 2017 at 14:48

1 Answer 1

Reset to default
2
$\begingroup$

"I couldn't understand even the first line of the Gödel's proof." Gödel's proof of what?

The mention of forcing [in the original title] suggested that what you are ultimately interested in is independence proofs, i.e. understanding how Gödel showed that AC is consistent with ZF, CH consistent with ZFC, and how Cohen used forcing to show that not-AC is consistent with ZF, not-CH consistent with ZFC.

In which case the book for you is probably Kunen's classic Set Theory (now in a new version from College Publications). It has to be said that getting to grips with forcing proofs isn't easy: however Gödel's consistency proofs using constructible sets are relatively accessible.

If on the other hand the talk about ZFC is a red herring, and what you are interested in is Gödel's proof of the incompleteness theorem [as the comment below now suggests], then that's a whole different ball-game (it's a general result about theories which incorporate a little arithmetic, and not especially to do with set theory). I'd recommend P*t*r Sm*th's Introduction to Gödel's Theorems, but then I would, wouldn't I ...? See http://www.logicmatters.net/igt/

$\endgroup$
1
  • $\begingroup$ Exactly and yes i heard that proof of forcing is extremely hard, so i cannot handle that right now, but i am about to start with Godel's Incompleteness theorem. $\endgroup$
    – Rubertos
    Oct 16, 2012 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.