1
vote
1answer
23 views

Why is Skolem normal form equisatisfiable while the second order form equivalent?

I asked in another question when is it appropriate to de-Skolemize a statement. The answer, I'm not sure I'm satisfied with yet, relies on a second order logical equivelance, but Skolem normal form ...
0
votes
1answer
41 views

Universe of discourse in $A \subseteq B$

In the following logical analysis: $A \subseteq B $ $\forall x(x \in A \implies x \in B)$ Is the universe of discourse for the above logical form is A since the ...
0
votes
1answer
25 views

Clarification regarding bound variables and quantifiers

I have been working on one of the problem like this: $ x \in \wp(A \cap B) $ $ x \subseteq (A \cap B) $ $ \forall y (y \in x \implies y \in (A \cap B)) $ $ \forall y (y \in x \implies y \in A ...
4
votes
2answers
47 views

When is de-Skolemizing statements appropriate?

In first order logic we often convert prenex normal form statements to Skolem normal form statements to eliminate the existential quantifier: $\exists$x$\forall$y$\exists$z$\phi$(x,y,z) becomes ...
1
vote
1answer
35 views

Second order universal quantifier elimination restriction

Dirk van Dalen in his Logic and Structure gives following universal elimination rule: from $\forall_{X^n} \phi$ infer $\phi^*$ where $\phi^*$ is $\phi$ in which every occurence of $X^n(t_1, ..., ...
0
votes
4answers
50 views

Solving $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$

I have been solving this problem from Velleman's How to prove book: $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$ This is my ...
0
votes
1answer
24 views

Set of all perfect squares

I have been going through Velleman's How to prove book and they have explained the set of all perfect squares using this set: $S = \{ n^2 | n \in N\}$ Then it is ...
0
votes
1answer
24 views

Bounded quantifier and it's meaning

It's explained in Velleman's how to prove book that $\exists x \in AP(x)$ means that there is at least one value of x in the set A such that P(x) is true. Then ...
1
vote
2answers
24 views

Proving the Truth Value of Quantified Statements

I would like to know an efficient way of disproving existential quantifier ∃ to show that "for every value of a P(a) is false." ? Also, proving universal quantifier ∀ to show that "for every a, P(a) ...
0
votes
1answer
17 views

Simple Question on Quantifier Logic [closed]

is this a valid implication: $(\forall\epsilon>0.\exists x\in A.x>a-\epsilon)\implies(\forall\beta\epsilon>0.\exists \beta x\in \beta A.\beta x>\beta a-\beta\epsilon) $ $,\beta>0$
0
votes
1answer
51 views

Analyzing logical form of ∀x∀yM(x, y)

I have been going through Velleman's How to prove book and in one of their sample problems they have used ∀x∀yM(x, y) for ...
1
vote
1answer
71 views

Find a universe for variables x, y, and z for which the statement is true and another universe in which it is false.

Find a universe for variables $x, y$, and $z$ for which the statement $∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y)))$ is true and another universe in which it is false. Is there a more ...
1
vote
1answer
63 views

Use predicates and quantifiers to express this statement.

“Some students in this class grew up in the same town as exactly one other student in this class." I'm thinking there is a relation T(x,y) where the student x grew up the same town as student y. And ...
0
votes
2answers
49 views

Trying to understand negation of quantifiers

Trying to understand the negation of the following: For this: ∀x~P(x) I have this as negation: ~∃xP(x) For this: ~∃x(∀yP(y) Λ Q(x)) I have this: ∀x(~∃yP(y) V ~Q(x)) Are these correct? If not please ...
1
vote
1answer
83 views

Proof using existential quantifier [closed]

Prove: $$\begin{align} \exists x ~:~ \bigg(p(x) &\rightarrow q(x)\bigg) \ How do I go about proving this? Can I distribute the existential quantifier in the first term?
0
votes
0answers
28 views

Existential quantifier with implication/conjunction as a Venn diagram?

I'm having trouble visualizing the following statements in a Venn diagram: $$\exists x\in D, Q(x) \implies P(x) $$ $$\exists x\in D, Q(x) \wedge P(x) $$ For the first statement, does it look like ...
0
votes
1answer
44 views

Proving property for all predicates in first order logic

Let's consider language with predicate $P$ and following derivation $${{{[P[a/x]]^1} \over {P[a/x] \rightarrow P[a/x]}}\rightarrow I^1 \over {\forall_x (P(x) \rightarrow P(x))}}\forall I$$ Doesn't ...
0
votes
4answers
84 views

Translate these statements into English

