Logic - 2017-11-28

Leaky Nun

00:39

@user21820 @MatheinBoulomenos does the model of constructible points have the same first-order consequences with the usual model of Euclidean geometry?

MatheinBoulomenos

@LeakyNun I know basically nothing about this stuff, but isn't Euclidean geometry complete by a theorem due to Tarski?

Leaky Nun

@MatheinBoulomenos the theory of algebraic closed fields is also complete, yet it admits many models

cf Lowenheim-Skolem theorem

MatheinBoulomenos

right

Leaky Nun

so Tarski's axioms should have a countable model

@MatheinBoulomenos the theory of dense order (with language signature {<}) is surprisingly complete...

alright, not very surprising

MatheinBoulomenos

00:56

But what does completeness mean? I thought it means that the first-order statements which are true in one modeal are true in all models

Leaky Nun

1. $(\forall x)(\neg(x<x))$
2. $(\forall x)(\forall y)(\forall z)(x<y \implies y<z \implies x<z)$
3. $(\forall x)(\forall y)(x<y \implies \neg(y<x))$
4. $(\forall x)(\forall y)(x<y \lor y<x)$
5. $(\forall x)(\forall y)(x<y \implies (\exists z)(x<z \land z<y))$

@MatheinBoulomenos good question:

let's define a model from the basics

a language is a set of symbols, which include the standard logical symbols (and sometimes the equality symbol) and variables. the other symbols is called the signature

a (well-formed) formula is a string of symbols from the language satisfying certain property (to ensure that the string makes sense)

a sentence is a formula in which every variable is bound (i.e. have $\forall x$ or $\exists x$ in front of it)

a theory is a set of sentences (that may be infinite) (that we want to be true)

a model is an interpretation of the constants, functions, and relations, in the language, with the domain being the set of objects

the size of a theory is the cardinality of the set of sentences, and the size of a model is the cardinality of the domain (which is a set)

MatheinBoulomenos

wait, what do you mean by "interpretation"?

Leaky Nun

@MatheinBoulomenos recall that the symbols are formal symbols with no meaning. a model interprets those symbols

if we have a constant symbol in the language, the model maps it to a constant term in the domain

MatheinBoulomenos

okay

Leaky Nun

now, for L a language, T an L-theory, M an L-model, phi an L-sentence

M |= T, which reads "M is a model of T", means that every sentence in T is true in M

M |= phi, which reads "M is a model of phi", means that phi is true in M

T |= phi, which reads "phi is a logical consequence of T", means that phi is true in every model of T

note that we have overloading of |= aka abuse of notation

note that either M |= phi or M |= neg phi, by requirement of model (which I did not include)

but we do not have "either T |= phi or T |= neg phi" (think about L = language of groups, T = theory of groups, phi = group is abelian)

MatheinBoulomenos

01:02

okay that makes sense

Leaky Nun

now, Godel's completeness theorem, which is "semantic-completeness", states that "T |= phi iff T |- phi"

MatheinBoulomenos

what does the latter notation mean?

Leaky Nun

it means that phi is provable from T (under classical logic)

note that Godel's completeness theorem applies for any theory T

now, this is not to be confused with syntactic completeness of a theory, which states that for every phi, T |- phi or T |- neg phi

this is not true in general

MatheinBoulomenos

okay, so these are the theories we call complete?

Leaky Nun

in fact, Godel's incompleteness theorem (syntactic-incompleteness) gives a criterion for the incompleteness of theories

@MatheinBoulomenos yes

when we say that a theory is (in)complete, we really mean syntactic-completeness

particularly so for incomplete (because semantic-completeness is an axiom)

@MatheinBoulomenos is there any point/concept that you would like me to expand on?

this is helpful for me also to consolidate my knowledge

MatheinBoulomenos

01:10

@LeakyNun So are there situations where we can prove something in one model and conclude that it must hold in other models?

Leaky Nun

@MatheinBoulomenos you mean model of a theory?

MatheinBoulomenos

yeah

Leaky Nun

note that models are L-models, and are not contingent on any theories

models are not based on theories

should I take your sentence to mean "where we can show that a sentence phi is true in a model M of a theory T and conclude that phi is true in other models of T"?

MatheinBoulomenos

yes, that's what I meant

Leaky Nun

sorry for being pedantic, but it is quite needed in this case for my clarity

because "provable" |- and "true" |= are very different concepts

MatheinBoulomenos

01:12

no, it's good that you're correcting me, if I want to learn this

Leaky Nun

the situation is exactly when T is complete

no

if you can actually prove phi from T, then you also have that situation

but "completeness" is definitely a strong criterion

@MatheinBoulomenos do you follow?

MatheinBoulomenos

I don't really understand why the completeness of Euclidean geometry does imply that all models have the same first-order consequences

Leaky Nun

let T denote the theory of Euclidean geometry

let M and M' be models of T in which phi and neg phi are true respectively

since phi is true in M a model of T, neg phi is false in M, so we have T ⊭ neg phi (notice it is neg phi here)

since neg phi is true in M' a model of T, phi is false in M', so we have T ⊭ phi

which contradicts the completness of T

MatheinBoulomenos

Okay

Leaky Nun

@MatheinBoulomenos do you have any questions?

3 mins ago, by Leaky Nun

let T denote the theory of Euclidean geometry

note that T is for Tarski :P

"Euclidean geometry" is really a model, not a theory

MatheinBoulomenos

01:20

But when you asked "does the model of constructible points have the same first-order consequences with the usual model of Euclidean geometry?" and I replied "I know basically nothing about this stuff, but isn't Euclidean geometry complete by a theorem due to Tarski?", you said something about Löwenheim-Skolem

Ah okay, that explains it

I thought Euclidean geometry is a theory

Leaky Nun

recall that a theory is a set of sentences

Euclidean geometry has all the (real) objects, (real) constants, (real) functions, and (real) relations, so it is a model

MatheinBoulomenos

Oh yeah, I need to work on the basics

Leaky Nun

do you have any particular "basic" in mind?

MatheinBoulomenos

I think I just need to digest the information

So if we have a theory, how can we know if there even exists a model? If we can conclude a contradiction from the theory, then there can't be a model, right?

Leaky Nun

@MatheinBoulomenos correct

MatheinBoulomenos

01:25

But to contruct models, we need a meta-theory (e.g. set theory)?

Leaky Nun

yes, we usually use ZFC and classical logic as the meta-theory, but I wouldn't really bother

yes, ZFC, with choice

MatheinBoulomenos

Is "field with characteristic 0" expressible in first-order logic?

I think not

Leaky Nun

in which theory?

MatheinBoulomenos

If we just take $0,1,+,\cdot,=$ as a language

Leaky Nun

the language of rings

MatheinBoulomenos

01:30

anyway, this was very helpful, thank you @Leaky

Leaky Nun

summary:
1. A language is a set of symbols which include standard logical symbols, optionally the equality symbol, the variables, constants, functions, and relations.
2. The set of constants, functions, and relations of a language is called the "signature" of the language.
3. A well-formed formula is a string of symbols in the language that makes sense, so $x=x$ is a well-formed formula while $\lor \land y \neg x$ is not.
4. A sentence is a formula that is bound, i.e. without free variables. So $(\forall x)(x=x)$ is a sentence while $x=x$ is not.

@MatheinBoulomenos ACF0 is an infinite theory

I don't think it is finitely axiomatizable

MatheinBoulomenos

okay

Leaky Nun

and by the way, axiom of theory means a set of sentences that have the same first-order consequence of the theory

MatheinBoulomenos

okay

Leaky Nun

@MatheinBoulomenos glad to have helped you

MatheinBoulomenos

01:33

So the compactness theorem implies the existence of a non-archimedean real closed field?

Leaky Nun

yes, the hyperreals

