Logic - 2017-12-11

user21820

04:06

@LeakyNun @DavidReed: Forgot to mention that, as I told Secret before, injections do imply a size constraint, whereas surjections do not. In my opinion, they imply a complexity constraint.

If S does not surject onto T, it implies that T is sufficiently more complex than S to prevent us from finding such a surjection.

David Reed

For finite sets they both give size constraints

user21820

Yup.

Indeed from the ideal program model I mentioned earlier, this is natural, because func(obj,bool) needs the halting oracle to decide, whereas obj is a trivial type (answer "yes" to every input).

David Reed

comp sci?!?!?!

You were just telling me how much you disliked MIPS

Made it sound like you wouldn't be interested in comp sci altogether. Anyways that's awesome man

user21820

MIPS is to theoretical CS as punch cards are to Python, or worse.

Computability is like (Math+CS)/2

David Reed

assembly gives you a much better perspective as to how a computer thinks then a high lvl programming language imo

That's why I enjoyed it. Digital logic design I also very much enjoyed

user21820

04:11

@DavidReed I enjoyed it enough to build a minimal working MIPS processor in Logisim...

But once is enough.

David Reed

Yes I did something similar once as well

Although truthfully very little of it was really original given how standardized components like adders/multiplexers etc have become

My sister actually just returned to school and is working on a B.S. for comp sci

user131753

Sorry to interrupt but I think that Gödel didn't went insane, he was just paranoid. There is no sufficient historical reference that states that Gödel became insane as you were suggesting here @DavidReed,

user131753

in Philosophy of Mathematics, 10 mins ago, by David Reed

He ultimately went insane

user21820

Lol.

David Reed

To my recollection he refused to eat because he believed he was being poisoned

user21820

04:14

Sources say that he starved himself to death because he was paranoid about people poisoning him. That's insane to me.

I'm paranoid (Leaky and David know it) but not like that.

David Reed

I also consider that to be a loss of touch with reality sufficient to declare as insane

paranoia is a classical element of schizophrenia, which is effectively the textbook definition of insane

Along with psychosis

user21820

Lol okay okay I didn't come here to talk about Godel's end.

=P

David Reed

No worries. I actually need to get to bed. Not feeling so great today. I will definitely try to jump back in tomorrow though. Until next time!!

user21820

@DavidReed Okay good night!

@user170039: Since you asked about Skolem's paradox, and I can't easily find what I said before about it, let me just briefly say again. If you discard the (in my opinion meaningless) ZFC kind of reasoning that permits the deduction of surjection from injection, then Skolem's paradox sort of goes away.

As you can see from the ideal program model, described yesterday, obj can very well be countable but func(obj,bool) is uncountable.

Despite being strictly contained within obj.

So it is countable in the sense of injection but uncountable in the sense of surjection.

Skolem's paradox is only paradoxical in the naive ZFC view that these two notions of uncountability are the same.

Secret

08:22

Footnote to be discussed later: Pondering about the halting problem for analog computers

yeah, and I think the inability to (insert suitable adjective if any) find an injection basically means that the notion of uncountable cardinality can never be predicative (or even constructive without some prescribed function that construct them in the first place). Since you said even in ZF the cantor theorem proof is only one direction because power sets are assuming they can split the universe to work out which subset is in the set or not,
it means uncountable cardinality (and size in general) is potentially a circular concept, and not provable to exist without some axiom to add them in

So if uncountable cardinality has to go (predicative versions of ZF, predicative type theories etc.), and that the notion of Lebesgue measure being so important in defining continuous probability distributions, it means somehow it has to be recovered in some way from the increase in complexity of the objects (i.e. somehow Lebesgue measure has to pop out from the notion of a lack of surjection from some type A to B)

Otherwise, we might be able to get around it by redefining a new measure which does not rely on uncountable cardinals, and rebuilt all the machinery of probability theory and some continuity theorems in real analysis from that

