Questions concerning predicate calculus, i.e. the logic of quantifiers.

learn more… | top users | synonyms

2
votes
1answer
23 views

Uniform Continuity implies Continuity

Let $f$ be a function from a metric space $X$ to a metric space $Y$. Show that if $f$ is uniformly continuous on $X$ then $f$ is continuous on $X$. Show that the converse is not true. Uniform ...
1
vote
3answers
48 views

Distribution of universal quantifiers over implication

I want to prove that $∀x(φ(x)⟹ψ(x))$ implies $∀x(φ(x))⟹∀x(ψ(x))$. I read they are not equivalent, but I am not sure why. I tried the following: $∀x(φ(x)⟹ψ(x))$ $⟹[φ(a)⟹ψ(a)]$ is true. $⟹φ(a)$ is ...
2
votes
2answers
34 views

Inference in Predicate Logic

I have stumbled upon the following reasoning, but I'm not sure if it's correct. Here it goes: Domain X $\forall x :\phi(x)⟹\gamma(x)$ Let $E\subseteq X⟹[\forall x\in E :\phi(x)⟹\gamma(x)]$ Suppose I ...
1
vote
2answers
33 views

Predicate logic inference in a simple proof of uniform continuity.

For a function $f$ from a metric space $X$ into a metric space $Y$, uniform continuity can defined in this way: $\forall ε>0:\existsδ > 0:\forall p,q\in X:d_{X}(p,q)<δ \rightarrow ...
0
votes
1answer
20 views

Free and bound variables in quantificational logic

I'm solving exercise 3 in page 63 of the book "How to prove it" by Daniel J. Velleman. I don't know if my solutions are correct so I post those solutions here and want you to tell me if I'm correct, ...
1
vote
1answer
42 views

Set-builder Notation

In set-builder notation we describe a set in the following way: $A=\left\{x:\phi (x)\right\}$ Is it correct to say the following? Fix any $x_{0}\in X$ Evaluate the predicate $\phi(x_{0})$ ...
0
votes
1answer
19 views

Proof of equivalent formulas