MatheinBoulomenos

nice

Leaky Nun

note that you have to expand the language

Leaky Nun

01:52

in Mathematics, 32 secs ago, by MatheinBoulomenos

@LeakyNun can we express algebraicity in first-order?

@MatheinBoulomenos could you clarify what you mean using the terminology of language/sentence/theory/model?

MatheinBoulomenos

Okay, suppose we have the language L which consists of $\{0,1,+,=\}$ and the logical symbols

Leaky Nun

you should have $\times$ also, but move on

MatheinBoulomenos

Suppose for simplicity we want to express algebraicity over a fixed prime field, else we would need a larger language

is there a L-theory in ZFC such that the models are precisely algebraic extension fields of the fixed prime field?

and is this possible in first-order?

Leaky Nun

@MatheinBoulomenos yes

you're really helping me lol

this is actually what I'm going to talk about

now the language of rings has signature $\{0,1,+,\times,=\}$

the theory of fields is the set of field axioms

now, the theory of algebraic closed fields, ACF, is a countably infinite theory

MatheinBoulomenos

okay, but what a about if we don't require algebraic closed, but just algebraic?

is this still first-order?

Leaky Nun

01:59

hmm, no, because of compactness theorem

good question

MatheinBoulomenos

so the compactness axiom also implies the existence of algebraic closures, right?

for a finite subset, we can just construct a field containing the roots using quotients of polynomials

Leaky Nun

how do you imagine the set to be?

MatheinBoulomenos

well, for every non-constant polynomial we have a sentence that says that the polynomial has a root

and the field axioms, of course

Leaky Nun

how are you going to state that $x^2 - \sqrt2$ has a root?

MatheinBoulomenos

I meant for every non-constant polynomial with coefficients in the ground field

Leaky Nun

02:04

hmm

MatheinBoulomenos

from the compactness theorem, we get an extension that contains an algebraic closure

Leaky Nun

but not necessarily the algebraic closure

MatheinBoulomenos

we can just restrict us to the algebraic elements of that extension

that part is not mode-theoretic

Leaky Nun

not even necessarily algebraic closed

are you trying to construct a theory such that the only models of T is exactly the algebraic closures of the base field?

MatheinBoulomenos

no I'm asking several unrelated questions about fields

Leaky Nun

02:07

I'm lost

MatheinBoulomenos

sorry

Leaky Nun

it isn't your fault

and fwiw, ACF is a first-order theory, and so are ACF_p for every prime p and ACF_0

for every prime p, ACF_p is complete; ACF_0 is complete

MatheinBoulomenos

I was just wondering if you can somehow use the compactness theorem to show the existence of algebraic closures

Leaky Nun

but you can't require the model to not have transcendental elements

MatheinBoulomenos

yeah, but using field theory it's enough to show the existence of a field that contains an algebraic closure

Leaky Nun

02:11

why?

MatheinBoulomenos

If $L/K$ is a field extension. $\{\alpha \in L \mid \alpha \text{ is algebraic over } K\}$ is a field

Leaky Nun

hmm, interesting

so I think it works then

MatheinBoulomenos

02:26

I'll try to generalize this, this is going to be a huge language and theory, but whatever. Let F be a field. We construct a language L that has signature $\{+,\times,=\}$ and also one constant for every element of F. We then construct a L-theory that has all the field axioms, one sentence for every relation of elements in L and one sentence for every non-constant polynomial with coeffcients in F stating that there exists a root

every finite subset of the theory has a model, we can just construct finite extensions of F by using quotients of polynomial rings

so we get a model of the whole theory by the compactness theorem

then when we restrict to the elements that are algebraic over F, we get an algebraic closure of F

is this correct? @LeakyNun

Leaky Nun

@MatheinBoulomenos magnificent

have you read about Lowenheim-Skolem's proof?

MatheinBoulomenos

not yet

Leaky Nun

interesting

because "one constant for every element" and "one sentence for every relation" are basically how you use compactness to prove upward Lowenheim-Skolem...

MatheinBoulomenos

I see

I just don't understand why we need countability in Löwenheim-Skolem

Leaky Nun

well, an uncountable theory may not have a countable model, I think

MatheinBoulomenos

02:42

Makes sense

Leaky Nun

@MatheinBoulomenos thanks for your questions, see you

MatheinBoulomenos

@LeakyNun thanks for your explanations, see you!

user21820

10:07

@MatheinBoulomenos I do not think LeakyNun has answered your question, even though he has shown you how the von Neumann ordinals behave. When you do transfinite induction, you do not take union just because the ordinal stage is a limit ordinal. You will have to look at the actual rigorous use of transfinite induction. If I am not mistaken the way you have been shown is very clumsy.

We can take the simplest example of the existence of a basis of any given vector space V. By transfinite induction V can be well-ordered. Initialize S = {}, then enumerate the vectors in V in that order and at each stage add the current vector v to S iff S⋃{v} is linearly independent. At the end, clearly every vector in V is in span(S), and we just have to check that S is linearly independent, which you should be able to prove.

I didn't need to split cases according to whether the stage was a successor or limit stage!

All the hard work is done by the transfinite recursion used to construct S, which I have detailed in my post.

I recall some set-theoretic constructions that need to handle the successor and ordinal cases differently, but I think outside of set theory not many applications of transfinite induction will actually have to do that.

@LeakyNun Constructible meaning? Euclidean geometry meaning? If both are using the same tools (say compass and straightedge), then yes almost by definition because 'constructible' just means 'can be obtained by the tools' and 'euclidean geometry' proves only what 'can be obtained by the tools'. Of course, I'm skipping all the tedious technical details.

@MatheinBoulomenos That's why it's better to distinguish semantic-completeness from syntactic-completeness.

@LeakyNun It's dense linear orders without endpoints. Their theory is syntactically-complete.

It is the first-order logic that is semantically-complete.

@LeakyNun Yes the set of axioms { c[i] ≠ c[j] : i,j∈S ∧ i≠j } where the c's are constant-symbols can only have models of size #(S), of course.

Leaky Nun

10:40

@user21820 thank you

@user21820 how do you prove transfinite induction?

user21820

11:13

@LeakyNun Read the post. It's all there! I didn't explicitly mention where I used the axiom of replacement, but it should be clear to you if you go over it. Note that the only use of transfinite induction is to produce a well-ordering of the set you are interested in (here V). If you already have a well-ordering then you do not need transfinite induction, nor replacement.

3

A: Definition of Ordinals in Set Theory in Layman Terms

Counting has two purposes, namely for specifying sizes and indices. These are directly related for finite quantities, because the number of natural numbers (including $0$) less than $n$ (before the position $n$) is $n$. But in set theory, when generalizing to infinite sets these two notions becom...

@LeakyNun: If you want to see an example where you do need the split cases, consider ordinal multiplication. Addition is simply concatenation, and no case splitting is needed there. But multiplication is not so easy.

a·(b+1) = a·b+a.

Leaky Nun

well that just depends on how you define addition

user21820

a·b = sup { a·c : c < b }.

Leaky Nun

the definition I've seen is
1. a+0=a
2. a+S(b)=S(a+b)
3. a+b=U{a+n|n<b}
alright, you don't really 2, but...

@user21820 is there a theory of ordinals without ZFC?

user21820

@LeakyNun You need both.

Leaky Nun

both?

user21820

11:19

ω+1 is not Union { ω+k : k<1 }.

I mean, you need both (2) and (3).

Leaky Nun

is it not?

right, it isn't

then in this case you clearly need case splitting

user21820

Anyway that's von Neumann ordinals. Concatenation works for the original notion of well-ordering, so as I said you don't really need case splitting for addition.

However, if you really have nothing better to do, you can define a+b = sup { a+S(c) : c<b } and it covers all 3 cases! @MatheinBoulomenos: you may also be interested in this curiosity but it has no practical purpose.

But for multiplication there is a problem I think.

Leaky Nun

@user21820 as an unrelated note, I find it quite curious that Presburger arithmetic is complete

user21820

Well even for multiplication there is another way if you really really have nothing better to do.

Leaky Nun

@user21820 multiplication is just product right

user21820

11:25

No...

I wrote the two main cases above.

The trivial case is a·0 = 0.

Leaky Nun

I mean, cartesian product

user21820

Uh yes yes.

Then it was exponentiation that had the major problem.

Lol.

But anyway there is an 'algebraic' definition of ordinal multiplication that covers all cases, just that it is very nothing-better-to-do style.

a·b = sup { a·p+q : p<b ∧ q≤a }.

I hope I didn't make a mistake, but something like that would work. It's been a long time since I did this kind of silly thing.

But exponentiation is a much more tricky business.

@LeakyNun I also found it curious, but never really thought much about it. Seems to me that addition alone is like having unary strings as compared to binary strings in the intended model of TC.

Leaky Nun

maybe

user21820

In computability there seems to be numerous instances of discrete threshold of 2 or 3 between simple and complicated, with a vast chasm in-between.

Here the threshold is 2. Consider any NP-complete problem and you will find typically threshold of 3.

For example 2-colouring is polynomial time; even linear. 3-colouring is NP-complete.

Leaky Nun

what is 2-colouring?

user21820

11:35

The problem of determining whether a given graph can be 2-coloured.

Leaky Nun

I see

user21820

2-SAT (look up boolean satisfiability) is in P. 3-SAT is in NPC.

Leaky Nun

4-colouring becomes polynomial again ;)

user21820

Nope!!

That's 4-colouring of a planar graph.

Leaky Nun

well, alright

user21820

11:36

But incidentally, I think 3-planar-colouring is also NPC.

@LeakyNun: Anyway I've to go now. See you next time! =)

Leaky Nun

see you

Leaky Nun

12:24

1 hour ago, by Leaky Nun

@user21820 is there a theory of ordinals without ZFC?

langauge has signature {0,ω,S,+,x,<}

Leaky Nun

12:50

ordering:
1. (∀m)(¬(m<m))
2. (∀a)(∀b)(∀c)(a<b⟹b<c⟹a<c)
3. (∀a)(∀b)(a<b⟹¬(b<a))
4. (∀a)(∀b)(a<b∨b<a)
constants:
1. (∀m)(¬(m<0))
2. 0<ω
3. (∀m)(∃n)(m<ω⟹m=0∨m=S(n))
successor:
1. (∀a)(¬(S(a)=0))
2. (∀a)(¬(S(a)=ω))
3. (∀m)(∀n)(S(m)=S(n)⟹m=n)
4. (∀a)(a<S(a))
addition:
1. (∀m)(m+0=m)
2. (∀m)(∀n)(m+S(n)=S(m+n))
3. (∀m)(∀n)(∀y)((∀x)(x<n⟹(m+x)<y)⟹m+n<y)
4. (∀m)(∀n)(∀x)(m<n⟹x+m<x+n)
multiplication:
1. (∀m)(m⋅0=0)
2. (∀m)(∀n)(m⋅S(n)=(m⋅n)+m)
3. (∀m)(∀n)(∀y)((∀x)(x<n⟹(m⋅x)<y)⟹m⋅n<y)

transfinite induction:
1. (∀m)((∀n)(n<m⟹φ(n))⟹φ(m))⟹(∀m)φ(m)

user21820

14:47

@LeakyNun Well of course you can build your own theory, but probably anything you will build will come short. For instance, ω^ω with the ordinal arithmetic is a model of your above theory, assuming your axioms mean what they are labelled (too lazy to read everything).

Reason is simple; ω^ω is closed under addition and multiplication.

Leaky Nun

@user21820 I know theories are limited by Lowenheim-Skolem, but that doesn't mean I can't build it

user21820

Sorry by come short I meant come short of the theory of ordinals you get within ZFC.

Leaky Nun

sure

user21820

That's presumably what you wanted.

No?

Leaky Nun

no, I still want to build it even though I can't control the cardinality

I know that omega^omega will be a model

user21820

14:49

Ah okay.

So what else were you looking for in your theory?

For a related fact, there are weak foundational systems that have ω^ω as proof theoretic ordinal, which roughly means it is the least ordinal for which they cannot construct and prove a well-ordering.

Reverse mathematics

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones. The reverse mathematics program was foreshadowed by results in set theory such as the classical theorem that the axiom of choice and Zorn's lemma are equivalent over ZF set theory. The goal of reverse...

Leaky Nun

@user21820 well I would like to be able to prove, e.g. 3+omega = omega

user21820

So you're asking for a complete axiomatization of ω^ω with ordering and addition and multiplication and constants 0,ω?

Then looks like it's doomed by the incompleteness theorem...

=D

Leaky Nun

but surely 3+omega=omega can't be the independent sentence

user21820

Of course not.

You should be able to prove simple facts.

Leaky Nun

how should I axiomatize it then?

user21820

14:54

Isn't that up to you? Since there is no objective goal given the essential incompleteness?

Leaky Nun

I can't seem to prove 0+x=x from the axioms though

did my axioms capture all the essential properties?

user21820

Hmm..

Your last axiom for constants is weird; it only talks about finite ordinals.

Leaky Nun

it says omega is the first limit ordinal

user21820

Yes.

But what about ω+ω?

Leaky Nun

what about it?

user21820

14:56

I mean you are not capturing the basic fact that every ordinal is either zero or successor or limit.

Leaky Nun

I thought "limit" just means "non-zero non-successor"

user21820

Yes that is what I said earlier but if you do it that way then you don't have the basic fact that every limit ordinal has no nearest neighbour on the left (smaller).

Leaky Nun

what does that mean?

user21820

I edited; shouldn't have used the term "predecessor".

Leaky Nun

still what does that mean?

user21820

14:59

You can express that fact in your language.

Leaky Nun

I don't even understand it

user21820

You also don't have the basic fact that every successor ordinal has a unique nearest neighbour on the left.

"on the left" = "smaller".

Leaky Nun

that's successor is injective

user21820

Successor is injective does not imply "nearest neighbour" is unique.

It just implies you have predecessors (inverse of successor).

Leaky Nun

could you express it in the language?

user21820

15:03

You're not going to try? It's like "dense" and "discrete" in expressing the axioms for dense linear orders.

"has no nearest neighbour on the left" = "dense on the left".

user21820

15:14

@LeakyNun: Ping me when you get it. Also, in fact you can say a lot even with just the ordering symbol (not even using addition and multiplication)! See the comments by David here:

4

Q: Ordinal pair $(α,β)$ such that $α<β$ and $Th(α,<) = Th(β,<)$

A number of weeks ago I was thinking of finding an example of a complete countable theory with only one binary predicate that is not $ω$-categorical. I later realized that $Th(\mathbb{Z},<)$ works, but an earlier thought was to find two non-isomorphic well-orders that have the same first-order th...

MatheinBoulomenos

21:16

@user21820 maybe I'm just dense, but I still don't understand it. What exactly do you mean by "at each stage"?

I understand what "at each stage" means for successor ordinals

but I don't see how this works for limit ordinals as well

Leaky Nun

22:03

@MatheinBoulomenos hi

I won't answer questions about ordinals (because of my incompetence)

but we can talk about model theory :P

@user21820 I was rushing my work at that time and didn't want to think

@user21820 (∀x)(∀y)(¬(x<y)∨¬(y<S(x)))

Leaky Nun

23:35

@user21820 it turns out that this can be deduced from the fact that every successor ordinal has a unique nearest neighbour on the left

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic