# Questions tagged [quantifiers]

The quantifiers $\forall$ ("for all") and $\exists$ ("there exists") distinguish predicate calculus from propositional logic.

1,791 questions
Filter by
Sorted by
Tagged with
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 ...
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
317 views

1 vote
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
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 ...
1k views

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 ...
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 ...
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))$ ...
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 ...
1 vote
88 views

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
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 ...
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 vote
61 views

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).$$
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 ...
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 ...
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 ...
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 ...
1 vote
### 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 ...
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 ...