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

learn more… | top users | synonyms

1
vote
3answers
70 views

Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?

I'm currently trying to prove that $\exists n\forall m~P(m,n)\Rightarrow \forall m\exists n P(m,n)$ formally. This is important to me because my professor and various only sources have hinted that in ...
1
vote
2answers
46 views

Can I do instantiation like this?

Suppose, if I have been given this: $\forall x \in A(P(x))$ and $\exists y \in A(Q(y))$. Now from $\forall x \in A(P(x))$ using universal instantiation, I get $P(c)$ where $c$ is an arbitrary element ...
3
votes
1answer
46 views

Counting quantification and the cardinality of a set

A counting quantifier is a quantifier that denotes how many elements satisfy a predicate. I will use the notation $C_n x P[x]$ to denote that there are $n$ elements that satisfy $P$. I was thinking ...
1
vote
1answer
20 views

Question on existential quantifier.

Let us consider the following predicates. $A(x)$: $x$ is $A$ type. $B(x)$: $x$ is $B$ type. Then convert the following statement in terms of predicate expression. Some $A$'s are $B$. Then which ...
0
votes
0answers
57 views

“there are infinitely many” with finitely many variables

I vaguely recall reading somewhere that one cannot say "there are infinitely may" using a formula with only finitely many variables. A bit more precisely, let $\mathcal L$ be the result of extending ...
2
votes
1answer
31 views

Nested quantifiers order?

$$a) \quad \forall x\exists y(3x+4y=12)$$ $$b) \quad \exists x\forall y(3x+4y=12)$$ Am I correct in saying that a) is correct while b) is false?
1
vote
0answers
41 views

Is $\exists x(P(x)\rightarrow\forall y P(y))$ a tautology? [duplicate]

This is from the book by D.J. Velleman-"How to prove it?" Sec 3.5 Excercise 31: Prove $\exists x(P(x)\rightarrow\forall y P(y))$ Suppose the universe of discourse is set of all men. Let statement ...
1
vote
3answers
31 views

Difference between these two logical expression

I am trying to solve the following problem: Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate “x has asked y a question,” where ...
4
votes
1answer
46 views

“There are exactly two values of $x$ for which $P(x)$ is true” formula using logical symbols

Assuming $P(x)$ is true. The statement: "There are exactly two values of $x$ for which $P(x)$ is true" can be rewritten using logical symbols as follows: $$\exists x \exists y[(P(x) \wedge P(y) ...
1
vote
0answers
33 views

Prove Ordering of Mixed Quantifiers

I'm trying to familiarize myself with some of the formal logic behind mathematical proofs, and I'm having trouble proving some things explicitly even though I have no trouble with them intuitively. ...
1
vote
1answer
58 views

Is proving $m(E) < \epsilon, \forall \epsilon > 0$ equivalent to prove $m(E) = 0$?

Definition of measurable set: A set $E$ measurable if $$m^*(T) = m^*(T \cap E) + m^*(T \cap E^c)$$ for every subset of $T$ of $\mathbb R$. Definition of Lebesgue measurable function: Given a function ...
3
votes
2answers
69 views

Are the quantifiers interchangeable?

In other words, is it true that $\forall x \; \exists y\;\phi(x, y) \iff \exists y\;\forall x \; \phi(x, y) $?
-2
votes
1answer
70 views

Is the following statement true: $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$? [closed]

Is the following statement true: $(\exists \, a,b \in \mathbb{R}), (\forall x \in \mathbb{R}), (ax+b=x)$? Having a hard time proving this statement.
0
votes
4answers
46 views

A tautology that contains quantifier and logical connective.

It might seem a stupid "question", but I need a logical explanation of it. If $p(x)$ is a predicate and $q$ is a statement, then $(\forall x:p(x))\wedge q\iff \forall x:(p(x)\wedge q)$, and ...
0
votes
1answer
50 views

Scope of Quantifier, bit puzzling

$\forall x(p(x) \rightarrow \exists xq(x))$ $p(x)$ : $x$ is a human. $q(x)$ : $x$ has a job Help me understand this in english please?
2
votes
3answers
59 views

Quantifier elimination over rationals.

My question is concerned with a statement in Marker's Model Theory. The statement is that for formula $\phi(a,b,c)=\exists x(ax^2+bx+c=0)$, we cannot have a quantifier free formula $\phi'$ such that ...
1
vote
2answers
44 views

Multiple Quantifier Proof

I am completely confused on how to go about proving this multiple quantifier expression. $$(\forall m\in\mathbb Z)(\exists N\in\mathbb Z)(\forall n\in\mathbb Z)(n\geq N\Rightarrow (n-1)^2 \geq m^2)$$ ...
1
vote
2answers
21 views

Is there a difference between these statements about natural numbers?

Can i say that $(\forall x \in \mathbb{N}:x^2=x) \vee(\forall x \in \mathbb{N}:x>1)$ is the same statement as:$\forall x \in \mathbb{N}:(x^2=x)\vee(x>1)$ ? If not, why? Thanks.
0
votes
1answer
42 views

First Order Logic Question

$\forall x\ \forall y\ P(x,y) \to \forall x\ \forall y\ P(y,x)$ Is this a tautology? Is there a set method that we can use to find whether a wff is a tautology?
2
votes
1answer
47 views

Basic First Order Logic Question

Which one of the following well formed formulae is a tautology? (A) $\forall x\exists yR(x,y)\iff\exists y\forall xR(x,y)$ (B) $[(\forall x\exists y(p(x,y)\Rightarrow R(x,y))]\Rightarrow ...
1
vote
2answers
33 views

Nested Quantifiers Doubt: “If $xy$ is equal to $x$ for all $y$, then $x=0$”

If $P(x,y,z)$ represents $xy=z$. Then represent the following statement using quantifiers,connectives etc. "If $xy$ is equal to $x$ for all $y$, then $x=0$". The answer given is $\forall x[ \forall ...
0
votes
1answer
30 views

Translate into a formula using quantifiers

Let B(x) be “x is a bird”, F(x) be “x has feathers”, and Y(x) be “x can fly”. Then translate into a formula using quantifiers: Some things that can fly are not birds.
2
votes
3answers
92 views

Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime. Attempt: The first thing that I decided to do was to try and factor it. I immediately saw that it ...
2
votes
2answers
43 views

Difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$

Existential quantifier confusion: what is the difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$? What are the differences between those two ...
2
votes
1answer
52 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
2
votes
1answer
87 views

Quantifier-free induction and comparison with $\sqrt{2}$

I am trying to understand quantifier-free induction in the system called PRA - primitive recursive arithmetic which states the following: $$ \frac{ \varphi[0] \quad \varphi[n] \implies ...
1
vote
0answers
77 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
1
vote
1answer
25 views

using logical quantifiers to write that f approaching infinity DOES NOT tend to infinity

Is this the same as writing that the limit of f as f approaches $\infty$ is L? i.e.: $\forall \space \epsilon > 0 \space \exists \space c \space \forall \space x>c : |f(x) - L|< \epsilon$
1
vote
3answers
51 views

When does the negation of a universal quantifier require a disjunctive statement?

Here's a question I got wrong on a HW assignment recently, which asked students to negate the given statement and assign that negation a truth value. Q: There are exactly 3 points on every line. my ...
0
votes
1answer
56 views

Logical Equivalence: $\exists x((P(x) \land \lnot Q(x))\Leftrightarrow R(x)) \iff (\forall xP(x)\Rightarrow \exists y(Q(y) \lor R(y)))$

I am trying to show LHS equivalent to RHS however, but I am unsure on this specific example. Any help would be appreciated. $$\exists x((P(x) \land \lnot Q(x))\Rightarrow R(x)) \iff (\forall ...
1
vote
0answers
39 views

Truth value of a mathematical statement about circles?

Let $A$ be the set of circles in the plane with center $(0,0)$ and let $B$ be the set of circles in the plane with center $(-2,3)$. Furthermore, let $P(C_1,C_2)\colon C_1$ and $C_2$ have exactly one ...
1
vote
2answers
33 views

Find a logical predicate for some given conditions

I am trying to give an example of a predicate $P(x, y)$ such that $\exists x$ $\forall y$ $P(x, y)$ and $\forall y$ $\exists x$ $P(x, y)$ have different truth values. I am struggling to think of such ...
0
votes
1answer
29 views

Can First Order Logic identify that two variables are the same object?

Supposed I defined: $Px$ = $x$ is a person $Lxy$ = $x$ loves $y$ And I expressed that everyone loves someone: $$(∀x)(Px \implies (∃y)(Py ∧ Lxy))$$ However I want to formally exclude narcissists ...
3
votes
1answer
76 views

Does “Everyone loves all kittens” imply “Everyone loves a kitten”?

In my logic class, we explored whether various quantified statements implied others. We agreed that the statement "Everyone loves everyone" implies that "Everyone loves someone": $Px$ = $x$ is a ...
1
vote
1answer
35 views

Discrete Structures: Trying Correcting my Predicate Logic with the appropriate quantifiers

I am trying to correctly use predicate symbols and using the appropriate quantifiers were I have to write each English language statement in predicate logic and the domain is the whole word. $P(x)$ ...
0
votes
0answers
32 views

Adding Sentence Variables and Quantifiers to Formal Languages

I have been thinking about the following construction, and was contemplating investigating it for my undergraduate thesis: Let $L$ be a formal language, e.g. the set $\{x_1, x_2, \dots, \forall, ...
0
votes
0answers
15 views

How to use a predicate function when formalizing predicate propositions?

I've tried the following question from my maths assesment but not sure if I'm using the predicate, fool(p,t) correctly. Can anyone advise on if I'm using it ...
1
vote
2answers
62 views

for some or for all

The following text is from Velleman's How to Prove book from the reflexive closure section: According to the definition we gave in the last section, the ...
0
votes
0answers
26 views

Problems of Quantifiers

Translate the following natural language sentences to quantified statements. Then apply the negation on them so that no negation sign appears to the left of a quantifier. Then express the most ...
0
votes
2answers
40 views

Truth Value for Quantifier

What would be the truth value for the following two quantifiers if n and m are both integers? I have trouble proving each of these statements. I appreciate any help you can provide! a)   ...
3
votes
1answer
44 views

How to prove $(\forall x,y\in\mathbb{Z})(5\nmid xy\to(5\nmid x\land 5\nmid y))$

Question: Prove $x,y\in\mathbb{Z},\Bigl((5\nmid xy)\to(5\nmid x\land 5\nmid y)\Bigr)$ where $\forall a,b\in\mathbb{Z},\bigl((a\nmid b)\leftrightarrow(\forall k\in\mathbb{Z},b\neq ak)\bigr)$ and ...
0
votes
2answers
48 views

Order of logical quantifiers within a statement

I understand that the order of the quantifiers of a statement determine the truth value of statement. For example, $$\forall x \in \mathbb{R}, \exists y \in \mathbb{R}\ \text{such that}\ ...
1
vote
1answer
53 views

Quantifiers for mutually distinct variables

Okay, this is freaking me out, I'm going nuts. In a first-order condition with formula $\phi$ containing $x, y$ such as $\forall x\forall y . \phi$ I need to ensure that the second variable bound ...
0
votes
0answers
25 views

quantization of a discrete probability source

The alphabet of a memory less source is $A=\{-5,-3, -1, 0, 1, 3, 5\}$ with corresponding probabilities $\{0.05, 0.1, 0.1, 0.15, 0.05, 0.25, 0.3\}$. If I know that the source can be quantized ...
2
votes
2answers
108 views

Quantifier for “there is at most one”?

As "there is at least one" and "there is exactly one" both have their symbols, I wonder what is the common notation for "there is at most one"? By "common" I mean the desired notation can be used ...
2
votes
1answer
37 views

Prenex normal form of $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$

I have the statement $\neg \big(\forall x \ P(x) \vee \forall x \ Q(x) \big)$ and I have to write it in prenex normal form. First I use the second De Morgan law $\neg \big(\forall x \ P(x) \vee ...
1
vote
0answers
21 views

Universal Instantiation

I'm a bit confused about how Universal Instantiation works. I read that you shouldn't really plug in any value "a" for x in "For all x P(x)" unless a choice for "a" pops up in the givens but in the ...
2
votes
2answers
79 views

How do I show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are NOT logically equivalent?

Show that $\forall x \ P(x) \vee \forall x \ Q(x)$ and $\forall x (P(x) \vee Q(x))$ are not logically equivalent. Can someone give a hint?
1
vote
1answer
108 views

$P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations.

Suppose that the domain of the propositional function $P(x)$ consists of the integers -2, -1, 0, 1 and 2. Write out each of these propositions using disjunctions, conjunctions and negations. a) ...
2
votes
0answers
50 views

When does renaming bound variables require a fresh variable?

Suppose that $E_1$ and $E_2$ are two $\alpha$-equivalent first-order logic formulas (or $\lambda$-terms), and let $V$ be the set of all variables (free and bound) used in $E_1$ or $E_2$. Is it ...