Logic - 2017-10-26

shredalert

08:36

@user21820 hello.

user21820

@shredalert: Hi!

shredalert

@user21820 busy day today?

user21820

Actually no. Yesterday was my busy day. But I'm always busy doing something. =)

shredalert

Same here

I came across a pretty nice description of structural induction from a set of online lecture notes.

user21820

Link? =)

shredalert

08:40

@user21820 math.la.asu.edu/~boerner/mat243/…

@user21820 page 6.

I like the population and inheritance metaphor used

user21820

Ah okay that generative viewpoint is great for CS students.

But note that the generative viewpoint doesn't work well when the recursion goes beyond ω, though such situations don't quite come up in practical CS.

shredalert

Another one I liked was from a discrete math book I own. It goes along the same lines as the dominoes methaphor for regular induction, but with an added bit that we can imagine the dominoes 'branching off in different lines' and then proving that each of those lines keep falling.

user21820

Yes that works too.

But you need it in reverse.

Namely all incoming dominoes must fall to push the next one over.

shredalert

ah, yes.

That's the case when using structural induction on trees, isn't it?

because if we want to prove something it has to be shown that it holds all the way down to the roots?

user21820

It can be said to be always the case. Structural induction always goes from the smaller to the bigger, and the bigger is recursively defined in terms of possibly more than one smaller thing.

From the top-down viewpoint, it's always many small to one big.

Of course, from the bottom-up viewpoint a small object may participate in generating multiple big ones, but it's better to avoid in pedagogy as you have to be concerned about 'waiting'.

shredalert

08:50

I found an old book on amazon called Induction, Recursion, and Programming by Mitchell Wand. Got it for basically cheaper than a sandwich. Hoping it has some good examples and explanations in it.

user21820

Lol!

shredalert

I do that quite often. Get really cheap old books. They tend to not be watered down like most books today.

user21820

@shredalert: If you want interesting and not too easy induction problems... Help yourself to the following. =)

6

A: Can someone give me an example of a challenging proof by induction?

Elementary number theory $ \def\nn{\mathbb{N}} $Take any $x,y \in \nn$. We say that $d$ is a gcd of $x,y$ iff $d \in \nn$ and $d \mid x,y$ and $k \mid d$ for any $k \mid x,y$. Define $\gcd(x,y)$ recursively as $\cases{ x & if $y = 0$ \\ \gcd(y,x) & if $x<y$ \\ \gcd(x-y,y) & if $x \g...

3

A: Good, simple examples of induction?

Prove that the greedy algorithm for the change-making problem with Fibonacci denominations produces an optimal solution (uses the minimum number of coins possible). This problem is not as easy as it looks. Note that there may be more than one optimal solution. It would also be instructive to try...

8

A: Good, simple examples of induction?

Base problem Some positive integers are written on the board. At each step one of the integers $n$ is erased and replaced with any number of positive integers that are all less than $n$. Of course, if the erased integer is $1$ then no new positive integers can be written on the board. Prove that...

That thread has a ton of other examples you can try too.

shredalert

@user21820 many thanks!

relations, predicates, induction, and recursion are by far my favourite topics of study

user21820

@shredalert Yeap induction/recursion is very interesting. It is in fact very intriguing that we can prove a lot using just induction on the naturals, as long as we can reason about higher-order objects. There is an interesting fact that PA cannot prove its own consistency but ACA (which is essentially predicative 2nd-order PA) can, and this crucially relies on the full induction schema in ACA. ACA0, which only has an induction axiom, has the same strength as PA.

ACA0's induction: ∀set S ( 0∈S ∧ ∀n ( n∈S ⇒ n+1∈S ) ⇒ ∀n ( n∈S ) ).

ACA's induction schema: P(0) ∧ ∀n ( P(n) ⇒ P(n+1) ) ⇒ ∀n ( P(n) ).

Where the schema is applied to every 1-natural-parameter sentence P.

shredalert

09:13

I've been trying to translate the structural induction definition into predicate logic.

I'll type up my attempt.

user21820

Sure.

shredalert

$B$ is the base set of our recursively defined set $S$, and P(x) is the property we want to prove. Let $f_k$ be the functions that generate new elements of $S$.

$(\forall x(x\in B\Rightarrow P(x))\wedge(\forall x\forall f_k(x\in S\Rightarrow(P(x)\Rightarrow P(f_k(x)))))\Rightarrow \forall x(x\in S\Rightarrow P(x))$

user21820

09:42

@shredalert Something is wrong with this. As I said it's better to do a top-down approach. In your approach you can't handle any situation where each object breaks down into multiple smaller objects.

Which means you're not capturing structural induction at all.

shredalert

@user21820 wouldn't that breakdown be part of the proof of $P(x)\Rightarrow P(f_k(x))$?

user21820

Not at all.

shredalert

Could you give me a predicate definition along the lines of what you intend?

I haven't seen a predicate definition of structural induction anywhere, so I decided to give it a shot, and for the simple cases I looked at, it worked out

The definition above that is

user21820

Just for example, a full binary tree is made of two subtrees and a root, but you can't generate all the full binary trees by any single generating function.

If one naively does f = ( tree T ↦ [root,[T,T]] ), f applied iteratively to the base 1-node tree would only generate complete binary trees, not all full binary trees.

@shredalert Sure. But do you understand the above objection?

shredalert

That should be covered in the translation, I did mention $\forall f_k$

So either something is wrong in my translation or the article I linked earlier.

user21820

09:49

That doesn't work. Please think carefully about it.

Sorry I hadn't read the linked pdf properly. Yes it (page 6) is incorrect!

shredalert

It's okay. I want to clear my understanding of structural induction, so I am looking around for stuff. Are there any notes you could direct me to?

user21820

For now, if you want to be safe, I suggest you stick to the explanation in my post on structural induction, and take a look at the comments where I provided an example. I'm sorry I don't know of material that covers the same thing. However, I will still give you a version of structural induction in logical form.

shredalert

@user21820 much appreciated. Thank you.

user21820

It applies whenever you have a collection S and a function f : S → N, and a predicate P : S → bool. Then structural induction says: ∀x∈S ( ∀y∈S ( f(y)<f(x) ⇒ P(y) ) ⇒ P(x) ) ⇒ ∀x∈S ( P(x) ).

Note that the English in the linked post has two conditions only because it's confusing in English to rely on vacuous truth.

Otherwise condition (2) suffices. Namely, if you can show that ( given any object x in S, if every object in S of smaller size than x satisfies P, then x itself satisfies P ), then every object in S satisfies P. Size is captured above by f.

shredalert

Ah, yes. I think I get what you were stating now

So the subtrees are y with x being the main root

user21820

10:00

Incidentally, you can prove structural induction by using classical logic plus ordinary induction alone. I always recommend my students to try this haha..

@shredalert x is the big tree. Subtrees are captured by y, yes. It's not actually important how the breaking-down happens, but it's important that structural induction applies for arbitrary (even infinite) breaking down.

If you can't prove structural induction from ordinary induction, tell me and I'll give you a hint.

shredalert

@user21820 I'll give it a shot sometime.

brb

user21820

10:44

@Idonotknow: Sorry I forgot to ping you to let you know that I've pinned the link to the newest version of the write-up on the incompleteness theorems.

Idonotknow

11:22

@user21820 :(

user21820

@Idonotknow: Lol. I pinged everyone in the discussion, and couldn't remember everyone else who wanted it.

Idonotknow

:( @user21820

user21820

@Idonotknow: If you had dropped into this room while I was around, I would have remembered.

Anyway stop making sad faces and go read it first. =)

Idonotknow

@user21820 :( ..... hahaha No worries ...... you mean previous sunday at 1?

user21820

Oh that; I forgot to unpin that old announcement.

Eh if you make too many sad faces, as time goes to infinity your face will get stuck in a sad position. =S

Idonotknow

11:30

@user21820 hahaha .... I want make sad faces anymore ..... I was going to attend it but it was at the same time of my work

user21820

@Idonotknow I see. When (UTC) do you work?

Idonotknow

@user21820 could u please take votes for discussion time?

what do you mean by (UTC)?

user21820

google.com/search?q=current+time+in+UTC

Idonotknow

When will be the next discussion? @user21820

user21820

@Idonotknow It depends heavily on how many are interested and when they can make it. The last time I asked, I adjusted the time to cater to the first few who said they wanted to join. It's difficult to cater to all because everyone is in a different time zone.

@Idonotknow: But even if there is no discussion, feel free to ask any question on the write-up here in this room, and I'll respond.

Idonotknow

11:35

I work on Sunday , Saturday and Tuesday.....@user21820 .... so I prefer discussions not to be on that days

user21820

The only advantage of a group discussion is that there can be many questions and also questions wouldn't be repeated by the participants.

Idonotknow

yeah @user21820

user21820

@Idonotknow I see. The easiest days to have a group chat are the weekends because then most people don't have school/work and so can make it for a larger range of hours. So on sunday do you have time besides for sleep and work?

Idonotknow

Actually I did not study incompleteness theorems ....... so usually I read what the participants wrote silently(not always) ....... I want to learn incompleteness theorems from the beginning. @user21820

user21820

@Idonotknow That's fine. The only major prerequisite you need to read the first half of my post is basic programming knowledge and understanding of basic logic concepts such as a deductive system for first-order logic.

For the first there are ample Python tutorials online and an online compiler as well. For the second try Forallx linked from here.

Idonotknow

11:40

On Sunday you can make the discussion after 8 p.m (I am from Egypt). @user21820

user21820

@Idonotknow Oh 8pm Egypt time is in the middle of the night for me.

Idonotknow

@user21820 where is the first half of your post?

wow @user21820

user21820

@Idonotknow Do you see the pinned post (on the right)? That's the whole write-up.

Idonotknow

yes I can see it @user21820

great @user21820

user21820

The second half starts with the section "soundness versus consistency".

The first half already proves the incompleteness theorems. The second half is further in-depth discussion.

Idonotknow

11:43

Great @user21820

user21820

Let me know how you find it!

Idonotknow

Okay , I will read it and give you my feedback.

thanks you :)

user21820

@Idonotknow: You're welcome!

user21820

17:04

@amWhy In general such questions seem to point to a systematic failure of mathematical education in many parts of the world, where students are just taught to 'use laws' instead of being taught the precise conditions for certain properties to hold. The use of the term 'law' or 'rule' is also terrible.

amWhy

@user21820 indeed. I just cringe when the same kinds of "fake proofs" repeatedly reappear, (not necessarily the fault of the askers, but rather all the answerers who continue to say the same thing over and over again, and as though they are uniquely sharp or clever, or brillian, for having "solved the paradox". So, I'm not pressing for a campaign for deletion of the question. Just don't like folks earning a hundred or more rep for adding the same old, same old, answers.

user21820

Actually, I prefer to delete almost all such questions because majority of the answers have lousy pedagogy. Such as here, where the top-voted answer assumes an unstated branch cut. Worse still, even the general community on MathEducators SE disfavour a logically sound pedagogy.

@amWhy: For example, I wrote this long ago, and in my opinion 4 of the answers with higher score than mine are bad pedagogy. All questions involving fake proofs or paradoxes would be totally banished if students had even a rudimentary grasp of logic.

amWhy

@user21820 Well, I haven't read enough at MathEducators SE to conclude the same.

amWhy

17:28

@user21820 I do believe those with background in mathematics, cognition, and Undergraduate mathematics education can contribute to discussions wrt to "how students at this level or that level, cognitively are capable of understanding can be important in order to bridge the gap of where they are at, and how best (pedagogically) to do this.

Mathematicians, alone, (with no understanding in cognitive development, and often very little understanding of those who "don't get mathematics easily) are often clueless regarding the crucial sorts of questions and presentations and explanations along the way in order meet the students where they are at, currently, and challenge them, in lectures, exercises, explanations, in an effort to spring-board them into a more nuanced and mathematically mature understanding.

user21820

@amWhy This is definitely a discussion that ought to be had. If you like, we could move it to the Logic room or SBA's room and continue there. In my opinion, educators in general do not have a solid enough foundation in logic to grasp just how crucial it is to fully understanding mathematics, and even when they do they don't see the need to teach it properly, sometimes giving the excuse that it is too hard. Actually it's not at all hard; they just don't know how to do it.

amWhy

I think it's a balance, in terms of pedagogy: We need those very learned in mathematics, and we need those who devote their studies specifically to how users learn mathematics, the "blocks" and "hurdles" that are widely shared, and the methods to help them move beyond the hurdle/block... When we have each respecting the other, awesome learning can occur.

Of course, there a mathematicians with an intuitive and experienced pedagogy. And we have we have math educators who earn PhD's in mathematics, and also a master's degree in undergraduate mathematics education.

user21820

@amWhy Of course. It's just disappointing to see educators being unable to educate and yet telling others how to do it.

amWhy

Where ever you'd like to move this discussion, is fine by me. I'm not here to argue, but just as I think generalizations of stereotypical mathematicians are exaggerated, I think that the stereotypically-characterized educator is exaggerated as well.

user21820

17:44

← 12 messages moved from CRUDE

amWhy

:40788017 You've just made a stereotypical characterization of an educator. Some yes, all no.

user21820

@amWhy Yes I know what I'm saying sounds like a very harsh evaluation of the 'typical' math educator, but believe me I have tested lots of people who are teachers or will be teachers and they mostly fail to be able to do basic sound logical reasoning consistently.

When even professors at my university cannot understand correct logical proofs, but accept incorrect ones, it tells me enough.

← 1 message moved from CRUDE

And when I try to explain how to teach logic properly, most of them reject me just because that's not the way it's been typically done.

The posts on MathEducators SE give me the impression that this is a widespread problem, not just at my university.

amWhy

Well, I know that at the institution where I teach, undergraduate logic is a required course for secondary teachers certification in math. As is proof-methods, as is real-analysis and abstract math, and set theory, et al. Indeed, a those who want to teach math are held to the same course requirements as are pure and applied math students. And 80% of those who graduate with a math degree & teaching certificate, continue their studies in math to MS completion, 40 % of which then go on to PhD.

user21820

@amWhy Interesting. Not so where I am. Anyway I've to go, but we can continue this next time! See you! =)

amWhy

@user21820 Take care... Cya!

Espinoza

17:52

If I have a finite set of symbols A, and want to prove that the set of sentences is enumerable. I wanted to know what fails when applying a diagonal argument to try and prove that this set is not enumerable. Like this: " If I were to list the sentences of length n, couldn't I concoct a new sentence of length n+1 that isn't in the list." How does this fail to prove that this set is not enumerable?

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic