Name: Propositions as Types - Computerphile
Uploaded: 2020-03-27T17:43:49.000Z
Duration: 17 min 46 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Transition words & phrases

so I wanted to talk about propositions as types because it was something which sort off came out.

When I talked about type theory, I thought some people asked about this and I thought, It's a good bit more to go a bit more to detail.

The nature you could say the relation between proofs and propositions, A straight cop for short is the same, in some sense, as programs.

Basically commission, which I would like to explain.

So first of all, let me explain a little bit by proposition.

Many prime numbers are this program swords, numbers, stuff like this.

I sometimes use examples from the view bird like trains.

Today we go to the zoo or something like this.

But really, it's not about the propositions I'm interested in here are not like everyday propositions, but they're so precise.

Statements about programs are mathematical objects or whatever.

Pool warrant, ages but I'm going to use maybe some more primitive types, which maybe not s as coming.

Uh, it's a proof want survey to justify a proposition, I'd and what's the problem?

I should be watching computer file if you know what this is.

The thing about about logic and reasoning.

So traditionally there's another creation I would liketo I don't This is the idea that top equals booth.

This idea is very widespread on mathematics.

It's related to what we call classical logic.

And initially, if you first learn a bit of a logical looks quite well, there's these operations we like and conjunction or disjunction implication navigation.

We can explain them as operations on Duel, and maybe you've seen these tooth tables which defying all this operations.

But then you learn about predicated logic.

So Critical Lodging has some other symbols, like this one, which means for all and this one which means exist.

So, for example, we can work something like for all natural numbers for all ex in N.

So something holds for financial numbers you know nothing.

F off x the F It's a function which assigns to every national number two civilians.

That's a predicated for every natural number.

Now, if I want to define the meaning of this statement, I have to compute a 1,000,000,000 this bullion it's okay to if this function returns to for every input.

But I don't know how to pull them such a function because I have to check infinitely many inputs to say that I can't return to what it has to be to everywhere, a kind of guy to pull them.

I mean, I can't start tying f zero f one f or two and if it's always to it if it ever falls, because it must be for you.

But if it stays too, I never know when to return to.

To me, that means that this idea of Popsicles school doesn't really work for me.

As a computer scientist, maybe may say OK and mathematics, that's okay, but I like to use a deal's from computer science toe, explain mathematics and here let me turn over.

Instead of trying to explain minutes tool, which is tricky, it may explain what it's evidence for this proposition.

I say a proposition and then explain what sort off, except as evidence evidence to accept this proposition and the evidence of a proposition.

So the idea is we assigned to every proposition a type off its proofs or evidence.

And whenever you find can deliver an element off this type, you have very fine this proposition, so it's really, really a fundamental, different point of view to logic.

Instead of talking about tooth, we talk about evidence and the proposition as types.

Translation translates propositions as types is a heartless is work.

I want just to tell you what a proof, a simple proposition and proposition a logic.

I want to prove what's called a tautology, p and Q or our implies P and Q or peace sent.

I find obviously useful to think off complete association so that C P means it rains today.

Is we go to the zoo and are we have chicken for dinner.

So I say, Okay, it rains and we go to the zoo where we have chicken.

Then either it drains and we go to the zoo over it rains and we have chicken for dinner.

This implication hasn't got anything to do this to concrete instance, she ations off P Q and R.

If ever replace it with something else, it would still remain to.

So it doesn't tell you anything about whether it rains.

It is what's called a tautology, which means it's, too for any peak.

Okay, so everyone to check that this is a tautology and we use the previous idea.

We have just took a ball to stable and shake.

That's two everywhere, but I won't know to use this proposition.

Is types principle to explain viruses a tautology?

What I'm going to do is I'm going to consummate this into a type and the town station.

I have to give a translation for every operation here for every logical operation for the end of the hall for authentication.

So what's end What is evidence for P and Q evidence for P and Q is a pair off evidence for P and evidence or Q and the D notice as the product?

So this is what mathematics called cottage in Poland or product off types.

And the basic rule is if you have an element X off P and an element of eye off, you can put them together like two pools.

All right, That's element off P times killed.

That's the product was quite widely used, so we translate conjunction.

That's the product, because evidence would pee in, few disappear off evidence would be and evidence work.

You know, the next thing is P or kick you out of it.

There's another operation, which is less familiar in mathematics.

It's wouldn't plus, it's a son, and this coast wants to either.

We have an element of Cuba, but we're labeling which one of this so it's not.

Subtitles ListPlay Video

Propositions as Types - Computerphile

sort

evidence

convince

express