Questions tagged [quantifiers]

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

Filter by
Sorted by
Tagged with
-1
votes
0answers
22 views

Express the following statement without using quantifiers [closed]

Assume that the domain is {−4, −3, −1, 1, 3, 4}, where P (x) is a propositional function ∃x(¬P (x)) ∧ ∀ x ((x < 0) ⇒ P (x))
0
votes
0answers
53 views

Formal Logic/Metalogic: Defining Wff Substitution while Forbidding Double Quantification

This question is closely related to the answer here. I'm working in a system of logic which has the usual semantics for building Wffs out of terms and atomic formulas. However, in the interest of '...
2
votes
2answers
57 views

A model in which the formula holds

I'm supposed to find a model in which the formula $$\exists x(\forall y(P(x) \land Q(x,y)))$$ holds. Does the model below work?: $M$: $U = \{a,b\}$, $P=\{a,b\}$, $Q=\{(a,b), (b,a)\}$.
3
votes
0answers
50 views

if $Γ\vDash\forall x_{1}...\forall x_{n}\left(\left(\exists yϕ(x_{1}...x_{n},y\right)\leftrightarrowϕ(\frac{t}{y})\right)$ then ψ exists

Let $Γ$ be a set of sentences over a dictionary $\Sigma$. it is known that for any formula $\phi(x_1,...,x_n)$ has logical term t, such that $\text{fv}(t)\subset\{x_1,...x\}$ and $$Γ\vDash\forall x_{1}...
3
votes
2answers
109 views

How should $\exists x P(x)\land\exists y Q(y)$ be interpreted?

If I encounter an statement like the following: $$\exists x P(x)\land\exists y Q(y)$$ Should this be interpreted as if x and y refer necessarily to different objects or it is to be interpreted as they ...
0
votes
0answers
24 views

Proving the invalidity arguments in quantifier logic.

I am studying how to prove an argument in quantifier logic is invalid. The textbook I am using by Virginia Klenk claims that you can use a Model Universe that contains a finite number of objects to ...
0
votes
1answer
35 views

Clarifying a step in the bisection proof of Weierstrass-Bolzano Theorem

Let $(x_n)$ be a sequence of elements of an interval $[a,b]\subset\mathbb{R}$. Then there exists a point of accumulation $c$ of the sequence with $c\in[a,b]$. The proof goes like this: Let $I_1=[a,b]...
2
votes
0answers
45 views

FOL formula transformation

I have the following predicates: President(P) Age(P) Is this FOL formula transformation correct? I'm a little unsure. The minimum age of the president is 25 years old. $$ ∀P[\text{President}(P) ⇒ \...
-1
votes
1answer
44 views

First Order Logic formula transformation

I have the following predicates: Doctor(D) Hospital(H) WorksIn(D, H) HasShift(D, IdS, H) Is this FOL formula transformation correct? I'm a little unsure. Every doctor that works in hospitals has at ...
2
votes
1answer
100 views

Is $\forall x,\exists y (x \ge y^2 \Rightarrow x>0)$ same as $\forall x (\exists y: x\ge y^2\Rightarrow x > 0)$

The first statement: $\forall x \exists y (x\geq y^2 \Rightarrow x > 0)$ The Second statement: $\forall x (\exists y: x\geq y^2 \Rightarrow x > 0)$ Actually, my question is this: In the first ...
0
votes
1answer
24 views

Distributive property of division over addition and logic

The distributive property of division over addition reads $\forall x\in\mathbb{R}, \forall y\in\mathbb{R}, \forall z\in\mathbb{R}\setminus\{0\} : \frac{x+y}{z}=\frac{x}{z}+\frac{y}{z}$ We know that $\...
1
vote
1answer
26 views

Which logical rules are used in combining universal quantifiers with same conditional

If I have $$ \forall x: (x < 5) \rightarrow (f(x)<g(x)), $$ $$ \forall x: (x < 5) \rightarrow (g(x)<h(x)) $$ I'm allowed to combine the implication into: $$ \forall x: (x < 5) \...
0
votes
1answer
31 views

$\forall x\in A(\in\mathcal P(E)),\,P(x)\Leftrightarrow\forall x\in E,\,(x\in A)\wedge P(x)$?

The question is in the title. When I am working in $\mathcal P(E)$, do statements like $\forall x\in A,\,P(x)$ translate to $\forall x\in E,\,(x\in A)\wedge P(x)$ or to $\forall x\in E,\,(x\in A)\...
0
votes
0answers
26 views

What is the rule for changing variables in quantifiers?

In this answer https://math.stackexchange.com/q/4323221 I finish by using this change of variable rule $\forall x: P(x) \iff \forall y: Q(y)$ where $Q(y)=P(f(y))$, so the change of variable is $x=f(y)$...
1
vote
2answers
68 views

Is there a difference between using two vs one universal quantifier for two variables?

Is $\forall x \forall y$ equivalent to $\forall (x, y)$? For example, here is the statement of a Symmetric Relation in both ways: $\forall x \forall y[xRy \rightarrow yRx]$ $\forall (x,y)[xRy \...
1
vote
1answer
38 views

Existential quantifier question $\forall x \forall y(P(x)\land P(y) \implies x=y)$

Quesiton about existential quantifier The unique quantifier is $!\exists xP(x)$ so only one x is true. And I am wondering if the following is equal to unique quantifier $\forall x \forall y(P(x)\land ...
2
votes
1answer
73 views

double negation to statements contain several quantifiers

I would like to use double negation to equivalently re-express sentences contain several quantifiers. And after reading related materials Generalized quantifiers and relations, Classical vs. modern ...
1
vote
1answer
58 views

negating nested generalized quantifiers

From the definition of the square of opposition, I know that the sentence “All the apples are red.” has a same meaning as “It’s not the case that some apples are not red. ” and “No apples are not red.”...
2
votes
3answers
80 views

How to notate the universal quantifier when applied to an equation?

So I have an equation with infinite regular solutions. Let's say this equation is $$\sin^{-1}(0)=\pi n$$ where $n$ is any integer. How do I express this formally using the universal quantifier? Do I ...
2
votes
2answers
73 views

Trying to understand Sequent Calculus inference rules for quantifiers $\forall$ and $\exists$.

I'm trying to understand any of the LK sequent calculus (logic) inference rules for quantifiers (if I can understand one well enough, perhaps I can use that to inform my understanding of the other ...
3
votes
1answer
59 views

Clarification regarding substitution in sequent calculus

Wikipedia's Sequent Calculus article states: $A[t/x]$ denotes the formula that is obtained by substituting the term $t$ for every free occurrence of the variable $x$ in formula $A$ with the ...
4
votes
1answer
82 views

Proving $\forall x[p\vee\Phi(x)]\Longleftrightarrow [p\vee\forall x[\Phi(x)]$, where $p$ does not contain $x$ as a free variable

How to prove this formula? $$\forall x[p\vee\Phi(x)]\;\Longleftrightarrow\; [p\vee\forall x[\Phi(x)]$$ where $p$ does not contain $x$ as a free variable. I was reading Set theory by K. Kuratowski, A. ...
2
votes
1answer
49 views

Natural deduction and introduction of universal quantifier

I have a hard time with quantification introduction and elimination ; for instance, if I want to prove $$\forall x \quad (Px\rightarrow Px ) $$ I am tempted to do the following : $$\underline{[Py]}_{\,...
-1
votes
1answer
48 views

How can I solve this $(∀x)(∃y)P(x,y) <-> (∃y)(∀x)P(x,y)$?

Is the following example true? If yes give explanation why ? $$(∀x)(∃y)P(x,y) \leftrightarrow (∃y)(∀x)P(x,y)$$ I tried using values for $x$ and for $y$, and restricted them to the following: $x > 3$...
1
vote
1answer
63 views

What do you call the set definition part of a formula?

Suppose I have a formula with two parts: First is a description of the element and set on which an equation will depend, and the second is the equation itself. Example: First, the formula quantifies ...
0
votes
0answers
50 views

The strong twin conjecture can be transformed into the unsolvability of a particular Diophantine equation

Let us consider the strong twin conjecture: For all positive integer $n$ there exist a prime $p$ such that $$n+4<p<2^n2^4$$ and $p$ is a prime and $p+2$ is a prime Since the inequalities and the ...
0
votes
0answers
49 views

Predicate Logic Question - Let T(a) be "a is a teacher" and S(a) be "a is a student" - What is "Every Teacher is also a student"

I had this question on a previous exam and am trying to understand where I went wrong. My attempt for this question yielded me: $$\forall x(T(x)\land S(x))$$ My logic in thinking this was the solution ...
0
votes
1answer
34 views

Deriving a conclusion from two premises, only one of which is quantified

I have these premises: $\forall x:S(x)\to E(x)$ $S(x)\land D(x),$ and this conclusion: $\exists x:E(x)\land D(x).$ I'm having a hard time figuring out how to use rule(s) of inference to derive the ...
0
votes
1answer
49 views

What is $\forall_x\exists_yA(x,y)$ where A(x): X is pointing to Y?

I am new to predicate logic and am just learning about it; I encountered this problem on a quiz and was disconcerted by how I was supposed to answer it. My answer for the quiz was: For every x, there ...
0
votes
1answer
96 views

representing a sentence with quantified statements

My approach to this question: $$ \exists x(P(x)\to R(x)) $$ I cannot verify if my answer is correct, any help to verify my answer would be appreciated and if I did wrong any help to explain why ...
2
votes
0answers
93 views

Logics without or with weakened Universal Generalization?

Are there any well-known/useful logics in which UG fails to hold in full generality? I'm developing a logic that well captures a phenomenon at the level of propositional logic (with no quantifier), ...
2
votes
1answer
42 views

Can an existentially quantified formula be a tautology

I was wondering if a formula of the form $\exists xP(x)$, where $P(x)$ is any formula, can be a tautology. To me the domain could be empty, and therefore it is not satisfiable in every structure. But ...
2
votes
1answer
30 views

Represent statements with the help of quantifiers

I need to represent the following statements using quantifiers in this task: (a) For any real number $x$, if $x$ is rational, then also $\sqrt{x}$. (b) For some natural numbers $n \geq 3$ and ...
10
votes
2answers
935 views

Is the Lyapunov stability definition ambiguous?

I understand the conceptual idea of Lyapunov stability. My question is about the formal definition. Wikipedia's definition is very much in line with others I found: An equilibrium, $x_{e}$, is said ...
2
votes
4answers
116 views

Find the negation of the following quantified sentence $(∀x)(p(x)∨q(x)→¬q(x))$

I'm trying to deny a quantified sentence. My attempt: To negate a quantified sentence, I just need to change the quantifier and connectives. So: $$(∀x)(p(x)∨q(x)→¬q(x))$$ Denying: $$(∃x) (p(x) ∧ ~q(x) ...
1
vote
2answers
169 views

Meaning of "$\exists$" in "$\{y \in Y : \exists x \in X \text{ such that }f(x) = y\}$"

I came across this definition of the range of a function: For a function $f : X → Y$, the range of $f$ is $$\{y \in Y : \exists x \in X \text{ such that }f(x) = y\},$$ i.e., the set of $y$-values ...
0
votes
0answers
62 views

Translation involving ∀x∀y∀z

Domain of discourse: the set of human beings. Exercise($x$) := $x$ enjoys exercising. How does $$∀x∀y∀z ( (x ≠ y) ∧(y ≠ z) ∧(x ≠ z) \to (\text{Exercise}(x) ∧ \text{Exercise}(y) ∧ \text{Exercise}(z)) )$...
1
vote
2answers
130 views

Expressing "at most" in predicate logic

I need to translate to predicate logic: "Every natural number is the sum of at most four squared natural numbers". The word that causes problems for me is the word "at most". Here ...
2
votes
2answers
64 views

Determining the truth value of $∃x∀y (y=x^2+2x+1)$

The domain for $x$ and $y$ are all integers. $∃x∀y (y=x^2+2x+1)$ can be interpreted as: There is an $x$ for all $y$ such that it satisfies $y=x^2+2x+1$. There is a single $x$ value which results in ...
0
votes
2answers
70 views

What is the difference between ∃x∀y and ∀y∃x? [duplicate]

What is the exact difference between ∃x∀y(condition) and ∀y∃x(condition)? Translating these into English, ∃x∀y(condition) = There is an x for all y such that (condition) is satisfied. ∀y∃x(condition) ...
2
votes
2answers
65 views

Nested quantifiers for $y < x^2$

$∀x ∃y P(x, y)$ For every $x$ there exists a $y…$ This is true, because for every number $x$ there exists at least one number $y$ for the statement to be true. For example, we can choose $x=100$ and $...
1
vote
2answers
70 views

Why does "Some student has asked every faculty member a question" translate to $\forall y (F(y) \to \exists x (S(x) \lor A(x, y)))$?

Context: I'm in undergrad discrete math, this is a textbook question from Discrete Mathematics and its Applications 7th edition Here's the question: Let S(x) be the predicate "x is a student,&...
3
votes
2answers
78 views

Translating statement into predicate logic

P(x,y) = def "x divides y" Statement: "There is no largest prime number" UoD: Z+ How do we translate this into logic? I'm thinking between these two options: $$∀x∃y[y>x \land ∀z(...
6
votes
3answers
347 views

Why is the statement $(\forall x\in\mathbb R)(x^2\ge0)$ true even when $x$ is not a real number?

It seems obvious that the statement $(\forall x\in\mathbb R)(x^2\ge0)$ is true. To prove it, however, we need to show that the implication $x\in\mathbb R\to x^2\ge0$ holds for all $x$. But suppose ...
1
vote
2answers
50 views

Translating English statements into quantifiers and predicates. [duplicate]

Consider the following statement: "All your friends are perfect." This can be translated into quantifiers and predicates as follows : Let P (x) be “x is perfect” and let F (x) be “x is your ...
1
vote
1answer
113 views

The negation of this proposition

Suppose $p(x)$ is a proposition about a real variable $x$ in the interval $(0,1)$. Let $P$ be the proposition $$\bigg(\exists x_0\in(0,1), p(x_0)\bigg)\implies\bigg(\forall x\in(0,x_0), p(x)\bigg) .$$ ...
0
votes
0answers
45 views

Tuples and Multiple Quantifiers

So I'm familiar with predicate logic and the usage of nested quantifiers. However, I've never seen anything like this before. How would I even go about reading this? Also, I don't understand the ...
1
vote
1answer
66 views

Fitch - Formally prove that these two premises lead to ∃x(Small(x)) using ∃ Elimination

∃x(¬Large(x)) ∀x(Large(x)∨Small(x)) So far I have this: How do I get to the goal of ∃x(Small(x))? Am I missing something small or am I doing it completely incorrect?
1
vote
1answer
51 views

Negation of the statement without negation symbol

The statement is : $\forall x \in \mathbb{Z}$, $\exists y \in \mathbb{R}, (x\geq y \Rightarrow \frac{x}{y}=1)$. I think the negation without negation symbol will be as follows : $\exists x \in \mathbb{...
1
vote
1answer
74 views

Nested Quantifier placement confusion

I'm working on a question right now that's asking me the difference between "For every integer a, b, if for every integer x, ax+b is even ... " and "For every integer a, b, x if ax+b is ...

1
2 3 4 5
33