Questions tagged [predicate-logic]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

How to show that the Alexander Subbase Theorem is ZF-equivalent to the Compactness Theorem for first order logic?

Alexander Subbase Theorem (ASB): Let $X$ be a topological space. $X$ is compact if and only if there is a subbase $\mathcal{B}$ for the topology of $X$ such that every subcollection of $\mathcal{B}$ ...
user avatar
  • 2,962
0 votes
1 answer
29 views

Quantifiers and usage of the infinum

Let $A$ be a set. Define $d(x,A) = \inf \{d(x,a)| a \in A \}$. So for any $a$, $d(x,A)\leq d(x,a)$ and for any other $r \leq d(x,a)$ we have $r \leq d(x,A)$. Now let $x$ and $y$ be two different ...
user avatar
  • 493
10 votes
3 answers
219 views

Is there a purely topological proof that a certain topological space derived from logical compactness is compact?

Let $L$ be a first order language, and let $S_{L}=\{\sigma:\sigma\;\mbox{is an $L$-sentence}\}$. Also, by logical compatness I mean the Compactness Theorem of first order logic. Compactness Theorem: ...
user avatar
  • 2,962
5 votes
2 answers
110 views

Are this two sentences equivalent?

I have a sentence in natural language: "the sum has a neutral element and it is unique", which I have to write in a first order language that has a binary relationship symbol of equality $='$...
user avatar
  • 183
2 votes
2 answers
76 views

What is the purpose of a certain problem?

I am self-learning the material and I have encountered this question in the lecture notes by Stephen G. Simpson that I am reading: Let $L=\{R,\ldots\}$ be a language which includes a binary predicate $...
user avatar
  • 2,962
1 vote
1 answer
29 views

Notation for the set of conjonctions of two adjacent level of the levy hierarchy

Let $\Sigma_n$ and $\Pi_n$ be two levels of the levy hierarchy. We consider the set of formulas $$\Gamma = \left\{ \phi \wedge \psi, \phi \in \Sigma_n, \psi \in \Pi_n \right\}$$ Is there a common name ...
user avatar
  • 173
1 vote
1 answer
68 views

What strategies could be used to prove the validity of this argument in order to not violate restrictions on universal generalization (Hurley)

I'm considering a particular argument while working through Hurley's Concise Introduction: ...
user avatar
  • 11
0 votes
1 answer
18 views

English to predicate- and vs imply [duplicate]

"Some student in this class hass taken a course in java". First we decided that U is domain. we defined S(x) to be x is student in class. And J(x) to be x has taken java. The solution is :$\...
user avatar
  • 1
1 vote
1 answer
65 views

How to prove that $∃x J(x)$ and $J(m)$ are not logically equivalent?

I'm supposed to use counter models to establish that the two sentences $∃x J(x)$ and $J(m)$ are not equivalent. My initial work is this, does it seem right? Domain: Lionel Messi, Cristiano Ronaldo J(...
user avatar
-5 votes
0 answers
56 views

How do I translate the following sentences from English to predicate logic? [closed]

The thief is only liable if they saw him enter the tunnel and found the stolen item in his possession. If witnesses see him enter the tunnel and the stolen object is not found in his possession, then ...
user avatar
-5 votes
1 answer
32 views

Which variables are bound and which one are free? [closed]

Choose which variables are bound and which one are free? a) ∀x ∃z [sin(x+y)=cos(z-y)] b) ∃x ∃z [x^2+z^2=y]
user avatar
0 votes
0 answers
30 views

can I falsify a traditional inference with modern natural deduction like system?

I can represent a traditional syllogism with the language of first-order predicate logic. and If the syllogism is valid, then I can prove it with natural deduction system or tableaux. If the syllogism ...
user avatar
0 votes
1 answer
28 views

Need help constructing a proof tree (or truth tree) for the following argument symbolized in predicate logic.

For context, I am a logic simpleton studying for an exam in a graduate-level introduction to symbolic logic. One of the techniques I'm expected to know is constructing proof trees to test the validity ...
user avatar
  • 55
2 votes
1 answer
122 views

Elementary equivalence between a well-ordering and linear ordering

Consider a language $L$ consisting of a binary predicate $R$ and some additional predicates (e.g. $=$) so that the $L$-structure $M=(U_{M},R_{M})$ is isomorphic to $(\mathbb{N},<_{\mathbb{N}})$. I ...
user avatar
  • 2,962
2 votes
3 answers
50 views

Predicate logic: Symbolize this categorical statement.

I am a logic neophyte and simpleton studying for an exam in a graduate-level course in elementary symbolic logic. I am trying to symbolize the following categorical statement: "No artist is a ...
user avatar
  • 55
2 votes
2 answers
113 views

Does "if" turn a free variable into a bound variable?

A closed formula expresses a proposition (which is a truth-apt concept, so a concept that is either be "true" or "false"). A closed formula is a Boolean-valued formula with no free ...
user avatar
  • 925
-1 votes
0 answers
32 views

Proving Identity Laws in Logic using Natural Deduction

We know that there are identity laws in formal proofs in a system of natural deduction like =In, =Out. So, I am stuck at such a problem where we have to prove an equality i.e. q = u using the ...
user avatar
0 votes
0 answers
37 views

Predicate Logic: Deduction for Quantifiers

So, I was bothered by the question of natural deduction wherein we have to prove ∀h(Fh ⇒ Fk) from premise ∃g Fg ⇒ Fk given that k is a constant which isn't used before To get the conclusion in ∀(_) ...
user avatar
0 votes
1 answer
25 views

Natural Deduction: Universal Quantifiers in Predicate

How do we prove the conclusion: ∀x(Ax ∨ ⇁Ax) This is also called LEM, i.e. the Law of Excluded Middle. I'm confused while proving this because for ∀x, deduction assuming some constant is required. So, ...
user avatar
-1 votes
0 answers
79 views

~∃(X)(H(X) ∧ I(X)) - No human is immortal predicate logic [closed]

When watching the Veritasium video "Math's final flaw", at 12:27, he quickly mentioned a logic statement that said "No human is immortal" I did some research on predicate logic (...
user avatar
0 votes
0 answers
27 views

What is incorrect with my first-order predicate calculus?

I'm trying to write the FOL for "Borrowing a book doesn’t change who owns it" given the functions: Book(x) = x is a book Owns(x, y) = x owns y Provide(x, y) = x provides y My attempt was ∀...
user avatar
-2 votes
1 answer
87 views

Question from predicate logic exam: Given model with the domain D [a,b], say whether the formulas listed below are true or false. [closed]

I've got a logic exam coming up and one of the question types is puzzling to me. If anyone could help me by explaining what this is about to me, I would appreciate it greatly. The question is: Given ...
user avatar
  • 55
1 vote
1 answer
69 views

Translating from English into predicate logic

I am learning the formal method, and I am not so sure if I have translated these statements correctly. a) “Every state has exactly one head of state.” Interpretation: D = the set of all states and ...
user avatar
  • 21
1 vote
1 answer
41 views

Instantiation vs substitution in Smulyan's First order Logic

I am learning logic by reading R.M. Smullyan's First Order logic. I have included images of the relevant pages below. On page 44 he defines: a formula $A$ is closed if for every variable $x$ and every ...
user avatar
  • 2,962
1 vote
1 answer
49 views

Isn't this wrong: if `all A are B` and `all B are C` then `some A are C`?

I found that statement on Generalized Quantifier page of the Stanford Encyclopaedia of Philosophy. ...
user avatar
  • 263
0 votes
1 answer
32 views

Given the following structure, how do I translate the these statements into formulas in predicate logic?

The following is a problem from our book in predicate logic. "Work over the arity type: 'one binary relation, one constant symbol, one binary operation' and then consider the structure $$ Q := \ &...
user avatar
  • 55
0 votes
0 answers
26 views

Questions about smt-solvers.

Are smt-solvers (like z3) theoretically able to (always correctly) check consistency of any 1.-order logic formula? How does smt-solver algorithm work in details? Are there any algorithms that could ...
user avatar
0 votes
1 answer
27 views

Rewrite proposition with logical symbols

I want to rewrite the following proposition in mathematical language (and by mathematical language I mean symbols such as: $\forall , \exists, (, ), \implies$ and so on). Proposition: Every non-...
user avatar
0 votes
0 answers
36 views

Axiomizing meets/joins of a lattice directly instead of quantifiers

The usual strategy of axiomizing logic axiomizes quantifiers first and then defines joins and meets in terms of them later. Can you reverse the order of definitions? I know various logics can be ...
user avatar
0 votes
1 answer
41 views

countermodel interpretation - another example with existential quantifiers

Still struggling with interpretation in logic. I have this: ∀xp(x) ↔ ∀xq(x), ∀xq(x) ↔ ∀xr(x) |=∃x(p(x) ↔ r(x)) 1. I first tried to solve it with a resolution method, and got stuck on this: $ \lnot px \...
user avatar
0 votes
1 answer
52 views

How to read quantified statements without variables and unquantified statements with variables? What does an existence predicate achieve?

I was looking up free logic on wikipedia https://en.wikipedia.org/wiki/Free_logic and reading it posed more questions than it explained. The "explanation" paragraph lists three theorems of ...
user avatar
0 votes
0 answers
12 views

Reference for strengthening of Church's theorem on undecidability of predicate calculus

I need a reference (it can be either a book or a published paper in English) for the following result: "Let $L$ be a language containing a 2-ary predicate symbol, then the set of all logically ...
user avatar
0 votes
1 answer
56 views

Understanding Interpretations with quantifiers in first-order logics, using examples

I am finding difficult to understand the meaning of definitions and would found useful to grasp things by examples, first. Can you show the concept of interpretation and how to find a counter model of ...
user avatar
0 votes
0 answers
21 views

Given the following formula in predicate logic, determine for which valuations it holds.

