# Questions tagged [predicate-logic]

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

3,811 questions
Filter by
Sorted by
Tagged with
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}$ ...
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 ...
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: ...
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 $='$...
76 views

1 vote
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(...
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 ...
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]
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ∀(_) ...
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, ...
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 (...
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 ∀...
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 ...
1 vote
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 ...
1 vote
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 ...
1 vote
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. ...
32 views

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:&...
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 ...
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(...
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-...
1 vote
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 "...
1 vote
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)}...
1 vote
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 ...
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}$) ... 