Logic - 2017-12-19 (page 2 of 3)

7:00 AM

note that i'm using S to denote a collection on which closure is being taken

Yes, simply because the definition of a closure of S under F is that it is the minimal collection that contains the original S and is also closed under each function in F.

If any collection does not contain the original then it is not a closure of the original under any circumstance.

LastIronStar

@user21820 What makes me uncomfortable with this definition is that it assumes magically I have already gotten a closed collection S. It is not constructive in some sense. What would be appealing is if we can define Closure(X,f) given an arbitrary collection(set?) X and a function f.

user21820

@LastIronStar That is why I said its existence depends on the meta-system's capabilities.

Some are unable to prove that such closures exist.

But any practical MS can, for example via the way I showed above:

24 mins ago, by user21820

One way is to recursively define T[0] = S and T[k+1] = T[k] ⋃ { "¬"+x : x∈T[k] } ⋃ { x+"∧"+y : x,y∈T[k] } ⋃ ...

22 mins ago, by user21820

The closure in the above way would be Union { T[k] : k∈N }.

20 mins ago, by user21820

You can check that if you apply any of those maps to a member of T[k], the result will be in T[k+1]. Thus if you apply them to the union of all the T[k]s, the result will remain in the union.

Secret

I need some hints on finding that technical issue. I don't even know if I have the required knowledge to be aware of its existence

user21820

@Secret My definition essentially claims that such closures exist.

I then justified, see quoted comments, why they do.

I haven't justified that a minimal one exists, but let's just settle existence first.

Secret

7:07 AM

35 mins ago, by user21820

But there is a technical problem. Do you see it?

Are we talking about this one?

user21820

That's unrelated.

Oh that's what you're talking about?

Lol.

Secret

yeah

LastIronStar

LOL

user21820

"¬A∧B" can be constructed from atoms "A" and "B" using the mappings in two different ways.

Secret

uh, I need to clear my brain a bit...

user21820

7:10 AM

By our definition, it is a Prop. Closure does not mean there are unique ways to get from the original collection to each member of the closure. But then there would be no truth assignment on propositions.

LastIronStar

Let's take a break? @Secret @user21820

user21820

56 mins ago, by user21820

MS: We call g a truth assignment on propositions iff g is a function from Prop to {0,1} such that for any x,y in Prop we have ( g("¬"+x) = ( 1 if g(x) = 0 ; 0 otherwise ) ) and ( g(x+"∧"+y) = ( 1 if g(x) = g(y) = 1 ; 0 otherwise ) and ...

Secret

sure

user21820

Sure.

Lol.

LastIronStar

ok, laters!

Secret

7:12 AM

(Unrelated to logic discussion above):

So one of my dreams 2 days ago caused me to ponder about the notion of computational complexity as in the dream it shows me the non-surjection from the naturals to the reals. After I woke up, I then started think about alien technologies and came to a preliminary conclusion that I do need some notion of a limiting complexity to compare a hypothetcal alien technology to that of humans.
After that I started to wonder what does it mean for a real life entity to be as complex as the natural numbers and the real numbers

user21820

@Secret Lol. Is that supposed to be in your room? =)

Or you could set up a Secret Dreams room.

Secret

Well, let me just isolate my question from that:

Since we already can have complexity numbered by any natural number, what does it mean for something as complex as the collection of all natural numbers and the collection of all reals?

I am trying to think about a physical interpretation of surjection in your predicative system since you mentioned your system can be applied to all practical maths

user21820

@Secret I don't get your question, honestly. You'd have to define what you mean by complexity if it's meant to be a question in logic.

@Secret In that system complexity is just an idea, not a number

Once you learn enough logic, you can look at Turing jumps and the related arithmetical hierarchy. That is one notion of complexity. There are many others.

If you interpret the diagonalization argument in computability terms, it shows that there is no computable surjection from programs to program deciders.

Because func(obj,bool) would be interpreted as the collection of all programs that output a boolean on every input.

This can then be understood as saying that the Turing jump is more complex (one level higher) than ordinary programs.

Secret

hmm, that makes sense, so the notion of surjection in that system is analogous to a turing jump

user21820

Vaguely yes.

The same proof relativizes to any oracle, meaning that it applies to programs that are permitted to use any fixed oracle. For example, let P(1) be the collection of programs that can use the halting oracle.