Translate the following statements into English, where $C(x)$ means '$x$ is a comedian', $F(x)$ means '$x$ is funny' and the domain consists of all people: a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x)) c) ...
0
votes
2answers
58 views

How to prove that for all $x$ there exists some $y$ where $ (x^2 + y^2 \geq 0)$?

How can I prove that $\forall \,\,x\,\,\exists y\,\,,(x^2 + y^2 \geq 0)$?
2
votes
1answer
70 views

Predicate logic proof problem

Where the domain of the variables are Real Numbers, determine the truth value for the following: $$ \forall x \exists y(y^2-x<200) $$ I don't understand how to formally prove this problem. Since ...
1
vote
2answers
59 views

How to prove that we can switch two $\forall$?

This is true? See a simple proof (High-school level) Thanks e.g: $$\forall x, \forall y\;P\;\text{is true}. \iff \forall y,\forall x\;\text{P is true}$$
0
votes
1answer
30 views

Understanding triple mixed quantifiers

I'm having a hard time understanding mixed quantifiers of this form: $$\forall x\exists y\forall z(...)$$ and similarly $$\exists x\forall y\exists z(...)$$ It really hurts my head to think about ...
0
votes
1answer
35 views

What is the difference between these two logical expressions?

I'm reading our lecturers recitations, and the lecturer remarked some comment that confuses me. Consider the expression $\exists !x:P(x)$, where $P$ is some predicate. This expresses the existence ...
1
vote
2answers
31 views

Order of parameters in quantified predicates

I'm studying up for my midterm in Discrete Math and I've been looking at sample questions and their solutions. There is one I don't really understand and I was hoping someone could help me out. ...
1
vote
1answer
25 views

Equivalence of Quantified Predicates

I'm in Discrete Math and I copied down some rules in my notes. Unfortunately I'm not sure if I made a typo or not, let me show you what I mean. Equivalence of Quantified Predicates Symmetry of 'All' ...
0
votes
1answer
25 views

How to formulate this logic formula

The problem setting is very simple. Suppose we have three variables x, y and z and a constraints C/3 predicate that is satisfied by the three variables C(x,y,z), but C/3 might not be the only ...
2
votes
1answer
65 views

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$

Express $\forall n \in \mathbb N$, $\exists m \in \mathbb N$, $n^4 = m^2$ in words without using the symbol $\mathbb N$. My Solution: For all $n$ that is an element of Natural number there is ...
1
vote
2answers
26 views

Logic question is it true

Exercise: $$\begin{align} (\forall x>2) &~:~ |x|<3 \tag{P1}\\ (\forall x\in\mathbb{R})(\exists\varepsilon > 0) &~:~-\varepsilon <x<\varepsilon \tag{P2}\\ (\forall ...
1
vote
3answers
75 views

Prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ using natural deduction

I want to prove $\exists_x(\phi(x) \rightarrow \psi) \iff (\forall_x\phi(x) \rightarrow \psi)$ where $x \notin FV(\psi)$ using natural deduction method. I was able to prove implication from left to ...
0
votes
0answers
34 views

How can I represent these discrete math statements with predicates and quantifiers?

Use the predicate $A(x, y)$ that denotes ("$x$ loves $y$") Someone loves a person who loves everyone. Everyone loves someone who is loved by someone. I know I need to use nested universal and ...
0
votes
0answers
42 views

Logical Notations for Descriptive Mathematical Statements

I'm studying Discrete mathematics and I'm faced with a problem of converting a descriptive mathematical statements into logical notation. Any help would be appreciated. Thank you. a). Any integer ...
1
vote
1answer
37 views

Analyzing Set of all Perfect squares

I have been reading Velleman's How to Prove book and the following statement in the book confuses me: For example, suppose we wanted to define S to be the set of ...
1
vote
0answers
40 views

Interpreting logical forms involving quantifiers

I have been trying to translate these two logical form into English statements without using any quantifier laws: (a) ∃x∀y ¬L(x,y) (b) ¬(∃x∀y L(x,y)) where ...
0
votes
2answers
112 views

Expressing statements in positive way

I have been working on this problem from Velleman's How to prove book: Negate these statements and then reexpress the results as equivalent positive ...
0
votes
2answers
60 views

Why does the author define these “logical notations” for set logic with “if then” and &?

In Section 1.1 of "Set Theory for Computer Science", the author defines $ \forall x \in X. P(x) $ and $ \exists x \in X.P(x) $ as shorthand for $ \forall x.(x \in X \Rightarrow P(x)) $ and $ \exists ...
2
votes
1answer
55 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
86 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
91 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
502 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
50 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
93 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
33 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
76 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
38 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
55 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
41 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
61 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
28 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
85 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
50 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 ...