Logic - 2018-11-23

« first day (828 days earlier) ← previous day next day → last day (2284 days later) »

user21820

07:52

@LeakyNun Haha you want to make people here scratch heads, right? For others' reference, the conversation started in the main chat-room here and the solution is here and here.

Note that the computable reals encoded as Dedekind lower cuts does not seem to have computable addition or negation, whereas their encoding as Cauchy sequences has computable addition, negation and multiplication.

9 hours later…

Leyla Alkan

16:33

user image

Hi! If the formula is not true, then there's a seq $s$ in $\Sigma$ st $s$ satisfies $(\forall x_i)\mathscr{B}$ and $s$ doesn't satisfy $(\exists x_i)\mathscr{B}$ Here I want to ask if $(\exists x_i)\mathscr{B}$ and $\neg(\forall x_i)\neg\mathscr{B}$ are equivalent, since the lack of parantheses makes it hard to see this for me. Can someone tell me about the thought process here?

Holo

@LeylaAlkan Yes, $\lnot (\forall x)$ is $(\lnot (\forall x))$, and $(\exists x)R\equiv (\lnot (\forall x))\lnot R$(it my be a definition, or a theorem, depends on the convention)

Leyla Alkan

Oh, okay. Thanks

Leyla Alkan

16:50

Is it correct to say if a sequence $\vec a$ satisfies $(\forall x)( \varphi\rightarrow \psi)$ and $(\forall x)\varphi$, then it also satisfies $(\forall x) \psi$ ?

Holo

@LeylaAlkan do you know that $(\forall x)R$ is satisfied if and only if $R$ is?

Leyla Alkan

yes

Then it's correct

Holo

Yes

Leyla Alkan

17:25

Can we deduce $\vec a$ satisfies $\neg\psi $ from the part "$\vec a$ doesn't satisfy $(\forall x)\psi $

@Holo ?

In particular, if $\vec a$ doesn't satisfy $\psi $, can we say that $\vec a$ satisfies $\neg\psi $ ?

Leyla Alkan

18:12

Here's another one:

I want to show $(\exists x)( \forall y)\varphi\rightarrow( \forall y)(\exists x)\varphi $ is logically valid
My attempt:

Assume it's not logically valid. Then, there's an interpretation $\mathscr{M}$ for which it's not true. Hence, there's a sequence $\vec a$ in the domain $M$ of $\mathscr{M}$ such that $\vec a$ satisfies $(\exists x)( \forall y)\varphi$ and $\vec a$ doesn't satisfy $( \forall y)(\exists x)\varphi$ ,i.e $\vec a$ doesn't satisfy $(\exists x)\varphi$, I intuitively see that this contradicts to the previous part "$\vec a$ satisfies $(\exists x)( \forall y)\varphi$" ,but I do…

Leyla Alkan

18:47

1) $\vec a$ satisfies $(\exists x)( \forall y)\varphi$ $\iff$ $\vec a$ doesn't satisfy $(\forall x)( \exists y)\neg\varphi$ $\iff$ $\vec a$ doesn't satisfy $( \exists y)\neg\varphi$ $\iff$ $\vec a$ satisfies $( \forall y)\varphi$ $\iff$ $\vec a$ satisfies $\varphi$

2)$\vec a$ doesn't satisfy $( \forall y)(\exists x)\varphi$ $\iff$ $\vec a$ doesn't satisfy $(\exists x)\varphi$ $\iff$ $\vec a$ satisfies $(\forall x)\neg\varphi$ $\iff$ $\vec a$ satisfies $\neg\varphi$
Since $\vec a$ satisfies both $\varphi$ and $\neg\varphi$, which is a contradiction, then the formula must be valid.

Is this okay now?

Holo

19:30

Sorry, I wasn't here @LeylaAlkan , no, "A does not satisfy φ" does not implies "A satisfy ¬φ". It is possible that from a set of formulas you can't prove φ and yet you also can not prove ¬φ.

Also, to prove that claim I think it will be easier to use the definition of the interpretation $\mathscr{M}$

Leyla Alkan

19:44

user image

I saw this in the book, that's why I did it that way

Holo

19:55

@LeylaAlkan I thought that you used sequence as in theory from the language(in which case, take A=ZF, φ=AC), from the pic I can see I was wrong, what does wf means and what does s*(t[i]) mean?(it looks more like the definition of an interpreter in a model)

Leyla Alkan

user image

wf stands for wellformed expression

So, now my solution is valid right hahahha

Holo

It is weird wording choice for the definitions, but yes, unless I missed something there you are correct

Leyla Alkan

20:11

Well, thank you then, you've been very helpful :)

1 hour later…

Leyla Alkan

21:13

user image

Let's take example (a). So, now before attempting to find a counterexample how do we know sth is not valid? I couldn't prove

Holo

22:05

@LeylaAlkan (∀x)P is a requirement on the behavior of P as a whole, while, P⇒Q is a case by case requirement

Malice Vidrine

22:19

@LeylaAlkan - In what way are you trying to prove that it's not valid prior to finding a counterexample? A proof of the existence of a counterexample is the only thing that constitutes such a proof.

Holo

@MaliceVidrine I think they meant an intuition for the cases where the question will be "prove or disprove"

Malice Vidrine

Ah. I think to that the answer is "you probably won't have an intuition beforehand, without some experience" :P Though keeping in mind the counterintuitive behaviors of the implication connective is a good place to start in this example.

Leyla Alkan

What do you mean by the counterintuitive behaviors of the implication connective ? :)

Malice Vidrine

I think the easiest model for seeing why that particular one isn't valid, as an example, is to take the natural numbers, and let one of the predicate symbols mean "is odd" and the other mean "is even". Then the antecedent is true and the consequent false.

@LeylaAlkan - Most people find unusual the fact that a conditional with a true consequent, or a false antecedent, is automatically true. Because it seems unusual, people starting out in logic often forget to exploit that fact.

Holo

@MaliceVidrine I prefer to start with finding fintie models, like {0,1}, A^M[2]=F,A[1]^M(0)=T,A[1]^M(1)=F

Malice Vidrine

22:30

In particular, the fact that we can make the antecedent in (a) true for very silly reasons is handy for finding a counterexample.

@Holo - I always find it easier to look for examples in the naturals or reals. Everyone has their own groove.

Holo

@MaliceVidrine True

Leyla Alkan

@MaliceVidrine Yeah actually odd-even thing is used for proofs in logic quite a lot as I've seen so far, and I see your point as well. So I should find a way to make the antecedent true and the consequent false.

Malice Vidrine

22:51

Yup. And for the consequent in this case to be false, you just need one element in the universe of your model that is A_1 and not A_2. The overall intuition that guided me for the counterexample is that the antecedent is somehow "very easy to make true" and the consequent is somehow "very easy to make false".

Which is, of course, informal and not always obvious, but it works out surprisingly often :P

Leyla Alkan

Surely not without some experience

Malice Vidrine

Definitely takes experience. Not an overwhelming amount, but some.

Leyla Alkan

user image

There's this question

Since they do not contain atomic propositions, I can't prove if they are logically valid. Put aside the ones that I found counterexamples for, what about the ones that are not logically valid but I failed to find a counterexample ?

:D

Malice Vidrine

So one thing about logically valid sentences is that their negations are inconsistent. So if you can't find a counterexample, work out what their negations are and see if you can derive a contradiction.

Leyla Alkan

23:06

good approach

Malice Vidrine

Still doesn't help for the ones that still don't turn out to be valid, but that's one of those things there's not really a remedy for besides exceptionally good imagination. Personally, I'm terrible at finding counterexamples for anything even moderately complicated :P

Leyla Alkan

23:32

I found nothing so far, could you help me for some of them so that I could do the rest on my own?

The first one is literally strange

Leyla Alkan

23:46

user image

Actually, this interpretation works for (a) . I think this is what you also meant, right? @Holo

Malice Vidrine

So that one is valid. One way to see this is just to negate it (which just means dropping the initial negation symbol). Then instantiate the existential variable; we don't have any other free variables, so we can just use y. Then this says for all x, R(x,y) <-> -R(x,x); but if you instantiate the universal quantifier as y, and you'd have R(y,y) <-> -R(y,y), which is obviously a contradiction.

Leyla Alkan

Hope I find you guys here tomorrow as well, I need to get some rest now

Malice Vidrine

See you later!

And I hope the writers of that exercise only mean "finding an appropriate interpretation" for the cases when they are not valid, because an interpretation doesn't tell you anything about validity...

« first day (828 days earlier) ← previous day next day → last day (2284 days later) »

Transcript for

Nov '1823

♦ $Mathematics$ Logic

This room is meant for discussion about logic, including found...

formal-systems foundations logic no-trolls

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2025 Stack Exchange Inc; legal

mobile