Using the oracle means the oracle magically halts on every input and gives the right answer.

Then again there is no surjection from P(1) onto deciders in P(1).

This shows that the second level in the arithmetical hierarchy is strictly higher than the first (which is higher than the zeroth).

And so on.

@Secret It is not that a surjection is complicated.

( obj x ↦ x ) is a surjection from obj onto obj.

It is that if T is more complicated than S then one should not expect there to be a surjection from S onto T.

Secret

7:27 AM

yup

Leaky Nun

hi everyone

what's going on here?

Secret

you got a bowtie

Leaky Nun

yes I did

Secret

mostly logic class and then brief discussion on computational complexity and also consciousness matter debate

o, and stuff about the lawmaker

Leaky Nun

hmm

user21820

7:34 AM

@LeakyNun Well I tried to show that we can define semantics within the meta-system, but apparently it got a bit too complicated for Secret and LastIronStar.

It's not their fault though, since they haven't seen notions like closure before.

@LeakyNun: In case you're thinking of using inductive definitions as in type theory, I don't want to because that's just hiding things under the rug. =)

Secret

Perhaps the most surprising thing I learn from that is the notion of closure only need a $\omega$-sequence and not an arbitrarily countable sequence, whch further adding the pile of evidence against the justification for the use of $\omega_1$

I have seen closure before in topology and abstract algebra, but I never saw it get explained to that detail

user21820

@Secret Yes that's indeed the case, at least for closures of the sort I have defined.

Secret

Sometimes that makes me wonder, if we can somehow define concisely what is the collection of all practical mathematics, then perhaps it might be possible to prove within some MS that uncountable well orderings are independent of this collection, thus further establishing the status of uncountable well orderings as nonconstructive, and adds more weight to choose a more predicative MS

user21820

@Secret "Practical mathematics" will always remain a human cultural construct, even if it is influenced by the real world. Hence you may define it one way and others may disagree with you.

However, there's something that can be said about ω[1].

Z set theory (named for its inventor Zermelo) cannot prove the existence of ω[1].

ZFC can prove that V[ω+ω] is a model of Z, where V[k] is the k-th set in the cumulative hierarchy.

Never mind if you don't know what these mean, but Z can do pretty much all practical mathematics.

So in that sense we have some system ZFC that modern set theorists like that shows that a weaker system Z (that they agree is sufficient for almost all mathematics outside of set theory) cannot prove the existence of an uncountable well-ordering.

Oh hello @freshmouse! I didn't notice you pop in. Are you interested in logic?

Secret

I have seen those terms before and knew the very rough definitions, but yeah, you are right that to not assume I knew them.

user21820

7:45 AM

V[k+1] = Powerset(V[k]). V[ω] = Union { V[k] : k∈ω }. V[ω+ω] = Union { V[ω+k] : k∈ω }.

For reference.

Leaky Nun

so beth sets

user21820

@LeakyNun Not sure what that means?

Secret

yup, that's how V is defined, I first came across them when simpleart taught me ordinal notations and I read breifly on these in order to make sense of admissible ordinals

user21820

Beth[1] is at least Aleph[1], which doesn't exist in V[ω+ω].

@LeakyNun: Unless you mean something else?

Leaky Nun

is V[0] countable?

Secret

7:46 AM

since (in the absence of the axiom of construction V=L), L is (insert suitable sentence that I forgot) of the cumulative hierarchy and L is needed to talk about admissibles

user21820

@LeakyNun Sorry forgot to define V[0] = ∅ = {}.

Leaky Nun

oh

Secret

(The above sentence illustrates what I mean by my knowledge being haphzard. Suppose you ask me something about a field of study F, it is more often I came up with sentences S like "object + description + unknown", where the frequency and positions of unknowns are mostly random)

Leaky Nun

the von Neumann hierarchy

user21820

Yes. V[ω] = ω.

Leaky Nun

7:49 AM

is V[omega] countable?

then V[omega+1] is beth 1

user21820

Heh answered before your question.

@LeakyNun Definitely not.

P(N) is not a cardinal.

Leaky Nun

Beth number

In mathematics, the infinite cardinal numbers are represented by the Hebrew letter ℵ {\displaystyle \aleph } (aleph) indexed with a subscript that runs over the ordinal numbers (see aleph number). The second Hebrew letter ℶ {\displaystyle \beth } (beth) is used in a related way, but does not necessarily index all of the numbers indexed by ℵ {\displaystyle \aleph } . == Definition == To define the beth numbers, start by letting ℶ ...

Secret

Most of the time, people will think I have sufficient background on discussing a subject until later is because when they interpreted S, they sometimes can mentally fill in the unknowns, and end up with the intended meaning even though I don't know the terms

Leaky Nun

beth_1 = 2^aleph_0

user21820

@LeakyNun No.

Secret

7:51 AM

and when they give the answers A, for most situations, I can easily google for the terms I don't know in A and thus gradually understand their answers

user21820

@LeakyNun The wikipedia article is correct under the standard interpretation of set theorists, which you're missing. Hence the confusion.

Leaky Nun

but powerset = 2^

user21820

Beth[k+1] is the cardinality of P(Beth[k]), which is 2^Beth[k], where this ^ is cardinal exponentiation.

It is not 2^Aleph[k], because ^ here is automatically type-inferred to be ordinal exponentiation.

Leaky Nun

I meant cardinal exponentiation

afterall you said powerset

user21820

And it is not 2^N in the undergraduate set theory sense.

Secret

7:53 AM

However, as this logic class have shown, it seems for more formal fields F (and hence more rule abiding) the more likely I will be found to lack the knowledge to discuss about F since it is more likely for the random occurence of unknowns in S to miss out enough important details to make the question unclear

user21820

I repeat. P(N) is not a cardinal, and cannot be a Beth number.

Leaky Nun

but its cardinal is a beth number

user21820

Yes.

Leaky Nun

8 mins ago, by user21820

V[k+1] = Powerset(V[k]). V[ω] = Union { V[k] : k∈ω }. V[ω+ω] = Union { V[ω+k] : k∈ω }.

@user21820 are you just trying to be pedantic?

user21820

I'm not being pedantic. The cardinality of P(ω) does not exist in V[ω+ω]...

The sets in the von Neumann hierarchy up to V[ω+ω] do not contain a single uncountable cardinal.

Despite containing uncountable sets.

So it is wrong to call those things constructed as Beth numbers/sets.

@LeakyNun <− This in particular is false.

Leaky Nun

7:56 AM

so |V(omega+1)| is beth_1

user21820

Yes.

In ZFC.

Good now?

Leaky Nun

no

I think V(omega+1) is in V(omega+2)

user21820

It is.

But its cardinality isn't.

Wait.

What do you mean by in...?

Leaky Nun

$\in$

@user21820 I insist that beth_1 is an element of V[omega+2]

and that V[omega+1] is beth_1 itself

user21820

@LeakyNun I am pretty sure it is false. Namely, V[ω+1] = P(ω) ∉ P(P(ω)) = V[ω+2].

Haven't though of an obvious reason yet though.

Leaky Nun

8:03 AM

@user21820 are you saying that A ∉ P(A)?

user21820

@LeakyNun That's not always true. Come on your basic set theory is lacking!

Leaky Nun

here's a proof: A ⊆ A, so A ∈ P(A). That's always true

your basic set theory is lacking

user21820

You are right.

I need a break.

Do too much logic already.

Leaky Nun

now V[ω+ω] = beth_ω

user21820

No that cannot be true.

Leaky Nun

8:04 AM

ah god

user21820

As I said none of the uncountable ordinals are in V[ω+ω].

Leaky Nun

that's wrong

beth_1 is in V[ω+2]

so beth_1 is in V[ω+ω]

user21820

This time you are wrong. Please think carefully. All you had was #(V[ω+1]) = Beth[1].

You did not have V[ω+1] = Beth[1].

Leaky Nun

@user21820 that's easy

show me an element in V[ω+1] that is not in beth_1

or an element in beth_1 that is not in V[ω+1]

Secret

then it seems that O can be defined as $\aleph_0$

user21820

8:09 AM

→ 20 messages moved to Rambles

@LeakyNun I can't in ZFC, because CH is independent of it. But in ZFC+Con(ZFC), we can construct a model M of ZFC where CH fails. Then in M we have Beth[1] > ω[1] and hence ω[1] ∈ Beth[1]. But in M we also have ω[1] ∉ V[ω+ω].

I guess I need M to be a model of ZFC with the same ordinals. So Con(ZFC) may not be strong enough.

Not sure about that.

Let me find some set theory expert who talks about this.

@LeakyNun: TADA! Here:

5

A: What set theory axioms do I need to believe in uncountable ordinals?

As [1], [2], [3], and [4] may tell you, the axiom of choice is not needed to define $\omega_1$ (in particular [1] and [4]). Two key axioms are the power set axiom and the replacement axiom schema. In [2] and [3] you can see why the axiom of power set is needed. It is consistent with $\sf ZF$ wit...

Leaky Nun

@user21820 come on

beth_1 is defined to be powerset(aleph_0)

and V[ω+1] is defined to be powerset(V[ω])

you said that V[ω] = ω

user21820

You come on. Unless you doubt Asaf. He says that V[ω+ω] only has countable ordinals. So you are wrong.

@LeakyNun This is false. I already explained above.

22 mins ago, by user21820

Beth[k+1] is the cardinality of P(Beth[k]), which is 2^Beth[k], where this ^ is cardinal exponentiation.

22 mins ago, by user21820

It is not 2^Aleph[k], because ^ here is automatically type-inferred to be ordinal exponentiation.

22 mins ago, by user21820

And it is not 2^N in the undergraduate set theory sense.

In undergraduate set theory you use 2^N and P(N) interchangeably.

This is definitely not what is used in the definition of cardinals (Beth numbers).

Leaky Nun

28 mins ago, by user21820

Yes. V[ω] = ω.

that's wrong now

user21820

@LeakyNun Hmm.

Leaky Nun

now will you stop treating me like somebody who knows nothing about set theory

user21820

8:18 AM

@LeakyNun But you don't admit your mistakes. I admit mine.

Leaky Nun

my next sentence would be

that's wrong now, so beth_1 is not V[omega+1]

@user21820 ok?

user21820

@LeakyNun Look P(ω) does not give you Beth[1]. And unless I'm making another mistake I can prove this.

Leaky Nun

@user21820 that's wrong

P(omega) is beth_1

user21820

So despite my mistake, your reasoning does not work even if we are talking about P(ω) instead of V[ω+1].

@LeakyNun As I keep saying, you are wrong about this, so stop saying it.

This is a matter of definition of beth numbers.

Boots

Hello.

user21820

8:22 AM

And it is separate from the powerset.

Leaky Nun

ah

I see now

@user21820 I'm wrong :P

user21820

Great! We should probably now agree.

@Boots Hello!

Leaky Nun

yes

Boots

It's funny I end up here actually, I am thinking of studying Logic (no previous experience except an undergraduate in pure mathematics). Does anyone know if "A Mathematical Introduction to Logic" by Enderon is good? Also I sort of prefer youtube lectures if that's worthwhile here.

user21820

But for completeness, let me sketch my argument for why P(ω) cannot have Beth[1].

And you can poke any hole in it.

ω ⊆ V[ω].

This should be correct, unlike my previous wrong claim that ω = V[ω].

@Boots It's no good in my opinion. I understood it perfectly because I already knew most of what was in it, while my fellow classmates did not get what was going on.

Boots

8:24 AM

I am interested in learning things like Godel's proof, Set Theory, (Turing Machines if that makes sense here)

@user21820

user21820

Do you have mathematical background already?

Boots

that's a shame :(

@user21820 yes as I said I have an undergraduate in pure mathematics

Leaky Nun

@user21820 that's right, since V[omega] is all the sets you can write in {} notation

user21820

And do you know programming or Turing machines?

@LeakyNun So if Beth[1] ∈ P(ω) we should also have Beth[1] ∈ P(V[ω]).

Boots

@user21

user21820

8:27 AM

But Beth[1] is an uncountable ordinal and Asaf says that V[ω+ω] does not have uncountable ordinals. So by Asaf I should be correct?

Boots

@user21820 yes I have a lot of programming experience.

Leaky Nun

@user21820 lol I thought you're going to come up with a proof

and then it turned out to be "by Asaf"

user21820

No no at the error rate I have it's too risky. =P

Boots

@user21820 I've read a bit about Turing Machines but nothing formal.

user21820

@Boots Then great! If you want to go straight to the incompleteness theorems, you just need to read the first half of the pinned post on the right about the incompleteness theorems.

Boots

8:28 AM

@user21820 I also started the first chapter of the book...Did a few of the proofs...Let me see what I did in particular..

Leaky Nun

@user21820 then why bother stating "ω ⊆ V[ω]" to start with, if Asaf says "V[ω+ω] is a model of these axioms, and there are only countable ordinals in that model"

Boots

@user21820 yes but I would also like to get a Logic background.

user21820

@Boots Actually since you have programming background, Enderton may work for you the same way it worked for me.

So you can continue and see how it goes.

Boots

@user21820 is it with a CS application or something?

Leaky Nun

@Boots play with this

I like to learn by examples

user21820

8:30 AM

@LeakyNun Hmm I was showing that Beth[1] ∉ P(ω). We can't use Asaf's post directly because a model of ZFC minus replacement does not tell us anything about the 'truth' in (this version of) ZFC itself.

If you see an easier proof, could you sketch more details?

Boots

@LeakyNun thak you, I will take a look

Leaky Nun

I don't see why Asaf's statement does not exactly state that

Boots

@user21820 does Enderton cover things you're talking about right now?

Leaky Nun

After all, Asaf said that "V[ω+ω] is a model of ZFC-R, and V[ω+ω] only has countable ordinals"

user21820

@Boots Hardly.

Leaky Nun

8:31 AM

V[ω+ω] is a fixed set, and that it is a model of ZFC-R doesn't make it any different

Boots

@user21820 Hahaha

@user21820 do you think it's interesting/worthwhile to read?

user21820

@LeakyNun Neither gives what we want, because as you said correctly, V[ω] is not ω.

Leaky Nun

Asaf was saying that ZFC |= (V[ω+ω] |= ZFC-R), I think

Boots

It's only 4 chapters.

Leaky Nun

@user21820 you only want to establish that V[ω+ω] does not contain beth_1, right?

beth_1 is not a countable ordinal, so by Asaf it is not in V[ω+ω], QED

user21820

8:33 AM

@Boots If you actually finish that book, it would give you sufficient foundation to fully understand much of my post about the incompleteness theorem.

In fact, without that book, you should be able to understand the first half already, so you can try it out.

@LeakyNun No I wanted to show your original claim was false. =)

3 mins ago, by user21820

@LeakyNun Hmm I was showing that Beth[1] ∉ P(ω). We can't use Asaf's post directly because a model of ZFC minus replacement does not tell us anything about the 'truth' in (this version of) ZFC itself.

Leaky Nun

oh

user21820

Aha.

So do you see a better way?

Leaky Nun

well

every set in P(ω) is a subset of ω

beth_1 is hardly a subset of ω

user21820

Sorry.

Gah.

I keep saying wrong things today.

I wanted to show that Beth[1] ∉ P(P(ω)).

Leaky Nun

well

elements in P(P(ω)) are subsets of subsets of ω

user21820

8:35 AM

Yea. So it's not obvious.

Leaky Nun

ah

it's hard because actually R can be embedded in P(P(ω))

order-embedded

user21820

Yes. That's why set theorists say that Z is sufficient for practically all practical mathematics.

Because V[ω+ω] has not only reals but functions on reals and so on.

It just doesn't have uncountable well-orderings.

Leaky Nun

right

user21820

@Boots: Anyway we're now talking about set theory, which technically has nothing to do with logic per se.

It's just a historical fact that modern mathematics has chosen ZFC set theory as foundational, so there we are.

@Boots: If you want a concise motivation and explanation of ordinals and cardinals in ZFC, you can see here:

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...

Set theory is orthogonal to logic, but it frequently comes up in discussion because logic is of course applied to the conventional foundational system.

@LeakyNun So anyway my earlier argument using Asaf's was obviously wrong too. Too few powersets.

Leaky Nun

let beth_1 be a subset of subsets of ω

i.e. every element of beth_1 is a subset of ω

ω+2 is an element of beth_1

ω+2 is a subset of ω

user21820

8:43 AM

I see where it's going.

Lol.

So simple. It applies to any uncountable ordinal, I think.

Generalized it should give the proof of Asaf's claim.

Leaky Nun

it applies even to countable ordinals

user21820

ω+ω itself, yea.

I'm not sure why I forgot this; just a few months ago I knew it very well. In particular you've now reminded me that (I think) V[ω[1]] is the first stage that has ω[1] as a member.

Leaky Nun

I can believe that :P

ah, so V[a] is the first stage that has a as a member

> a as a

user21820

No V[k+1] is the first stage that has k as a member.

I think.

By transfinite induction.

Leaky Nun

look at what you just said

and what you just just said

user21820

8:49 AM

My first claim is wrong.

V[ω[1]+1] is the first stage that has ω[1] as a member.

Leaky Nun

fair enough

proof by transfinite induction

user21820

You're not asking me to prove it right?

Leaky Nun

no

I didn't say "prove by transfinite induction"

I said "proof"

user21820

Actually something sounds odd about my claim.

Leaky Nun

what does?

ah, because sup { n+1 | n < ω } only takes you to ω

user21820

8:52 AM

Do you have a counter-example? I only have a vague intuition issue.

Leaky Nun

doesn't V[ω] contain ω?

ah, no it doesn't

user21820

Haha you're falling for the same illusion as I did.

that's

Not as a member. =)

well

8:53 AM

I reconcile my intuition. The intuitive claim is that k ⊆ V[k] for every ordinal k.

Leaky Nun

aha

user21820

That should be correct, provable by transfinite induction, and implying the original claim.

Leaky Nun

that works

user21820

Oh it doesn't prove the minimal part of my claim.

Hmm...

Leaky Nun

well proof by transfinite induction :P

user21820

8:55 AM

I guess that works. But I'm too lazy to do it properly, and I think you didn't do it either.

Leaky Nun

fair enough

user21820

Like if there is a counter-example k there is a minimal one and then...

Leaky Nun

I mean

the claim is n<k -> k not subset V[n]

proof by xfi on k

user21820

Interesting way to put it.

Leaky Nun

I thought that's how you write minimality

user21820

8:58 AM

I would have written k ≤ n ⇔ k ⊆ V[n].

Which of course, gives the same thing.

I just didn't think in terms of minimality.

Leaky Nun

hmm

isn't mine just the contrapositive of your reversed direction

user21820

It is. That's why I said "interesting".

I automatically wanted elegance, so I had to reverse yours to grasp it.

Leaky Nun

lol

user21820

Anyway did you see my recent 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...

I'm wondering whether I should be asking on MO instead, since a lot of my questions are just going unanswered.

Leaky Nun

hmm

user21820

9:10 AM

@LeakyNun: Aha here is one that you may be able to answer. If you find a nice solution, I'll accept it!

5

Q: Can 2 Rubik's cube faces generate a corner 3-cycle?

If you turn only two adjacent faces of the Rubik's cube, is it possible to reach a state where only three corner pieces are out of place (and all other pieces are in the original places)? This was a question I thought of many years ago. At that time I was able to prove it by writing a comput...

group-theory permutations puzzle alternative-proof rubiks-cube

Leaky Nun

hmm

Asaf Karagila

9:57 AM

For chrissakes. Ordinals are not the only well-ordered sets. In V[\omega+\omega] there are plenty uncountable well-ordered sets. Just not every well-ordered set is isomorphic to a von Neumann ordinal.

The \beth notation, usually taken in ZFC, denotes ordinals, so P(\omega) or any V[\alpha] is hardly ever a cardinal.

Using the \aleph indicates cardinals, so 2^\aleph[0] is always cardinal exponentiation. If you want ordinal arithmetic, use the ordinal notation of \omega[\alpha].

Finally, the reals can be order embedded into P(\omega), you don't need to go to the second power set.

user21820

@AsafKaragila Well of course. I meant von Neumann ordinal when I said "ordinal".

Asaf Karagila

@user21820 Yes, I know. I just wanted to make that explicit.

user21820

Anyway, hello and welcome to this room.

I think this is the first time you've been in here. =)

Asaf Karagila

And also goodbye forever.

user21820

Why?

@AsafKaragila What is this about??

user21820

10:26 AM

@bat_of_doom: Hello! What brings you here? Any inquiry about (mathematical) logic is welcome.

user21820

10:42 AM

@JohnMa: Hello!

user21820

12:08 PM

@LeakyNun: This is so weird. Anyway did you know you can rotate and scale the 'hat' that you've got, so that it fits nicely on your shirt?

Secret

Asaf never came to chat for such a long time. I wonder what brought him here...

user21820

@Secret I have no idea what is going on. This month is a weird one.

Secret

and then, there's also this interesting thing of many minecraft servers and old project I used to been to suddenly all coming back to live while they should have been history

Let me just check what's on the recent news... lol

hmm... nothing very out of the ordinary. Guess its just community stuff

bat_of_doom

@user21820 Hi. I am really interested in mathematical logic, but my institute doesn't offer a course on it. So, I was just looking for posts which I can understand. Browsing this chat, I did come across a proof of godel's incompleteness theorem using unsolvability of halting problem, which I find quite interesting.

user21820

12:24 PM

@bat_of_doom Yes please feel free to ask anything about it. If you have programming background, you should be able to more or less understand the first half, which is enough to reach a complete proof of the generalized (first) incompleteness theorem.

And if you want a standard reference text and don't mind high information density, then Rautenberg is the book for you (linked from the other pinned post about good introductory texts). You can browse through the other books to see what you like. Also you can look at other stuff linked from my profile some of which are related to logic.

Either way, if you don't understand something, you can ask here.

bat_of_doom

Thanks. I will look in your posts. Are you sure they do not require any prerequisite in logic?

user21820

@bat_of_doom They are written at widely varying levels. What mathematical background do you have?

bat_of_doom

I am an undergraduate in BTech, mathematics and computing. I am currently in my third year.

I have done courses in basic abstract algebra, linear algebra, analysis, number theory and combinatorics.

user21820

That's great. Your computing background should make my post about the incompleteness theorems easy to understand, at least the first half. For the second half, it does require basic knowledge of first-order logic, including a deductive system for it and basic facts such as compactness and semantic completeness.

bat_of_doom

I have studied a bit of first order logic in a discrete mathematics course. However, I am not familiar with compactness and semantic completeness.

user21820

12:35 PM

Semantic-completeness of first-order logic means that every sentence that is true in all models (of the axioms) is provable (from the axioms).

This is the converse to soundness of first-order logic, which means that every sentence that is provable is true in all models.

Compactness of first-order logic means that, for every set S of first-order formulae, if every finite subset of S has a model then S itself has a model.

bat_of_doom

What is a model?

user21820

Basically it is a domain plus an interpretation of the symbols in the language that makes all the axioms true.

But of course I'm omitting all the details. Perhaps you could take a look at Hannes' notes linked from my post.

It should cover the basics of first-order logic quite well.

Chapter 3 defines semantics. But if you find it too dense, I could explain it to you myself.

@bat_of_doom: Actually just recently I was teaching two others here. We've so far covered a Fitch-style deductive system for propositional logic, as well as the semantic-completeness theorem for that system.

If you're interested in reading transcripts, I could point you to them.

bat_of_doom

12:51 PM

Please do point me to them, I will have a look at them later.

user21820

@bat_of_doom: Okay I covered basically the rules for propositions that I gave here (you can find it under Natural Deduction from my profile):

4

A: Predicate logic: How do you self-check the logical structure of your own arguments?

Truth tables are not enough to capture first-order logic (with quantifiers), so we use inference rules instead. Each inference rule is chosen to be sound, meaning that if you start with true statements and use the rule you will deduce only true statements. We say that these rules are truth-preser...

I presented it slightly differently, but it's basically the same. One of them didn't like the idea of having "false" be a valid sentence. So I modified the rules slightly giving:

This silly chat somehow does not quote long messages properly.

1. Repeat:
| A
|---------
| A
2. If-Sub
|
|---------
| If A:
|      A.
3. If-Repeat
| A
| If B:
|---------
|     A.
4. Implies-Intro
| if A:
|     B.
|----------
| A => B.
5. Implies-Elim
| A.
| A => B.
|-----------
| B.
6. And-Intro
| A.
| B.
|-------
| A and B.
7. And-Elim
| A and B.
|---------
| A.
| B.
8. Or-Intro
| A.
|---------
| A or B.
| B or A.
9. Or-Elim
| A or B.
| If A:
|     C.
| If B:
|     C.
|---------
| C.
10. Not-Elim
| not not A.
|------------
| A.
11. Not-Intro
| If A:
|     B.

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic