Logic - 2018-11-24

user21820

07:24

Does anyone have a completely discrete proof of the combinatorial claim in the following video?

in This is the Realm of Simply Beautiful Art, Nov 18 at 14:36, by Feeds

Sneaky Topology

►

user131753

13:34

The following question is more suitable for the users of this room and so I am asking this here. If anyone thinks otherwise then please let me know.

user131753

Let $U$ and $V$ be two formulas (of First Order Predicate Calculus). Let $P_U$ be a formula in which $U$ occurs as a subformula. Let $P_V$ denote the result of replacing some occurrences of $U$ by $V$. Let every variable that is free in $U$ or $V$ and bound in $P_U$ be in the list $v_1,\ldots,v_k$. Then, $$\vdash\forall
v_1\ldots\forall v_k(U\leftrightarrow V)\to(P_U\leftrightarrow P_V)$$

user21820

Feb 26 at 15:46, by user21820

@user170039 No, until you agree to stop supporting cranks.

user131753

@user21820 I didn't ask you to answer this question. If you don't want to answer, then don't.

user131753

Anyway, my question wasn't finished.

user21820

Stop pinging me. You insisted that I stop pinging you, but you continue to ping me.

user131753

13:44

So, my question is: What is the reason (or reasons) for including, "Let every variable that is free in $U$ or $V$ and bound in $P_U$ be in the list $v_1,…,v_k$.." in the statement of the result? What happens if we violate the condition?

user21820

math.meta.stackexchange.com/questions/27744/…

user131753

More specifically, what will be the problem in the following "result"?

user131753

Let $U$ and $V$ be two formulas (of First Order Predicate Calculus). Let $P_U$ be a formula in which $U$ occurs as a subformula. Let $P_V$ denote the result of replacing some occurrences of $U$ by $V$. Then for any variable $v$ we have,
$$⊢∀v(U↔V)→(P_U↔P_V)$$

user21820

George Chen posts the following:

All formalists seem to have acquired the amazing ability to pack a great many errors in a very short sentence; some can appear intellectual just by speaking nonsense. — George Chen Aug 23 '17 at 1:41

Also his profile leads to his blog that includes posts such as this (cached here). Note the last three paragraphs in that blog post.

Note that in a deleted comment on the above Meta thread, GC even said "@ProfessorVector - He who had the heart to erase someone's posts would have no scruple to burn him at the stake. It is wise to imitate early Christians and go underground. Do not respond to the dare." (Jan 18 at 22:23).

user21820

14:22

Note also that GC said in 2018:

> @user170039 - I'm thinking about creating a Church of Bertrand Russell where freedom of speech is absolute. The minimum requirement is that everyone must show his true identity. In 2017, it is dangerous to believe that one still has privacy. – George Chen Jan 6 at 17:19

But his blog post about exactly that was in 2013.

Furthermore he wrote:

> Once you read PM, you naturally feel an urge to rewrite a lot of textbooks. It is a daunting task. We need a legion of hardcore Russellians. – George Chen Jan 8 at 1:14

Leyla Alkan

17:21

Hey guys!

Can you please check my solutions @Holo @MaliceVidrine? or other people if they're interested?

I think the way I show (a) is false

user21820

@LeylaAlkan Hello! Next time please don't post too many picture URLs, as they take up a lot of unnecessary space. For reference, your workings are here: part 1, part 2, part 3.

→ 3 messages moved to Sandbox

@LeylaAlkan Yes your attempt for (a) is wrong. You want "true under every interpretation", not just the one you tried.

Leyla Alkan

So, how to show it properly then?

user21820

@LeylaAlkan Either by definition of the semantics of your sentence in question, or by literally proving it syntactically (using the deductive system you are given). Neither is hard.

Leyla Alkan

17:37

But the question tells us find appropriate interpretations

Question:

user21820

@LeylaAlkan The question is not accurate.

To prove that every interpretation satisfies some sentence, you cannot possibly find "appropriate interpretations" to do so, but must reason about every arbitrary interpretation.

Only if you want to prove that some interpretation does not satisfy some sentence, then you can do so by constructing one such interpretation.

Leyla Alkan

Yes, but I tried to show that the negation of the sentence is not logically valid, hence the sentence is logically valid.

user21820

@LeylaAlkan Tell me, is "forall x,y ( x=y )" logically valid? What about "not forall x,y ( x=y )"?

Leyla Alkan

I think I misinterpreted "logically valid sentences is that their negations are inconsistent" as "logically valid sentences is that their negations are not logically valid"

user21820

Yup.

Perhaps you should look back to propositional logic first. Is "P" logically valid? Is "not P" logically valid? You can see that even if "not P" is logically invalid, it does not imply that "P" is logically valid.

It can be (as here) that both a proposition and its negation are logically invalid. Same for first-order sentences. So you can't prove logical validity from logical invalidity of the negation.

So you need to perform actual quantifier reasoning. I will give you an outline and your homework is to fill it in.

Leyla Alkan

17:56

Okay, that would be helpful

user21820

Given any structure M with domain S that interprets binary relation R:
	If exists y in S ( forall x in S ( R(x,y) iff not R(x,x) ) ):
		Let c in S such that forall x in S ( R(x,c) iff not R(x,x) ).
		Then ...
		Contradiction.
	Therefore not exists y in S ( forall x in S ( R(x,y) iff not R(x,x) ) ).
	Thus M satisfies ( not exists y ( forall x ( R(x,y) iff not R(x,x) ) ) ).
Therefore ( not exists y ( forall x ( R(x,y) iff not R(x,x) ) ) ) is logically valid.

This is called a Fitch-style proof, and I advise you to use it until you can reason like this mentally. The core idea is simply that the indentation shows what each header governs, and the headers governing any particular line specifies the context of that line, and every sentence written is true in its context.

To fill it in, copy-paste to your favourite text-editor, fill in the gap, then copy-paste back here then press "fixed font" then "send". I have to go and will check it tomorrow if MaliceVidrine hasn't already done so.

Actually I should be more precise:

Given any structure M with domain S with binary relation R on S:
	If exists y in S ( forall x in S ( R(x,y) iff not R(x,x) ) ):
		Let c in S such that forall x in S ( R(x,c) iff not R(x,x) ).
		Then ...
		Contradiction.
	Therefore not exists y in S ( forall x in S ( R(x,y) iff not R(x,x) ) ).
	Thus M satisfies ( not exists y ( forall x ( R(x,y) iff not R(x,x) ) ) ).
Therefore ( not exists y ( forall x ( R(x,y) iff not R(x,x) ) ) ) is a logically valid
first-order sentence over the language with a binary-predicate symbol R.

Leyla Alkan

Oh, okay, thanks a lot. I understood it but I am not sure in the exam we are allowed to use this method

user21820

18:13

@LeylaAlkan Well, any real mathematician has no trouble understanding that format. When I was a student I answered all my exams that way. But you're free to rearrange the proof into a paragraph format in your exam. Here though, I expect beginner students in logic to use this format as it will make it much easier for both them and me to pinpoint errors.

Holo

21:37

@user21820 I have unexpected problem with AutoHotKey... I have hot string \in for ∈ and \int for ∫, so I can't use ∫!(I know I can make it to work only after I press space or so but this will be too much of a bother!)

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic