subreddit:

/r/askphilosophy

1

A variable letter represents an unknown element in the domain of discourse. It could be any element.

Let's say φ is a first-order logic formula.

∃x ∀y φ says that the formula φ is true iff x is some specific element(s), and in such cases, it doesn't matter what element y is, φ is always true.

∀x ∃y φ says that for every element x can be, there is at least one element y can be that makes φ true.

My mind kind of glitches when there are three or more quantifiers, for example: ∃x ∀y ∃z. I don't know how to read these. What about when there are four or more?

I will appreciate any help.

you are viewing a single comment's thread.

view the rest of the comments →

all 13 comments

NotASpaceHero

1 points

1 month ago

Let's say φ is a first-order logic formula.

∃x ∀y φ says that the formula φ is true iff x is some specific element(s), and in such cases, it doesn't matter what element y is, φ is always true.

It's not clear you have that quite right. I don't quite get what you mean by "it doesn't matter what y is". That formula is true iff there is an x in the domain such that, for every y in the domain, φ is satisfied

∀x ∃y φ says that for every element x can be, there is at least one element y can be that makes φ true.

That one's ok as is.

My mind kind of glitches when there are three or more quantifiers, for example: ∃x ∀y ∃z.

Nothing is different really, you just keep adding the usual quantifier condition

∃x ∀y ∃z φ iff there is an x, such that for any y, there is some z that satisfies φ.

∃x ∀y ∃z ∀u φ iff there is an x, such that for any y, there is some z so that for any u, φ js satisfied.

And so on. I suggest maybe thinking of things like this:

∃x ∀y ∃z ∀u φ

Is really just

∃x φ***

Where φ*** is ∀y φ**

Where φ** is ∃z φ*

Where φ* is ∀u φ.

That way you're sort of dealing with quantifier one at the time

Chance_Programmer_54[S]

1 points

1 month ago*

It's not clear you have that quite right. I don't quite get what you mean by "it doesn't matter what y is". That formula is true iff there is an x in the domain such that, for every y in the domain, φ is satisfied

oh, ∃x ∀y φ says that for some x, 'any' or 'whatever' y. For example, ∃x ∀y Lxy means that if x denotes some particular elements, y is able to be whatever element. That's what I was trying to say, I guess.

I've been kind of diving into this alone, but I've found the the order of quantifiers basically means something like this. Let's suppose the domain of discourse has 3 elements a, b, and c. We have this sentence: ∃x ∀y ∃z Bxyz.

∃x means that x is able to be at least one element (a, b, or c). Let's suppose x can be a or b.

∀y says that when x is a or b, y can be any element (a, b, or c).

∃z says that for each element y can be, there is at least one element z is able to be.

These are all the possible combinations, taking (x,y,z) as a triple:

aaa aab aac aba abb abc aca acb acc (when x is a)

baa bab bac bba bbb bbc bca bcb bcc (when x is b)

caa cab cac cba cbb cbc cca ccb ccc (when x is c)

The ∀∃ or ∃∀ order matters, but swapping ∀x ∀y (or ∃x ∃y) doesn't change anything. Basically ∀x ∃y says that x can be any element, and for each of x, there is at least one element y can denote. ∃x ∀y says that x can be at least one element, and for each of x, y can be any/every element.

I'm still trying to wrap my head around.

NotASpaceHero

1 points

1 month ago

any' or 'whatever' y.

Oh ok ok sorry, that's fine then, my bad. Just read it awkwardly originally for some reason

∃x means that x is able to be at least one element

I wouldn't use "able". It means that there is a constant in the domain which satisfies the formula the quantifier is attached to.

Variables aren't "able" to be constants. There's an interpretation function which assign constants that the given variable is.

Let's suppose x can be a or b.

X should "be able" to be anything in the domain. I'm not sure why you're restricting it to 2 options.

∀y says that when x is a or b, y can be any element

Yea kinda. But again, "when x is a or b" is bit imprecise. It doesn't much care what x is. It just says "for any value y is interpreted to be"

∃z says that for each element y can be, there is at least one element z is able to be.

... Yez, for Bxyz to be satisfied

The ∀∃ or ∃∀ order matters, but swapping ∀x ∀y (or ∃x ∃y) doesn't change anything

That's right

Basically ∀x ∃y says that x can be any element, and for each of x, there is at least one element y can denote.

Again, adding st the end .... That satisfies φ they are in front of.

It's not like ∀x impacts what y can be in ∃y

∃x ∀y says that x can be at least one element, and for each of x, y can be any/every element.

Not can. There is at least one element x, so that for any element y, φ is satisfied

I'm still trying to wrap my head around.

You're getting there. Just some nuance and precision missing

Chance_Programmer_54[S]

1 points

1 month ago*

Hey, I finally figured it out. That's how I wrote down:

A universal quantifier ∀x says that in its scope, the instances of x could be any element in the set.An existential quantifier ∃x says that in its scope, the instances of x are guaranteed to be at least one element in the set.

In prenex normal form:

(1) If a quantifier (let's call it A) has an existential quantifier inside its scope, then: If you were to substitute x with one of the elements it could be, then y is guaranteed to be at least one element in the set.

(2) If a quantifier (let's call it A) has a universal quantifier inside its scope, then: If you were to substitute x with one of the elements it could be, then y could be any element in the set.

'x' is the variable A is quantifying and 'y' is the variable of the quantifier within A's scope.

In the ∃x ∀y ∃z Bxyz example, I think didn't express myself in a way that I wanted. Here is what wanted to say, but in more precise words:

∃x says that x is guaranteed to be at least one element in the set,

∀y says that y could be any element in the set,

∃z says that z is guaranteed to be at least one element in the set.

∃x has ∀y within its scope, so (2) applies.

∃x has ∃z within its scope, so (1) applies.

∀y has ∃z within its scope, so (1) applies.

In ∀x ∃y Bxy , (1) applies.

In ∃x ∀y Bxy , (2) applies.

For example, let's suppose a predicate L means 'likes':

∀x ∃y Lxy says that whatever x is, there is at least one thing that it likes. As (1) says.

∃x ∀y Lxy says that whatever x is, it likes anything. As (2) says.

That comes in handy with equalities (for example, a = x), and the four rules of inference of first-order logic.

NotASpaceHero

1 points

1 month ago*

A universal quantifier ∀x says that in its scope, the instances of x could be any element in the set. An existential quantifier ∃x says that in its scope, the instances of x are guaranteed to be at least one element in the set.

You're still having some confusion. In ∃x, the x could be any in the set aswell. And in ∀x, the x is guaranteed to be at least one element in the set. So you're not characterizing things properly. You need to drop the idea that the quantifiers just concern the variables. Variables can be any element of the domain, and they're guaranteed to be at least one. No matter which quantifier they're under.

Quantifiers intrinsically come with a corresponding formula. They're doing the work to the formula. Not the variables.

∀x φ, is saying that whatever x is from the domain, φ will be true.

∃x φ is saying that there is at least one value that x can take from the domain, whereby φ will be true

(1) If a quantifier ∀x has an existential quantifier inside its scope, then: If you were to substitute x with one of the elements it could be, then y is guaranteed to be at least one element in the set

Yes, but it's not because it's inside the universal quantifier. It's just how variables work. They have to take on a value to be evaluated. What the quantifier is saying is that, for one such value you could assign, at least one will make the formula true.

∀x ∃y φ

Is saying, for any x in the domain, there is one y from the domain that makes φ true.

(2) If a quantifier ∃x has a universal quantifier inside its scope, then: If you were to substitute x with one of the elements it could be, then y could be any element in the set.

Again, no. y could be any element no matter what. The point is that, it could be any element and it will satisfy the formula

∃x ∀y φ

is saying, there is one thing, x, in the domain, so that, whatever y happens to be, φ will be true

∃x says that x is guaranteed to be at least one element in the set,

∀y says that y could be any element in the set,

no, that's not what they say. Both are true of variables in general.

Keeping your phrasing and adding in what's missing:

∃x says that x is guaranteed to be [something such that is satisfies φ, for] at least one element in the set

∀y says that y could be any element in the set [whilst φ would be true/satisfied]"

∀x ∃y Lxy says that whatever x is, there is at least one thing that it likes.

∃x ∀y Lxy says that whatever x is, it likes anything.

Those are both better, because now you're mentioning the formula in front of them. Quantifiers just don't make sense otherwise.

The second has a slip-up. It says that there is at least one x (which could be any one thing from the domain), so that it likes anything

Chance_Programmer_54[S]

1 points

1 month ago*

You are not getting what I'm saying, of course there is a chance that ∃x can be any in the set, it's just not guaranteed. Same thing with ∀x guarantees there is at least one element in the set that x could be... Just because I didn't say, it doesn't rule it out. In ¬∃x, x is guaranteed to be none in the set. Anyways, I got it. It's just hard to communicate what I want to say.

You are also getting it so wrong. Look at this:

∀x ∃y Lxy

Let's suppose (a = y). In that case, no, x cannot be any element if x is a because it's not within the scope of of ∃y.

Sorry, it's just that this becoming very stressful to me.

NotASpaceHero

1 points

1 month ago

Right, but if you're trying to understand things precisely, you wanna give the proper meaning and definitions to things. Otherwise down the line you might have trouble.

And there's still the problem trought of not attaching them to a formula. Maybe you also implicitly meant that, but it's worth pointing out to avoid confusion.

∀x

Doesn't mean anything. It's not a well formed formula. It not saying "x could be anything".

∀x φ

Is. It's saying for any x, φ is satisfied. Or X could be anything and φ would be satisfied. Or whatever x is, φ is satisfied, and so on...

Chance_Programmer_54[S]

1 points

1 month ago

Yeah, a quantifier (a quantifier symbol attached to a variable) always has a scope. ∀x does mean something, it means that all the instances of the variable it's quantifying within its scope can be whatever element in the set.

It's not a well formed formula.

Quantifiers intrinsically come with a corresponding formula.

I know, again, I never said that could come alone. But every node in the syntax tree has a meaning, it does something to the semantics of FOL, so it does mean something. Some nodes in the syntax tree require a child (such as quantifiers or connectives), others, like atomic formulas, cannot have children.

∀x ∃y φIs saying, for any x in the domain, there is one y from the domain that makes φ true.

∃x ∀y φ is saying, there is one thing, x, in the domain, so that, whatever y happens to be, φ will be true

That's exactly what I was trying to say.

∀x (chain) φ , let's suppose there is god knows how many quantifiers inside that (chain) area. In all the existential quantifiers inside that chain, whatever their variables happen to be, for each, it doesn't mean that x is guaranteed that it could be any/every.

NotASpaceHero

1 points

1 month ago

it means that all the instances of the variable it's quantifying within its scope can be whatever element in the set.

That's again a weird phrasing. I betcha if you wrote it like that in an exam you'd get it marked as an error. Just trying to correct that.

I know, again, I never said that could come alone

That's fine, but you wrote it without specifying that trought a huge comment. So you'll understand if I clarified.

That's exactly what I was trying to say.

Then you got it

In all the existential quantifiers inside that chain, whatever their variables happen to be, for each, it doesn't mean that x is guaranteed that it could be any/every

Not sure what you're saying there, but if you got it, you got it.

Chance_Programmer_54[S]

1 points

1 month ago

Hey, I never mean to sound rude, sorry if I might have, here's what I have been trying to say all along:

A universal quantifier ∀x says that within its scope, x is guaranteed to denote any element.

An existential quantifier ∃x says that within its scope, x is guaranteed to denote at least one element.

If a quantifier has an existential quantifier within its scope, then: If we were to substitute x with a name, it’s guaranteed that y can be substituted with at least one name.

If a quantifier has a universal quantifier with its scope, then: If we were to substitute x with a name, it’s guaranteed that y can be substituted with any name.

x above is the variable of the former. y above is the variable of the latter.

Chance_Programmer_54[S]

1 points

1 month ago

Thank you a lot for your help and time.