2
votes
1answer
39 views

Deciding between implication and conjunction

This is one of the solved problems in Velleman's How to prove book: Analyze the logical forms of the following statements: 1) John likes exactly one person. ...
2
votes
4answers
74 views

Analyzing the logical form of “All married couples fight”

This is one of the example problems in Velleman's How to Prove book: Analyze the logical forms of the following statements. All married couples have ...
0
votes
2answers
43 views

Concluding Truth Value from Universe of Discourse

I have been working on the following problem from Velleman's How to Prove book: Are these statements true or false? The universe of discourse is the set of ...
3
votes
3answers
436 views

Idiomatic mathematical english statement for ∃x[P(x) ∧ ∀y(P(y) → y ≤ x)]

I have been working on problems from Velleman's How to Prove book and hit upon the following problem: Translate the following statements into idiomatic ...
0
votes
2answers
41 views

Questions regarding Universal Quantifiers

The question is to show that: $$\exists x:(P(x) \implies Q(x))\qquad\equiv\qquad\forall x:P(x) \implies \exists x:Q(x)$$ First I use double negation to get to the universal quantifier since it ...
0
votes
2answers
85 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
0
votes
1answer
20 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
0
votes
0answers
64 views

Relation between existential and universal quantificator in category theory

Let $\mathscr C$ be a cartesian (i.e. with finite limits) category with subobject classifier $\Omega$ and generic subobject $\tau:I\to\Omega$ (here $I$ denote the terminal object). Let $f:X\to Y$ and ...
0
votes
1answer
32 views

Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$ I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P ...
1
vote
0answers
50 views

Universal and Existential Quantifiers

Are there any examples of a predicate P(x ) of a variable x such that the truth value of P(x) remains invariant under exchange of the Universal Quantifier ∀ and the Existential Quantifier ∃ -thanks
2
votes
2answers
39 views

Definition and decidability of bounded quantifiers

Consider quantifier-free formulas $P(x,y) = Q(x,y)$ of Peano arithmetic. Consider $P(x,y),Q(x,y)$ to be terms composed of variables $x,y, \operatorname{succ}, +, \times$. Note that these are ...
1
vote
1answer
58 views

Can universal instantiation be used more than once?

I'm trying to follow a proof in a logic text and it seems like the author used universal instantiation twice to reach the needed result. I was under the impression that you could only use UI one time ...
0
votes
0answers
23 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
66 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 ...
1
vote
1answer
42 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
39 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
81 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
45 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
45 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
106 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
430 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 ...
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
73 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$ ...
3
votes
5answers
93 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
99 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!
3
votes
3answers
89 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
51 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 ...
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 ...
1
vote
1answer
69 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
3answers
108 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
2answers
63 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
61 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
24 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
114 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~ ...
2
votes
1answer
57 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
88 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
83 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
71 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 ...
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
90 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
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
122 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? ...
2
votes
2answers
114 views

What is the purpose of universal quantifier?

The universal generalization rule of predicate logic says that whenever formula M(x) is valid for its free variable x, we can ...
0
votes
2answers
148 views

Translations from English to predicate logic, using quantifiers.

Let "book" be the set of all books and "Author" be the set of all authors. $\in$ denotes set membership. Consider the following predicates: short(x) is a predicate indicating x is a short book. ...
3
votes
2answers
106 views

Skolemization of a Formula

I have the following formula: forall x(p(x) <- exists y q(y,x)) What is the Skolemization of the above formula?
3
votes
2answers
41 views

Meaning of duplicated predicate quantifiers

What is the meaning of duplicated predicate quantifiers? Examples: $$ ∃x\ ∃x\ ∀x\ ∀x\ P(xy) \\ ∀y\ ∀x\ ∃x\ ∀x\ ∃x\ ∃y\ ∃x\ P(xy) \\ ∃y\ ∀y\ ∀x\ ∃x\ ∃y\ ∀y\ ∀x\ ∃x\ ∃x\ P(xy) $$