The problem is the following: "Let $\varphi := \Big(P_1(x_1,x_2) \rightarrow P_1(x_2,x_1)\Big)$ be a formula in predicate logic. Describe (in as simple form as possible) exactly which values of $...
user avatar
  • 55
1 vote
0 answers
79 views

Is it correct to judiciously construct a quantifier tableau to yield a desired falsification of a formula, yet the rules to apply weren't exhausted?

I am a beginner in logic, which I am learning on my own. I am aware of the fact that a quantifier tableau with open branches doesn’t always show the formula under consideration is falsified- unless ...
user avatar
  • 2,962
0 votes
0 answers
45 views

How to disprove that $∀_x (p(x)∨q(x))⊨∀_x p(x)∨∀_x q(x)$ with an interpretaion

I am requested to prove or disprove that $\forall_x$ $(p(x)\lor q(x))$⊨$∀_x p(x)\lor ∀_xq(x)$ I have written the following interpretation bellow. However I have two questions concerning formalization.....
user avatar
  • 47
0 votes
0 answers
11 views

Composition and removal of quantifiers in predicate logic in PCNF (prenex conjunctive normal form) - resources

I am struggling in working with predicate logic proofs. The material I am using as reference is not very clear in the explanations, I feel there is an exceeding use of acronyms and symbols in ...
user avatar
6 votes
1 answer
117 views

Proving (disproving?) a statement when its condition is not satisfied

Consider the following implication. Let $k\in \mathbb{Z}$. If $k^{2} + 5k$ is odd, then $k^{2}+5k+1$ is odd. At first it seems to be false, and one could proceed easily to prove it false directly by ...
user avatar
  • 115
2 votes
1 answer
55 views

How does one prove inadmissibility of inference rules in First Order Logic?

In FOL, can we say that if from a set of assumptions gamma we have no proof of A, then we have a proof of not-A ($\Gamma \vdash \neg A$)? Additionally, are these rules admissible as part of a first ...
user avatar
-1 votes
1 answer
63 views

There is a student in this class who has been in every room of at least one building on campus

I am stuck on a question in Kenneth H. Rosen's Discrete Mathematics (7th edition): There is a student in this class who has been in every room of at least one building on campus. My solution is $$\...
user avatar
0 votes
1 answer
35 views

What does it mean for propositions to be in parenthesis without logical operators.

i have stumbled upon this on one of my schools automatized tests. In my universities discrete math 1 module: "Let P and Q be logic expressions, applying the laws of calculus prove the following:&...
user avatar
  • 3
0 votes
1 answer
43 views

How do I prove the following statement regarding partitions of a set?

$\exists! x:Px\implies (\forall x(Px \implies Qx) \iff \exists x(Px \land Qx))$ Essentially, the values of x for which P is true form partitions of the universe. This question came to mind when ...
user avatar
3 votes
2 answers
194 views

Is negation distributive?

Take a proposition like $\neg(\forall x \in S, P(x))$. If negation is not distributive, how does one determine which connective to be negated? Here are the options I've seen: $$\neg(\forall x \in S, P(...
user avatar
0 votes
0 answers
14 views

Number of pairwise non-isomorphic countable normal models

Let the signature $\Omega$ be finite and consist of singular predicate symbols and equality. So, how to prove that every theory in the signature $\Omega$ has at most a countable number of pairwise non-...
user avatar
1 vote
2 answers
52 views

Modelling properties as "inference" (implications) or "and" (conjunctions) in logic

In translating sentences to propositional logic, I am often found puzzled if I should model a property as a conjuction between sentences, or as an inference. e.g. (I use symbol "V" as "...
user avatar
1 vote
0 answers
59 views

Predicate Logic - What is the difference between these two answers?

Main Question Okay so the question at hand is to describe this statement using set theory and possible from logic. Everybody is friends with everybody My answer would be for this: ∀x∈S |{z∈S, f(x,x,z)}...
user avatar
1 vote
1 answer
81 views

Are there limitations to notation?

I know that there are certain rules that allow to introduce new symbols to a language, which can be found here: https://en.wikipedia.org/wiki/Extension_by_definitions or How could we formalize the ...
user avatar
29 votes
1 answer
2k views

Can Peano arithmetic prove the consistency of "baby arithmetic"?

I am reading Peter Smith's An Introduction to Gödel's Theorems. In chapter 10, he defines "baby arithmetic" $\mathsf{BA}$ to be the zeroth-order version of Peano arithmetic ($\mathsf{PA}$) ...
user avatar
  • 4,879
0 votes
1 answer
52 views

Natural Deduction with Identity

I am confused on how to deal with identities in natural deduction proofs with predicate logic. More specifically, how would one go about solving this? ...
user avatar
4 votes
3 answers
450 views

Can notation ever lead to mistakes?

I wondered whether notation in mathematics can lead to actual mistakes in proofs and deductions or whether notation is just style that doesn't matter logically. I read that there are formal rules to ...
user avatar

1
2 3 4 5
77