...actually, might do this experiment later by first using ZF (knocking out all impredicative elements) as a test ground: What happens if we construct a model of the reals such that it is unprovable if the countable sets inject into it but the countable set definitely does not surject into it, run all the proofs the is required to establish $\lambda^*([a,b])=b-a$ and the nested interval theorem, and then see the results that popped up

Perhaps, having only complexity may be sufficient to prevent the Lebesgue measure to collapse to zero, and thus things may not be affected

actually, take a stronger position: Construct the reals such that countable sets does not surject into it, and the reals biject with all its countable sets

so what we will end up in the end is the models thinks the reals are countable, despite having the same elements as the default model of ZF

One simple approach I have in mind is to throw away powerset, then fiat in the reals with the properties described above, construct the elements of the reals in the usual manner of first defining rationals, then take dedekind completions (all of these does not use anything more than countable cardinals). So we should have a countable cardinal collection of dedekind cuts and that can be identified with the elements in the reals, and then run through the Lebesgue measure proofs to see what happens

typo: real inject with all its countable sets

LastIronStar

09:23

@Secret That's an interesting thought

Secret

Well, that's not really my idea, it's just in today's complexity criticality and computation symposium, the host speaker mentioned about that there may be no halting problems for analog computers. Google is also not very helpful on that matter, as there seemed to be quite mixed results

LastIronStar

Do you have a link to this symposium talk

nevertheless, the thought is still interesting :D

Secret

Well, today is just Day 1, thus there are no links yet. Also I should said more accurately, that the host speaker's comment to another speaker's talk about analog biochemical computers is it is unknown if there is a halting problem for analog computers, and that might be why biological systems use analog computation despite being less efficient than digital computation

I can however refer to the papers of the talk of the other speaker, though

arxiv.org/abs/1706.02206

LastIronStar

Is this the one? sydney.edu.au/complex-systems/events/c3symposia/…

that would be pretty cool

btw what is your field of research/interest?

ofc i presumed you are an academic, correct me if i'm wrong

Secret

Yeah you can only find the flyer so far:
Of course, any real life computers (unless there exists physical actual infinite objects or infinite memory, or infinite time step processes), will not really be analog. An ideal analog computer (which has infinite states) will be an example of hyper computation, though even for that it is unknown if there is a halting problem for this class of hyper computation

No I am just a chemistry PhD in that uni, I just happened to have interests spanning through all human knowledge domains thus people often think I know a lot but in fact I just knew enough t…

LastIronStar

09:32

Wow! That's great, I'm a chemistry buff myself :D

Secret

What field in chemistry you are in?

LastIronStar

I am not professionally into it, my field of research is computer science. But I did love it enough to almost be part of my country's IChO team (back in the day i must hasten to add)

Secret

I see. I am actually not very good at computational sciences. user21820 discussions and wikipedia is basically where I learnt most of the computational theory stuff

I suck even more on the practical aspects of computer science. I am pretty much a computer blind

LastIronStar

well, I think everyone's starting somewhere. Hopefully, I'm not too far behind

btw I love Organic Chemistry

to be specific Organic synthesis

wbu?

Secret

I like organometallic, because its more fun to play with all 118 elements of the periodic table then to be restricted to 15 something of them (and more importantly, the complexes have pretty colours). This field also naturally include organic chemistry because ligands are mostly organic molecules

LastIronStar

09:42

That's one area I never really got an opportunity to learn @ school

Secret

I also interested in computational chemistry (though I hate coding), because having a strong theory to explain why a reaction goes is often useful to plan new reactions without issues of chemical loading when using them in labs and expensive chemicals

in particular, I like almost all aspects of quantum mechanics, and quantum chemistry is highly relevant in making new materials

My PhD combine both fields togethers

LastIronStar

that sounds like a good match between theory and practice

Secret

Indeed, there will be wet labs next year, I just need to make sure all that hard coding is done before that

LastIronStar

I wish you the best of luck.

user21820

12:38

@Secret What is giving you the idea that the Lebesgue measure needs ω[1]?? It doesn't.

Secret

nah, I am talking about uncountable cardinalities in general, not necessary well ordered, cause Lebesgue measure does need uncountable sets which are those that don't biject with countable sets (as those will have zero measure). (in particular, there are models of ZF where every set is lebesgue measurable, and that has nothing to do with $\omega_1$

However, since only very recently I am made aware in this chat that the original cantor theorem does not really address the injective case, I am wondering whether a surjection based definition of uncountability can still allow uncountable sets t…

user21820

@Secret A cardinal in ZFC is an ordinal. If you don't mean cardinal in ZFC, then don't use that term.

Measure theory is going to be beyond you right now, since you don't have a good logic foundation.

[0,1] is uncountable with measure trivially equal to 1.

Secret

But that's the question: which notion of uncountability is needed for Lebesgue measure, since we are commonly taught uncountability in the notion of bijections, but in predicative models, injections are unprovable thus we are only left with surjections, which convey complexity, is that sufficient?

But I guess I will return to this topic later after sharpen up the logic foundation, though I want to comment that at my present knowledge complexity (which is related to computation) and measure (which is a generalisation of length) felt so different

user21820

You apparently don't know anything about the Lebesgue measure.

Nothing in its definition refers to uncountability.

Secret

Well I knew how it defined, and alessandro and I worked through a few examples

the Lebesgue outer measure need to fulfil countable subadditivity

alessandro said the subadditivity is not arbitrary, but must be countable, otherwise it will not be translation invariant

user21820

12:52

I don't think you know at all, and I don't know whether Alessandro told you the right definition.

Secret

In ZFC, Real intervals are uncountable since they don't biject with countable sets

The Lebesgue outer measure $A \mapsto \Bbb{R}\cup \{\infty\}$ is defined to be the infimum of the lengths of intervals in the open cover of the set to be measured. It satisfies the following:
1. $\lambda^*(\emptyset) = 0$
2. $\lambda^*(\bigcup_{k=1}^{\infty} A_i) \leq sum_{k=1}^{\infty} \lambda^*(A_i)$
3. $\lambda^*(a,b)=b-a$
4. $\lambda^*$ is translational invariant

We can then showed that all closed intervals of the form [a,a] has the measure 0 by having a nested sequence of intervals $(b,c)$ which at the limit, the infimum of b and the supremum of c converges to a, then use 3 to show that a-a=0

user21820

@Secret This is more or less okay, and there is nothing in the definition of the outer measure that has anything to do with uncountability.

In fact, it suffices to restrict to simply a (countable) sequence of intervals.

Secret

but isn't the indexed set for condition 2 is often emphasised to be countable. If uncountability is not important, why will they be emphasising that?

user21820

If you read what you wrote, (1) to (4) are properties, not definitions.

And again, this has nothing to do with cardinality, so it's wrong to use that term. You simply have the fact that the union of a (countable) sequence of subsets of R has outer measure at most the sum of their outer measures.

A (countable) sequence is merely a function on naturals.

There is no need/reason to think of it as anything else.

Secret

13:09

hmm... so for the case like rationals and finite sets, then the correct interpretation is because the sum vanishes due to the open cover at the limit shrink arbitrarily small, and not because they are countable?

user21820

You should prove it. Then you will know what is required.

Namely, prove that any countable set of real numbers has outer measure 0.

Countable simply means is the image of some function on the naturals.

(It's true of Lebesgue measure too, but one step at a time.)

Secret

For ZFC, I have done that for rationals. Following after the above proof that the singletons are measure 0, we can use the cantor pairing function to enumerate the rationals. We then take this collection to form a union. Then by 2, all the terms sum to zero.

For an arbitrary countable set, I think you need axiom of countable choice to enumerate the elements, but the same conclusion should follow.

For an arbitrary outer measure, if it is translation invariant, then the singletons must have measure zero, thus the above proof in the manner of rationals and other countable sets can be carried…

user21820

@Secret This is not a proof.

I did not mean that you can use the properties you stated.

I meant that if you ever want to understand the assumptions needed by a theorem, you will have to do it yourself from scratch.

So work through the actual definition of outer measure for a countable set.

Secret

hmm... I think I had not read that deep into the general outer measure case yet (so far only have focused on Lebesgue measure computations and simple proofs like the nested interval lemma), so I guess that means we need to hold the discussion until later...

user21820

It's not hard. Unless you don't actually know what the definition (not the properties) means.

First for convenience define for every sequence f of sets that Union(f) = { x : ∃n∈N ( x ∈ f(n) ) }.

Secret

13:27

I read: "for each f indexed by the naturals, there exists an element in at least one of the f s"

user21820

No. Parse again.

Secret

"The union of f is a set where there exists an element such that the element is in one of the sets in the sequence indexed by some natural n"

user21820

No. Before you attempt to rephrase it, you should at least make sure you can translate directly the logical notation, don't you think?

Secret

right, heads back to forallx

user21820

Yes you should just finish your logic foundation first. But here is how it should look like:

> Union(f) is the set of all x such that ( there exists a natural n such that x is a member of f(n) ).

It's fine to rephrase it to:

> Union(f) is the set of all x such that ( x is a member of f(n) for some natural n ).

But note that without the brackets it will become ambiguous.

That's why no point rephrasing into English.

Secret

13:37

Besides the significant errors in bold fonts above, I also made the mistake of trying to parse f(n) into a statement of f and n, and not realise we actually need the bracket in the parsing (I was expecting parsing = a full english sentence)

Anyway, that does not (insert suitable word) the fact that my logic foundation is still very weak. In fact, it might be possible one reason I have such trouble solving physics problems including overinterpreting the physics meaning of maths formulae may be linked to my logic

user21820

I know I may seem biased, but in my opinion learning all other fields of mathematics would be significantly easier if you learn basic logic first.

It's a matter of doing it in the right order.

Total time/effort will differ if you do it in different orders.

Secret

Given how this is concretely the first time where my haphazard background does not managed to converge me to a coherent discussion of the topic (as in the past, my haphazard background is just "dense" enough to continue the discussion in a manner that the experts knows to some degree what I am talking about even though I don't understood half of the symbols, and the expert talks as if I am an expert in the field),
I think contrary to what most people think of me as a organised and analytic person, I am actually more intuitive. (which might explain why when I did psychometric tests recently …

typo:

may not actually, replace "not" with "not only"

user21820

@Secret I have a knack of seeing through people, which I'm sure you knew from the beginning. As for logic, it will mostly help you to be more precise in your thoughts and expression. It should also help you to grasp mathematics in full, meaning you should have either 100% certainty in your understanding of something, or 100% certainty that you do not understand.

And you're certainly capable of learning logic in a short time, if you did try.

David Reed

21:48

@Secret @user21820 Yes. Virtually all universities require math majors to take a "logic and proofs course" around second year. Secret I would highly recommend buying "Mathematical Thinking: Problem Solving and Proofs", It is a great book with diverse topics in both continuous and discrete math, I reference it all the time.

In terms of "the right order" I don't think someones first exposure to set theory should be axiomatic--just naïve.

David Reed

21:59

Also, with regards to the "right order" concept. You are trying to jump around in ways that blow my mind. It's very silly to try and construct the lebesgue integral without having constructed the reimann integral first. The whole reason of introducing the lebesgue integral is to get to the dominated convergence theorem, which in general you then actually wind up applying to the Riemann integral in calculations.

You are correct in that without uncountable sets, everything would be of measure zero, and there would be no point in this construction at all. @user21820 The notion of uncountability is implicitly used in the definition of outer measure, in the sense that the infimum is only guaranteed to exist because of the completeness of the reals. You are correct however in that this would be a very peculiar way to think about it.

Secret

22:15

Well, naïve set theory has been taught back in my first year maths but they basically run through membership, powerset, union and intersection stuff that is more on computation, nothing very deep

David Reed

That's correct

Most undergrads never see the ZFC construction, they use it implicitly of course, but go through all four years without ever learning it.

By the time they do see it, the notion of whether "uncountable sets are really necessary" never enters their mind because they've used the notion so many times.

Anyhow, if you do want to go through lebesgue integration, "A primer of lebesgue integration" has a great development, it's available as an ebook on amazon

But honestly you should buy a book on regular old real analysis first

To study the lebesgue integral prior to that would be like taking organic chem prior to taking general chem

I do applaud your curiousity though :) You are very much like me in your enthusiasm to learn everything you possibly can about every possible field.

Secret

Well, for foundation of mathematics, my curiosity starts out only having the goal of making sense infinity in mind. It just happens when predicative mathematics was first introduced to me during the chats with user21820, it resonated so strongly with my wish on being able to explicitly prove and construct mathematical objects in a non vague manner, that I became fully pulled into it in terms of curiosity

David Reed

Believe me, you will find that the proofs in real analysis are extremely non-vague

the nested interval theorem is something you learn in the first few weeks of a real analysis course

Secret

22:33

One of the things I am weak at logic is my brain semi shuts down when seeing a sentence with too many < symbols and nesting of brackets. Hopefully forallx will help me surmount that gap

My mental imagination and visualisation hangs at too many explicit nestings

David Reed

tell me if this one is easier to understand for you....

sec. comp is running very slow

wrong one

LastIronStar

Hi @Secret @DavidReed

David Reed

@Secret there

@LastIronStar Hi there!

LastIronStar

I am learning ordinals, it's fun :D

David Reed

oh yah? that's cool.

I'm not the best to ask about cardinals/ordinals because it's been so long since I've gone through them

LastIronStar

22:41

Is there any particular source you would recommend for this?

David Reed

I went through ZFC one time-nearly a decade ago, and haven't given it a second look since

hrm

have you gone through First order logic?

LastIronStar

@DavidReed Nope, I am just starting out in Logic.

And have seem to have taken a liking for YUGE numbers

I'm reading forallx

David Reed

I don't know of any meta-constructions of cardinals/ordinals but 820 might. I only know of ones explicitly constructed in a first order theory

A very good introduction to FOL is "computability and logic" by Boolos

which to my recollection can be rented as an ebook for as little as 10 bucks on amazon

LastIronStar

ok, i will forage this book

Secret

@DavidReed I have not learnt any of the 3 theorems used in that proof. But suppose I just use their results, then the proof flows except at theorem 2.12. For that I might actually need to lookup theorem 2.12 to fully convince myself

David Reed

22:52

I just meant the statement of the theorem itself

It's using the monotonic convergence theorem and the comparison theorem

Any monotonically increasing sequence bounded above converges and it's limit is its supremum, similar for bd below

Secret

The statement of the theorem is clear to me. There aren't many explicit nesting of symbols used

David Reed

The image there makes it clearer as well I think

Once its clear to you you can go through a very easy proof that e is irrational ive posted on this site..

Secret

It does, cause unlike daminark, I am a visual learner.

link?

David Reed

1

Q: Easy proof of the irrationality of $e$

What is a particularly elegant proof that $e$ is irrational that requires a minimum background in analysis?

its a self question self answer

Secret

The proof flows for me: your intervals basically enumerates the nth partial sum of the Taylor series of e with the intervals

David Reed

23:05

It's not my proof :). I got it here :

I believe I gave him credit. If I didn't please let me know so that I can

nvm. Yes I did.

Oh, for some reason I thought you said "your proof flows for me" and not "the proof"

Secret

Interesting how they exploited the nowhere dense property of the integers

Btw what I meant by "too much nesting" and my brain shuts down is when reading certain long statements in set builder notation such as the definition of the axiom of replacement

Also I suspect the irrationality of e^e may be proved in a similar way unless there does not exists "nested closed hyperbox theorem"

This is because we will instead be dealing with an infinite sum: $$\sum_{k=1}^{\infty}\sum_{l=1}^{\infty}\frac{1}{k!l!}$$

Since e^x is continuous everywhere, any path that converge to x should converge to e^x, so we can pick closes rectangles of the form $[a_n,b_n] \times [c_n,d_n]$ to converge to e^e

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic