Logic - 2018-01-04

user21820

04:12

@DavidReed: Hello! Haven't seen you in a while. How are you?

David Reed

04:44

Yo there

I am so so

@user21820 How about yourself?

Ive kind of been avoiding this room since the twinky incident

turned 30 yesterday

Bringing an end to what will hopefully be both the darkest and most illuminating years of my life.

@user21820

user21820

@DavidReed I seriously forgot what "twinky" refers to already.

David Reed

that person that came in because I was "handsome" and then started talking about ppl wanting to kill him

user21820

Oh lol! Anyway it's not your problem at all, so why worry?

David Reed

It just made me uncomfortable

How's life? Anything going on logic wise that's of interest lately?

user21820

Well anyone could do the same to any other user, whichever room they go to. For example if you click on my username, you'll see all the rooms I am currently in. There's no privacy on Math SE, but the mods will see to any discomfiting behaviour. =)

David Reed

04:58

what wound up happening that night?

user21820

It just stopped. End of story. Moderators deleted the two worst ones of his comments (about "killing").

And I think he got suspended for a day. Oh I checked; it was only a 1-hour ban.

David Reed

I'm going to the galapogos islands in 3 weeks. Words cannot express my excitement

user21820

@DavidReed Aha. That sounds like fun.

Either way, take care of yourself while you're going around having fun. =)

David Reed

Its where Darwin formulated his theory of evolution, almost all the creatures there are endemic--cannot be found anywhere else on earth

penguins, giant turtles, manta rays, sharks, whales, funky looking birds etc

user21820

Haha. You mean Galapagos.

David Reed

05:02

is that not what I said?

oh the spelling

typo

user21820

Lol.

There are weird-looking creatures all over the earth.

David Reed

Our cruise ship has a glass bottomed boat, so can see underneath

user21820

That's nice.

"Our"?

David Reed

my dad and brother

user21820

That's great.

David Reed

05:04

going to get to snorkel with sea lions which I'm actually pretty psyched about as well

user21820

Curious. How much does it cost per person?

David Reed

How about you? anything exciting for the new year or plans for the future?

all in all for the three of us will be about 20k

american

user21820

I see.

David Reed

you going to be at the computer here for awhile?

user21820

@DavidReed Nothing much new coming up, but I'm trying to finalize the fine details of my type theory, which would be my preferred foundational system.

@DavidReed Yes for the next couple of hours I think.

David Reed

05:07

awesome. me as well

user21820

@LastIronStar: Hello there! Hope my stupid error last time didn't confuse you too much. Did you see my corrected solution?

David Reed

You can move the above to the trash if you want

LastIronStar

@user21820 I didn't read the first one lol

user21820

@LastIronStar Ok good.

@DavidReed No need, but if you want it moved to your own chat-room I can do so.

David Reed

I just know some ppl are really strict w off topics. your besty 0039 for instance

doesn't bother me

I jumped into a misc. chat the other day and saw you two had been going at it again.

LastIronStar

05:11

@Secret You around?

user21820

@DavidReed Not my besty, whatever that means, lol. I'm really strict against cranks and immorality (which explains why my attitude towards them is so harsh), but that's about it.

David Reed

besty = best friend

user21820

Nope. I do not know him/her except as another user on Math SE.

@LastIronStar You can't wait to start, right? =)

David Reed

170039 you don't know?

LastIronStar

@user21820 haha yeah

David Reed

05:13

@LastIronStar don't let me interrupt you

user21820

@DavidReed Not at all. What made you think I was friends with him/her? If I were, then I wouldn't be having those discussions online but in person away from others' eyes.

LastIronStar

@DavidReed No worries! @Secret seems to be offline so the logic discourse has to be paused :)

David Reed

I was being ironical....

user21820

Lol. You love pulling my leg as far as it will go, eh?

LastIronStar

@DavidReed Happy Birthday! :D

David Reed

05:15

its obvious that you're not. Everytime I jump in a room its "WELL IF YOU'RE GOING TO CENSOR ME THEN IM MOVING THIS TO TRSH". Its like a tornado of just each of you moving the other's msgs into trash

Thanks man!

What's something logicy that I can 3d print

user21820

@DavidReed Um... cat chasing its own tail?

David Reed

is that symbolic of logic to you?

user21820

No.

I was just being a random idea generator.

David Reed

the logic analog of printing a pig PI statue

big*

LastIronStar

@user21820 Isn't an Ouroboros better for self-tail chasing related symbolisms?

user21820

05:19

@LastIronStar I don't like snakes.

David Reed

I could maybe make a cup with a turing diagram on it I suppose

user21820

Ah I know I know. Print a set of Wang tiles.

LastIronStar

@DavidReed You could print the symbols for Logic Gates

David Reed

That as well

LastIronStar

or just NAND gate

David Reed

05:21

both are good ideas

keep it in the back of your mind for the next few days, I'm waiting on more filaments now. I've become totally addicted to this thing

but I'll take a picture of it and upload it here for you to see

and if you want one I can mail it to you or to a nearby fedex pickup location (thinking of mr privacy for the latter)

LastIronStar

Is it possible to make your own 3D printer?

David Reed

yes

haha

you want me to make you a 3d printer?

LastIronStar

Ideally, Yes

that would be great

David Reed

I just bought a book that tells how to make one

but you still need extra metallic parts and the like

LastIronStar

You can share the name of the book?

David Reed

05:25

I can probably do better and share the open source/design for it

one moment

RepRap project

The RepRap project started in England in 2005 as a University of Bath initiative to develop a low-cost 3D printer that can print most of its own components, but it is now made up of hundreds of collaborators world wide. RepRap is short for replicating rapid prototyper. As an open design, all of the designs produced by the project are released under a free software license, the GNU General Public License. Due to the ability of the machine to make some of its own parts, authors envisioned the possibility of cheap RepRap units, enabling the manufacture of complex products without the need for extensive...

user21820

Interesting.

LastIronStar

cool

David Reed

I'm going to go lookup math ones ppl have put online and see if theres anything logicy

Somebodys done one better and printing functioning logic gates

pinshape.com/items/35390-3d-printed-tactile-logic-gates

user21820

05:40

@DavidReed For interesting logic stuff that I did recently, I solved my own question about extensions that fail to be sound at a specific level in the arithmetical hierarchy.

In my original post, I had a non-constructive proof at the Σ2 level:

David Reed

well well well

do share

user21820

1

A: Can there be two different math?

Yes. Let $S$ be our chosen foundational system. Even if we somehow know that $S$ is $Σ_1$-sound, we still cannot rule out the possibility that $S$ is $Σ_2$-unsound! Here truth and arithmetical soundness are of course defined with respect to the natural numbers in the meta-system. First conside...

Then I asked a few people (Asaf and Noah) whether they could answer my follow-up question in my comment, but neither gave an answer, so I posted it as a question:

2

Q: Computable extension to $Σ_1$-sound system that is $Σ_2$-unsound?

Recently, I wrote this post showing (if I did not make a mistake) essentially that: For any nice formal system $S$ that is $Σ_1$-sound there exists some extension $S'$ that is $Σ_1$-sound but $Σ_2$-unsound. (Here "nice" is the usual kind of technical requirement, but you could simply assume t...

2

Eventually after reading Gro-Tsen's answer, I realized I could use the computability-based proof of the Rosser incompleteness theorem to get an even stronger generalization.

Hence my self-answer. I think it nicely shows the incredible advantage of the computability-based viewpoint. It's much easier to think in terms of oracle programs than in terms of plain arithmetical sentences.

David Reed

This reminds me

what was the resource you used for computability based metalogic for FOL

user21820

@DavidReed If you're asking for where I learnt the computability-based stuff in my post about the incompleteness theorems, I didn't have any resource except the blog post I linked from my post.

But because of my background in both mathematics and computer science, I realized just how powerful it was. It's true that the ideas are probably already known to logicians very early on. But Kleene was the only reference I tracked down who used the zero-guessing problem.

Sorry not Boolos. Haha..

David Reed

@LastIronStar How are you in your logic studies? Have you started on sytax and semantics for FOL yet?

As mentioned I will be largely brain dead until feb 12

so not too far away

user21820

05:51

@DavidReed Did your doctor say anything about alternative techniques to sleep?

David Reed

that's why I've answered only easy reference requests types of questions lately

rep has been stagnant

I see him next wednesday

He's in LA. I

i'm currently in dallas

user21820

Ah okay.

David Reed

but its not a sleep thing. Just have to wait until I restart some meds towards the beginning of the semester for me to really dive into thinks requiring significant though

that's why I have starred them for later

LastIronStar

@DavidReed I'm currently reading this book called "The Foundations of Computability Theory" It is pretty good so far.

David Reed

sec I'll look it up.

LastIronStar

05:54

sure

David Reed

The boolos book we recc'd has some basic stuff on that as well. It has register computability, which is the closest model to a computer

empty this register into the accumulator etc

LastIronStar

Yes, planning to read Boolos as well. I just wanted to try something new so picked this up :)

David Reed

gotcha

wise move

LastIronStar

FYI

I will be updating this from now:

github.com/lastironstar/Logic-Notes

so that there's one place to refer stuff

David Reed

I generally by 5-6 texts on the same subject I'm trying to learn about

generally if one of them is weak on one part the other is strong etc.

cool man

LastIronStar

05:57

Currently, I'm lacking in Problem Solving Confidence - not just in logic, but in general :( so that's preventing me from opening more books parallely.

David Reed

I applaude your curiousity on the subject.

LastIronStar

Thanks

David Reed

MUST BUY: MATHEMATICAL THINKING: PROBLEM SOLVING & PROOFS

user21820

@LastIronStar You could add the proof you just finished. =)

David Reed

I use that all the time

been 10 yrs and not a year that goes by I don't reference it

LastIronStar

05:58

@user21820 adding all the proofs i've done so far :)

David Reed

@LastIronStar you simply must buy that book. I have recommend it on this website at least 10 times in my post

LastIronStar

@DavidReed Looks pretty solid, thanks!

David Reed

It was for my undergrand mathematical thinking/proofs/ pre abs algebra class

user21820

@DavidReed Lol let people buy what they want. I'm personally more in favour of free references online because some people (me included) do not wish to spend much money unless necessary.

David Reed

Yes I'm obviously not demanding he buy the book, what was meant that my recommendation for it is 12 stars out of 10

LastIronStar

06:04

@DavidReed I thinking it's mainly a psychological block you know, I am trying to find that attitude adjustment that will get me more motivated to stay on the problem.

David Reed

any problems in particular?

LastIronStar

Because I used to be pretty good at problem solving a few years back!

Well, instead of thinking about the problem itself, i'm thinking more about the consequences and trying to meta-adjust my thought process etc,. if you know what i mean.

David Reed

you get good prob solving in comp sci as well. Learn about how to break down complicated problems into a series of smaller problems that are easier to solve

is this like a proof type problem or a find a solution type problem?

LastIronStar

It's a issue of stable confidence i feel.

@DavidReed what do you mean?

more like Olympiad type problems.

if that's of any help

David Reed

Is the problem like : " Prove that if.." or "Show this problem has a unique solution and find it"

LastIronStar

06:09

oh, either in this classification - I think the parameter to go by is that i'm hitting a ceiling of difficulty beyond which i'm unable to persist and solve.

user21820

9

A: When to give up on a hard math problem?

It depends on the problem. Since you've tried a lot of problems already, I think it is not too hard to guess whether the solution is really completely out of your reach. In that case, either you can look at a solution if there is one, or you can simply put the problem aside and wait until you fee...

LastIronStar

to be clear it seems as though no amount of persistence will help at difficulties beyond this threshold of "YOU SHALL NOT PASS!!!"

David Reed

If you could think of an example, I could tell you how I would approach the problem

user21820

@LastIronStar The hard part is figuring out what that "you shall not pass" level is, so that you can correctly give up and look at the solution or set it aside temporarily. This would be easier with more experience.

LastIronStar

@DavidReed Right now, it's not that difficult a problem but i'm stuck in any case - I'm trying to prove that with high probability randomised quick sort runs in O(n log n) comparisons.

David Reed

06:14

What I can tell you is that there is something I call "mathematical maturity" it only develops by solving homework problems and doing proofs (and understanding the proofs). And as time goes on, things that would have totally overwhelmed you in the past became really trivial

LastIronStar

@user21820 well, there's no solution to look at it in most cases since i'm embarking on research work.

David Reed

I can prove any result from undergraduate analysis or algebra right this moment without any references if I gave myself 5 freebies and didn't include stokes theorem

user21820

@LastIronStar Ah then you'd only have the option to "set aside temporarily" and do something different for a while.

There's the brute-force option of trying all possible proofs, but that is very unlikely to get anywhere except for the simplest problems.

David Reed

So that's a "proof" problem and not a "solve" problem, if that clarifies my meaning earlier

LastIronStar

Yes, I understand that mathematical maturity takes its sweet time to ripen but i'm worried about it constantly

David Reed

06:18

So what would count as "high" probability

LastIronStar

@user21820 Yes, I don't think this is an option.

David Reed

95%

user21820

@DavidReed It's a technical but vague term usually indicating that probability goes exponentially to zero as n goes to infinity.

LastIronStar

no so w.h.p is something like "running time is bounded by (n log n) with a probability of 1 - (1/n)

David Reed

you mean convergence in probability then

user21820

06:19

Oh so mine would be "very high probability" in comparison to yours, I guess.

LastIronStar

where you can replace 1/n with anything that decreases fast enough with increasing n

user21820

@DavidReed No; in CS we typically want a hard bound on the probability, not a soft convergence guarantee.

LastIronStar

yes, it is very high probability

user21820

I think we can get very high probability for randomized quicksort.

LastIronStar

I know it's possible

i'm just stuck

David Reed

06:20

I shall look this up quicly

I haven't looked at sorting algorithms in a lifetime

LastIronStar

I don't want hints either so it seems like i'm gonna be stuck for a bit.

user21820

Aww I was just going to ask whether you wanted a hint.

LastIronStar

I should be able to solve this for my paygrade so taking hints is detrimental in the long run :)

but any advice on attitude adjustment and general approach is welcome :D

@DavidReed There's a wonderful book on Probability tools for Computer Science if you are interested.

by Mitzenmacher and Upfal, do check it out.

David Reed

Ok so it looks like it just means the probabilities converge to 1 in the regular sense

user21820

@DavidReed No we want hard bounds... It won't do to have an arbitrary convergence rate.

LastIronStar

06:25

yes but rate of convergence is also important.

David Reed

With high probability

In mathematics, an event that occurs with high probability (often shortened to w.h.p. or WHP) is one whose probability depends on a certain number n and goes to 1 as n goes to infinity, i.e. it can be made as close as desired to 1 by making n big enough. == Applications == The term WHP is especially used in computer science, in the analysis of probabilistic algorithms. For example, consider a certain probabilistic algorithm on a graph with n nodes. If the probability that the algorithm returns the correct answer is 1 − 1 / ...

LastIronStar

specifically, you want it to converge better than or at least as fast as 1 - 1/n

but the definition of fast enough is a bit loose.

user21820

@DavidReed As I said, it's a technical but vague term and the Wikipedia article you cited isn't doing a good job of explaining that.

David Reed

Ok. I see

user21820

Typically, having failure rate of 1/n as n → ∞ is good enough for most purposes because it can be bootstrapped to higher polynomial orders. But in some cases we want exponentially low failure rate, not just polynomial in 1/n.

LastIronStar

06:27

@user21820 actually the wiki seems to explain it fine!

user21820

@LastIronStar It only gave 1−1/n as an example, not as the definition of "WHP".

Granted, it's vague, but when people in the literature use it we definitely want to look for "precisely how fast".

LastIronStar

yes, that is good right? cos WHP can mean exponential for some areas and something else elsewhere.

user21820

@LastIronStar Of course, but people not familiar with the area will not know that, and the article would be better if it made that clearer.

There's always a mismatch between terms in a field and what outsiders would think at first.

LastIronStar

yeah I agree with that.

it could be better

David Reed

the only one that shows up with that author is "Probability and Computing"

I'll probably get that one irregardless of whether I get the other

LastIronStar

06:31

oh, they are coauthors.

that's the one.

i should have been clearer in hindsight

David Reed

thanks for the recc sir

I've been meaning to catch up on statistics for the mcat

which means I have to refresh on probability

Which means I have to refresh on the fourier transform :((((

LastIronStar

I'm not sure if this is a good resource for probability leaning on statistics but it is, as I said, excellent for Probability as used typically in Algorithmic Analysis and the sort.

David Reed

I'm interested in all types of probability irrespective of their usage in statistics

Frankly, I'm interesting in everything

LastIronStar

ok good, then this will be very interesting for you! It has loads of problems as well :)

@DavidReed *interested FTFY :P

David Reed

yes typo

whats ftfy mean?

LastIronStar

06:36

Fixed That For You :D

user21820

Lol!

David Reed

ah ok

LastIronStar

ok, i'm gonna attack the problem once more now, let's hope it yields! see you two laters!

David Reed

later man

LastIronStar

@DavidReed Once again, Happy Birthday! I wish you the very best of health and happiness here on out :)

David Reed

06:39

Well thank you! Much appreciated.

I have a year and a half of chemistry to finish by the end of the summer

along with a semester of sociology and a semester of psychology

Come the twelth I will be in school nonstop until next winter

user21820

@LastIronStar See you!

@DavidReed: I didn't realize you're not much older than I am. Haha.. =)

David Reed

How old did you think I was?

user21820

About 35? I'm not good at guessing ages anyway.

David Reed

Ah

alright man I'm pooped. I'll stop by again soon.

It was good catching up

user21820

I'm going to be away too. See you later!

Alessandro Codenotti

09:28

@user21820 another quick question concerning the graphs exercise, what's exactly a chain?

user21820

11:33

@AlessandroCodenotti Sorry didn't see your message. Oh for that post it is about directed graphs so it's not symmetric and need not be irreflexive. A chain in that context would be a (possibly infinite) sequence ... → u → v → ... , where the only edges are from a vertex to its immediate successor in the chain.

Alessandro Codenotti

12:59

Hm, ok so for the first one I can add a constant $c$ and consider sentences $\varphi_n$ saying "there is an element $x$ which is a distance of at least $n$ steps from $c$" to get a model with an element infinitely distant from $c$ by compactness

No, wait, that doesn't work, I need all the sentences to reference the same $x$, so I add a second constant symbol $k$ and modify $\varphi_n$ to say that $c$ and $k$ are at least $n$ steps of distance from each other

user21820

13:37

@AlessandroCodenotti That's right.

Alessandro Codenotti

@user21820 Cool, for the second one I think not even a single semi-infinite chain can be axiomatized, let alone a disjoint union of them, because I can add countably many constants $c_i:i\in\Bbb Z$ and consider sentences $\varphi_n$ saying "$c_{-n}$ to $c_n$ are linked in the usual order" and by compactness I get a model in which there are infinitely many elements to both sides of $c_0$

user21820

@AlessandroCodenotti What if you are allowed to have constant-symbols in the language?

Oh well the same argument works, though you can't exactly say "let alone".

Anyway the sketch in my post is for the interpretation of "semi-infinite chain" as being "a chain with a starting point", whereas your argument also deals with the interpretation of "semi-finite chain" as being "a chain with either a starting point or ending point".

Alessandro Codenotti

13:59

Oh, right, I tend to think about graphs as not directed so I didn't notice the difference

Sanity check: any such chain is countable, right?

user21820

14:16

@AlessandroCodenotti Yes, because we're not talking about a linear ordering here.

Alessandro Codenotti

@user21820 So to use a cannon to kill a fly one can't axiomatize a single chain by Löwenheim–Skolem

user21820

@AlessandroCodenotti Lol...

At least, that cannon didn't destroy the third exercise. =D

Alessandro Codenotti

nope, the union of $\kappa$ many disjoint chains works as a model of cardinality $\kappa$ so something a bit finer is needed :P

Actually I'm not sure whether it can be axiomatized or not in the third one, I need to think about it

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic