45 votes
Accepted

In proofs, are "for each" and "for any" synonyms?

Compare A1. If there’s a simple solution for each of the problems, the test is too easy. A2. If there’s a simple solution for any of the problems, the test is too easy. These are not equivalent. ...
Peter Smith's user avatar
  • 54.5k
44 votes

"If everyone in front of you is bald, then you're bald." Does this logically mean that the first person is bald?

You can see what's going on by reformulating the assumption in its equivalent contrapositive form: If I'm not bald, then there is someone in front of me who is not bald. Now the first person in ...
Barry Cipra's user avatar
  • 79.8k
42 votes

"If everyone in front of you is bald, then you're bald." Does this logically mean that the first person is bald?

Mathematical logic defines a statement about all elements of an empty set to be true. This is called vacuous truth. It may be somewhat confusing since it doesn't agree with common everyday usage, ...
MvG's user avatar
  • 42.4k
40 votes
Accepted

Does the unique existential quantifier commute with the existential quantifier?

No, they do not commute. Consider for example the nonnegative reals as a linear order. Then $$\exists x\exists !y(y\le x)$$ is true (take $x=0$), but $$\exists!y \exists x(y\le x)$$ is false since ...
Noah Schweber's user avatar
33 votes

In proofs, are "for each" and "for any" synonyms?

They are synonymous, but may be used in different contexts.   Both declare that the predicate applies to every entity in the domain.   However, "for each" is more often used in an imperative ...
Graham Kemp's user avatar
25 votes

Does leaving universal quantifiers up to context lead to ambiguity?

Yes, it does generate ambiguity. Let $E$ and $O$ be predicates for "is even" and "is odd," respectively, and consider the difference between $$\forall x(E(x)\rightarrow O(x))$$ and ...
Noah Schweber's user avatar
24 votes

Is the Lyapunov stability definition ambiguous?

You're not interpreting the logic correctly. It doesn't say “there exists a single positive number $\delta$ which works for all positive numbers $\epsilon$”, it says “for any positive number $\epsilon$...
Hans Lundmark's user avatar
23 votes
Accepted

How to convert numerical claims to first order logic?

Here are some possible ways to make these kinds of numerical claims in general: 'At least n' (Method 1) "There is at least 1 P" : $\exists x P(x)$ "There are at least 2 P's" : $\exists x \exists y (...
Bram28's user avatar
  • 99.6k
21 votes

"If everyone in front of you is bald, then you're bald." Does this logically mean that the first person is bald?

It's worth looking at the reputations of the users who've given the contradicting answers, because different groups of people use language differently and on this occasion rep seems to neatly ...
Steve Jessop's user avatar
  • 4,106
19 votes
Accepted

What will be the negation of this statement:

Yes, that works. In logic, the original is: $\forall x (S(x) \rightarrow \exists y (H(y) \land I(y,x) \land \exists z (P(z) \land L(z,y) \land ((R(x) \land B(x)) \lor (E(x) \land K(x)))))$ If you ...
Bram28's user avatar
  • 99.6k
17 votes

Distributive Property of Quantifiers

here are some basic distributive properties in quantifiers, hope it might help someone. ∀x(P(x) ∧ Q(x)) ≡ (∀xP(x) ∧ ∀xQ(x)) ∃x(P(x) ∧ Q(x)) → (∃xP(x) ∧ ∃xQ(x)) ∀x(P(x) ∨ Q(x)) ← (∀xP(x) ∨ ∀xQ(...
Sanjay Kumar's user avatar
17 votes
Accepted

Are quantifiers redundant by treating free variables as implicitly universally quantified?

The problem with replacing $\exists$ with $\neg\forall\neg$ to not have to worry about the order of quantifiers becomes apparent if you actually try doing so and omitting the quantifiers. For ...
Eric Wofsey's user avatar
16 votes

Are these arguments invalid?

A nice tool for analyzing these kinds of categorical syllogisms are Venn Diagrams. Let's do this for the first argument. First, draw a Venn diagram for the 3 sets of things involved in the argument: ...
Bram28's user avatar
  • 99.6k
15 votes

What's funny about $\forall \forall \exists \exists$?

For a joke to convey its point, it has to allude to some nearby cultural association that many people in the audience will understand. By far the most recognizable instance of $\forall ... \exists$ ...
zyx's user avatar
  • 35.4k
13 votes

Difference between "for any" and "for all"?

"Any" is ambiguous and it depends on the context. It can refer to "there exists", "for all", or to a third case which I will talk about in the end. https://en....
Mosab Shaheen's user avatar
13 votes

What's the difference between $∀x\,∃y\,L(x, y)$ and $∃y\,∀x\,L(x, y)$?

I'm late to the party but: replace "loves somebody" with "has someone as a mother". Everbody has a mother. vs. There is somebody who is everybody's mother. ?????
fleablood's user avatar
  • 124k
13 votes

Problems teaching introductory logic. Is this a statement? "If x is an integer, then..."

This gets into a bit of a murky situation, actually. Let's start with a simpler claim: the expression "If $x$ is an integer, then $x^3>3$" is not a sentence, but rather a formula - the issue being ...
Noah Schweber's user avatar
13 votes

The real and deep meaning of quantifiers in first order logic and set theory

You assume that there exists a universal set, then seem surprised that you can conclude that there exists a universal set from this assumption. If you just don't assume it in the first place, then the ...
user3482749's user avatar
  • 6,660
13 votes

Understanding Universal Quantifiers (Order Matters)

The correct general statement is: You can swap adjacent universal quantifiers, provided their domains of quantification are independent. That is, a statement “$\forall x \in A,\ \forall y \in B, \...
Peter LeFanu Lumsdaine's user avatar
12 votes
Accepted

Why does universal generalization work? (the rule of inference)

1. What is meant by the second paragraph ? That is, when we assert from ∀xP(x) the existence of an element c in the domain, we have no control over c and cannot make any other assumptions about c ...
Caleb Stanford's user avatar
12 votes
Accepted

Example of a quantifier which is not compatible with ordered pairs.

How about $\exists!$, the unique existence quantifier? Working in the structure $(\mathbb{N};<)$, we have that $\exists !x\exists !y(x>y)$ is true but $\exists !(x,y)(x>y)$ is obviously false....
Noah Schweber's user avatar
11 votes
Accepted

Scope of quantifier (LOGIC DISCRETE MATH)

It's often a matter of parentheses: In a formula like $\forall y P(y)$ the $y$ in $P(y)$ is within the scope of the $\forall y$, but in a formula like $\forall y Q(x) \land P(y)$ it is not, since ...
Bram28's user avatar
  • 99.6k
11 votes
Accepted

How to understand intuitively why "$\exists !x \exists !y$" is not equivalent to "$\exists !y \exists !x$"?

To start things off, let's whip up a simple-to-understand example showing that the sort of switching you have in mind can't possibly be legal in general (it sounds like you already know this, but ...
Noah Schweber's user avatar
10 votes

What's the difference between $∀x\,∃y\,L(x, y)$ and $∃y\,∀x\,L(x, y)$?

That's a great example of why quantifiers don't commute! For the sake of simplicity, assume everybody in the world is married, and everybody loves his spouse. Then the first formula is satisfied. ...
Mikhail Katz's user avatar
  • 41.6k
10 votes

Why is quantifier elimination desirable for a given theory?

You're quite right that we can "shoehorn in" quantifier elimination to any theory we want, by adding new predicates for all old formulas (this is called Morleyization if I recall correctly). So ...
Noah Schweber's user avatar
10 votes

What is the inverse for ∀

Neither of the sentences you've written does the job. First of all, "$\forall x(F(x)\wedge P(x))$" is absurdly strong: forgetting the $P$-part it implies that everyone is your friend, which ...
Noah Schweber's user avatar
10 votes
Accepted

Is the Lyapunov stability definition ambiguous?

$ϵ$ is primary, $δ$ is secondary depending on it. As you have chosen $x(0)$, you already know the radius $δ$ in $\|x(0)-x_e\|<δ$ and thus also the $ϵ$ it is based upon. So there remains no freedom ...
Lutz Lehmann's user avatar
10 votes
Accepted

Difference between “for some $k$” and “for some arbitrary $k$”

In your first example, I would just write “where $k$ is an integer”. But “some” is okay. The point is, since $n$ is already known, $k$ is completely determined. Writing “where $k$ is some arbitrary ...
Michael Weiss's user avatar
9 votes
Accepted

Aren't vacuous statements True and False simultaneously?

You did not negate the statement "all elements of a set S have property X" correctly. The opposite of "all elements of a set S have property X" is not "no elements of set S have property X". The ...
Ted's user avatar
  • 33.7k

Only top scored, non community-wiki answers of a minimum length are eligible