Logic - 2018-08-23

user21820

09:55

@LeakyNun I think you'd have to be more specific, as to what models between which you are considering absoluteness. Let's be more precise. Take any n-parameter property Q over ZFC. We say that Q is absolute for a model M of ZFC iff ∀x[1..n]∈Dom(M) ( ( M |= Q(x[1..n]) ) ⇔ Q(x[1..n]) ). Now take any models M,N of ZFC with Dom(M)⊆Dom(N). We say that Q is absolute between M,N iff ∀x[1..n]∈Dom(M) ( ( M |= Q(x[1..n]) ) ⇔ ( N |= Q(x[1..n]) ) ).

(Note that Q is not an object inside ZFC but a meta-object. And both notions of "absolute" are not properties over ZFC.)

So if you're asking "Is countability absolute for every model of ZFC?" then the answer is trivially "no" if ZFC is consistent, because there would be a countable model M in which the reals R is uncountable but of course the interpretation of R in M is externally countable. Even if you restrict to transitive models, the answer is still "no" if ZFC has a transitive model, because ZFC would have a countable transitive model.

Leaky Nun

but R isn't an ordinal

user21820

10:12

@LeakyNun But you can just take ω[1].

Which comes down to the non-absoluteness of P(ω).

Leaky Nun

if M is a standard submodel of N, can ω[1]^M = ω^N?

user21820

If M,N are transitive models of ZFC, then ω is absolute for each of them, so ω^M = ω = ω^N. But ω^M ∈ ω[1]^M, so the answer is "no".

I don't know what happens if you don't restrict to "transitive models". I know very little higher set theory.

Leaky Nun

you have got to be kidding me

ω[1]^M can be a countable ordinal in N

but it can't be anything that I can name

user21820

@LeakyNun I don't understand whether this is a serious remark or not...

Leaky Nun

is there a definable non-absolute countable ordinal?

absolute as in absolute between standard submodels

I mean, think about the ramification of the fact that P(N) is not absolute

since we normally take ZFC to be the axioms of the "real world"

that would mean that we can never know if our true P(N) contains the correct sets

user21820

10:25

Well, if there is a transitive model, then there is one with least rank k, and k is a countable ordinal. So if you work within ZFC+st(ZFC), where st(ZFC) is the axiom that states existence of a transitive model of ZFC, then k would be a definable countable ordinal but the defining property would not be absolute. I think.

@LeakyNun And that's the point of the Skolem paradox. Remember I said before that we have no evidence that P(N) contains anything beyond the definable subsets of N. ACA is the first nicely closed system in that sense; it is closed under forming definable subsets over itself.

Leaky Nun

so in L, P(N) contains only the definable subsets of N?

is "L |= CH" still independent of ZFC?

user21820

@LeakyNun In some fashion yes, but "definable" is iterated along the ordinals in ZFC, so it's very different from ACA. In particular, L contains all the ordinals, and so L is very far from countable.

L is the skinniest class model of ZFC that contains all the ordinals.

Leaky Nun

so does NBG prove ZFC consistent?

user21820

@LeakyNun ZFC proves ( L |= CH ).

Leaky Nun

:o

shock

I mean, both answers would be shocking to me

user21820

10:30

Note that L is not a set, so ZFC does not prove existence of a model that satisfies CH.

Leaky Nun

just like we are either alone in the universe or we are not; both are equally terrifying

user21820

After all, it can't even prove existence of a model of itself.

@LeakyNun NBG is a conservative extension of ZFC, from what I read. It is clear that it is conservative for the reasons I mentioned to you last time (definitional expansion) except for one axiom that is slightly stronger in NBG than its counterpart in ZFC. I can't recall what it is now.

Leaky Nun

why does ZFC prove L|=CH?

@user21820 I mean, V is an object in NBG

and V |= ZFC

user21820

Aha I'm going to just dump a wiki link on you:

Constructible universe

In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted L, is a particular class of sets that can be described entirely in terms of simpler sets. L is the union of the constructible hierarchy Lα . It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both...

It links to the section explaining how ZFC proves ( L |= GCH ).

Leaky Nun

how would you define L to someone who doesn't know model theory?

user21820

10:35

@LeakyNun Um... I don't?

Lol.

Well, if ZFC does not make sense then L has no basis either. If you think ZFC makes sense, then L is just the 'minimum' that must exist if you iterate the axioms along all ordinals.

Leaky Nun

isn't V also?

you're just taking powersets each time

user21820

V is the whole thing if you have foundation, because you 'union' all the iterates of the powerset axiom through all the ordinals, and foundation tells you that you will catch every set. L is what happens if you don't 'union' all the powersets but rather only 'union' the 'definable' elements of each powerset iterate.

Leaky Nun

P(N)^L is uncountable, so there are uncountably many definable subsets of N?

user21820

@LeakyNun I did say:

> "definable" is iterated along the ordinals in ZFC, so it's very different from ACA.

Leaky Nun

why does P(N)^L contain more things than the definable subsets of N?

user21820

10:43

One step of adding "definable" subsets of N gives you ACA (if you add induction after that).

Where "definable" here means "definable given previously constructed objects".

L is made from doing ORD many steps of adding "definable" subsets of previously constructed objects.

You can only imagine L properly if you can imagine ORD in the first place.

Leaky Nun

what does P(N)^L[ω[1]] looks like?

user21820

And the wiki article does mention where the arithmetical sets appear in L, and where the hyperarithmetical sets appear in L.

Leaky Nun

wait L[ω[1]] isn't a model of ZFC

is it a model of anything?

user21820

@LeakyNun Yes it is a model of ZFC with only countable replacement.

Same like V[ω[1]].

Leaky Nun

so it does have P(N)

user21820

10:50

@LeakyNun It has what it thinks is P(N). Not necessarily the 'real' P(N).

Note that L[k] is countable for countable k, so L[ω[1]] is the first uncountable stage.

If CH fails in the 'real' universe, then L[ω[1]] cannot contain the 'real' P(N).

Leaky Nun

Can you give me an element of P(N)^L \ P(N)^L[ω[1]]?

math is a lie

user21820

Lol I don't even buy full ZFC, so I'm not sure how to answer your question.

This post says that you can do a (presumably transfinite) induction argument to show that L[k+1] \ L[k] is non-empty for every ordinal k.

Wait, that's not what you asked.

Leaky Nun

is it what I asked?

right, it isn't what I asked

user21820

But I think a similar argument might work.

I'm guessing we can show that, for every ordinal k, if P(N)^L[k] ≠ P(N) then P(N)^L[k] ≠ P(N)^L[k+1]. If so, and if CH fails, then P(N)^L[ω[1]] ≠ P(N)^L[ω[1]+1].

This sounds wrong. Hmm..

Even this only goes up to L[ω[1]]. And I don't understand practically all of the other answer on that thread.

Leaky Nun

11:18

this is ridiculous

math is a lie

user21820

Lol you can try out alternative foundations.

But if you want to stick to a ZFC-style system, I think a relatively safe one is bounded ZFC, where Specification and Replacement are only valid for bounded defining formulae.

Leaky Nun

@user21820 when we say "the consistency of ZFC is independent of ZFC" we're already 3 layers deep

user21820

At least, when I say that I am working in a weak meta-system such as ACA, and it's a conditional: "If ZFC is consistent then ZFC does not prove ( ZFC is consistent )."

Yup I skimp on belief and stick to conditionals. =) — user21820 2 days ago

Leaky Nun

12:19

@user21820 Is the element relation externally well-founded?

user21820

12:33

@LeakyNun Um I can't tell what you mean by that question...

Leaky Nun

@user21820 work inside ZFC. assume that (M,∈) is a model of ZFC. Is ∈ a well-founded relation?

Mitch

13:23

I have a question about provenance of some terminology in logic. Or rather I am interested in such a question posted on ELU:

2

Q: What is the origin of "law of excluded middle"?

