For questions about formal deduction of first-order logic formula or metamathematical properties of first-order logic.

learn more… | top users | synonyms

0
votes
1answer
27 views

Predicates about functions in 1st order logic

Given the usual definition of function as a subset of $ D \times C $. What is the correct way to write "All functions $ f $ from $ D $ to $ C $ have property $P(f)$". This is both a question about ...
0
votes
1answer
31 views

Resolution calculus converting into set of clauses

Here is $T$: $a \lor \neg b$ $\neg a \lor (c \land d)$ $b$ I am suppose to use resolution calculus to prove that $T \models d \land b$ holds. As in the first step, we translate $T$ ...
0
votes
0answers
16 views

Is (A v C) v B in conjunctive normal form?

I need T to be a set of clauses in conjunctive normal form. T = { (¬A ^ ¬C) → B } T = { ¬(¬A ^ ¬C) v B } T = { (A v C) v B } I 'simplified' it to T = { (A v C) v B }, is it in CNF? ...
2
votes
2answers
50 views

Can we prove ZFC is consistent?

Or can we prove the independence of the CH? Let's place ourselves in first order logic. If CH was proved unprovable and ZFC was inconsistent, let P be a paradox in ZFC. 1)We have: P is true 2)And P ...
4
votes
1answer
31 views

No simplifying identities for any single nonzero number under addition.

Consider the structure $(\mathbb{R}, +, r)$, where r is a nonzero real number. Are the commutative and associative identities already sufficient to derive all universally valid equations in that ...
2
votes
1answer
43 views

Definition of “substitutable” in Mathematical Logic

I'm reading Leary's Mathematical Logic text where it defines the phrase "substitutable" and most of it is sensible: $t$ is substitutable for $x$ in $\phi$ if $\phi$ is atomic. $\phi := ...
1
vote
1answer
34 views

Logical form of a set-theoretic statement.

From Velleman's 'How to Prove it' book, there is one statement - written below - of which I don't know how to write the logical form of, and I'm wondering if somebody could write it out. The ...
0
votes
0answers
12 views

Find a formula of predicate logic for not decreasing and increasing sequences

There is a language $L = \{+, s\}$ with "=" + is func symbol behaving like this $(a_0, a_1, ....) + (b_0, b_1,...) = (a_0+ b_0, a_1 + b_1,...)$ s - shifts sequence to the left, i.e $s((a_0, ...
3
votes
0answers
45 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
1
vote
0answers
61 views

satisfaction of a sentence with two quantifiers

I want to be sure that I understand how to show that a structure satisfies a sentence under a variable assignment, and suspect that I'm handling the computation of multiple quantifiers incorrectly. ...
1
vote
1answer
21 views

Counting models that satisfy PL sentences

I have an assignment where I need to count the number of models of a certain sort which satisfy a given sentence, and I keep finding that the number of models I count exceeds the total number of ...
1
vote
2answers
53 views

Existance of an (in)finite theory having infinite model

Please help me to study the following simple cases: Let $P$ be a binary predicate symbol. I am trying to find out, if there exists a satisfiable $T$ having infinite models only, for the following ...
1
vote
2answers
25 views

Universal Instantiation and Proof of: if $x$ and $y$ are odd integers, then $xy$ is odd.

I have a question about the first part of the proof for the statement "If $x$ and $y$ are odd integers, then $xy$ is odd" if we are using a direct proof. Now i've gotten the proof roughly correct but ...
1
vote
1answer
35 views

First-order logic: largest size among smallest finite models for formulas of a given length

Apologies for the somewhat cryptic title. For any first-order formula X, let ssm(X) be the size of the smallest finite model of X. By size I mean number of individuals. So, for example, ssm('Fa ...
3
votes
1answer
36 views

Deducing the compactness theorem from the completeness theorem (in first order logic)

Given that $\Sigma\vdash\phi \Leftrightarrow \Sigma\vDash\phi$, I want to prove: $\Sigma \text{ satisfiable} \Leftrightarrow \text{ every finite subset of } \Sigma \text{ is satisfiable}$. I will ...
2
votes
1answer
43 views

algebraic closure is the intersection of all elementary sub-models of the monster

This is a question from an exercise in model theory. Let T be a complete theory, $ \mathfrak{C} $ monster model of T (a $ \kappa $ saturated model of cardinality $ \kappa $ for some large $ \kappa $) ...
1
vote
0answers
53 views

Why does this mass equation not work in this calculus application problem?

This is a homework problem which I have already solved, but I want to know why my first approach did not work. I have already asked my professor this question, but he did not explain it very well. ...
0
votes
2answers
47 views

Can we say in first order logic the following: Every person who loves everyone is good?

I have just started to learn the first order logic. I have learned that one can use predicated to specify relations between specific objects (or entities). For example: $LocatedIn(Berlin, Germany)$ ...
1
vote
1answer
46 views

Recursive definitions in formal logic

A binary tree $T$ is either A single vertex, or A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. Suppose ...
1
vote
1answer
26 views

Is this formula in normal form prenex $(\forall x)(\exists y)(P(x) \land (\exists z)Q(y, z))$?

In my course notes, this $(\forall x)(\exists)z(P(x) \land (\exists z)Q(y, z))$ formula is said to be in normal form prenex. But, shouldn't al cuantors be in the ...
0
votes
1answer
24 views

Misunderstanding the concept of semantic consequence

In my course notes I have a statement like this one: Let $F_1, ..., F_n \in FOL$. We say that $F$ is a semantic consequence from $F_1, ..., F_n$ and we denote that by $F_1, ..., F_n \vDash F$ if ...
2
votes
0answers
36 views

Extending the language in Henkin style completeness proof for first-order logic

There is a detail in the Henkin style proof of completeness for first order logic that I can't quite understand. So in the first part (Lindenbaum's Lemma), we need to show that a consistent set of ...
0
votes
1answer
33 views

Extension of a theory vs conservative extension

I'm not sure whether I get the difference between extension $T'$ of some theory $T$ and conservative extension $T''$ of this theory. Extension $T'$ of $T$: Language $L\{P\}$ and it's theory $T$ ...
0
votes
1answer
35 views

Prove that if an existential formula A is satisfiable in a countable structure, then it's valid

Question Prove that if an existential formula A is satisfiable in EVERY countable structure, then it's valid. Proof: My proof is that $B=\lnot A$ is universal so if B is not satisfiable in any ...
1
vote
2answers
47 views

Can't find a theory which meets conditions

I'm trying to solve this problem. There is a language $L = \{f\}$ with equality (we can use '$=$'), where $f$ is a unary function. Our goal is to decide and prove, whether there is a theory $T$, ...
0
votes
0answers
20 views

Example CNF for FOL

I don't understand this example: $\forall x [\forall y\ Animal(y)\Rightarrow Loves(x,y)] \Rightarrow [\exists\ y Loves(y,x)] \\$. After, I must eliminate biconditionals and implications. In the ...
2
votes
2answers
60 views

Trying to understand self-reference as it relates to Godel's Second Incompleteness Theorem

As noted in this post, I'm trying to understand how a sufficiently powerful consistent theory $T$ can prove statements about itself without contradicting Godel's Second Incompleteness Theorem. Let ...
1
vote
1answer
23 views

How to find a formula that is true for the given model in the First Order Logic?

I think I might get lost in the definitions. I am not sure if this is the right way to deal with models and formulas in the First Order Logic. I am not looking for the solution for this particular ...
0
votes
2answers
65 views

Is it possible to formalize $T \models \sigma$ within the deductive calculus?

I know that the notion of $T \vdash \sigma$ is formalizable within any sufficiently powerful theory $T$ but is $T \models \sigma$ formalizable as well? How is this possible if there are infinitely ...
3
votes
2answers
80 views

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my "proof" of "ZF is inconsistent" was that I was not considering that there are models with non-standard integers. However now I think I ...
1
vote
2answers
48 views

What does this deduction involving provability imply?

I recently asked this question asking why my reasoning for ZF being inconsistent was wrong. I didn't realize that we have to account for models with non-standard integers. However, I'm left with the ...
7
votes
1answer
80 views

What's wrong with this proof of ZF being inconsistent?

I'm studying (independently) mathematical logic and in investigating self-referential statements I developed a result which I don't know how to interpret. I'll use the notation from Enderton's "A ...
0
votes
1answer
60 views

Is there an non provable sentence from Peano Arithmetic?

I'm trying to deduce the following sentence using only Peano Axioms: "There exist infinite prime numbers" Since PA is known to be incomplete, its possible there is no such proof supporting the ...
-4
votes
1answer
39 views

How can I prove $(P \to Q) \to (\lnot Q \to \lnot P)$?

I'm struggling to grasp how to do natural deduction and am going through questions but this one has stumped me completely. The question is to prove $(P \to Q) \to (\lnot Q \to \lnot P)$ without the ...
0
votes
0answers
7 views

Expressibility of the existence of a clique.

I'm doing some tasks using Ehrenfeucht-Fraisse game. I managed to show that some properties are not expressible in first order logic, but I cannot deal with such a problem at all. Show that the ...
0
votes
2answers
68 views

Proof by contradiction in predicate logic

So we are given the following to prove, only by proof by contradiction $\forall x(Q(x)\to P(y)) \vDash \forall xQ(x)\to P(y)$ Now the first thing that comes to mind in predicate logic when i am on a ...
1
vote
1answer
96 views

What is the first order formulation of Zorn's lemma in the language of set theory?

Very often in notes of courses in set theory you find the assertion that in ZF the Axiom of choice (AC) is equivalent to Zorn's Lemma (ZL) (which is equivalent to Well Ordering Principle which it ...
0
votes
1answer
27 views

Completeness of an FO theory with a single model

Prove or disprove: If some FO theory $T$ has only one infinite model up to isomorphism (of cardinality $n$) , then T is complete.
0
votes
1answer
33 views

Proving a Tautological implication in logic

Ok so we are asked to prove the following: $\Sigma \cup\phi\vDash\psi$ if and only if $\Sigma\vDash\psi\rightarrow \phi $ where $\Sigma$ is a set of types(not empty set), and $\phi$ and $\psi$ are ...
1
vote
1answer
53 views

Completeness of infinite first-order theory [closed]

Let $T$ be a infinite first-order theory T, over the empty signature ($\Sigma =$ {}), as follows: $$T = \{\phi_n : n \in \mathbb{N} \}$$ where $$\phi_n \equiv \exists x_{1},\exists x_{2},\exists ...
1
vote
1answer
46 views

Skolem Theorem private case, preserving extension

Question: Let T be a theory of statements over a signature $\sigma$ and $\phi$ is a formula over $\sigma$ s.t. $x,y$ are the only free variables. We define a signature $\sigma'$ by adding a new binary ...
0
votes
2answers
44 views

Possible interpretations for a predicate symbol in first order logic

PART A So, given as structure A :{1,2,3} and we are studying the languge of the real numbers. We are asked to say how many possible interpretations for the predicate symbol $<$. My question is ...
0
votes
2answers
22 views

Models for predicate logic

Determine whether the following formulae have models: i) $∃x\,∀y\,(Q(x, x) ∧ ¬Q(x, y))$ ii) $∃x\,∃y\,(P(x) ∧ ¬P(y))$ Not sure if these are right: i) $D=\{a,b\}$, $Q(a,a)=1$, and ...
0
votes
1answer
22 views

Odd sized dictionary

Question: Let $\sigma$ be a signature that has only equality as a relation in it. Prove that there doesn't exist a statement $\phi$ s.t it's valid in M $\iff$ $|D^M|$ is odd. My problem: I think the ...
1
vote
2answers
29 views

Possible structures in first order logic

So i was studying about structures in first order logic and i saw a question of this form: Given a syntax A:{P} where P is 2-ary predicate symbol and {0,1} as universe we work. How many different ...
0
votes
1answer
38 views

What is the complexity of first order logic?

I would say that first-order-logic has a data complexity and a formula complexity. Data complexity: fix the theory and let the structure vary and measure complexity in the size of the domain of the ...
1
vote
1answer
15 views

Determining validity in predicate logic

Not sure if I've done this correctly. Check the following formulae for validity. If valid, justify why. If they are not valid, give a countermodel. i) ∃xP(x)→∀xP(x) ii) ∀xP(x)→∃xP(x) ...
1
vote
1answer
45 views

Counterexample for first order logic argument

Find a counterexample to show that the following argument is not valid: ∃xP(x), ∃x(P(x) → Q(x)) |= ∃xQ(x) To my understanding, I have to a select a single element $x$ such that the ...
1
vote
2answers
45 views

prove that any two isomorphic structures are elementarily equivalent

Imagine we have two L-structures $M$ and $N$. For each L-sentence $\phi$ , $M$ models $\phi$ iff $N$ models $\phi$. We call $M$ and $N$ two elementary equivalent L-structures. We say $M$ and $N$ ...
0
votes
0answers
26 views

find an embedding such as F from each numerable and countable set to $Q$

Imagine we have a vocabulary called $V$ and we have two $V-structures$ such as $M$ and $N$. An embedding is a function from $U_M$ to $U_N$ which preserves the interpretation of $V-formulas$. Now i ...