Questions tagged [quantifiers]
The quantifiers $\forall$ ("for all") and $\exists$ ("there exists") distinguish predicate calculus from propositional logic.
1,791
questions
0
votes
1
answer
33
views
Prove: |= ∀xϕ→ψ ↔ ∃x(ϕ→ψ), with x not belonging to FV (ψ)
|= (∀xϕ→ψ) ↔ (∃x(ϕ→ψ)), with x not belonging to FV(ψ) (Free Variable).
I have been struggling with this exercise for a while. I have to prove this formula using either the valuations or as shown in ...
- 1
-1
votes
2
answers
43
views
Can the Absorption law be applied in universal quantifier? [closed]
Is the followings valid?
∃x P(x)∧(Q(x)∨P(x))
=∃x P(x)∧(P(x)∨Q(x)) commutative laws
= ∃x P(x) absorption laws
- 1
3
votes
4
answers
317
views
What is the difference between "for all" and "there exists" in set builder notation?
I'm having trouble with a specific example of set builder notation, and I'm hoping someone can help.
Here's an example of what I am having trouble with:
$$A = \{n \in \mathbb{N} : \exists x \in \...
-1
votes
2
answers
66
views
Why does switching the quantifiers make the statement false? [closed]
According to my teacher,
for every $y$ there exists an $x$, such as $y=0$ OR $xy>0$
is a true statement, while
there exists an $x$ for each $y$, such as $y=0$ OR $xy>0$
is a false statement.
...
1
vote
3
answers
97
views
$\forall x(P(x) \rightarrow Q(x))$ and $(\exists xP(x) \rightarrow \forall yQ(y))$ having different truth values
I've just been introduced to predicate logic and have been stuck on this question:
Define predicates $P(x)$ and $Q(x)$ with the same domain such that the formulas $$\forall x(P(x) \rightarrow Q(x))$$ ...
- 11
0
votes
2
answers
48
views
What is the calculation law in proposition logical?
How is $¬(∃x¬P(x))$ calculated to $∀xP(x)$ ?
In my understanding,
$¬(∀xP(x))$ can be calculated to $∃x¬P(x)$, and
$¬(∃xP(x))$ can be calculated to $∀xP(x)$ ?
Is my calculated result right? What's the ...
- 155
1
vote
1
answer
76
views
Is it valid to quantify two variables over the same universe using the same quantifier (like in $\forall a,b \in \mathbb{R} \:\: P(a,b)$)?
I am wondering if we can quantify two variables over the same universe using the same quantifier, such as in $\forall a,b \in \mathbb{R}\:\: P(a,b).$
Are statements like this found in mathematical ...
- 1,673
1
vote
1
answer
45
views
Can the two place "Most C are D" quantifier be defined from the one place "For most X" quantifier?
The two place quantifier "All C are D" (where C and D represent classes) can be defined from the single place quantifier "For all X", like so: "For all X, if X is C, then X is ...
- 18.5k
10
votes
3
answers
1k
views
Difference between “for some $k$” and “for some arbitrary $k$”
I am told that the “for some” and “for some arbitrary” are different.
For example, when proving the statement “if n is odd, then $n^2$ is odd”, one of the steps includes writing $$\text{$n = 2k+1,\:\:...
- 103
2
votes
0
answers
27
views
For a Wiener process, when can one exchange “for all $t$” and “almost surely”?
Certain local properties of the Wiener process $W_t$ are quick to prove at $t = 0$, for instance:
almost surely $W_t$ is monotonous on no interval beginning at $t = 0$;
almost surely $W_t$ is not ...
- 439
3
votes
2
answers
53
views
Problem with converting predicate expression to Prenex Normal Form
if I have the following predicate:
$$\exists x \neg P(x) \lor (\exists{x} \neg Q(x) \land \forall x \neg R(x))$$
What I did:
First, I used the tautology $\forall x A(x) \land \exists x B(x) = \forall ...
- 187
1
vote
1
answer
63
views
Set of natural numbers as the intersection of inductive sets
I was studying foundations of arithmetic, and reasoning about the set of natural numbers. In Peano arithmetic, we can talk about $\mathbb{N}$ without defining it explicitly or trying to prove its ...
1
vote
0
answers
20
views
Rudin $9.3(a)$'s led me to a question about the existence logic quantifier and it's variables
If $X$ is a vector space with $\dim X =n $, and $E=(x_1, ..., x_n)$ is a set of $n$ vectors, $E$ spans $X$ if and only if $E$ is independent.
This is theorem $9.3 (a)$ from Rudin, Principles of ...
- 969
6
votes
2
answers
1k
views
Does leaving universal quantifiers up to context lead to ambiguity? [closed]
An example of this notation would be extensionality: $$ \forall x \forall y [\forall z (z \in x \Leftrightarrow z \in y) \Rightarrow \forall w (x \in w \Leftrightarrow y \in w)].$$
If we write $$ (z \...
- 69
0
votes
1
answer
21
views
Quantifiers with restriction to predicate
I want to express that a formula $Q(e)$ should hold for all elements $e$ of a set $S$ that fulfill some predicate $P(e)$.
These are the options that I know:
restrict the set:
$$ \forall e \in \{ e \...
- 3
2
votes
4
answers
92
views
Help with negating proposition $P: \forall a\in\Bbb R, \forall b\in\Bbb R, f(a)=f(b)\rightarrow a=b$
Let $\,f(x)=x^2-2x-8\,,\,$ $\forall x\in\Bbb R$.
Consider the proposition
$P: \forall a\in\Bbb R,\;\forall b\in\Bbb R,\, f(a)=f(b)\rightarrow a=b$
Find $f(x)=0$.
Negate the proposition $P$.
Find ...
- 53
-1
votes
1
answer
94
views
Are "∀x ∈ R" and "∃x ∈ R" propositions?
Is the proposition which consists solely of "∀x ∈ R" considered true because x does not fail to satisfy any conditions we lay out? Or is it not a proposition?
Is the proposition which ...
- 1,673
0
votes
1
answer
100
views
What are all the restrictions on existential generalization (When CAN'T we use it)?
I know that I am using existential generalization wrong here, I don't know exactly how but the conclusion is absurd.
Let $F$ be any functional predicate.
$F(x)=F(x)$ axiom
$\forall x(F(x)=F(x))$ ...
2
votes
2
answers
113
views
Translating "There are two different students in your class who between them have sent an e-mail message to or telephoned everyone else in the class"
Let $M(x,y)$ be “$x$ has sent $y$ an e-mail message” and $T(x,y)$ be “$x$ has telephoned $y$”, where the domain consists of all students in your class. Assume that all e-mail messages that were sent ...
- 97
1
vote
2
answers
88
views
To prove that for every $x$, $(x\in Z\implies x\in R),$ is it ok to write "For any $x,$ suppose $x\in Z$. Then... Then $x\in R$"?
To prove that for every $x$, $(x\in Z\implies x\in R),$ is it ok to write "For any $x,$ suppose $x\in Z$. Then... Then $x\in R$" ?
For example, in the above proof of $$\forall x{,}y\left(\...
0
votes
2
answers
186
views
Which of these translates the universal and existential quantifiers better?
Consider this proposition (which I know is false):
$$(\exists y{\in}\mathbb Z)\,(\forall x{\in}\mathbb Z)\,(y > x).$$
I am wondering whether the analogy of picking a variable value according to the ...
- 1,673
0
votes
1
answer
102
views
Does 'if and only if' flip a quantifier?
I want to understand how this sentence works, as to me it seems 'if and only if' changes meanings of the statements:
Suppose that $a,b\in \mathbb N$. Then there exists a unique $d \in\mathbb N $ for ...
- 11
0
votes
1
answer
43
views
Is this a valid way to derive the second quantifier negation law from the first one?
The first quantifier negation law says that
$\neg \exists xP\left(x\right)=\forall x\neg P\left(x\right)$
And the second says that
$\exists x\neg P\left(x\right)=\neg \forall xP\left(x\right)$
Is this ...
- 167
1
vote
1
answer
59
views
Problem understanding quantifier for x in epsilon-delta definition of a limit
My textbook gives the definition of the limit of a function at a point as below: $$(\forall \epsilon>0)(\exists \delta>0)(\forall x\in \mathbb{R}), 0<|x-a|<\delta \implies |f(x)-L|<\...
0
votes
1
answer
64
views
What's the domain of $x$ in the RHS of the following logical equivalence, $\forall x \in D, P(x) \equiv \forall x, x \in D \rightarrow P(x)$?
Given the following logical equivalence,
$$\forall x \in D, P(x) \equiv \forall x, x \in D \rightarrow P(x)$$
The LHS of the equivalence states that "for all $x$ in the domain $D$, $P(x)$". ...
1
vote
0
answers
88
views
Necessity of the Replacement Theorem for erasing null quantifiers
There is an exercise in Mendelson's Introduction to Mathematical Logic, 6th edition:
If $\mathscr C$ is obtained from $\mathscr B$ by erasing all quantifiers $(\forall x)$ or $(\exists x)$ whose ...
- 109
0
votes
0
answers
21
views
Confusion on Locally Integrable Function Induced Measure is Regular
The statement that I am trying the proof of is:
$f \,dm$ is regular iff $f \in L^1_{loc}(\mathbb{R}^n, m)$, where $m$ is the Lebesgue measure.
Here is the proof provided by Folland:
In the proof, ...
- 1,096
1
vote
1
answer
61
views
What is the error in this deduction of $ \exists x (P) \leftrightarrow P$?
We use Hilbert-style systems. Let $\mathrm{Ax}$ be the set of all logic axioms (tautologies and quantifer axioms). Then for any formula $P$ where there's a free variable $x$, we have $\mathrm{Ax} \cup ...
- 318
1
vote
2
answers
65
views
Does $\forall x \exists y (P(x) \land Q(y))$ imply $\forall x P(x)$? [duplicate]
I am not sure if the $x$ in $\forall x \exists y (P(x) \land Q(y))$ carries some kind of "context" from the $\exists y$ that would make $\forall x P(x)$ not neccesarily true.
- 153
0
votes
0
answers
27
views
Predicate logic and material equivalence.
Predicate logic and material equivalence.
-
---
Hey all,
I have a question about predicate logic and material equivalences. When using the rule of material equivalence on a biconditional - 'if and ...
0
votes
1
answer
39
views
How to prove vacuous quantifier
$ \exists x (Fx \rightarrow \forall x Fx) $
I am trying to construct a derivation for this problem which can be found in the UCLA logic software program under chapter 3 of the derivation section.
Up ...
0
votes
1
answer
69
views
Universe of discourse in quantifiers
I am reading "How to prove it" by Velleman and am currently in the chapter about quantifiers. I don't understand why
$$
\exists x \in A (P(x))
$$
is equivalent to
$$\exists x~(x\in A \wedge ...
- 669
1
vote
0
answers
14
views
Does quantifier elimination preserve equi-satisfiability or equivalence?
Does quantifier elimination (QE) preserve equi-satisfiability or equivalence?
I always thought it preserves equi-satisfiability (and not equivalence) but in the book [Bradley, Manna], they say both ...
- 247
1
vote
0
answers
32
views
Are there terminating methods to provide models of first-order theory formulae?
If a first-order theory is decidable on its existential fragment, does this imply that we have a method (that guarantees termination) to obtain models of existentially quantified formulae within this ...
- 247
0
votes
1
answer
59
views
Help proving the equivalence of lower semicontinuity and sequential lower semicontinuity involving the negation of a stament with multiple quantifiers
Let $X$ be a metric space, $G:X \to \mathbb{R}$ a functional
Def 1) $G$ is slsc(sequentially lower semicontinuos) at $x$ $\Longleftrightarrow$ $G(x) \leq \liminf_{x_n\rightarrow x} G(x_n)$ $\forall ...
- 2,696
1
vote
1
answer
110
views
Unsure about determining an argument's validity
Suppose that the discourse domain is $\{2,3,\ldots\}$ and
$p(x,y)$: $x$ is a factor of $y$
$q(x,y,z)$: $z = GCF(x,y)$
$r(x)$: $x$ is prime.
Check whether this argument is valid:
$$ \forall x\exists y\...
- 31
2
votes
2
answers
80
views
Negating an existential conditional statement
$∃$ quadrilaterals $x$ such that if $x$ is a parallelogram, then $x$ is a kite.
I understand the above statement to be false.
Using the formulae $$¬(∃x∈U)[P(x)]≡(∀x∈U)[¬P(x)]\\
¬(p⟹q)≡¬(¬p∨q)≡¬¬p∧¬q≡...
- 51
1
vote
4
answers
103
views
How would one write "There are teachers that teach students" using quantifiers?
Regarding the statement "There are teachers that teach students" I'm unsure on how to properly write it as a proposition. The way I wrote it in my notes was:
Let:
I(x) : x is a teacher
S(y) :...
- 47
1
vote
1
answer
69
views
Translating "If there were no computers with antivirus every computer would work fine."
"If there were no computers with antivirus every computer would work fine".
Use: O(x) = x is a computer, A(x) = Computer x has an antivirus, F(x) = x works fine.
My take is $$∀x((O(x)∧¬A(x))...
- 53
0
votes
1
answer
69
views
Negation of converse of a theorem related to linear independence
Theorem $T:\quad$ Let $S = \{v_1, v_2,..., v_p\}$ be a set of vectors in $\mathbb R^m$. If $p>m$, then this set is linearly dependent.
Theorem $T$ can be proved to be true.
Converse $T_c$ of ...
- 2,127
2
votes
1
answer
54
views
What does $\exists x\left(L\left(x,x\right)\wedge \forall z\left(L\left(x,z\right)\rightarrow \left(z=x\right)\right)\right)$ mean?
I translated "There is someone who loves no one besides himself or herself" as $$\exists x\left(L\left(x,x\right)\wedge \forall z\left(L\left(x,z\right)\rightarrow \left(z=x\right)\right)\...
- 45
3
votes
1
answer
194
views
On the statement $ \exists \alpha>0 \quad \forall s>0 \quad \exists x>1 \quad\left|\int_1^x \frac{f(t)}{(t-1)^\alpha} d t\right|<s$ and its negation.
Suppose that $f: \mathbb{R} \rightarrow \mathbb{R}$ is a continuous function. Write down the negation of the statement $$\exists \alpha>0 \quad \forall s>0 \quad \exists x>1 \quad\left|\int_1^...
- 33
2
votes
1
answer
67
views
Are these formulas equivalent?
I am solving the problem from the textbook, and g) part states "There is exactly one person whom everybody loves." L(x, y) is "x loves y."
(1) The first and easiest solution is: $\...
- 45
0
votes
1
answer
102
views
"No integers $x$ and $y$ exist for $28x+7y=8$"
What is the logical structure of this statement?
No integers $x$ and $y$ exist for $28x+7y=8.$
I'm not sure, but I think the answer is
$$¬∃x\;∃y\;(x ∈ \mathbb Z ∧ y ∈ \mathbb Z ∧ 28x + 7y = 8).$$
- 11
2
votes
1
answer
84
views
In First Order Logic, why are we allowed infinitely long sets of finite formulas, but not infinite formulas?
Consider the empty language $L = \{\}$. Then we are said to be able to define the set of infinitely many elements, say $K = \{x_1,\cdots,x_n,\cdots\}$, as the set satisfying the infinite set of finite ...
- 145
0
votes
1
answer
90
views
How do I show if (∀x∃y∀zP(x, y, z)) ⇒ (∃y∀x∀zP(x, y, z)) is a logically valid statement?
I have tried to add a double negation to the left hand side and then swap the existential quantifiers, which gives:
¬¬∀x ∃y ∀z P(x, y, z) ⇔
¬∃x ¬∃y ∀z P(x, y, z)
This, I thought, means I can swap the ...
- 11
0
votes
0
answers
44
views
Tarski-Vaught Test with languages without constants
Does the Tarski-Vaught Test apply to structures of languages that do not contain any constants? From the proofs I've tried to find in textbooks, it relies on quantifier elimination which also relies ...
- 855
4
votes
3
answers
494
views
Equivalent statements not giving equivalent negations
Consider the statement $\forall \epsilon >0 \exists y\ldots.$ Negating it gives $\exists \epsilon>0 \forall y\ldots.$ I understand this.
$\forall \epsilon:\epsilon>0 \exists y\ldots.$ is ...
- 171
1
vote
0
answers
37
views
Negating $\sim(∀x∈ℤ : ∃y∈ℤ: x+y = 5)$
Is the following true?
$$\sim(∀x∈ℤ : ∃y∈ℤ: x+y = 5) \quad≡\quad \sim∀x∈ℤ : ∃y∈ℤ: x+y = 5 ?$$
If not, can somebody explain how i can produce statements that are equivalent to the LHS? I get confused ...
- 11
1
vote
2
answers
80
views
"Neither Ana nor Bob can do every exercise but each can do some."
I’m a bit confused as to how I should translate the following sentence:
Neither Ana nor Bob can do every exercise but each can do some.
I've identified the atomic sentences $A$ = Ana can do every ...