Reading an article I have stumbled across the concept of law of excluded middle. Wikipedia mentions that original expression is principium tertii exclusi which literally translates to principle of the excluded third. My native language (Romanian) also uses the literally translation. I am wonde...

Which is really asking (TLDR), when did the translation of 'tertium non datur' as 'law of excluded middle' first appear in English? Or why 'middle' instead of 'third'?

Maybe the term in medieval Latin was actually 'principium tertii exclusi'.

But still. the latin is literally 'excluded third', not 'excluded middle'.

The question is not about the appropriateness at all (the metaphor is obvious).

user21820

@LeakyNun Add constant symbols c[0..] and axioms stating ... ∈ c[2] ∈ c[1] ∈ c[0], to get a first-order theory ZFC'. Then by compactness if ZFC has a model (equivalently is consistent) then ZFC' is consistent. But any model of ZFC' blatantly has an ∈-descending sequence of elements. The only thing that saves ZFC' from being inconsistent is that that sequence is never an element of the model.

@Mitch Technically it would have been a better fit for History of Science and Mathematics.

Mitch

@user21820 thank you. I'll suggest that it be moved there.

user21820

In any case, I don't think people here know much history of mathematics.

Mitch

More likely than the ELU crowd

user21820

Hahaha! But there is an interesting mathematical reason why it would eventually be described as a "middle" option.

Mitch

13:36

Oh? Beyond the obvious metaphor?

user21820

Namely if you interpret "true" as 1 and "false" as −1 and "and" as "min" and "or" as "max" and "not" as "negation", then indeed one can consider what happens with a third middle truth-value of 0.

Furthermore, this idea extends to quantifiers naturally; "forall" is "min over the domain" and "exists" is "max over the domain".

This immediately generates what is known as Kleene's 3-valued logic.

Also, not coincidentally, the propositional fragment of this 3-valued logic has a physical realization in logic circuits, where "true" is pull-up and "false" is pull-down and "null" is neither (open circuit).

Again, it's in the middle. =)

Mitch

Oh OK. That's the metaphor I was talking about. In word, given true and false, it is easier to manipulate them formally, if you do not consider a third way. There are many ways to not be either true or false, and 'tertium non datur' simplifies this considerably. But, as thoughts go, these 'third' logical values, where would they go if they did in fact 'exist', yes, they'd go 'between' true and false, in the middle of them. That's the metaphor.

As to an analytic interpretation, it is a little easier to give true = 1 and false = 0 over reals, and then define 'A and B' as 'a*b', 'not A' as 1-a, etc. and then boolean statements translate to polynomials over [0, 1]

Or you can stick to discrete values via Kleene (or many other three valued or n-valued logics)

user21820

13:52

@Mitch This does not work, for the simple reason that A∧A ought to be equivalent to A no matter what.

@Mitch As for where other truth-values would go, intuitionists may say that it is misleading to think of them as in-between. This in-between thing only makes sense for certain kinds of logics such as over boolean algebras or Kleene's 3-valued logic. In fact, other 3-valued logics don't share such a nice interpretation.

Mitch

@user21820 good point, I'm just telling you what others have proposed. there's also and = min llke you suggested.

@user21820 Sure. There are may ways of not being either true or false that are not simply 'partly true partly false' on a continuum between. Just explaining the obvious metaphor of 'third way' being 'between/middle'.

famesyasd

15:15

:45536404 do you prove that like:
given any x
   if x = 0
       13 = 13
       x = 0 and 13 = 13
       (x= 0 and 13 = 13) or (x != 0 and x * 13 = 1)
       exists y (x = 0 and y = 13) or (x !=0 and x * y = 1)
    if x!= 0
        x * 1/x = 1
       x !=0 and x * 1/x = 1
       (x = 0 and 1/x = 13) or (x!=0 and x * 1/x = 1)
       exists y (x = 0 and y = 13) or (x!=0 and x * y  = 1)
   exists y (x= 0 and y = 13) or (x!=0 and x * y = 1)
forall x exists y (x = 0 and y = 13 or x!=0 and x * y = 1)

user21820

Quick edit it and press "fixed font" and then "send".

=)

famesyasd

saved

user21820

@famesyasd Yeap that shows the 'existence' part. You still need the 'uniqueness' part, otherwise it's not enough to permit the definitorial expansion.

(By the way, special stuff like quote-reply and links don't work in "fixed font", so next time you can separate into different messages.)

For reference this is about:

Jul 8 at 15:05, by user21820

The theorem now becomes "∀x∈R ∃!y∈R ( x=0 ∧ y=13 ∨ x≠0 ∧ ( x·y = 1 ) )".

famesyasd

okay

user21820

@famesyasd: I've to go soon, but I've to think again about whether we really need the 'uniqueness' part. I wrote in this post the following:

> For each (k+1)-parameter sentence φ over the current language such that you have proven "∀x[1..k] ∃!y ( φ(x[1..k],y) )", you can add a new function symbol f and the axiom ∀x[1..k] ∀y ( f(x[1..k])=y ↔ φ(x[1..k],y) ).

But just now I wondered whether I could relax it to:

> For each (k+1)-parameter sentence φ over the current language such that you have proven "∀x[1..k] ∃y ( φ(x[1..k],y) )", you can add a new function symbol f and the axiom ∀x[1..k] ( φ(x[1..k],f(x[1..k])) ).

famesyasd

15:28

I think you can

as far as i can remember to deduce this axiom it doesn't requiere uniqueness

user21820

I think so, but to be sure, do you have a logic text that explicitly says so? The one I have also had the 'uniqueness' criterion.

If you just do the latter, it is effectively Skolemization, but I'm not sure if it is conservative over the original (does not prove any new theorem in the original language). That's what I need to think about again next time.

famesyasd

@user21820 No, I'm just speaking from my expereinece I think that whenever I deducded this axioms I think I never used uniqueness so nothing I can do to show that formally

@user21820 did you read enderton's book on set theory?

user21820

No I didn't read it.

famesyasd

it's called "Elements of set theory"

okay

@user21820 I wanted to ask when someone asks for example: How may functions exist from 2-element set to 3-element set what do they mean by "function"?

user21820

@famesyasd Well the standard definition of "function" in set theory is a set of pairs that represent the mapping.

So you just have to count how many possible mappings there are.

famesyasd

15:38

hmm okay, and when we write f: R -> R f(x) = x^2 \forall x \in R how exactly do we get this notation?

user21820

If you want an abstract approach that isn't tied to set theory, then you just need function extensionality, which is that functions f,g are equal iff they have the same domain S and ∀x∈S ( f(x)=g(x) ).

@famesyasd It's how we write in ordinary mathematics. After all, a function merely needs to specify the output for each input from the domain. Whether you encode it as some kind of set when working in a set theory, is another matter.

And we don't use the symbol "∀" in such writing.

famesyasd

@user21820 in a set theory we can get some functions by constructing its specifying set or also by definitorial expansion?

user21820

@famesyasd No in set theory you can only construct functions by its specifying set. Definitorial expansion does not produce objects!

famesyasd

why would I want to construct functions if I have definitorial expansion? I don't get it

user21820

Because definitorial expansion does not give you objects that you can reason about. For example functions from N to N. You can quantify over them and so on. You cannot do that with definitorial expansions.

famesyasd

15:50

okay I think I see

is it possible to describe some functions by constructions with sets and also by definitorial expansion?

user21820

@famesyasd Yes. Every function that you can explicitly construct is also something that you can get via definitorial expansion. However, there are definable 'functions' that are not functions, such as the powerset 'function'. And there are functions that are not definable by us, if you believe Cantor's theorem outside, since there are uncountably many functions from N to N but only countably many defining formulae you could possibly write down.

For another example, the function ( N k ↦ k·3+1 ) is definable over PA, but does not exist as an object in the intended model of PA. It is also definable over ZFC, and also an object you can construct within ZFC.

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic