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
15 views

First order logic expression of “Each finite state automaton has an equivalent push-down automaton”?

Problem is Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such ...
-1
votes
0answers
44 views

Term rewriting; Compute critical pairs

I have tried to solve the following exercise but I got stuck while trying to find all the critical pairs. Any help is appreciated. Let $$ \sum = \left \{ \circ, i, e \right \} $$ where $\circ$ is ...
3
votes
1answer
55 views

The $<$-relation on $\mathbb{Z}$ is not definable in $(\mathbb{Z}, 0, +)$

I am a complete newcomer to logic and I'm having trouble proving the following: The $<$-relation on $\mathbb{Z}$ is not definable in $(\mathbb{Z}, 0, +)$. Now, I know that the $<$-relation on ...
0
votes
1answer
43 views

Sentence $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements

I'm trying to prove this result: For any natural number $n \geq 1$ there is a sentence $\phi_n$ such that $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements. My attempt: By induction ...
1
vote
3answers
74 views

Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?

I'm currently trying to prove that $\exists n\forall m~P(m,n)\Rightarrow \forall m\exists n P(m,n)$ formally. This is important to me because my professor and various only sources have hinted that in ...
2
votes
1answer
30 views

Show that there is such an algorithm

Let $L_P = \{+, \geq; 0, 1\} $. The first-order theory of $\mathbb{N}$ in the language $L = L_P \cup \{exp_2\}$, where $exp_2$ the function which sends a natural number $n$ to $2^n$, is decidable. ...
-1
votes
0answers
27 views

Proof validity of following FOL/statement using Hilbert like system.

I am new to FOL . and not getting Hilbert Like system.. 0Proof validity of following FOL/statement using Hilbert like system. (a) All trees are plants. All plants are living things. So all trees are ...
-2
votes
1answer
52 views

Proof validity of following FOL/statement given by Natural deduction

The fastest running person is a Jamaican. Therefore, anyone who is not a Jamaican can be overrun by someone. User predicate P (x) : x is a person, F (x, y) : x can run faster than y and J(x) : x ...
0
votes
1answer
38 views

Winning strategy for graphs (Ehrenfeucht-Fraïssé games)

I'm stuck with a question: Proof that you can't express if a graph is cyclic in first-order logic. The definition of cyclic is that for every node there is a ...
3
votes
1answer
50 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 ...
3
votes
0answers
34 views

complex numbers from real closed fields

I am very interested in first order axiomatizations of the complex numbers, but I have never actually seen one laid out. Algebraically closed fields of characteristic zero are a start, but they don't ...
1
vote
1answer
20 views

Question on existential quantifier.

Let us consider the following predicates. $A(x)$: $x$ is $A$ type. $B(x)$: $x$ is $B$ type. Then convert the following statement in terms of predicate expression. Some $A$'s are $B$. Then which ...
2
votes
2answers
80 views

Can we treat logic mathematically without using logic?

I'm reading Kleene's introduction to logic and in the beginning he mentions something that I have thought about for a while. The question is how can we treat logic mathematically without using logic ...
1
vote
1answer
33 views

Finite set of formulas from $L(A)$ is realized iff it is consistent with $Th(\mathfrak{A})$

Let $\mathfrak{A}$ be an $L$-structure with domain $A$. If $\Sigma$ is a finite set of formulas in $L(A)$, how can I prove that $\Sigma$ is realized in $\mathfrak{A}$ iff it is consistent with ...
0
votes
1answer
55 views

Boolean formulas over omega automata

I've been reading on omega automata(automata on infinite words) and stumbled upon a definition involving logic which caught me off guard. For example, on Buchi automata the definition I originally ...
6
votes
2answers
95 views

Defining the existence of a non algebraic element in the language $L:= \{0,1,+,\cdot\}$

I raise following question after reading this post. Is it possible in the language $L:= \{0,1,+,\cdot\}$ to write sentences for which a model will necessarily contain a copy of $\mathbb Q$ and a non ...
1
vote
2answers
71 views

Language structure of $\mathbb{R}$ and $L_{\mathbb{R}}$

Ok, so, I'm reading up on some first order logic and am now studying languages and structures. If we define the language $L:= \{0,1,+,\cdot\}$, with $0,1$ the constants and $+, \cdot$ the $2$- place ...
2
votes
2answers
60 views

Prove that $\exists z \in \mathbb R\forall x \in \mathbb R^+[\exists y \in \mathbb R(y-x=y/x) \iff x \neq z]$

This is Velleman's exercise 3.4.13: Prove that $\exists z \in \mathbb R\forall x \in \mathbb R^+[\exists y \in \mathbb R(y-x=y/x) \iff x \neq z]$. I am am stuck on that one. Seems like I am ...
0
votes
1answer
40 views

(Sphere Lemma) Hanf locality Lemma and locally threshold testability

I am reading the proof of Hanf's Sphere Locality lemma for (finite or infinite structures but with bounded degree), and I'm trying to understand the details of the proof! I'm confused with the ...
2
votes
1answer
52 views

Local isomorphism question in logics

The definition of a local isomorphism between structures: a local isomorphism between structures $\mathcal{A}$ and $\mathcal{B}$ over an alphabet $L$ is a finite relation $$\{ ...
7
votes
2answers
113 views

First-order definition of nonnegative in integers

Given the structure $(\mathbb Z,+,-,\times,0,1)$, what's the easiest way to write "$x\ge0$" in that structure? I know that this works: $$\exists a\exists b\exists c\exists d,a^2+b^2+c^2+d^2=x$$ ...
7
votes
1answer
52 views

Prove that if $\mathcal F \subseteq \mathcal G$ then $\bigcap\mathcal G \subseteq\bigcap\mathcal F$

This is Velleman's exercise 3.3.13. Suppose $\mathcal F $ and $\mathcal G$ are families of sets and $\mathcal F \subseteq \mathcal G$. Prove that $\bigcap\mathcal G \subseteq\bigcap\mathcal F$. My ...
2
votes
1answer
77 views

Questions about Gödel, formal systems, propositional calculus and first order logic.

I've been reading Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid, and I'm loving it, though there are some things I don't quite understand yet. Propositional Calculus is a formal system, ...
1
vote
1answer
33 views

How to represent the sentence “If everyone votes then the motion passes” with FOL

Should it be ∀x Votes(x) ⟹ Passes(Motion)? Probably not, because if none but 'John' votes, then using extended interpretation, ...
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?
2
votes
1answer
161 views

Is there a rule for uniform substitution of predicate symbols in FOL?

In a Hilbert-style axiomatization of first-order logic (FOL), there is a rule for variable substitution but I don't see any rule for substituting predicate symbols. Consider a theorem like: $\forall ...
3
votes
1answer
36 views

Proving the Downward Löwenheim-Skolem using monotonic operators

This is another exercise from Kees Doets Basic Model Theory. Here's the idea. It's well known that the downward Löwenheim-Skolem theorem follows as an easy corollary of the following lemma using ...
2
votes
1answer
80 views

Help me solve this (∀x)[Px⇔(∀y)[Qxy⇔¬Qyy]]⇒(∀x)[¬Px] first order logic (step by step)

This is a MCQ of a competitive exam(GATE) , defined below . I found many different -2 explanation in market books and many other sources , but there is conflict between each explanation , I found all ...
3
votes
2answers
68 views

Proving that $\langle \omega+1, \leq \rangle$ and $\langle \omega + \omega^*, \leq \rangle$ are not elementarily equivalent

This is an exercise from Kees Doet's Basic Model Theory. The basic idea is to show that an ordering of type $\omega + 1$ is not isomorphic to an ordering of type of $\omega + \omega^*$, where ...
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?
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 ...
2
votes
3answers
59 views

Quantifier elimination over rationals.

My question is concerned with a statement in Marker's Model Theory. The statement is that for formula $\phi(a,b,c)=\exists x(ax^2+bx+c=0)$, we cannot have a quantifier free formula $\phi'$ such that ...
3
votes
1answer
40 views

Help understand theorem that any set of first order sentences satisfied by N has a model that's a strict superset of N.

I saw the following theorem (in Computational Complexity book by Papadimitriou, p. 111) : Theorem : If $\Delta$ is a set of first-order sentences such that $N$ $\vDash \Delta$, then there ...
1
vote
1answer
27 views

Over signature $S= \{f \}$, $n_f=1$, find a formula $\phi$ so that for every structure, $M \vDash \phi \implies|M|$ is infinite

Over signature $S= \{f \}$, $n_f=1$, find a formula $\phi$ so that for every structure, $M \vDash \phi \implies |M|$ is infinite I'm trying to solve this for a really long time. I tried to perhaps ...
1
vote
2answers
75 views

How to negate: not a limit point (symbolic logic)

1.There are few I have seen here. $\forall N(x), \exists x'\in B, (x'\neq x\wedge x'\in E)$. $\forall N(x), \exists x'\in B, (x'\neq x\to x\not\in E)$. $\forall r>0, \exists x'\in N_r(x)\cap E, ...
1
vote
1answer
39 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 ...
3
votes
2answers
57 views

Logical Statements - Proofs

Let $f$ be a real-valued function (a function with target space the set of reals). Let $P(x, M)$ stand for $|f(x)| \leq M $, let $N$ be the set of positive real numbers, and let $\mathbb{R}$ be the ...
0
votes
1answer
32 views

How is prolog's expressiveness more restricted than First Order Logic?

I gather than first order logic (FOL) is a mathematical creation. Prolog on the other hand is a logic programming language that closely resembles (implements?) FOL. I am wondering in what way is ...
0
votes
1answer
43 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?
-1
votes
1answer
60 views

Does $\mathcal{P}(\mathbb{N})$ contain infinite sets?

I know that $\mathcal{P}(\mathbb{N})$ is infinite and uncountable. However, is the power set of the natural numbers considered to contain only finite sets of natural numbers, or infinite ones as well? ...
0
votes
1answer
33 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).
1
vote
1answer
81 views

How to prove that a statement is a theorem using Hilbert's system?

I'm looking for an actual step-by-step way of proving that a statement is a theorem using Hilbert's system. For instance: As can be seen from the above picture, the solution consists in a series of ...
3
votes
1answer
283 views

Why does the Deduction Theorem use Union?

We have an initial set of premises $S$. We are given or observe or assume sentence(s) $A$ is/are true. We can then prove $B$. Formally, $S \cup \left\{A\right\} \vdash B$. Shouldn't it be an ...
2
votes
2answers
73 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
62 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 ...
2
votes
2answers
64 views

Explanation on the symmetry between identity axiom and cut rule

In Proofs And Types at the beginning of 5.1.4 Girard says that the identity axiom is somewhat complementary to the cut rule, more specifically 'The identity axiom says that $C$ (on the left) is ...
2
votes
1answer
17 views

If the canonical embedding is an isomorphism then U is a principal ultrafilter

My question is the reciprocal of this one: Show that if U is a principal ultrafilter then the canonical inmersion is an isomorphism between $\mathcal A$ and $Ult_{U}\mathcal A$ I also assume that $M$ ...
1
vote
1answer
91 views

Introduction to Symbolic Logic: 'Understanding Symbolic Logic, 2nd Edition,' by Virginia Klenk, Page 294

I read this passage in my textbook: ...if there is a counterexample in a domain with $m$ individuals, then there is also a counterexample in all larger domains. It follows by contraposition (and ...
-1
votes
2answers
31 views

Finding a morphism from one boolean expression to another i.e. $\phi :(x \Rightarrow y) \rightarrow (y \vee z)$

What I would like to do is figure out how to get from $(x \Rightarrow y) $ to $ (y \vee z)$, that what I could AND or OR to $(x \Rightarrow y) $ so as to give $ (y \vee z)$. Breaking this down I ...
0
votes
1answer
39 views

Proof that given an empty vocabulary, P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not definable.

Hi there i would like to prove this: Given an empty vocabulary L ( by empty I mean L = $\emptyset$), the property P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not ...