@MartinSleziak Hello. : ) Regarding exercise 4 on page 77: I think the universe of a model of $L_G$ could be any set. For example $\mathbb{N}$ or $\{0 \}$. It can't be the empty set since the constant $e$ has to be mapped somewhere.

So you're already in the model-theoretic part of the book.

@MattN I agree. If we want to make a model of $L_G$ from a group $(G,*)$, the universe will be the set $G$.

Have you seen this approach (definition of languages, formaulas, terms etc.) before, or is it the first time you see this? I'm just being curious

@MartinSleziak Theoretically it came up in the lecture at some point. But I don't like lectures so basically I learned of models and L-structures yesterday. It seems to be defined slightly differently in the course, page 9. In the book they call the thing you map the language to already a model which is slightly confusing as model is later redefined to mean an L-structure that satisfies all the sentences of the language.

@MartinSleziak The question is: when you write model do you mean a thing that satisfies all the sentences of $L_G$ or any L-structure?

In the book they seem to use the two things as synonyms. P.76: The language is supposed to enable us to describe certain mathematical structures called models of the language $L$ or $L$-structures.

But they define model of a theory on p.77 bellow.

@MattN Did you mean sentences of theory TG (p.78 above), where you wrote all the sentences of $L_G$?

There's a distinction between language of TG (theory of groups) and axioms of TG.

I did not think about this distinction when I wrote my reply, and in fact any group can serve as a model of $L_G$ (in the sense $L_G$-structure) and as a model of TG (in the sense model of a theory).

@MartinSleziak Right. There is "model of a language" (not necessarily satisfying all the axioms in the language) and "model of a theory" satisfying all the sentences in the language.

In this sense, any semigroup or monoid is an $L_G$-structure.

"pointed semigroup"?

I don't know how to call a semigroup, where I choose one special element.

I think any non-empty set is an $L_G$-structure. It doesn't even have to have a monoid structure defined on it.

@MartinSleziak I'm not sure. Are there any other sentences in $L_G$ apart from the three group axioms?

non-empty set with a binary operation and one element

@MartinSleziak Agreed.

You're right that associativity is not needed.

(A non-empty set is bound to have one element ; ) )

Yes, but you have to choose one.

There is a unary operation in the definition of $L_G$.

@MartinSleziak According to my current understanding that's needed if we ask whether the thing is a model (not just an $L_G$-structure), right?

@MartinSleziak What's that?

If you take $G={0,1}$ with the same binary operation, but if you choose a) the element 0 b) the element 1; you get two different $L_G$-structures.

Yes to both of your questions.

Yes, associativity only in model of theory.

Yes, I call unary operation what they call constant.

@MartinSleziak But isn't a unary operation for example $-: G \to G$, $g \mapsto -g$, which is not a constant?

You're right.

I should have written nullary, I guess.

I don't know, I've not heard nullary before : D

So simply ignore it. Let's agree that if I write nullary operation, I mean constant.

Ok! : )

What about $L_S$, the language of set theory? Can I use $\mathbb{N}$ to be the universe ("domain" as they call it in the lecture)?

But the point I was trying to make, is that it matters what you choose for the constant to represent $e$.

E.g. take $G=\{0,1\}$ with $\oplus$ - addition modulo 2.

@MartinSleziak Ack.

Take $e=0$ and $e=1$.

Both are $L_G$ structures.

But only in one case it will be a model, in the other not?

The first one is a model of TG; the other is not.

@MattN Exacetly.

Yay : ) I just scored a point : )

Sorry, I have to go AFK. To get my laundry from the washing machine. I'll be back in 15 minutes after I hang it.

Sure : )

Now if we use $\mathbb{N}$ as our domain/universe for $L_S$, can this be turned into a model of $L_S$ if we define the relation for $\in$ appropriately?

I think that if you looking only for $L_S$-structure (model of language), there won't be any problems at all.

bbl

Go get your laundry! I won't run away : D

For example we have to satisfy the power set axiom. I'm not sure how to think about this correctly yet but surely, the universe $U$ itself is also a set in the universe so the power set of $U$ will have to be in $U$ for it to be a model.

(where I wrote "has to be in" I probably meant "has to be order isomorphic to some subset of $U$")

@MartinSleziak I skipped 5 pages in part I which I'll read some time this week or so.

@MartinSleziak $\{0\}$ could also be an $L_S$-structure, right? Although that's a bit boring maybe as there are only two possible binary relations: either the empty relation $R = \{ \}$ or the one element relation $R = \{ \langle 0, 0 \rangle \}$ which says that $0$ is an element of itself.

Yes. all of them are $L_S$-structures.

For model of theory there will be problems, but it should fulfill some fractions of theory of sets.

But $(\omega,\in)$ seems to be more interesting, for the reason that it fulfills some of the axioms too

I guess extensionality could hold, for example.

The authors will probably get to this later in the book.

But it's worth mentioning, since you've seen things like this before.

@MartinSleziak But $P(U) \notin U$ so the power set axiom fails. Right?

@MattN Yes, powerset axiom fails.

Oh, wait a second.

Powerset axiom claims that each set has a powerset.

@MartinSleziak Yes, so the question is whether $U$ is itself a set in $U$.

And here $z\subseteq x$ is a shortcut for $(\forall w) w\in z \Rightarrow w\in x$.

If our universe is $\omega$ then $z\subseteq x$ is equivalent to $z\le x$.

This means that $z+1=z\cup\{z\}$ fulfills the requirements for the powerset of $z$ (in this model).

@MartinSleziak Which would mean the answer to my question is yes, $\omega$ is a set in $\omega$.

@MartinSleziak True! But the axiom still fails since $z + 1 \notin z$.

@MattN I would say that if we take $\omega$ as the universe, then $(\forall x)$ is the same as $(\forall x\in\omega)$. So now only integers have the role of sets.

Yes!

But $z\in z+1$.

I might have missed something there, but my feeling is that $(\omega,\in)$ fulfills powerset axiom.

@MartinSleziak $P(\omega) \notin \omega$ so the power set axiom fails. Or not?

but $\omega$ is not element of our universe

Oh true, $\omega \notin \omega$.

And also $P(x)$ might have a different meaning from the usual meaning of powerset in set theory in this special model.

I think we will get back to this later. In Chapter 7 there are a few exercises that ask whether $\langle\omega,\in\rangle$ fulfills some axioms. E.g. exercises 1,2 on p. 108.

So it might be better to leave the discussion about powerset axiom in $(\omega,\in)$ until later, when we are in Chapter 7...?

Ah cool, that's pretty soon.

Yes, agreed.

I see that the link you gave me was for the course 3136 Logik und Mengenlehre. In which year of study do people usually take that lecture?

I don't know. But it feels to me as if you could take it in any year as it doesn't seem to build on anything.

It seems that are some advanced things. E.g. he gets to forcing.

Yes but to understand forcing you only need what's been in the course.

burp

Welcome Asaf.

For the language of group theory you could use $\mathbb{N}$ as the universe and map $e$ to $0$ and then define $R = \{ \langle x, y, 0 \rangle \mid x,y \in \mathbb{N} \} $ then you'd get a model of $L_G$ that doesn't have an underlying set that is a group but the resulting thing would be a model. : ) I'm just playing around now.

But something about this must be wrong since I think I read that a model is a model of $L_G$ if and only if it is a group. Ah. But that is actually a group : D (the trivial group). Silliness.

By $\langle x,y,0\rangle$ you mean that $x*y=0$ for each x,y?

Yes.

Now I'm confused.

Well, that would be a model of $L_G$ ($L_G$-structure), but not a model of TG.

Doesn't have inverses : (

I missed that one.

Afk for a while to practice the guitar. Brb.

I'm wondering how to write down exercise 5 (a) on page 77. If $\varphi$ doesn't have free variables apart from $v_0, \dots, v_{n-1}$ and we replace all of them with $a_0, \dots, a_{n-1}$ after applying either valuation then the resulting expression is going to be same. How would you write this down properly?

@MattN I believe as an informal argument this is ok. If we would like to prove this formally, the proof would go by induction on "formulas complexity". (I'm not sure about the correct term.)

By this I mean:

1-st step: Proving this for atomic formulas.

inductive step: The claim remains true after all allowed ways formula-forming. (I.e. quantifiers, logical connectives.)

Thank you, I might have a go at this.

E.g., in that first step we would have to prove the claim for all formulas of the form $t_0=t_1$, where $t_{0,1}$ are terms. This would go again by induction on "tems complexity".

But I would be rather reluctant to try to write this down formally.

To me at seems as checking plenty of symbolic manipulations - even when we already understand that the claim is true.

Maybe that's why they rated it (R).

In this book the author calls it principle of structural induction.

@MartinSleziak Ooh! Thank you for that!

So first we'd have to show $\varphi = (t_0 = t_1)$ by induction over the terms' complexities. So we'd start with $t_0 = v_{i_0}$ and $t_1 = v_{i_1}$ in which case we have $t_0[a_{i_0}] = v_0[a_{i_0}] = a_{i_0} = v_1[a_{i_0}] = t_1[a_{i_0}]$.

Right.

As I wrote, it seems that there would be a plenty of details to write down, if we wanted to do the complete proof of this.

But "R" is supposed to be for "mature audiences". If it's that easy (just slightly tedious) it should be "G". Are we missing something?

Well, I guess someone who has never seen this type of induction before will not come up with that straight away.

Right.

I don't think they mentioned it in the book so far.

No but on the same page they mention recursion over the length of formulas which is kind of the same.

You're right.

But I still think that this inductive proof should be ok.

Ok.

The next step would be $t_0 = t_1$ for $t_0 = r_0(v_{i_0}, \dots , v_{i_{n-1}})$, $t_1 = r_1(v_{i_0}, \dots , v_{i_{n-1}})$, right?

Yes, that's right.

Ok, I think I'll skip this proof. ; )

But I like the idea.

If I was asked to prove 5(c), I wouldn't think of proving the things from 5(b) and 5(a) first.

I agree.

Actually, I ballsed up (and you didn't catch me : )): above the second step should be $t_0 = f_0(v_{i_0}, \dots , v_{i_{n-1}})$ and $t_1 = f_1(v_{i_0}, \dots , v_{i_{n-1}})$ because I used $r_i$ to denote a relation and that wouldn't be a term. I need functions $f_i$.

Yes.

Relations would give $r(v_{i_0},\ldots,v_{i_k})$.

Different kind of formula.

Yes. That would be in step 2 for atomic formulas.

Another typo in exercise 6 on page 78: the first occurrence of $\varphi_0$ should be $\varphi_2$.

Yes.

But regardless of the typo, this seems to be a tough one.

BTW do you happen to know what visible room mean in sound notification options?

No but it could mean that you only get audio notifications for the room of the active (visible) tab.

Ok, it makes a sound for message in any of the rooms I'm in.

I received notification for Mathematia room, which is in another tab.

Oh, ok.

I'll try separate FF window.

Now I have window in FF where only this chat is open, no other tabs.

Would you like me to write something to test?

And I've set it to visible room.

Ok,

It played the sound.

Could you try again, whether I'll try whether I hear it without headphones on my ears...?

Yes.

Can you hear this?

Seems to be loud enough.

This could work - I can read the book without checking the monitor every now and then.

***********

: D

back to the point, Exercise 6 seems to be really tough.

ok, it still clicks for other rooms too :-(

It seems that it doesn't matter whether it is separate window or tab.

@MartinSleziak I have it on "when mentioned", that works fine.

I get notified for all rooms I'm in but only if someone pings me.

Ok, I'll do the same.

If I don't react for long time, feel free to ping me.

I will : )

On page 59 at the bottom in the second part of the proof (showing existence): why is $Y$ not the empty set?

Which book?

Discovering Modern Set Theory: The Basics by W. Just and M. Weese.

books.google.com/books?id=TPvHr7fcvHoC&pg=PA59

Hang on. I'll check if I got something by that name.

I just started to have a think about exercise 7 on page 79.

Lemma 27?

Or Thm 25?

Before Lemma 27, in the proof of theorem 25.

"Now let $Y$ be the set of all $z \in Z$ for which ..."

Oh.

Empty sets don't generally have minimal elements... I guess.

It doesn't actually matter if $Y$ is empty or not.

Hm... or does it?

Or what if there is no such function $F_z : I(z) \to X$?

(for any $z \in Z$)

Oh, food is ready. Bye for now!

Bye.

Bye.

I have five more minutes.

Annnnnd we're off. Ciao!

@MattN I believe the only thing they need to show is $I(z)\subseteq Y$ $\Rightarrow$ $z\in Y$.

Then they use induction on wellfounded sets.

=Theorem 21

I'm not sure I understand the proof. They are doing induction to show that there exists an $F_z : Z \to Y$ but to do that they assume that there is an $F_z : I(z) \to Y$. What if there are no such $F_z : I(z) \to Y$? Does that not break the proof?

That's like with induction.

Assume that there are some?

But where is the base case?

In integers: You just have to prove the implication $(\forall k<n) \varphi(k) \Rightarrow \varphi(n)$.

Implicitly, you proved the base case too.

Doh. It is theorem 21.

@MartinSleziak Where?

Since for $n=0$ the assumption $(\forall k<n) \varphi(k)$ is vacuously true.

Oh.

@MattN I was just comparing this with the usual induction on integers.

You're right, it's theorem 27.

I don't have a theorem 27, apparently. : )

21

sorry

Is it so late already?

@MartinSleziak You were right : ) I just emphasised what you'd said.

ok

@MartinSleziak It's quite late. I think I'm going to bed soon.

Ok.

No problem.

I went through Chapter 5 today, skipping that Exercise about groups with at most 3 elements.

Thanks by the way, I much less want to stab myself in the guts if there is someone to talk about the book : )

I write some notes for me on the way, I'll put the last version here every day: msleziak.com/temp

@MartinSleziak Did you do exercises 7 and 8 on page 79?

About those two versions of Godel's completeness theorem?

Yes, I did them. And I even LaTeXed one of them.

Yes.

@MartinSleziak Aces. : )

@MartinSleziak I just saw. I haven't read it, going to try that myself tomorrow. Looks fairly short.

ok

So see you tomorrow probably.

I'll be here : )

Good night!

Good night!