I've been working on proving equivalent formulas using equivalences in predicate logic however I'm stuck trying to prove that these two formulas are equivalent: $ \forall x (A(x) \Rightarrow \exists ...
0
votes
2answers
32 views

How do you write the following set in predicate form? [on hold]

How do you write the set $$\left\{−\frac32, \frac94, −\frac{27}{6}, \frac{81}8, \ldots \right\}$$ in a predicate form?
0
votes
3answers
27 views

Logic quantifier position nuances

I've been learning about translating English to logic and vice versa and I have to say that I find this quite difficult. On a paper that I'm examining , I've across the following logic formula: ...
-4
votes
0answers
40 views

Which one of the following well formed formula is a tautology?

Which one of the following well formed formula is a tautology? (a) $\forall x \, \exists y \, R(x, y) \equiv \exists y \, \forall x \,R(x, y)$ (b) $\left[\forall x \, \exists y \,(R(x, y) \implies ...
0
votes
1answer
47 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?
4
votes
1answer
52 views

Question on the proof of completeness theorem

We want to prove the model existence lemma: $\mathcal{\varGamma}$ is a consistent set of $\mathcal{L}$-sentences $\Leftrightarrow$ $\mathcal{\varGamma}$ has a model. In the Henkin-style proof, we ...
2
votes
2answers
49 views

Distribution of universal quantifier with free variables.

My question is regarding the validity of the following statement: $$ (\forall a (\phi \implies \psi)) \equiv (\phi \implies \forall a \psi ),$$ provided, of course, there are no free occurrences of ...
0
votes
1answer
73 views

Proof of deduction theorem without induction

Can we prove deduction theorem without using inductive argument. Using MP and following axiom schema: 1) A⇒(B⇒ A) 2) [A⇒(B⇒C)]⇒[(A⇒B)⇒(A⇒C)]
1
vote
0answers
29 views

Predicate logic a game where player goes first?

What kind of predicate logic statement describes a game that the person who goes first can always win? Write you answer in terms of successive moves by two players. I am lost here I tried initially ...
0
votes
3answers
75 views

Logically equivalent formulas and contradiction

$\lnot A \Rightarrow A$ , is a contradiction. But $\lnot A \Rightarrow A$ is logically equivalent to $A\lor A$. Does it mean that $A\lor A$ always give contradiction?
4
votes
0answers
71 views

Can all axioms of mathematical theories be expressed with predicate logic?

The book Roads to Infinity: The Mathematics of Truth and Proof stated that, "All the standard mathematical theories have axioms that can be expressed in predicate logic." Predicate logic generally ...
1
vote
1answer
26 views

Predicate logic with negation “not”

I've really confused myself here: $$ P(x) = ``\text{x has a tail}" $$ How would I write: $$ ``\text{Not everything has a tail}" $$ would it: $$ ¬∀x P(x) $$ be correct?
-1
votes
0answers
20 views

Identity Substitution in Polyadic Singular Sentences

Let the sentence "Yash loves Priya" be symbolized as Lyp. Let the sentence "Priya is Dr.Lingnurkar" be symbolized as p=l. The identity substitution rule is a=b,ϕa,/∴ϕb. In my textbook, ...
1
vote
1answer
36 views

$\kappa$-categoricity in the language of identity

I have the following exercise from Dirk Van Dalen's Logic and Structure: Here with language of identity we mean the language with no extralogical symbols (i.e. no symbols of predicates, functions ...
0
votes
1answer
40 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?
-1
votes
0answers
37 views

Universum, interpretation few question.

i have few questin about predicate logic and interpretation : I have formula like this: 1) $(\forall x: \neg p(x) \vee q(x)) \Leftrightarrow \neg (p(x) \wedge q(x))$ No i must choose is either of ...
0
votes
1answer
28 views

Satisfiable formula only over even structares

In First order Logics, what formula can I cook up, that's satisfiable over all even structures, and only even structures. (even structure means it has an even number of elements in its domain).
0
votes
1answer
28 views

Show that $[(P→Q)∧P)]→Q$ is a tautology using rules of replacement

Show that $[(P→Q)∧P)]→Q$ is a tautology using rules of replacement I've done this so far, from $[(P→Q)∧P)]→Q$ to $[(~P∧Q)∧P)]→Q$ by Mat. Imp. to $[P∧(~P∧Q))]→Q$ by Commutation. After that ...
0
votes
0answers
32 views

Skolem normal form - difference form different thinking?

i found two tutorials which transfer this formula to Skolem form: $\forall x \exists y: \neg p(x,y) \vee \forall w \exists z: p(w,z)$ First case 1: $\forall x \exists y: \neg p(x,y) \vee \forall w ...
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 ...
0
votes
0answers
10 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
2
votes
2answers
72 views

How to translate set propositions involving power sets and cartesian products, into first-order logic statements?

As seen from an earlier question of mine one can translate between set algebra and logic, as long as they speak about elements (a named set A is the same as {x ∣ x ∈ A}). However I've stumbled upon ...
1
vote
2answers
29 views

Confused on negation?

My textbook has the following (see Page 8 of Eccles's An Introduction to Mathematical Reasoning): Consider the following statement about a polynomial $f(x)$ with real coefficients, such as $x^2 + ...
0
votes
4answers
74 views

Proof to be tautology

$\forall x : (p(x) \wedge \neg q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)$ The problem is: i know this is tautology but i don;t know how to proof it. Is anybody can help me?
1
vote
2answers
58 views

Can I prove set propositions using first-order logic?

I'm studying logic and sets and I have to say there's a strong similarity between the two. Most boolean/logic axioms also apply to sets. At the end of my course I also studied first-order logic (or ...
1
vote
2answers
30 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
2answers
36 views

Another basic Logic Question

Translate this statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the domain consists of all people. a) ∀x(C(x) → F(x)) The answer given in the book is:"Every ...
0
votes
1answer
55 views

Very Basic Logic Question

Given a set $S=\{-1,0,-5,-4\}$.Then is the following proposition true? $\forall x, (x>0 \implies x^2>0)$.
2
votes
2answers
53 views

Predicate logic by resolution

I've been trying to study logic lately, as part of my AI course, and I've been going through some old, simple exam questions from my school. There is one question about resolution in particular that I ...
-1
votes
1answer
16 views

$\{(\forall(x))P(x) \implies(\forall(x))Q(x)\} \implies (\forall(x))(P(x) \implies Q(x))$

$(\forall(x))(P(x) \implies Q(x)) \implies \{(\forall(x))P(x) \implies (\forall(x))Q(x) \}$ why this is not valid and how the converse of this is valid?
1
vote
1answer
30 views

Finite extension of decidable theory is decidable

Exactly what it says on the tin. I'm trying to prove that if T2 is a finite extension of decidable theory T1, then T2 is decidable.
2
votes
2answers
61 views

Explanation on the symmetry between identity axiom and cut rule

In Proofs And Types at the beginning of 5.1.4 Girard says that the identity axiom is somewhat complementary to the cut rule, more specifically 'The identity axiom says that $C$ (on the left) is ...
1
vote
1answer
60 views

Introduction to Symbolic Logic: 'Understanding Symbolic Logic, 2nd Edition,' by Virginia Klenk, Page 294

I read this passage in my textbook: ...if there is a counterexample in a domain with $m$ individuals, then there is also a counterexample in all larger domains. It follows by contraposition (and ...
2
votes
1answer
32 views

Semi decision procedures for Peano arithmetic?

Is there an efficient semi-decision procedure (i.e. an algorithm that sometimes works and sometimes not) for -at least- elementary problems in peano arithmetic? I am not talking about weak fragments ...
2
votes
3answers
91 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 ...
1
vote
1answer
21 views

Using predicate logic to see if P(X) holds

Suppose We have a set called ${A}$ and we let it equal to $A = \{a \in \mathbb{Z} \mid a^2 = 3\}$ and we let ${P(x)}$ be the predicate ${x \in \mathbb{Z} }$ Problems: 1.) ${\forall x \in A }, P(x)$ ...
0
votes
0answers
16 views

Convert integer based ranking system into trueskill

I have an existing ranking system with 16 individual ranks, numbered from 1-16. These ranks are accurate (although extremely imprecise). As in, a rank 14 will almost always beat a rank 12 or below, ...
2
votes
2answers
42 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 ...
0
votes
0answers
72 views

Determining a suitable universe of discourse

The question is this: Question: Identify a suitable universe of discourse such that the predicate z2 + 4 = 0 has existential import. Now if you try to factor this equation, you will see that it is ...
12
votes
1answer
177 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
2
votes
2answers
55 views

Finite fields properties

I had to solve a question in Logics, disprove the fact that "if two statements without free variables are satisfiable in the same finite structures, then they are logically equivalent". The only ...
3
votes
1answer
45 views

How to show that a logical argument is valid?

How to show that this argument is valid? $(\exists x) [p(x) \to q(x)] \to [(\forall x) p(x) \to (\exists x) q(x)]$ I started by showing that $\exists$x [p(x) $\to$ q(x)] is the premise. But I ...
0
votes
2answers
41 views

confusion about 2 first order logic wff's - they seem not equal, but instructor says they are =

I had a question about two first order logic formulas given in this lecture in the series on Discrete Mathematical Structures from IIT. The instructor says (at 36:19 in the video) that the ...
1
vote
1answer
44 views

$(Ǝx)H(x) \dashv \vdash (Ǝy)H(y)$?

I can prove the statement using the natural deduction, but I keep getting confused about this sequent, so it would be very thankful if someone can help me to understand this concept of predicate ...