Logic - 2018-01-12

Fred

00:48

Can anyone tell me if this type of problems is included in logic or is it primarily set theory: x says exactly one of us is lying

Y: two of us lying and z: all of us lying

I need to find who says the truth

David Reed

01:04

Hint. You have to ask one of them what the other one would say to the question

it is a logic problem

oh wait

no its a variant of that problem

Leaky Nun

it's more like a logic puzzle than the things listed in the description (formal logic / mathematical logic)

David Reed

but yes its a logic problem

Its on topic for the room

given that the room owner and I spent a great deal of time discussing the extreme version of this problem

user21820

03:06

@Zermelo's_Choice You're welcome to participate! Bring whatever deductions you want.

@Fred As LeakyNun says, it's a logic puzzle, but if you wish to discuss how to solve such puzzles in general using propositional logic, it's part of logic. It's definitely not set theory.

@DavidReed Extreme meaning? =)

David Reed

"boolos' hardest logic problem in the world"

user21820

Ah that. Yes I remember now. =)

David Reed

Our favorite 8th grader asked another question today that sort of touched on regularity

user21820

In case @Fred is interested in reading that conversation (intertwined with other random conversations, it starts here. My immediate answer was here. Later, I fixed the puzzle here and gave a clean analysis to actually systematically deduce a valid solution.

@DavidReed You mean axiom of regularity?

David Reed

yes

user21820

03:15

What in (elementary) ZFC would require regularity to prove?

David Reed

He didn't use the term regularity, but basically stated what would have been the axiom had the existence been changed to a universal

let me see if I can find it

user21820

So he just asked whether a set could be its own member

David Reed

1

Q: In ZFC given any set $X$ if $x\in X$ then is $\emptyset=x\cap X$?

Given any set $X$ and any element $x\in X$ then is $\emptyset=x\cap X$? Feels like it should be, I mean most of the time I don't even think of elements of sets as sets unless I'm deliberate doing so. Though I know if like I'm working in ZFC or something, then like pretty much everything I write...

Its nice to know hes really following up on it

user21820

03:29

@DavidReed Incidentally, my type theory has a universal type "obj" and we do have "obj∈obj", so no 'regularity' for my type theory.

But I like it; after all some programs (when run on themselves) accept themselves.

David Reed

@user21820 I would very much like to see it. I'm thinking right about 30 days from today I will be able to. I know you have been anxious for me to give my thoughts but absent the introduction of my semester "meds" I would not be able to give you any feedback that would be valuable.

user21820

@DavidReed Sure. There's no hurry. It get's better over time anyway. =)

David Reed

I would like it, if you have time, to give your thoughts on this post I have made.

3

A: What is the benefit in constructing the integers from natural numbers?

The result comes from a strong historical desire to find a list of axioms from which all mathematical truths could be proved in a first-order system. With the advent of calculus, people began to prove all types of completely incorrect statements by their cavalier manipulation of the infinite. Thi...

user21820

→ 4 messages moved to trash

@DavidReed I've read it before. And note that you don't have to delete comments when they get long.

Moderators will tell you that comments are not meant to be permanent, unlike answers, and that you could improve your answer to incorporate important comments, but most users (including myself) don't see the need to repeatedly update answers unless there really is something significant to add.

As for the content of your post, I disagree with:

> It is generally accepted that one should take as few axioms as possible.

David Reed

I know, it avoids me having to deal with getting yelled at though, and also keeps the site prettier. After he has read what I said there was no reason to have them there

that is called Ockam's Razor

I subscribe to it within reason

user21820

03:37

@DavidReed No that's not good for other readers who may be interested in reading the same comments.

@DavidReed I subscribe to it, as you recall our prior discussions. But that is not equivalent to minimizing the number of axioms.

For example, consider the conventional axiomatization of PA, and compare with the equivalent. I strongly prefer the equivalent because it reveals the structure (discrete ordered semi-ring) much more clearly than the other.

David Reed

The 2nd point I made for it I felt was stronger

LastIronStar

howdy

David Reed

In any event, the comments had very little value

user21820

For another example, consider the conventional axiomatization of groups and the equivalent (but silly) axiomatization with only left-identity and left-inverses.

Furthermore, Occam's razor actually would choose a far weaker foundational system than ZFC.

Because we simply have nothing in reality that needs the 'strength' of ZFC to be described, and because it is not clear that the set-theoretic stuff we use ZFC to describe actually has meaningful sense.

But all this is way above what the asker needs to worry about, so I won't post a comment on your post.

@LastIronStar Hello!

David Reed

Maybe I'm not familiar with Ockams Razor then, but I feel strongly that one should make as few assumptions as possible

LastIronStar

03:43

Reading chat.stackexchange.com/transcript/message/42109372#42109372

David Reed

unless you can make a bigger assumption that is ontologically the same assumption

user21820

@DavidReed That's a popular phrasing, but it's arguably wrong and misleading. What it truly means is to make the weakest collection of assumptions that suffices to explain what you want to explain, not necessarily the fewest.

David Reed

I agree with your statement there

That is really what I meant when I said that in the post

in the context of assuming the natural numbers and not the integers

in both instances the number of axioms is the same

user21820

@DavidReed Ah okay that wasn't clear to me. That's why I brought up the example of PA's two equivalent axiomatizations, and why it makes sense to choose the longer one as a discrete ordered semi-ring rather than the original Peano one.

@DavidReed I haven't come to that yet. I also disagree with that part about integers, but it's more difficult to justify my disagreement.

David Reed

I also felt that the point I made about it being harder to define OP's on Z was a good argument for it as well

I would be fine assuming everything up to the rationals myself

I would not feel comfortable assuming the reals

but if you assumed the integers for instance, how would you define the operations on them?

the naturals is easy because you just use the recursion theorem

user21820

03:47

First, the facts. It's not true that the strength of axioms is 'the same' in having integers outright compared with having naturals and constructing integers via equivalence classes. You completely forgot that you need set-theoretic axioms to do the construction. That's extremely bad from Occam's razor point of view.

David Reed

Did you read that post when it was first made?

user21820

@DavidReed More or less.

David Reed

Some would disagree with you, I myself do not

user21820

When I say "bad" it's because I'm referring to the ZFC-style axioms.

David Reed

I don't consider the assumption of the integers to be stronger than the naturals

user21820

03:49

If you work in a weaker type theory, you may be able to justify the construction of equivalence classes meaningfully.

Let's not go there yet.

David Reed

Ok

user21820

Secondly, it's easy to axiomatize the integers. Just use the axioms of a discrete ordered ring, and for induction we simply have it for the non-negative side.

Then immediately we recover PA for the naturals, and yet have integers baked right in.

David Reed

Let me ponder that for a moment

user21820

The reason I do not immediately advocate going this way is that there are potentially valid philosophical arguments that naturals are more natural than negative integers. I am not sure what physics suggests though...

The philosophical argument is that we clearly have a well-defined notion of finite strings of say two symbols. And such strings have a natural length. There is no negative length string.

David Reed

Lets approach it from how ZFC would have to be modified

user21820

03:53

@DavidReed No I'm only comparing between ACA built on top of PA and ACA built on top of the above axiomatization of integers.

Because it is unclear what it means to compare things from the viewpoint of philosophically unjustifiable systems.

David Reed

That's outside the scope of what I'm talking about

user21820

@DavidReed That's why it's irrelevant to the asker.

David Reed

Ah

So you actually read that post before we met

interesting

user21820

So if one argues that naturals arise naturally as lengths of finite strings, then it makes sense that integers are a conceptual construct rather than being on par with naturals.

David Reed

One could argue philosophically that -1 makes no more sense than $i$ does

or rather

user21820

03:56

But if one believes that there is a direct real-world interpretation of integers, such as the charge on a charged particle...

David Reed

is no less imaginary

user21820

(continued from previous comment) Then you have to admit there is a valid reason to consider the axiomatization of integers as a viably justifiable approach to describing the world.

David Reed

I wouldn't think of it as a number though

user21820

Oh? So is an electron's charge different in nature/quality from a positron's charge?

David Reed

I would think of it as a magnitude and then a "sign" to describe its polarity which we model as a negative number

brb

user21820

03:59

If you think of an integer charge as a sign plus magnitude, you face the problem of explaining why opposite charges just cancel as if they are elements of a ring, and why positive plus negative charge would just result in a final charge consistent with additive inverses.

Something just seems off about taking the syntactic (sign plus magnitude) way to describe particle charge, or spin quantum numbers.

Yet we have no negative-length strings, so I'm ambivalent about whether naturals or integers are more fundamental.

David Reed

There is NO explanation for it

it is what is observed in nature

I could very much say type A charge and type B charge instead of + and -

user21820

It's not about explanation in the sense of cause/reason.

It's about explanation in the sense of description.

Occam's razor applied this way is sometimes called "minimal description".

It does not mean we are giving the reason for the charges to be the way they are, just that we're giving what we believe is the simplest description, which we can then use to predict future behaviour.

David Reed

we are talking about whether negative numbers are natural, I do not believe they are natural in electrostatics, I think it makes life easier to MODEL them that way

user21820

@DavidReed So you think negative charges and positive charges are of different nature? That doesn't make sense...

David Reed

what do you mean by "nature"? Initially they were called glass charge and wool charge

you arbitrarily call one of them positive and the other negative and then the math becomes much simpler

but I think the statement it has 3 units of type B charge would be more accurate than saying it has -3 units of universal-type charge

user21820

04:10

I mean that if we believe the charges are actually governed by some law, it seems philosophically less problematic to assume that they are in a ring, rather than to assume that they come in 'two parts', namely sign and magnitude, which would have to be manipulated according to the ring axioms to obtain the correct results on addition of charges.

Just look at how you would define addition of charges as (sign,magnitude) pairs.

And notice the irritating odd element called zero as well.

David Reed

it is easier mathematically to use the 2nd I agree, I think the first sentence is a more accurate depiction of nature

user21820

@DavidReed First meaning what?

David Reed

from above beginning "but I think the statement.."

user21820

That's why I asked you whether you think positive and negative charges are of different natures. Granted, English is too imprecise for me to ask a precise question...

David Reed

and I asked what you meant by "nature"

I believe they are two sides of the same coin, but most definitely not the same

user21820

04:14

And how could I possibly explain what I mean... But if I get you right, you sort of believe that there are two kinds, positive and negative, and that one positive cancels out one negative. So you end up mathematically with a ring.

That's a defensible viewpoint, I think.

David Reed

there fields cancel

the charges themselves do not dissapear

but yes you basically get what I am saying

user21820

I see. Okay they stay but their effects cancel.

But I think that if you hold such a viewpoint you also have to hold the view that the naturals and integers are in no way embedded into the reals (or at least whatever seem to be underlying the particle wavefunction's support).

Is that right?

And so you can have charges being modeled by natural numbers (there are never negative numbers of any of them), but positions are totally different.

David Reed

I don't see how I would have to make that leap no

user21820

I mean that the wavefunction support seems to be dense and symmetric and unbounded in both directions. So there would not be a physically meaningful embedding of the naturals into the reals.

I shouldn't have said "in no way".

David Reed

I'm trying to distinguish between the way something in nature is modeled, and how it will not necessarily be a perfect portrayal of the thing itself

user21820

04:21

I understand that.

Anyway I got to go for a while. See you later!

David Reed

I also see no reason to introduce the notion of wave function here, because you are then drifting further into modeling

ok I'll see you in a bit

@user21820 I'm not certain there is anything in nature that would have the properties of a continuum, except possibly time (and I'm iffy even on that one)

Secret

> A mathematical theory is not to be considered complete until you have made it so clear that you can explain it to the first man whom you meet on the street

Hmm... I am wondering whether this is provable in first order logic. I also need to find a suitable bunch of assumptions to start my logical argument with. Will check later

completeness is also a vague term here. It can either mean the technical notion of completeness of a theory, or the layman notion that "there is nothing missing". The latter is quite hard to formulate

Meanwhile where did Lastironstar went...

Secret

04:55

in Mathematics, 2 mins ago, by user 170039

@Secret IUT?

Those who are interested can follow the discussion here as otherwise this post will get too long for logic room since it is not in an active discussion state

user21820

@DavidReed I don't know about that, but it seems to me that it is viable to explain quantum mechanical phenomena by treating the particle as literally the wavefunction, which should easily explain the non-local phenomena as well as various things such as the quantum eraser.

@DavidReed Yet I'm not even assuming the existence of the classical reals, namely a model of the second-order theory of reals.

user21820

05:15

I guess it depends on what is meant by second-order here. In a constructive type theory, the types one can construct are not as crazy as those that we can construct in ZFC, and that has direct effect on what can be a model of the second-order theory of reals.

That's the problem with second-order logic with full semantics; it depends on the meta-system intrinsically.

So I sort of believe the real-world meaningfulness (approximately) of the second-order theory of the reals represented in my type theory, but that is significantly different from the one in ZFC.

@Secret It should be "where did X go?", because "went" becomes "did go". =)

David Reed

05:38

@user21820 I think it would be better to have conversations like the ones we are having when I'm not on anxiolytics, they quite literally work by slowing down how quickly the cells in your brain are firing.

user21820

I see. No problem.

David Reed

As sometimes, when I'm not able to follow you it seems to frustrate you.

Again, in one month I think the overall quality of our discussions will increase 10 fold

user21820

@DavidReed Not frustrating most of the time, and not this time. =)

David Reed

Ok

user21820

@DavidReed But I look forward to 10-fold quality increase, given that it's already so good now.

Hahaha..

David Reed

05:40

It's a big difference, I just make an effort to stay off them during breaks so as to keep my tolerance down

user21820

I see.

David Reed

semester starts feb 12

user21820

Ah. That'll come in no time.

Mauro ALLEGRANZA

09:17

@FBIT - can you join this

user21820

09:47

@MauroALLEGRANZA: Hello and welcome!

If FBIT can't join due to reputation, let me know and I'll ask a moderator to grant access.

There's a longstanding 'bug' that owners can't do so despite being shown the ability to.

Mauro ALLEGRANZA

Sorry for my intervention; I'm trying to invite him, bt I cannot succeeed.

The help ref to an "invite" button that I cannot find.

user21820

FBIT is already here in this room.

Mauro ALLEGRANZA

OK, I see. @FBIT - it seems that you are in. Can you try to write ?

@user21820 - Thank you very much. Now we are in in both rooms; we have to make a choice :-)

FBIT

the formal systems one

Mauro ALLEGRANZA

Ok. @user21820 - Thanks agian for your support.

user21820

09:52

Wait you can write.

@FBIT: So yea feel free to continue wherever you wish.

Alessandro Codenotti

Hey everyone, a have a question! For a concrete example we say that in PA, with the language $L_{PA}=\{+,\cdot,S,0\}$ the order relation is definable, $x<y\iff \exists z(z\neq 0\land x+z=y)$, but what does definable exactly means here?

user21820

@AlessandroCodenotti It means exactly what is described in the following post as a valid definitional expansion, in this case adding a binary predicate-symbol.

6

A: How could we formalize the introduction of new notation?

What you may be looking for in your formal system is variously called full abbreviation power or definitorial expansion. Basically, it comprises rules that allows you to create on the fly new symbols extending the original language. We need one type of rule for each kind of symbol: $\def\eq{\left...

Alessandro Codenotti

Thanks, I'll read it in a moment

user21820

In particular, note that the new predicate-symbol "<" is not an object, but just like a syntactic short-hand for some parametrized sentence.

user21820

10:18

@FBIT: You're welcome to ask any logic-related questions here. I don't have book recommendations, but another user David Reed recommends "Computability and Logic" by Boolos. You can see some samples in the Logic Books room and you can ask David more about that book if you wish.

Leaky Nun

@user21820 how would one prove that $<$ is computable?

user21820

@LeakyNun I don't quite understand that question. It is computable because we can write a program for it, and prove that that program does what it is supposed to. What else?

Leaky Nun

hmm

I've seen things about decidability on nlab

also I've heard that decidable just means $\vdash x <y \lor \neg (x < y)$

user21820

10:40

@LeakyNun nlab is not in my opinion a very useful source to understand anything that you don't already know, and there are errors.

@LeakyNun As for this, it's common when talking about very constructive approach to real numbers. You cannot decide equality between computable reals.

But that has nothing to do with "<" in the context of Alessandro's question.

@AlessandroCodenotti: Do you understand what definability means now?

Alessandro Codenotti

10:58

Yep, thanks!

user21820

@LeakyNun: I can't believe I'm on the first page of the hats leaderboard for Math SE at rank 16 with 16 hats. Lol!

I didn't even try to get any.

Alessandro Codenotti

11:43

Oh, I forgot, I passed the (written part of) the logic exam, thanks again for all the questions you helped me with!

user21820

11:58

@AlessandroCodenotti You're welcome!

user21820

12:11

@LeakyNun: Have I ever shown you the meta version of Cantor's 'paradox'?

user21820

15:30

@amWhy: Hello!

amWhy

@user21820 Hello! How are you?

user21820

I'm fine, thanks! You?

amWhy

Busy, but I'm doing fine too!

user21820

Ah okay. I'll be more busy quite soon.

@amWhy: There are so many interesting logic questions on Math SE that I haven't yet gotten the time to attempt to answer.

amWhy

15:49

@user21820 I know... it's frustrating!

user21820

@amWhy It's also frustrating when I can't get feedback on the posts that I do manage to write. There are just too few logicians on Math SE that seem to want to do that.

user21820

16:05

@LeakyNun @AlessandroCodenotti: Hello! But I'm going to be off soon. So.. Bye! =)

Alessandro Codenotti

Hi and bye!

Leaky Nun

@user21820 maybe

@user21820 well I got on the second page

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic