Gödel Incompletness theorem

I am not familiar with model theory. As a matter of fact, I only had my first Logic and Set theory courses last semester. But still, there is a question that bothers me, and It could be nice if someone here could give me an explanation which does not requier more then the background that I have.

If I understand correctly, a model (or a structure?) is a set $(D,v_i,f_i,P_i)$, where $D$ is the set of items we make our claims on, $v$ are variables $f$ are functions and $P$ are relations that get $T$ of $F$ value. Also, If I got that right, the proof of Gödel showed that in certain structures Cantor's CH is true and in others not.

The thing that is not clear to me: isn't Continuum Hypothesis coming with a given structure? I mean, don't we know that: $D= \mathbb R$, $v_i$ can get real numbers, $f$ are all the mathematical functions that $f_i \rightarrow OR$ where $OR$ is the space of ordinals (or cardinals if it matters). So, what does that mean to talk about different models when refering to the CH.

Can anyone give me an example of a model where the CH is true, and a model where CH is not true where the two models are relevant to the question?

Thanks Lior

• I think he means Kurt Godel en.wikipedia.org/wiki/Kurt_G%C3%B6del – topsi Jan 14 '14 at 10:09
• I think that you are mixing up two different important results due to Gödel : the Incompleteness Theorem and his result about the independence of the axiom of choice and of the continuum hypothesis in set theory. – Mauro ALLEGRANZA Jan 14 '14 at 10:22
• You're making a huge salad of a lot of results in set theory and logic. – Asaf Karagila Jan 14 '14 at 10:27
• Start with a first-order language $L$ with a set of predicates, each predicate $P_i$ of $L$ being designated as $n$-ary for some nonnegative integer $n$. Assume the existence of a fixed, countable set of symbols $\{ v_i \}$ called (individual)-variables. Let $D$ be a nonempty set, and let $D_n$ the set of all $n$-tuples of elements of $D$, i.e. $D_n = \{ < a_1, ..., a_n> | a_1, ... a_n \in D \}$ . An $n$-ary relation on $D$ is a subset of $D_n$. 1/2 – Mauro ALLEGRANZA Jan 14 '14 at 10:34
• A structure for the language $L$ (or $L$-structure) consists of a nonempty set $D$, called the domain or universe, together with an $n$-ary relation $P*_i$ on $D$ for each $n$-ary predicate $P_i$ of $L$. 2/2 – Mauro ALLEGRANZA Jan 14 '14 at 10:36

First of all, let us clear some things.

Model of a theory $T$ in the language $\cal L$ is first of all an interpretation for the language, i.e. a pair $(M,\Sigma)$ where $M$ is a non-empty set and $\Sigma$ is an interpretation function. That is for every function symbol $f$ in the language, $\Sigma(f)$ is a function on $M$, and so on. Next we can define the satisfaction relation which tells us what sentences from $\cal L$ are true in this interpretation, and $M\models T$ if all the sentences in $T$ are true in $M$.

The completeness theorem tells us that $T$ can prove $\varphi$ if and only if whenever $M$ is a model of $T$, $M\models\varphi$. So provability, which is a syntactical relation between a theory and a sentence, is the same as semantic (or logical) implication. It is important to notice that this is true for first-order logic, but not necessarily so for other logics (such as second-order logic).

If there is a model of $T\cup\{\varphi\}$ we say that $\varphi$ is consistent with $T$, and if both $\varphi$ and its negation are consistent with $T$ then neither is provable from $T$ (and if neither is provable, then they are both consistent with $T$), in which case we say that $\varphi$ is independent of $T$.

Finally. Gödel proves that $\sf CH$ is consistent with $\sf ZFC$. He did so by showing that if we have a model of $\sf ZFC$ then we can construct a model where $\sf ZFC+CH$ is true. Paul Cohen, some twenty odd years later, proved that given a model of $\sf ZFC+CH$ we can construct a model of $\sf ZFC+\lnot CH$. Therefore both $\sf CH$ and its negation are consistent with the axiom of choice.

Now, Gödel also proved the incompleteness theorem which essentially says that a theory with such and such properties must have at least one statement which is independent from that theory. These statements are often "convoluted", they are constructed in a way that explicitly makes them independent. But once you are aware, and comfortable, with this phenomenon it's time to set sail and find statements which are organic (i.e. come up from the mathematics directly, natural questions to ask in the right context) and are independent.

The continuum hypothesis is such a statement, if we consider the first-order theory $\sf ZFC$. Note that the statement of the continuum hypothesis has nothing to do with the real numbers, just with their cardinality. Or rather, the cardinality of the power set of the integers.

Related:

• I like it; you linked together three of the most important results of Kurt Gödel : the completeness theorem, the incompleteness theorem and the result about the independence of the axiom of choice and of the continuum hypothesis in set theory ! I will very glad to read your Math Log textbook (are you planning to publish it ?)... – Mauro ALLEGRANZA Jan 14 '14 at 11:28
• Mauro: Actually Godel only proved the consistency, not the independence of the axiom of choice and the continuum hypothesis. As for a book, I'm flattered, but there's nothing planned at this moment. Perhaps someday. :-) – Asaf Karagila Jan 14 '14 at 11:58
• Asaf: I'll wait for it ... Thanks for your comment: I'm not well prepared about set theory (... either). I suspect having "added" Gödel's result with Paul Cohen's one; isn't it ? – Mauro ALLEGRANZA Jan 14 '14 at 13:00
• You might have to wait a very long time. It's not even provable that this time is bounded. :-) And yes, you appropriated Cohen's result to Godel. – Asaf Karagila Jan 14 '14 at 14:39