Logic - 2020-08-08

Threnody

4:12 AM

@MaliceVidrine So... if we have a class of all binary trees of height k, why can it also not be a set?

As I understand there can only be a finite amount of btrees of height k

Does it depend on how you encode a btree through set theory syntax?

user21820

5:19 AM

@Threnody No; the standard meaning of "binary tree" considers two of them different if their vertices are different. So you can extract a universal set from the set of all binary trees as per my prior remark:

12 hours ago, by user21820

So for example a graph has a set of vertices, and so any collection of graphs that does not restrict the vertices to some set will not be a set, since you can extract a universal set from it by just taking the union of all vertex sets from those graphs. Since every set occurs as some vertex in some graph, you get a universal set, which is impossible in ZFC.

It is different if you want just the set of all binary trees whose vertices are members of some specific set such as N.

But then arguably that is not the collection of all binary trees! Though due to the available isomorphisms one can consider the set BT of all binary trees on N to be a set of canonical binary trees.

Note that "canonical" here just means that every binary tree is isomorphic to some binary tree in BT. It does not mean that the binary trees in BT are somehow privileged.

Threnody

9:37 AM

Oooooh

I see.

@user21820 This is actually what I understood as a binary tree, the overall 'structure' not necessarily what the nodes are or where they come from

Although in practice we do care..

user400188

I am having trouble with the inexpressibility of finitude. The definition of this thing is that there is no way to construct a formula which is true in all theories satisfied by finite models, but not true in theories satisfied by infinite models. (1 of 6)

user21820

@Threnody That's why I said "a graph has a set of vertices", because any rigorous text would define it so. In many theorems of graph theory this does not matter, but in some cases it does matter. The point really is that if one wants to claim one is using ZFC then one had better know precisely what is or is not allowed.

user400188

I'll hold off my other posts until the current conversation is done. It's a long question (maybe I should just ask it on the main site, although I'd prefer to have a discussion.)

Threnody

No no it's fine

user400188

Ok then

The proof supposedly works like this:

Suppose that there is a formula $\Phi$ which is true in every theory satisfied by a model with finitely many objects. Then the conjunction of the following formulae is inconsistent (2 of 6):

\begin{align}\Phi\\\lnot\exists y\forall x(x=y)\\\lnot\exists y_1\exists y_2\forall x(x=y_1\lor x=y_2)\\\lnot\exists y_1\exists y_2\exists y_3\forall x(x=y_1\lor x=y_2\lor x=y_3)\\\dots\end{align}

user21820

9:41 AM

@user400188 Formulae cannot be true/false in a "theory". So I think you used the wrong term somewhere.

If not, the source of that statement is simply incorrect.

user400188

By $A$ is true in a theory T, I mean $A\in T$.

Continuing the question: However, every finite subset of formulae in the conjunction is satisfiable, so by compactness the whole thing is. The model which satisfied the whole thing will not be finite, so $\Phi$ is true in some infinite models. (3 of 6)

It seems to me that there are some mistakes in this proof though. Firstly, they claim that the conjunction of the formula I listed is inconsistent, follows from the idea that there is a formula $\Phi$ which is true in every theory satisfied by a model with finitely many objects. (4 of 6)

They do not explain why this should be the case. While it seems naively to work, without knowing the exact logic structure of $\Phi$, I do not have any concrete reason to believe it follows. (5 of 6)

Secondly, they claim that $\Phi$ is true in some infinite models. However they derived a contradiction earlier. Have they left the sub-context in which they derived the contradiction? If they did, then they should conclude that there is no $\Phi$ which is true in every theory satisfied by a model with finitely many objects. They should not claim from the contradiction, that the $\Phi$ which is true in all theories satisfied by finite models, is also true in some infinite models. (6 of 6)

user21820

@user400188 If that is the case then you still need to be clear what you mean by "every theory satisfied by a model ...". If you mean "every theory that has some finite model", then such a formula is 'almost never' in any theory to begin with.

That's just my immediate reaction, and now I'll look at the quoted proof.

user400188

"a model" here refers to some model. Thanks for the immediate reaction, they are sometimes useful insight.

user21820

@user400188 I have no idea what they mean by "inconsistent", since as you said it is plainly consistent by compactness.

And worse still, an infinite set of formulae does not even have a well-defined conjunction!

user400188

@user21820 That is one of the problems I am having.

Supposably, the idea that $\Phi$ and the other formulae can't be true in the same theory, is a direct consequence of $\Phi$ being a formula that is true in every finite model.

Also, I just realised I might have confused "True in a model", with "true in a theory satisfied by a model". So I'm going back to the lecture to check.

user21820

9:59 AM

I assume that your (3 of 6) is your argument, and it is completely correct. For that result you don't need the "in a theory with some finite model", and you could instead generalize the theorem to:

> Take any theory T that has models of unbounded size (i.e. for each k∈N there is a model of size at least k). Then there is no sentence that is true in every finite model of T but false in every infinite model of T.

I think there's no point trying to figure out what the quoted text is doing, since it is already wrong in talking about an infinite "conjunction".

user400188

@user21820 (3 of 6) is from the lecture.

@user21820 I am probably misrepresenting the lecture here, the exact wording was "infinite collection" not infinite conjunction, and they claim that the formulae in the infinite collection are "jointly inconsistent". Conjunction was my own wording.

user21820

That's odd. It makes completely no sense to have the wrong phrase "the conjunction of the following formulae is inconsistent" when you can just have (3 of 6) and immediately get the desired result.

@user400188 "Infinite collection" is correct. "Jointly inconsistent" is strange, but actually okay if they mean "semantically inconsistent" rather than "syntactically inconsistent" (though the latter is the standard meaning).

user400188

Alright then. I'll try to use the exact wording from now on, although I have never had a problem of thinking that a formal theory is equivalent to a conjunction of the things true in it, until now.

This is the lecture slide I got the proof from: https://imgur.com/a/Y2ZsWUv
I hope you don't mind that it's an Imgur link.

My main problem is the line "then these formulas are jointly inconsistent". I do not see how this follows from the supposition that $\Phi$ is true in every model with finitely many objects.

user21820

10:25 AM

@user400188 Imgur is definitely fine.

@user400188 As I said, I wouldn't ever write "jointly inconsistent" because I only use "[in]consistent" to mean "syntactically [in]consistent".

However, you can say that the set is supposed to have no model, because Φ is supposed to be false in an infinite model.

So if by "jointly inconsistent" the lecturer meant "has no model", sure. But might as well wait until the end to use the given condition "false in every infinite model" to get the contradiction.

user400188

@user21820 The way I read it, was that $\Phi$ was true in finite models, but nothing has been said yet as to whether it is true in infinite ones too. If you read it as true in finite and only finite models, then the jointly inconsistent line makes more sense.

user21820

@user400188 I took that supposition from the "not true in theories satisfied by infinite models" in (1 of 6).

user400188

That was a statement of what we were trying to prove, but not what was actually written in the proof. Although I suppose I should have inferred from the context that that was what they meant.

I think I understand the proof now, but I have another question now regarding an infinite disjunction.

user21820

Sure.

user400188

Suppose one exists, and it looks like this $a_1\lor a_2\lor\dots$. Then suppose we have an infinite collection of formulae $\lnot a_1,\lnot a_2,\dots$. By compactness, the set comprising of both the collection and the infinite disjunction is satisfiable.

But it seems to me that we could perform some kind of induction argument to show that such a set would be inconsistent.

That said I am struggling to come up with such an induction argument.

user21820

10:50 AM

@user400188 But isn't that the point? There is no infinite disjunction!

So now you know the reason for my immediate reaction to the use of the term "conjunction". It's not that the concept doesn't exist. Sure, people have considered infinite conjunctions/disjunctions, but they do not behave in the way you might expect.

In other words, your problem starts once you wrote "···".

The compactness theorem applies to PL or FOL, not things with "···".

And there is no induction argument necessary; each negated propositional atom cannot be satisfied unless the atom is false, and that of course implies that the 'infinite disjunction' is false.

user400188

11:13 AM

Regarding inexpressibility, I have come across the term functionally complete, or Turing complete. It seems to be the ability to express any function.

Now, in my first year of undergrad, we covered Boolean algebra (in engineering math, so it's probably different from the Boolean algebras I keep hearing about). Boolean algebra was defined for us to be turning complete. I remember there was a proof, but I don't remember the proof.

For us, it was defined as everything you can do with $A,B,C,\dots$ $\bar X$ (negation), $\cdot$ (AND), and $+$ (OR). There were no axioms, and the rules were not …

I have thought up until recently that FOL could do everything Boolean algebra could, and it also had some neat features that let you talk about quantification easier. But this proof of inexpressibility has me stumped.

Is it the case that Boolean algebra can express more than FOL, or am I just remembering things incorrectly?

This is actually a question I have been wanting to ask for years, but I did not have the background knowledge in inexpressibility yet. Today is the first instance where I can say "I have seen a proof of it now".

user21820

12:15 PM

@user400188 I don't understand your question, because as I just said PL does not permit "···". Neither does boolean algebra.

So it doesn't make sense to say that boolean algebra can 'express more' based on the above discussion. All you have there is a set of things that are not PL sentences and hence not manipulable using boolean algebra.

And, no, boolean algebra is not Turing-complete. "Turing-complete" is totally different from "functionally complete".

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic