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

learn more… | top users | synonyms

1
vote
1answer
53 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
30 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
41 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
28 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
33 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
49 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
27 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
2answers
70 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
241 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)] ...
1
vote
0answers
46 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
53 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
58 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
49 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
35 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
50 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
53 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
43 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
55 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
54 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
votes
0answers
36 views

Constructive proof of Banach Alaoglu's theorem.

Is there an intuitionistic (no use of axiom of choice) proof of Banach Alaoglu?
1
vote
1answer
19 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
38 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
16 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 ...
9
votes
0answers
63 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
53 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 ...
1
vote
1answer
44 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
43 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
109 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
35 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
43 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 ...
2
votes
1answer
31 views

Hilbert Calculus, Formal Proof Converse

I'm trying to find a proof of $\exists x\phi\rightarrow\exists y\phi^x_y$ in the Hilbert-calculus while working through a completeness proof for FOL on my own. Can anyone provide a proof of this ...
2
votes
1answer
41 views

Writing a sentence that is true in one model and false in the other

Let $Σ=(R)$, where $R$ is a binary relation. Write a sentence that is true in $\mathcal M_1$ but false in $\mathcal M_2$: $$\mathcal M_1=(P(N),⊂)$$ $$\mathcal M_2=(N,<)$$ I've been ...
1
vote
1answer
19 views

Find a first order sentence satisfied by models with square domain.

(c) Let $\mathcal{L}^*\subseteq\mathcal{L}^{\text{FOPC}}$ be a first order language of predicate calculus consisting of three unary function symbols $f,g,h$. (i) Write down an ...
0
votes
1answer
35 views

if skolem($\alpha$) is valid then $\alpha$ is valid

I am trying to prove the following claim: let $sk(\alpha)$ be the sentence received from the skolemization of a given sentence $\alpha$. Prove : $\vDash sk(\alpha) \implies \vDash \alpha$ I tried ...
1
vote
1answer
64 views

Prove or disprove wether the sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true

I got stuck at this problem for some hours: Determine whether the first-order sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true, where $Q$ is a 2-ary predicate ...
2
votes
1answer
76 views

Determine under which conditions the formula $\phi[t/x]\leftrightarrow \forall x ((x=t)\rightarrow \phi)$ is logically true

I am stucked at this problem for a long time: Determine under which conditions the following first-order formula is logically true $$\phi[t/x]\leftrightarrow \forall x ((x=t)\rightarrow ...
4
votes
4answers
79 views

If $T$ a consistent set of sentences and $a,b$ sentences such that $T\vdash (a\rightarrow b)$and $T\vdash (\lnot a\rightarrow b)$ Then $T\vdash b$ [closed]

I am stucked at this problem for a long time: Let $T$ be a consistent set of first-order sentences and let $\alpha,\beta$ be sentences. Prove that if $T\vdash( \alpha\rightarrow \beta)$ and ...
3
votes
3answers
35 views

Proof Using Natural Deduction (including '=' rules)

I have a natural deduction proof that I'm stuck on. Obviously I'm not asking someone to just tell me the answer, but if anyone could help me with the next step/point out any mistakes I've made it ...
1
vote
1answer
55 views

Prove by Natural deduction that $\lnot\exists xP(x)\rightarrow\forall x\lnot P(x)$

I got this problem: Prove by Natural deduction in First Order Logic that $\lnot\exists xP(x)\rightarrow\forall x \lnot P(x)$ I tried to prove it using the Contradiction Theorem but I got ...
0
votes
0answers
12 views

About equal substitutions

When we say that two substitutions, say $\theta,\sigma$ agree on the variables of a term $t$ what exactly do we mean ? Is it that both substitution act on the same variables and substitute them with ...
0
votes
0answers
11 views

Uniqueness of terms

One usually defines first-order terms to be variable symbols, constant symbols and for terms $t_1,...,t_n$ and a function symbol $f$ also $ft_1...t_n$ to be a term, cf. Ebbinghaus et. al. Then one can ...
-2
votes
1answer
26 views

FOL formula and check valididty of this? [closed]

I think the following is logically valid, but my TA says it's not logically valid. $ \forall x (A(x) \to B(x)) \to ( \exists x A(x) \vee \exists x B(x)) $ Who Can Clarify me about this Formula ?
3
votes
1answer
26 views

Functional completeness for a ternary operator

If I define a ternary logical connective $\clubsuit(a,b,c)$ by the following truth table: \begin{array}{ccc|c}a&b&c&\clubsuit(a,b,c)\\\hline ...
3
votes
0answers
87 views

Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials

I'm stuck at the following exercise: I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all ...