Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [predicate-logic]

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

Some well-known formal systems covered by this term are

  • first-order logic, containing the quantifiers $\forall$ and $\exists$
  • second-order logic
  • many-sorted logic
  • infinitary logic
4144 questions
2
votes
2 answers

Logical structure of $ (\forall x\ \mathsf{P}(x)) \implies \mathsf{Q}$, with $x$ absent from $\mathsf{Q}$

I'm trying to understand the logical structure of statements of the form $ (\forall x\ \mathsf{P}(x)) \implies \mathsf{Q}$, where $x$ does not occur in $\mathsf{Q}$. To prove such statements it is sufficient to prove that $ \mathsf{P}(c) \implies…
Maxis Jaisi
  • 1,553
2
votes
3 answers

If Las Vegas is the capital of Fiji, then $x^2=4$.

If Las Vegas is the capital of Fiji, then $x^2=4$. I was asked to state either the above claim is true or false. I must give a proof if it is true and counter example if it is false. I prove its contrapositive: if not $q$ then not $p$ in the truth…
Surdz
  • 627
2
votes
3 answers

The scope of quantifiers

If we had $\exists x [\text{PLAY}(x) \rightarrow \text{CLIMB}(c)]$, is this equal to $\exists x [\text{PLAY}(x)] \rightarrow \text{CLIMB}(c)$ as the scope of the quantifier does not contain $\text{CLIMB}$ in either case? Does this therefore mean…
Regina Phalange
  • 83
2
votes
1 answer

A question from Bourbaki's Theory of Sets

Concerning the proof of C34 (pp. 40-41): can the argument used to prove that $$(\exists x)(\forall y)R \implies (\forall y)(\exists x)R$$ is a theorem be applied to the (false) converse? In detail (working in $\mathscr{T}_0$): for any relation $R$…
Randy Randerson
  • 866
2
votes
0 answers

Are binary predicates sufficient

I seem to recall a result that says any set of axioms can be converted to a set of equivalent axioms that use only binary predicates and constants. Can anyone point me to that result?
dan b
  • 121
2
votes
2 answers

Establishing decidability/semi-decidability/undecidability of predicate

Can anyone explain how to approach such problems? I tried finding fitting lemmas, but I can't say I can put the pieces together.. Consider the predicates $P_1,P_2,Q_1,Q_2 : R$ $\rightarrow \{0,1\}$ such that $P_1 \vee P_2 $ , $Q_1 \vee Q_2 $ are…
josh
  • 21
2
votes
1 answer

Negation of predicate logic/sequence of numbers

The definition for limx→a f(x) = L is the following: For all real numbers epsilon > 0, there is a real number δ > 0 such that for all real numbers x if a − δ < x < a + δ and x not equal to a then L − epsilon < f(x) < L + epsilon. Write what it…
Helpsun
  • 43
2
votes
3 answers

Intuitive understanding of a logical equivalence

I am working through an introductory book on mathematical proofs and I have a question about an equivalence I have proven. The exercise says to show that $$\exists x(P(x) \to Q(x))$$ is equal to $$\forall xP(x) \to \exists xQ(x)$$ I can do that with…
sam.bishop
  • 311
2
votes
3 answers

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 P(k)) → P(n)], which is strong induction. To do it…
user231595
2
votes
1 answer

semantic consequence in first order logic

I'm asked to show that Fx does not semantically entail AxFx. However in the preceding paragraph the author tells me Fx is true in a model iff AxFx is true in that model. So how am I supposed to provide a model in which Fx is true and AxFx is…
James
  • 21
1
vote
1 answer

Example of first order logic,equivalence class,categoricity,abstract elementary classes

I have problems in a paper about AEC,with an example. In fact,I need to explain most of the details in that example. Let $\tau$ contain infinitely many unary predicates $P_n$ and one binary predicate $E$.Define a first order theory $T$ such that…
user122424
  • 3,926
1
vote
1 answer

predicate logic questions

I'm having serious trouble understanding how to prove whether the below statements are true or false. Normally (when I'm working with simple stuff like p(x) → q(x)) I would create a truth table and see if there is a way to make the left side true…
Ani
  • 13
1
vote
1 answer

Predicate logic, friends of friends are friends

How do I express this sentence in predicate logic, when I can pick the domain of discourse myself? Friends of Michelle's friends are her friends. I was thinking of picking the domain of discourse Michelle's friends: So that I would get $\forall x…
Byebye
  • 277
1
vote
0 answers

Expressing "there are exactly two P's" within the universe of discourse of all things that are P

I want to symbolize with the predicate calculus the sentence "There are exactly two people" Let, P = x is a person. Then the sentence would go: $(\exists x)(\exists y)(((x \neq y) \land Px \land Py) \land (z)(Pz \rightarrow (x = z) \lor (y =…
Jordan
  • 141
1
vote
1 answer

Give abstraction to formula and use the definition of tautological implication.

(a) Give the abstraction of $$ (\lnot((\forall x)(\varnothing(x) \land p)) \rightarrow \lnot q) \rightarrow (\lnot ((\forall x)(\varnothing (x) \land p)) \rightarrow q) \rightarrow ((\forall x)(\varnothing (x) \land p)) $$ (b) Use the definition…
Out Of Bounds
  • 1,531
1 2 3
…
22 23