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

learn more… | top users | synonyms

7
votes
1answer
41 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
65 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
31 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
95 views

Formula that's only satisfiable in infinite structures

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
142 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
28 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 ...
1
vote
1answer
66 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
63 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 ...
-4
votes
0answers
46 views

Which one of the following well formed formula is a tautology?

Which one of the following well formed formula is a tautology? (a) $\forall x \, \exists y \, R(x, y) \equiv \exists y \, \forall x \,R(x, y)$ (b) $\left[\forall x \, \exists y \,(R(x, y) \implies ...
0
votes
1answer
47 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
52 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
57 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
38 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
25 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
votes
0answers
20 views

Identity Substitution in Polyadic Singular Sentences

Let the sentence "Yash loves Priya" be symbolized as Lyp. Let the sentence "Priya is Dr.Lingnurkar" be symbolized as p=l. The identity substitution rule is a=b,ϕa,/∴ϕb. In my textbook, ...
1
vote
2answers
71 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
36 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 ...
2
votes
2answers
52 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
31 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
41 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
59 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
30 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
77 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
276 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 ...
0
votes
0answers
10 views

Basic Predicate & Quantifier Doubt

Which one of the following well formed formulae is tautology? (A)∀x∃yR(x,y)<=>∃y∀xR(x,y) (B)(∀x[∃yR(x,y)=>S(x,y)])=>∀x∃yS(x,y) (C)[(∀x∃y(p(x,y)=>R(x,y))]=>[∀x∃y(¬p(x,y) V R(x,y)] ...
2
votes
2answers
72 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
58 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
63 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
62 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
36 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 ...
2
votes
1answer
51 views

If a theory over a vocabulary $L$ has a model with countable domain, then it has a model with uncountable domain

For a homework I have been ask to prove that if a theory $\Sigma$ over a vocabulary $L$ has a model with countable domain, then $\Sigma$ has a model with uncountable domain. I have no idea how to ...
1
vote
1answer
55 views

Proof that an property is definable if and only if its axiomatiazable and its complement its axiomatizable

For a homework of first-order logic I need to prove that a property, lets call it P, is definable if and only if P is axiomatizable and the complement of P is axiomatizable. I have no idea of how to ...
0
votes
0answers
17 views

Reasoning in designator/formula proof

(Boldface letters denote syntactical variables.) Claim: Consider the formula $\lor \mathbf w\mathbf r$ in a first order language, where $\mathbf w$ and $\mathbf r$ are formulas. We have that $\lor ...
1
vote
1answer
45 views

Prove that the class of non-standard models of arithmetics is not axiomatizable

Given the language of arithmetics $L=\{0, 1, +, \cdot\}$ one should prove that the class of all non-standard models is not axiomatizable. So basically we have (for $M$ - standard model of ...
1
vote
0answers
18 views

Prove that class of models isomorphic to some infinite model $M$ is not countably axiomatizable

In a related question the author posted similar problem for finite models, and stated that in case of an infinite model the class of models isomorphic to the given one is not with FO-axiomatizable, ...
0
votes
1answer
57 views

Can $(\forall x) xE0=S0$ be one of axioms for a theory of arithmetic?

In Friendly Introduction to Mathematical Logic, Leary states that one of the axioms of arithmetic$N$ is: $(\forall x) xE0=S0$. which informally says that $x^0=1$ for every ...
3
votes
1answer
57 views

Encyclopedia of Mathematical Proofs with no English

I was wondering if anyone is aware of a modern book that builds a subset of elementary number theory from Peano axioms preferably in a Principia Mathematica fashion? Or similarly an encyclopedia of ...
1
vote
1answer
21 views

Satisfiability of sentences (Compactness theorem)

I'm not sure about this problem. I should determine if this if true or false: If L is languege $L-$sentence $\phi$ is satisfiable in every finite $L-$structure, is it satisfible also in every ...
-1
votes
2answers
40 views

Help with this explanation of the Material Conditional [closed]

Not too long ago I asked a question related to the material conditional that ended up proving just how limited my understanding of the material conditional actually was. In the meantime, I found a ...
0
votes
0answers
17 views

A question on First-Order Logic about Subformula

I am reading "First Order Logic" ,by R M.Smullyan, where notion of subformula is explicitly defined as the "Y is a subformula of Z if and only if there exist a finite sequence starting with Z and ...
10
votes
0answers
76 views

First order definition of $\pi$

$e$ has a very short first-order definition. It's the only constant that makes this true: $$\forall x,e^x\ge x+1$$ What about $\pi$? What's the shortest first-order definition we could give it? I'm ...
2
votes
2answers
55 views

Finite fields properties

I had to solve a question in Logics, disprove the fact that "if two statements without free variables are satisfiable in the same finite structures, then they are logically equivalent". The only ...
2
votes
1answer
49 views

Are there any consistency proofs for propositional or first-order logic?

Take for example the Hilbert-style axiomatizations of the propositional and first-order calculus. Since a crucial point when operating with a proof system is that no contradictions must be found in ...
3
votes
1answer
46 views

How to show that a logical argument is valid?

How to show that this argument is valid? $(\exists x) [p(x) \to q(x)] \to [(\forall x) p(x) \to (\exists x) q(x)]$ I started by showing that $\exists$x [p(x) $\to$ q(x)] is the premise. But I ...
6
votes
2answers
111 views

How do we know that our definitions/axioms are not contradictory?

Let us assume that we have declared some axioms. Now, we wish to declare a new axiom too. How do we establish that the new axiom is not a consequence of, nor a contradiction to the original set of ...
0
votes
2answers
43 views

confusion about 2 first order logic wff's - they seem not equal, but instructor says they are =

I had a question about two first order logic formulas given in this lecture in the series on Discrete Mathematical Structures from IIT. The instructor says (at 36:19 in the video) that the ...
0
votes
2answers
45 views

The problem of Free Variables in natural deduction rules ($\forall$, $\exists$, =).

I am in need of some clarification relating to the rules mentioned. I am doing two different courses on Logic (Philosophy / Computer Science departments) and unforunately they use slightly different ...
1
vote
2answers
61 views

Prove disconnectedness of a graph is not generalized first-order logic definable

I have proved the connectedness of a graph is not generalized first-order logic definable. How about the disconnectedness? Is it also not first-order logic definable? (A property $\Phi$ of ...