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

learn more… | top users | synonyms

0
votes
0answers
25 views

Predicate logic: Natural deduction exercise

I have the following logical formula to be proved by natural deduction rules for the predicate logic: $(x = 0) ∨ ((x + x) > 0) \vdash (y = (x + x)) \to ((y > 0) ∨ (y = (0 + x)))$ I am very ...
0
votes
4answers
67 views

Having hard time understanding implies

$P \Rightarrow Q$ I am having hard time understanding the second and third rows in the truth table. Implies means use if than, but the third statement is confusing. $P$ : Tesla Model S is a fast ...
1
vote
2answers
88 views
+100

How can I indicate that n and k are natural numbers in ∀n[(∀k < n P(k)) → P(n)].

$∀\, x \, \{x\in\mathbb N\rightarrow P(x)\}$ can be abbreviated to $∀ \hspace{.1cm} x∈ℕ[P(x)].$ But, I am not sure how I can indicate "concisely" that n and k are natural numbers in ∀n[(∀k < n ...
1
vote
1answer
13 views

In predicate logic, all $x$ in set $X$ who have quality A also have quality B

How do I convert the premise that all $x$ in set $X$ for which $A$ is true $\implies B$ is also true the main part where I am having trouble finding examples is "all $x$ in set $X$ for which $A$ is ...
0
votes
0answers
60 views

How to convert formulas to rectified prenex form?

I'm preparing to an exam and I haven't understood this question: Convert the following formulas into rectified prenex form: a) $F = (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z)) ...
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 ...
0
votes
0answers
29 views

If a variable does not exist is it bound?

I've been doing Logic equivalences questions and I've been taught that a variable $x$ is bound if it is under any quantifier such as $ \exists $ or $ \forall$ however I've come across a question where ...
1
vote
2answers
35 views

difference between some terminologies in logics

$$1) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, \alpha_k\vdash\alpha $$ Is a valid sequesnt. $$2) \alpha_1,\alpha_2,\alpha_3.......\alpha_{k-2}, \alpha_{k-1}, ...
-1
votes
1answer
47 views

How to reason with Equisatisfiability

I am having trouble reasoning about the equisatisfiability of statements. (In the following I'll use the notation where addition is OR, multiplication is AND, and overbar is NOT.) By exhaustive ...
2
votes
2answers
62 views

Understanding the proof of “connected set is interval.”

There is some questions about connected set. The first question arises in logical translation. I translated the property of interval into logical proposition that $\forall a,b \in E, \forall c : ...
0
votes
2answers
21 views

Translate usual sentence into logical proposition

Let $x$ is the notation of an element of argument domain. Now $Ax$ and $Mx$ is predicate for the sentence that "$x$ is an American", and "x is a man", respectively. I want to symbolize the sentence ...
-3
votes
1answer
102 views

What does this symbol mean (set theory)

I hate when I come across symbols I can't recognise or describe because it's nigh-on impossible to google for them, so I hope it's okay to post this here. Does anyone know what this symbol means ...
2
votes
1answer
82 views

What is a Primitive Atomic Formula?

I am reading "Axiomatic Set Theory" by Patrick Suppes and he defines a primitive atomic formula as follows: A primitive atomic is an expression of the form ($v\in w$ ), or of the form ($v=w$) where v ...
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 ...
0
votes
2answers
84 views

Show that $A \lor B ⊢ B \lor A$

Prove the following derivability claim using only our primitive rules: $A \lor B ⊢ B \lor A$ I know this can be attributed to the commutative property, but I'm not exactly sure how to prove this ...
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) ...
0
votes
0answers
15 views

A question on terminology

I started reading a Mathematical logic book.I wondered what is a definition by abstraction as well axiom schemata.
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. ...
0
votes
2answers
65 views

Goldbach Conjecture predicate form?

I am learning logic, and when I was taking a quiz one of the multiple choice questions was "Which of the following is an unsolved conjecture?" I picked the following answer because I thought it was ...
1
vote
2answers
116 views

Formula that's only satisfiable in infinite structures [closed]

What formula in first order logic can I write that's only satisfiable over infinite structures, over a dictionary without the = sign?
0
votes
0answers
31 views

predicate logic conversion

I am a novice in learning the conversion of english sentences to predicate logic.I can not convert these sentences into predicate logic. 1.Sue eats everything Bill eats. 2.Nazrul is a national poet. ...
2
votes
1answer
31 views

Bounded sets equivalent definition

Let $X$ be a metric space, and $E\subset X$. I have two definitions of a bounded set, I want to prove they are equivalent. Definition 1: $\exists M:\exists q\in X:\forall p\in E:d(p,q)<M$ ...
2
votes
1answer
29 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
86 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
48 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
40 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
23 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
45 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
21 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
3answers
33 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: ...
-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
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?
4
votes
1answer
60 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
58 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
89 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
30 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
103 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
74 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
vote
1answer
38 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
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?
0
votes
1answer
31 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
32 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 ...
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 ...
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
75 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
61 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
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
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 ...