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

learn more… | top users | synonyms

0
votes
0answers
10 views

proof of quantifier elimination in theory of real closed field/reals and existential quantifier over atomic formula

Standard proof of quantifier elimination for theory of real closed field/reals uses induction, as in Wikipedia article (http://en.wikipedia.org/wiki/Quantifier_elimination#Basic_ideas). However, it ...
5
votes
2answers
63 views

Alternate translation for: “Every real number except zero has a multiplicative inverse.”

A given text states, “Every real number except zero has a multiplicative inverse" (where mul- tiplicative inverse of a real number x is a real number y such that xy = 1). It offers the following ...
0
votes
1answer
50 views

Existential introduction - required or not?

Consider a theory $T$ in first order logic, and a formula $C$. If there exist a proof of $C$, and that all formulas in $T$ and $C$, none of them contains $\exists$. The question is: does there always ...
1
vote
1answer
53 views

Use of prime symbol in proof writing

Questions: So I looked through my course notes and saw this proof. I understand the content, but I'm confused about the use of the prime symbol. If we say that there is some $j'$ such that it is a ...
0
votes
0answers
31 views

Compare $(\exists x)(\forall y) x\geq y$ and $(\forall y)(\exists x)x\geq y$ [duplicate]

There exists an $x$, for every $y$ such that $x\geq y$ How is this false and this next statement true? For every $y$, there is an $x$, such that $x\geq y$ How is this true?
0
votes
1answer
42 views

Quantifier question?

How would I do the following quantifier and their negation No one loves everybody. or could you say : everybody does not love someone? x is all people So in symbolic this would be $\forall x, ...
1
vote
1answer
35 views

Quantifiers bind tightly?

Is this true that it is a commonly agreed rule that $\forall x\in A:P(x) \wedge Q$ and $\forall x\in A:P(x) \Rightarrow Q$ should be interpreted correspondingly as $(\forall x\in A:P(x)) \wedge Q$ and ...
1
vote
1answer
37 views

More questions on quantifiers

I have the following questions: Write the following statements in more abbreviated form, using quantifiers. Here the short phrases “is prime” and “is a line” are allowed, and the symbol $\Pi$ may be ...
0
votes
3answers
37 views

Translating a sentence into a logical expression.

I am having trouble understanding the solution given for a problem in my discrete mathematics text book. Any help would be much appreciated. Question: Let L(x, y) be the statement "x loves y", where ...
3
votes
1answer
76 views

Semantics and Logical structure in Definitons

Continuation of Free and bound variables in "if" statements definitions: A number is even if it is divisible by $2$. The number is even if it is divisible by $2$. Is the usage of the ...
2
votes
2answers
44 views

Free and bound variables in “if” statements

The assertion $x>2$ is true when we replace $x$ by a number greater than $2$($3$ for example) and false if we replace it by $1$. But the assertion $\forall x(x>2)$ is false. In the first case ...
1
vote
1answer
41 views

Logical structure of definitions

Here are some "concepts" that are confusing me: The assertion $x>2$ is true when we replace $x$ by a number greater than $2$($3$ for example) and false if we replace it by $1$. But the assertion ...
2
votes
4answers
103 views

$\exists \implies \forall$

I want to see some example theorem, when existence implies universality, so $\exists \implies \forall$ is true. I think matematical induction is a related technique, but I just don't see that ...
3
votes
1answer
61 views

Prove $\neg\exists x \neg P(x)$ is a logical consequence of $\forall x P(x)$

How would you prove that 2. is a logical consequence of 1. using a Fitch style proof? $\forall x P(x)$ $\neg\exists x \neg P(x)$
1
vote
4answers
418 views

Proof of Drinker paradox [duplicate]

I searched all over the internet but didn't find a formal proof for this paradox, so here is my attempt: $\exists x[P(x)\implies \forall yP(y)]$ Let $x=x_0$. Thus $P(x_0)$ is given. Let $y$ be ...
2
votes
1answer
24 views

Sets and Quantifiers

I have difficulty converting sentences into 'mathematical language'. According to my work above ...
3
votes
3answers
62 views

Truth set of a Universal Quantifier and Family of sets

The definition of an intersection of family($F$) is: $$\cap F=\bigl\{x\mid\forall A(A\in F \implies x\in A)\bigr\} $$ If my understanding serves me correctly this notation means that all the $x$ ...
3
votes
1answer
71 views

Definition of intersection of a family of sets

The definition of an intersection of family($F$) is: $$\cap F=\bigl\{x\mid\forall A: (A\in F \implies x\in A)\bigr\} $$ If my understanding serves me correctly this notation means that all the $x$ ...
1
vote
1answer
27 views

Set Theory Elementhood Notation

From How to Prove it: Given $A=\{n^2|n \in N\}$ where $N$ is the set of all natural numbers. I want to express A in terms of elementhood test notation. Velleman says $A=\{x| \exists n \in N ...
3
votes
5answers
86 views

Difference between bound and free variable

What is the difference between $\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$ I know in the first one the variable x is bound but in the second one the variable is free. What are the ...
1
vote
1answer
28 views

Quantifiers and negation range

Hello people I have a simple question. I have this formula from which I need to remove all the implications. Here it is. $\forall x ( [ Roman(x) \wedge know ( x, Marcus )] \rightarrow [ hate (x, ...
1
vote
1answer
96 views

Symbolic logic proof

Can any one please give me the correct proof for this, i got this far but i am stuck. Thank you!
1
vote
1answer
13 views

Simple proof with quantifiers. Help me understand.

I have to negate $$ \forall x \in \mathbb{Z} \space \exists y \in \mathbb{Z} \space (( x \ge y) \land (x + y = 0)) $$ and prove either the original proposition or negation is true. I get the ...
3
votes
3answers
83 views

Domain of discourse and quantifying in predicate logic

I am struggling with an idea about how quantifiers relate to domains of discourse. Given a statement "$x$ is divisible by $2$" represented by the predicate $D(x)$,the predicate currently has no truth ...
1
vote
1answer
49 views

Is there way to classify the quantifier rank $m$ first order sentence in first order logic

In its simplest situation, for example, if the signature contains only a binary relation $\sigma$, so the signature $\tau = \{ \sigma \}$, what are the inequivalent classes of all first order ...
1
vote
0answers
21 views

Semantics and expressive power of generic element quantifiers

In real analysis (and other applications like the graph-theoretic structural approach to sparse matrices), it would sometimes be convenient to quantify over all generic elements. A generic element ...
2
votes
2answers
53 views

Commutivity of unique existence quantifiers

Find an expression P(x,y) to disprove the following equivalence, $(\exists!x)(\exists!y)P(x,y)\Leftrightarrow(\exists!y)(\exists!x)P(x,y)$ I could only think of a few statements of $P(x,y)$ that ...
0
votes
1answer
44 views

General conceptual confusion relating to vacuous proofs and quantifier help

I need to prove the statement: Let $x \in \mathbb{R}$. Prove that $1 \le x \le 2$ if and only if $1 \le x \le 1+ 1/n$ for some $n \in \mathbb{N}$. So I start with the forward implication: If $1 ≤ ...
1
vote
1answer
64 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that ...
1
vote
1answer
46 views

How is a quantifier-free formula actually interpreted?

My understanding is that a quantifier-free formula in FOL is simply a formula that contains no quantifiers, just possibly free variables. How is such a formula interpreted? My understanding is that if ...
1
vote
3answers
106 views

What is the difference between these two propositions? [duplicate]

My text says: Let Evens be the set of even integers greater than 2, and let Primes be the set of primes. Then we can write Goldbach’s Conjecture in logic notation as follows: $ \forall n \in ...
0
votes
2answers
48 views

Stuck on a quantifier logic problem

I've been trying to prove this to no avail.. $\vdash\exists x(Px\rightarrow\forall xPx)$ The book gives a hint.. that it might be helpful to prove the following two before tackling the main problem: ...
0
votes
1answer
31 views

Explanation of ordering of quantifiers in Real Analysis

Why is the second part where the quantifiers are interchanged false? Is there a concrete example for this?
0
votes
2answers
56 views

Equivalent logical quantifier statements?

I was doing an exercise that said convert the statement "Jane saw a police officer, and Rodger saw one too" into the logical equivalent using quantifiers. My answer was: $$ \exists x(P(x)\implies ...
1
vote
2answers
58 views

Logical Quantifiers

I am wondering if there is a reference or book that clearly translates all English forms of logical quantifiers to mathematical quantifiers. For example, when we say for any element $ x \in S$, is ...
0
votes
1answer
23 views

Predicate logic describing a function that is not onto.

I'm trying to understand how to write predicate logic describing a function that is not onto. A function is onto if every element in the codomain gets mapped to by some element in the domain using ...
1
vote
1answer
52 views

How to disjunct $\forall x.(P(x) \lor Q(x)) $

I really don't understand how to disjunct this. The whole argument is: $$\forall x.[P(x) \lor Q(x)] \rightarrow \neg[\exists x.P(x)] \rightarrow \forall x. Q(x) $$ Am I supposed to use the ...
1
vote
1answer
107 views

Prove $\forall x~\forall y~\forall z (x+y)+z=x+(y+z), \forall x~\forall~y\exists z~ x=y+z, \forall x~\forall z \exists y x=y+z ⊢ ∃y∀x x+y=x$

I need help using the standard rules of predicate logic with quantifiers to prove $~\forall x~\forall y~\forall z ~~(x+y)+z=x+(y+z), ~\forall x~\forall y~\exists z ~~x=y+z, ~\forall x~\forall z~ ...
0
votes
3answers
40 views

Interpretation of quantifiers

While studying quantifiers I got all confused with the following explanation about the order of quantifiers. The statement ∀x ∃y, y > x claims that, for any real number x, there is a number y ...
2
votes
1answer
53 views

How do I use rules of inferences to imply a conclusion from 4 premises?

I am a little confused on how to use 4 premises to prove a conclusion. Can you please tell me if my logic is sound for the following proof: ...
1
vote
2answers
84 views

Are the following statements correctly translated?

Using predicate symbols shown below and appropriate quantifiers, write each English language statement as a predicate wff. Domain is all the objects in world. B(x) : x is a bee F(x) : x is a ...
2
votes
1answer
43 views

negation a logical statement/sentence with quantifier without universe of discourse

For example, $(\exists x) \,\,\forall y \in Y \,\, P(x,y)$. Here $\exists x$ does not have universe of discourse . In this case, can normal rule for negating the sentence/statement still be used? ...
1
vote
2answers
79 views

Question about quantifier logic

This is my first post on the mathematics stack exchange so please bear with me.. I am new to quantifier logic and I just can't seem to wrap my head around it. I have been given four statements and I ...
1
vote
3answers
69 views

Using quantifiers to express this sentence.

These are from a study guide, just checking my work. Let $F(x,y)$ be the statement "$x$ and $y$ are friends." where the domains consists of all people in the class. Use quantifiers to express the ...
3
votes
3answers
99 views

Why negating universal quantifier gives existential quantifier?

Negating a universal quantifier gives the existential quantifier, and vice versa: $\neg \forall x = \exists x \\ \neg \exists x = \forall x$ Why is this, and is there a proof for it (is it even ...
0
votes
4answers
75 views

$\lnot \exists x (\forall y (\alpha)\land \forall z(\beta) )\;$ is logically equivalent to which one of these?

These are the options: $\forall x(\exists z(\lnot \beta)\rightarrow \forall y(\alpha))$ $\forall x(\forall z(\beta)\to \exists y(\lnot\alpha))$ $\forall x(\forall y(\alpha)\to \exists z(\lnot ...
0
votes
4answers
85 views

Get rid of an existential quantifier

I have to remove the existential quantifier from the following formula: $$\exists i\left[\left(i \geq 0\right) \land \left(z-2i = 0\right) \land \left(y+i=x\right)\right]$$ First I make some simple ...
0
votes
1answer
17 views

Proving formally

$((\exists x : X.P) \Rightarrow (\forall x: X.Q)) \vdash (\forall x: X. PvQ) \Rightarrow((\forall x: X.P) \vee(\forall x: X. Q)$ exist stands for the existential quantifier all stands for for-all ...
0
votes
2answers
69 views

Sets and quantifiers question

Am I doing this correctly? Let S be a non-empty set, and let P(x) and Q(x) be open sentences that can be applied to any x∈S. For each of the following implications, determine whether or not it is ...
1
vote
1answer
117 views

∀x ∀y Q(x; y) What is the meaning

What is the meaning of ∀x ∀y Q(x; y)? Does this mean that: For all values of X every value of Y will satisfy Q(x;y)? so if Q(x;y) = x + y = x * 2 in this case ∀x ∀y Q(x; y) would be false? ...