Logic - 2016-08-17 (page 2 of 3)

toto

2:00 PM

I want know to define A' like :
A' := {a1, a2, a3, a4}

therefore A is a subpart of A'

and now i want to make a function f' from f which is defined on A' to B

and i want forall x in A, f(x)=f'(x)

how can i construct f' from f ?

i though i just have to do f' = f union {(a4, y)} where y is an element of B

can i ?

user21820

A' = A union {a4} = Union {A,{a4,a4}}, which is given by the axiom of pairing and union.

Yes f' = f union {(a4,y)} similarly, but you've to prove it is a function.

Otherwise you won't get what you want (function f' that extends f)

toto

ok, so proving it is a function is about proving that each first element of each ordered pair appears only once, and every element of the domain maps to a range element right ?

user21820

Ok I need to go now for a while.

Right.

toto

okay, and so, what i've done f' = f union {(a4, y)}, is what you call a proof by construction isn't it ?

and f is the restriction of f', but i have to prove it by induction

user21820

Yes absolutely right.

toto

2:07 PM

Well okay, no prob, thanks for the help

Yes, okay, i can see though that more clearly

the fact is that every time you create something

every time you change something in a set

you must prove that the properties of it still holds

user21820

Right. See you in about 30min. In the meantime, here's the rest of the outline of the recursion theorem proof.

Given set E and function g : E->E and c from E:
| [Steps 1,2,3,4]
Step 1 proves
forall k in N ( exists h : {0..k}->E ( h(0) = c and forall n in N[<k] ( h(n+1) = g(h(n)) ) ) )
Step 2 proves
forall k in N ( forall h,h' : {0..k}->E ( h(0) = c and forall n in N[<k] ( h(n+1) = g(h(n)) ) ) and ( h'(0) = c and forall n in N[<k] ( h'(n+1) = g(h'(n)) ) ) implies h = h' )
Step 3 first does
foreach k in N let H[k] : {0..k}->E such that ( H[k](0) = c and forall n in N[<k] ( H[k](n+1) = g(H[k](n)) ) ) )
by lots of set-theoretic machinery and then proves

toto

okay thanks !

user21820

2:58 PM

@toto: So, how's it?

toto

Well, tried to write on a piece of paper my proof

and i've one problem

we've a conjunction

user21820

which step?

toto

P(0) : "f(0)=a ^ f(n+1)=g(f(n)) , forall n in N<0

the initialisation

user21820

oh it works

the "forall" part is vacuously true

because there isn't any n in N[<0]

toto

i don't understand how f(n+1)=g(f(n))

when there is no elements to check with

N<0 is empty

user21820

3:02 PM

Yes that's the point. Remember the game semantics? As the Refuter I would have to start first and give you some n in N[<0]. I can't, so you win.

toto

hum

i see

but that's quite weird

i wrote on my paper

user21820

The proof goes:
Given n in N[<0]:
| n < 0.
| Contradiction.
| f(n+1) = g(f(n)). [Explosion!]

toto

(A != empty)->[forall n in N, f(n+1)=g(f(n))]

user21820

What's A?

toto

a set

so if A is empty, A != empty is false

and so the implication is true

well no, i'm speaking shit

user21820

3:04 PM

Yea you're going in circles.

Just follow the above proof. There's no need to split cases.

toto

nevermind, i though i understand it, but no

you say that, if there's a n < 0 and n is in N

user21820

Then contradiction.

toto

we now by defintion that every n in N is >= 0

user21820

Right.

toto

so n < 0 ^ n >= 0

so contradition, so by absurdum

n < 0 is false

the n >= 0, right ?

user21820

3:07 PM

No need to do that. Once you get contradiction the principle of explosion lets you deduce anything.

toto

you mean that we use the principle of explosion to prove f(n+1)=f(g(n)) ?

user21820

Yes. Is your question is about why the principle of explosion is true?

toto

yes

user21820

I got just the answer for you. See math.stackexchange.com/a/1668149/21820 =)

If you still don't believe the semantic explanation, note that you can get it syntactically via proof by contradiction:
If Contradiction:
| If not P:
| | Contradiction.
| Therefore P.
where you can think of "Contradiction" as any false sentence like "0=1".

toto

i don't get exactly what means explosion

it's the fact that something is true and false the same time

like P ^ not(P)

but, how does it implies that from (P ^ not(P)) i can say that any other thing will be true ?

user21820

3:19 PM

Because we can drag the contradiction in, as in the above proof.

The semantic explanation is simply that "False implies P" regardless of P

because that's precisely how we defined "implies" in logic.

The syntactic explanation is the proof I just gave. If you doubt any specific step you should point it out.

toto

ah i see

user21820

Got both explanations now?

toto

since "False => A"

will be true

then we know that a contradiction is always false

user21820

Yes. I should have used "false" instead of "contradiction" since you're a programmer.

toto

so (P ^ not(P))=> A

will always be true

user21820

3:21 PM

Right.

toto

but, that does not mean that A is false

user21820

Yes.

toto

only that the implies is true

well, that's.... weird

user21820

So, can now?

toto

but one more thing

during the initialisation

we're trying to prove P(0)

user21820

3:24 PM

Yes and we did. Is the proof weird to you too?

toto

so prove that there exists f such that f(0)=a ^ f(n+1)=g(f(n)) forall n in N<0

and so you have to give me a n that is less than 0 but a natural number

user21820

Yes I can't so I lose.

toto

we saw it is a contradiction, so it is always false

but here's the question

should i see it like

((A = {n in N | n < 0}) ^ A != empty set) => (there exist f such that f(0)=0 and f(n+1)=g(f(n)) foreach n in A)

user21820

Why?

You don't need the "!= empty set" part.

toto

cause if A is empty, (A = {n in N | n < 0}) ^ A != empty set) become false

and so

((A = {n in N | n < 0}) ^ A != empty set) => (there exist f such that f(0)=0 and f(n+1)=g(f(n)) foreach n in A)

become true

user21820

3:29 PM

but I don't see the need to distinguish the cases.

As said earlier, "forall n in A ( ... )" is true if A is empty.

toto

yes, but i was just looking for why

you called that vaccum truth

user21820

So you're not convinced by the proof I gave?

*vacuous truth.

Let's go back to the game semantics. We take turns to give each other objects according to the quantifiers. We also have some "justification" steps we need to perform. When you claim "A implies B" the game proceeds with Refuter justifying A and then Prover justifying B. If any one fails at any point then the other player wins.

toto

yes i see

i understand it

but, why do it works this way ?

user21820

Exactly the same with quantifiers

It's the way we defined them.

toto

why, if you can't give me an example, my predicate is true

user21820

3:33 PM

Because that's what it means to say "forall".

For any car C that belongs to me, C is transparent.

Unfortunately, I don't own any car.

So my statement is true.

toto

so, in the world of logic, that true to say, forall monkey with 48 head, monkeys have 52 tails ?

user21820

Yup

Anything wrong with that? =D

After all, we have to choose a precise meaning for quantifiers, and we chose this one.

toto

that's weird, because you can say false things about something that is obviously false

user21820

Do you dispute the truth of my statement about cars?

If you find the monkey one weird, you'd also have to dispute the car one to be consistent in your objection.

toto

well, what i find weird

i that, we know that every element in the car set

is not transparent

user21820

3:36 PM

(By the way the first ancient book in my reference list by Suppes literally goes into all this kind of philosophical detail, which is partly why I recommend it.)

toto

and you say that you have a car that is transparent

so, since you don't have a car, we can't prove that you car can't be transparent, so no way to say that you're telling something false

user21820

Yes. If you think my statement is not a good English statement, then you'll just have to accept that in logic it means something more like "For any car C that you can verify belongs to me, C is transparent."

toto

so, the idea is to that

to say that*

if you can't prove that something is false

therfore we accept it to be true ?

user21820

Nope. That's false actually.

Think about the claim again.

toto

yes, but i understood the way that

user21820

3:39 PM

It doesn't say that inability to disprove implies true

toto

every car you have is transparent

but you haven't any car

so you're talking about a property on an empty set

user21820

Yes.

toto

but i can't find an element of this set

user21820

In particular note that "C is transparent" is a meaningful statement only when C is an object.

toto

to prove, that's false

user21820

3:41 PM

So if you can't even get past the "car C that belongs to me", you can't even ask the question of "Is C transparent?"

Don't get confused between the statement under the quantifier and the whole quantified statement.

The whole quantified statement is true.

Vacuously.

toto

yes, but i don't get the underlying idea

is it true because we can't prove that is false

or do we just say that is true because that is a convention on an empty set ? like an axiom

user21820

It's not like that. Under mild conditions, not everything can be proven or disproven. (It's a deep result of logic.)

toto

Cause when you're saying, i can't give you an element that fits the requirements or N<0, therefore i loose

user21820

What we're talking about is the meaning we assign to the quantified statement.

toto

isn't it the same way of thinking that saying, since i can't find any example, i'll never prove that what you're saying is false, therefore we can say that's true

user21820

3:44 PM

Nope. Let's see why.

When I claim that "forall x in S ( P(x) )" is true because S is empty, it's not that you can't find any example, but rather that I can verify that you can't find any example.

This means that when you play the game and try to cheat by giving me some x that you claim is in S, I would be able to systematically disprove you.

toto

i see. But by telling such things

in my book they were saying

forall x in A, P(x)

where A = {a, b, c}

is the same as

P(a)^P(b)^P(c)

user21820

Yes remember I said it's true for finite A.

It breaks down completely for infinite A.

toto

but, if A is empty

you can't write anything, or

user21820

It's the empty conjunction.

The empty conjunction is true.

toto

why ?

user21820

3:48 PM

Heheh.

Another rabbit hole.

A large one.

Why is the empty product equal to 1?

toto

That's like every conjunction A^B is equivalent to A^B^true since true is the neutral element of conjunction ?

user21820

That's nearly it.

toto

what is the empty product ?

user21820

n! = 1*2*3*...*n.

0! = ?

toto

1

user21820

3:50 PM

x^n = xx...*x [n times]

factorial

x^0 = ?

1

0^0?

undetermined

3:51 PM

=D =D =D

WRONG

1

hu, sure ?

Of course.

okay

I'm not joking.

e^x = sum { x^n/n! : n from 1 to inf }

that's x^0/0! + x^1/1! + ...

toto

okay

user21820

3:52 PM

e^0 = ?

toto

1

user21820

Anyway there's a proper reason we choose this way.

It's related to being the neutral element

toto

really ?

user21820

but do you know why?

toto

no

hu well

maybe i know

user21820

3:53 PM

You're a programmer, it should make sense to you after a while.

toto

for the power

user21820

Tell me.

toto

x^0

is equivalent to x^0*x^-1

no

x^1*x^-1

it's equivalent to

user21820

that's only after you have that property

and it doesn't work for x = -2

toto

x^1*1/x

x*1/x = x/x = 1

user21820

3:55 PM

sorry what am i talking about

doesn't work for x = 0

toto

right

user21820

and doesn't work for say A^0 where A is a non-invertible matrix.

toto

well, i don't know

user21820

How do you define x^n rigorously.

for natural number n and real x.

toto

x^0 = 1
x^(n+1) = x*(x^n)

user21820

3:56 PM

recursive definition right?

toto

yes

user21820

see the base case must be that for it to work

and it makes sense too.. If you have a test with n true/false questions on it, how many possible answer scripts can you hand up if you answer all?

(and your answer for each question is either "true" or "false" and ignores handwriting)

toto

2^n

user21820

If the test has no questions on it, how many scripts can you hand in?

toto

2^0

1

user21820

3:59 PM

see what i mean?

toto

wtf

well, yeah, but, that's weird

user21820

Nice test?

Same with the empty conjunction.. Think of each conjunct as adding a constraint

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic