Morning.

Morgen!

Du sprichst Deutsch?

Natürlich.

That's a surprise : D

It is?

Yay, I think I just proved I => II. Now for the other direction...

Fine.

Did you use there they're two characterization of consistency?

I mean this:

The following two characterizations of consistency will be frequently used in this text without explicit reference.

A set $\Sigma$ of formulas of $L$ is consistent iff $\Sigma\not\vdash\varphi$ for some sentence $\varphi$ of $L$.

@MartinSleziak I proved it by doing (not II) => (not I). If there is no model then we have vacuously T makes all sentences true. So it makes true $\varphi$ and $\lnot \varphi$.

Let $\Sigma$ be a set of formulas of $L$ and let $\varphi$ be a formula of $L$. Then $\Sigma+\{\varphi\}$ is consistent iff $\Sigma\not\vdash\not\varphi$.

@MartinSleziak Yes.

fine, it seems we probably have similar proofs

So this is the direction you did, too?

I tried to do this one directly, but I don't think there's much difference.

In fact this is what I wrote down, to keep my attempt:

Ah cool, so we don't have the exact same proofs. That makes it more interesting : )

If $T$ is consistent, then there is a formula $\varphi$ such that $T\not\vdash\varphi$. By version I, this implies $T\not\models\varphi$. For the later to hold, there must be at least one model of $T$.

I concluded the proof by saying that since $T$ is consistent, either $T \nvdash \varphi$ or $T \nvdash \lnot \varphi$ hence (II) has got to be false.

Which is basically the same argument you wrote above: If there is no model then we have vacuously....

Yes, right.

So I would say there is only minor differences between the two proofs, they're practically the same.

How did you get $T \not \models \varphi$ implies that there has to be at least one model?

If $T$ has no models then $T\models\varphi$ for every formula by definition.

Definition of $T\models\varphi$ is that it is fulfilled in every model, IIRC.

How do you get "not models" in latex?

If there are no models, this is vacuously true.

\not\models

@MartinSleziak Thanks : )

Test: \nvDash $\nvDash$

I am not sure \vDash and \models are the same (spacing and such things): $A \vDash B$ $A\models B$.

@MartinSleziak Ah, right. $T \models \varphi \iff \varphi$ is true in every model of $T$. Hence negating both sides gives you "exists a model such that $\varphi$ is not true in it" on the right hand side.

@MartinSleziak Which one do you use?

I use \models

Me too.

@MattN That's the reasoning I had in mind.

I looked at your messages again.

Which one?

You wrote something like: Suppose T is consistent but has no model. This is basically negation of II.

Then you used validity of I, to show that this leads to T being not consisten.

Ok, so this is I $\Rightarrow$ II.

For a second I was hesitating whether it wasn't different direction. but it seems that I confused something.

Oh, I messed up I & II because I wrote them in a different order on my piece of paper : ( sorry for the confusion.

So now I'm confused too.

I tried to give the Zusamennfassung of your proof, from what you wrote here in chat.

I did "not (II) => not (I)" which is, as you said, "(I) => (II)". Now I'm trying to do "(II) => (I)".

That's what I wanted to hear.

: )

It's I=>II - in the notation from the book.

Yes.

I'm going to make something to eat. I'll be AFK for some time.

Ok! Guten Appetit. : )

Then $T \models \lnot \varphi$ (vacuously because it doesn't have a model) and hence by assumption we have $T \vdash \lnot \varphi$ which would be a contradiction to $T$ being consistent.

Now I'm going to do exercise 8.

Let $T$ be a theory.

Claim: $T$ has a model $\iff$ every finite subset $S$ has a model.

$\implies$ Assume $S \subset T$ does not have a model. Then by Gödel's completeness theorem version II, $S$ is not consistent. Hence $T$ is not consistent, that is, $T \vdash \varphi$ and $T \vdash \lnot \varphi$. By the soundness theorem we hence have $T \models \varphi$ and $T \models \lnot \varphi$. But this can only hold if $T$ does not have a model.

If $S\subseteq T$, then every model of $T$ is a model of $S$.

Isn't this shorter/simpler version of what you just wrote?

This should be the easier direction.

Your proof of I=>II seems ok to me.

@MartinSleziak True.

Again, it's II=>I in the book's notation, right?

No, I think it's I => II.

I assume I and "not II" and make a contradiction to show II has to hold.

Ok, doesn't matter; the important think is we've shown both of them are equivalent.

@MattN $\Longleftarrow$ Let $T$ be such that every finite subset $S$ has a model. Assume $T$ does not have a model. Then for all sentences $\varphi$ in $T$ we have $T \models \varphi$ and $T \models \lnot \varphi$. $S= \{\varphi, \lnot \varphi \}$ is a finite subset of $T$ hence by assumption has a model. But in any mode $M$, $M \models \varphi$ and $M \models \lnot \varphi$ is impossible hence $T$ has to have a model.

One direction of my proof has to be wrong since I don't seem to use that $S$ is finite anywhere.

IMO it's ok. You don't need finiteness for $\Longrightarrow$.

Your proof seems ok to me.

I tried to do this one using the fact that every proof is finite.

So if $\varphi$ is provable from $T$, only some finite fragment of $T$ is used in the proof.

Where did I use that $S$ is finite? It seems to me I showed the claim for $S$ arbitrary.

BTW if you remember, Asaf mentioned recently in the chat that he was giving a lecture which included the proof of compactness theorem using Konig's lemma. (That's a result on infinite trees - I don't know whether you've already studied things like this.)

@MattN You've used finiteness in $\Leftarrow$. Namely, you used the fact that $S=\{\varphi,\neg\varphi\}$ is finite.

Or I have misunderstood your question.

@MartinSleziak No I haven't.

@MartinSleziak But if I drop the assumption that $S$ is finite in the statement of the theorem then $S = \{ \varphi, \lnot \varphi \}$ is still a subset of $T$ and the rest of the proof still works even though $S$ is not necessarily finite.

So "If every arbitrary subset of $T$ has a model then $T$ also has to have a model".

@MattN This only says that you could also prove in the same way: If every subtheory $S\subseteq T$ has model, then $T$ has model.

This is a trivial result, since $T\subseteq T$.

If you assume that every finite subset has model, you have weaker assumptions and stronger result.

@MartinSleziak Oh.

Thank you : )

np

It's good way to study, that you check whether you have used all assumptions.

Yes otherwise the proof might be wrong : )

They mention exactly this somewhere in the book.

Since I've mentioned Konig's lemma, it's in Chapter 14 of this book. (It's 2nd volume.) They also have result about relation to compactness theorem there.

Ok.

So we have $T \models \varphi$ if and only if $T \vdash \varphi$.

Hence if I want to show that $\varphi$ is consistent with $T$, which is the same as saying $T \nvdash \lnot \varphi$, then it's enough to find a model of $T$ that doesn't make $\lnot \varphi$ true.

Ah, for this to work $T$ has to be consistent.

No, it works even if $T$ is inconsistent.

Found another typo: page 79, penultimate paragraph, "nonabilian".

By $\varphi$ is consistent with $T$ you mean that $T\cup\{\varphi\}$ is consistent?

Or you meant the following: If $T$ is consistent, then $T\cup\{\varphi\}$ is consistent.

(As in relative consistency.)

@MartinSleziak I meant this.

Well then $\varphi$ consistent with $T$ implies that $T$ is consistent.

True.

The whole talk about consistency has to be relative, in a philosophical sense at least, because you always at least assume the consistency of first order logic.

Hi, Asaf. I've mentioned proof of Compactness Theorem using Konig's Lemma above: chat.stackexchange.com/transcript/message/3173998#3173998

You were talking about it in some course you teach, right?

Yes.

Did you talk about compactness of predicate or propositional calculus?

The former requires more while the latter requires Koenig's lemma (which is fairly little).

First order-logic

Furthermore if the set of propositional variable is countable then we can prove it straight out of ZF.

Yes, this requires (in fact equivalent) to Stone's representation theory, the boolean prime ideal theorem, the ultrafilter lemma, etc.

Hmm... I don't see Google books preview for the Volume 2 of the book :-(

I'll check it later I have to go for a bit.

They formulated there the following weaker version of compactness theorem:

(WCT) Let $L$ be a first-order language without functional symbols, and let $(S_n)_{n\in\omega}$ be an increasing sequence of finite sets of quantifier-free sentences of $L$. If each $S_n$ has a model, then the theory $S = \bigcup_{n\in\omega} S_n$ also has a model.

And they claim that it is equivalent to Konig's lemma (in ZF) - Theorem 14.4.

Another equivalent condition from the same theorem is this:

(WTY) Every product $\prod_{n\in\omega} X_n$ of finite non empty Hausdorff spaces $X_n$ is nonempty and compact.

I would have to check where choice is used in the proof of Konig's lemma - I haven't thought about this before. I'll probably let it be at the moment.

Found another typo: page 59 in $(R)_z$ it should be $F_{\color{red}{z}} (y) = G(F_{\color{red}{z}} |I(y), y)$.

At the bottom of page 59: what does $J$ look like if $Z := \omega$?

If $Z$ is $\omega$, then $I(z)=\{y\in\omega; y<z\}$,

So I would say $J=\{z-1\}$.

@MartinSleziak Thanks! Sorry I wrote something other than what I meant. I was trying to figure out what $I(\omega)$ looks like!

@MattN But if $Z=\omega$, then $\omega\notin Z$.

You define $I(x)$ only for $x$ from that well-founded set you're working with.

@MartinSleziak Yes, let $Z := \Omega$, the set of all ordinals.

: )

Then $I(\omega)=\omega=\{1,2,\dots\}$.

I would say initial segment is pretty good name. It's descriptive.

Doh, I did it again. I meant $J$ for $Z := \Omega$!

Ok, so the question is $J$ for $Z=\Omega$ and $z=\omega$.

Yes: $J = I(\omega) \setminus \bigcup_{k \in \omega} I(k)$

It would be $J=\emptyset$, wouldn't it?

I don't know. Would it?

Ah yes.

I think so.

$I(k) = k - 1$

This kind of makes sense.

@MartinSleziak That should contain $0$!

@MartinSleziak Yes, after you told me that $I(\omega) = \omega$, I see that $J$ should be the empty set. Thanks!

@MartinSleziak Because in this inductive step, you would simply define $F_\omega=\bigcup_{n<\omega} F_n$.

Hm... Where does this $f$ come from at the top of page 61?

The guy who scanned the book was being a dick :-P

Why?

He's joking.

Obviously. :-)

But what's the joke?

I have a paper copy.

The joke was that $f$ came out of the bad scan.... I guess.

Ok. Level of funniness does not exceed 5 out of 10.

No, that the guy who scanned the book added it intentionally to fuck with the future readers.

Same level of funniness. : )

Bite my shiny metal spoon. :-)

You mean in 2nd line: $f:I(z)\to X\cup\{\infty\}$?

@MartinSleziak Yes.

They want to define function $G$ from the theorem about recurseive definitions.

@AsafKaragila There is no spoon.

So they have to define value of $G(f,z)$ for each $f$ defined on $I(z)$.

@MattN I have one right here by my side, therefore $\exists x.\mathrm{Spoon}(x)$ is a true sentence.

So they only saying: Suppose $f$ is given, we're going to define $G(f,z)$ to be like this.

@AsafKaragila No.

@MartinSleziak I see.

Right.

Thanks Martin.

Doh.

?

Just me making the same mistake for the third time. : )

@MattN Bite it.

Look, we have a visitor. Hello Brian.

Hullo.

@AsafKaragila It doesn't look so shiny to me, meatbag. (Noo, you tricked me into watching Futurama.)

Muhahaha!

I think one of the creators has PhD in physics?

Applied math.

There were some math jokes in that show.

Ken Keeler.

They proved a theorem just to write an episode around it.

The cumulative hierarchy and the von Neumann universe are the same, right?

No.

It looks like it's a subcollection of sets inside the von Neumann universe.

I would say every set has a rank by axiom of regularity, if you're working in ZFC.

A ranked family of sets, in fact.

So it is the von Neumann universe?

I'd say yes.

The von Neumann universe is $V$; the cumulative hierarchy is the family of sets $V_\alpha$.

You skipped a few chapters, didn't you?

But I guess they mentioned this somewhere in introduction.

No, that's actually a question that I've been wondering about unrelated to the book.

@BrianMScott But by the construction of $V$ there are no sets in it other than $V_\alpha$.

The universe is the "limit" of the hierarchy.

You mean $V=\bigcup V_\alpha$.

@MartinSleziak I'm on page 81 but I had skipped 61-65 which I'm reading now.

@MattN Sure there are: all of the sets that are members of the $V_\alpha$’s!

@MartinSleziak Yes.

@MartinSleziak Informally, yes.

Which is basically another way of saying that every set has a rank.

Yes.

@BrianMScott So they're not the same!

@MattN Which is what I said: $V$ is (informally) the collection of all hereditarily well-founded sets, while the cumulative hierarchy is a way of breaking that collection into sets by rank.

@BrianMScott Got it now, thank you!

I like the name a professor who taught me used for the cumulative hierarchy: Creating the universe (of sets) from nothing (=from $\emptyset$) There are sets which were created on the 1-st, 2-nd, ..., $\omega$-th, ... day

Sounds like Conway's Surreal numbers :-)

That was my reaction, too.

I should get that book, many people have mentioned it.

Of course the quote might get mangled by him translating it to Slovak and me back to English.

@MartinSleziak I meant Knuth's book.

And what is $z_0$ on page 61 in the proof of claim 31 (right before exercise 43) where it says "Then $z \neq z_0$."?

You’d have to check earlier in the book to be sure, but my guess is that it’s $\min Z$ with respect to the given well-ordering.

That would make sense. They didn't define it anywhere explicitly but they have used $x_0$ in another place to denote the $W$-minimal element in $X$.

Thanks.

I count this as a typo of the bad sort.

Then the answer to exercise 43 would be: if $z = z_0$ then $F(z_0) = G(F|\emptyset) = \emptyset \neq x$.

@MattN I don’t think so, but let me ask first: what’s their definition of $\sup^+$?

@BrianMScott They define it as the minimum element of $X \setminus DC(Y)$ where $DC(Y)$ denotes the downward closure of $Y$.

Doh.

$\sup^+$ of the empty set is of course not the empty set. Not in this case anyway. Unless $X$ is empty which it isn't, by assumption.

But it would be the minimal element of $X$ which it can't be because we picked $F(z)=x$ from a set from which we removed an initial segment $I(y)$.

Exactly: I believe that it should be $x_0$. But $x\ne x_0$; why?

@BrianMScott In the book where it says $z \neq z_0$ it should be $x \neq x_0$?

@MattN No, $z\ne z_0$ is fine. But the reason for this is that $x\ne x_0$.

Ah. : )

@BrianMScott Because $F(z) \in \operatorname{rng}{(F)} \cap X \setminus I(y)$ and $x_0 \in I(y)$?

So $x_0$ seems to be the notation for the smallest element of $X$ and $z_0$ the notation for the smallest element of $Z$, right?

@MartinSleziak Yes.

I'd say what you wrote seems to be a good argument.

@MartinSleziak That’s how I’m interpreting it.

@MattN Yes.

@BrianMScott Cool thanks. I got insecure because I had written this here.

@MattN I don’t think that I’d actually noticed that; if I remember correctly, I responded before you added that bit.

Probably. I wasn't looking at the screen when your post appeared. : )

Hello Srivatsan.

Matt, I know you don't like handwavy things but I actually added some "reading material" to the handwavy post in which I link to a non-handwavy explanation of the Levy collapse forcing.

That sounds above my head.

First I need to understand what was in the lecture. But I haven't looked at forcing yet.

@AsafKaragila What's the link to your answer?

@MattN It's the simplest example of forcing.

@AsafKaragila Thanks! I'll read it when I start doing forcing.

Good.

@MattN I am not sure how much time I will have during the workdays. (The next week will probably rather busy.) So it's quite probable that I won't have much time for reading the book. But I'll try at least to check every day, whether there is something new in this chatroom.

@MartinSleziak That's fine. : )

You'd probably be able to catch up with what I did during the week in a couple of hours if you wanted to next weekend.

What does the underline in $\underline{\notin}$ mean on page 61 in case 1?

@MattN I don’t see an underline, if you’re talking about $\infty\notin rng(F)$.

Yes, that's the one. Then it's probably a printo.

Good night folks.