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

Showing that $\neg[ Px\rightarrow \forall xPx]\vdash \forall xPx$ via generalization theorem

Let $P$ be a unary relation, we want to show that: If $\neg[ Px\rightarrow \forall xPx]\vdash Px$ then $\neg[ Px\rightarrow \forall xPx]\vdash \forall xPx$. I want to do that via generalization ...
1
vote
0answers
15 views

Is this theorem equivalent to “existential instantiation” rule?

In Enderton's, There is a theorem called "existential instantiation", it says: Assume that the constant symbol $c$ does not occur in $\alpha ,\beta , \Gamma$ and that: $$ ...
3
votes
1answer
34 views

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$?

Should $x$ be not free in $\beta$ to prove $\vdash [ \forall x(\beta\rightarrow \alpha)\rightarrow (\exists x\beta\rightarrow \alpha)]$? In "Mathematical Introduction to Logic, Enderton" This is an ...
-1
votes
0answers
36 views

Relations commuting with logical equivalence.

I'm looking for theorems of the form, 'Relation X commutes with logical equivalence', where X is NOT uniform substitution. What's the best place to find such theorems?
2
votes
0answers
14 views

Find a first order sentence satisfied in every finite semigroup but not in every compact semigroup

Several properties that hold in nonempty finite semigroups also hold in nonempty compact semigroups. Furthermore, many of these properties can be formulated by a first order sentence. For instance, ...
-1
votes
0answers
75 views

What is a Horn Clause? [on hold]

I am not an expert in Mathematics :) thus if someone can let me know What is a Horn Clause in layman's terms? I know it is used in First order Logic but I am unable to understand what is it and how to ...
1
vote
2answers
46 views

Proving contradiction with logical identities

We know that p → q is not equivalent to q → p. But suppose we make a proof system that has all the rules of logical identities plus the rule (“commutativity of implies”) p → q ≃ q → p. (We are using ...
0
votes
1answer
19 views

What is a predicate exactly in predicate logic?

I have been reading Predicate Logic couple of days and while everything has been pretty intuitive so far I understood that I do not exactly understand what the predicate is. This became clear after I ...
0
votes
1answer
18 views

Expanding a structure while keeping it a model of theory

Just so you know, this is a homework-related question. Let $L=\{0,f\}$ a language, and denote $(f^M)^n(a)=f^M(f^M(...f^M(a))...)$ I must show that there exists a model $M$ that satisfies: for ...
0
votes
2answers
73 views

First Order Logic vs First Order Theory

What is the difference between a First Order Logic and a First Order Theory. Can anybody please describe what each one precisely (formally) is? For a bit more elaboration on the question, I think ...
0
votes
2answers
40 views

Show this language structure models this sentence.

In an effort to educate myself, I am attempting the second problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below: Let $\mathcal{L} = \{\cdot, e\}$ be the ...
2
votes
2answers
63 views

First-order logic representation

I am having trouble translating these clauses to first order logic. 1) The only difference between a cat and a tiger is that a tiger kills. 2) If someone likes only people of the same sex then he is ...
1
vote
1answer
27 views

Is it impossible for a quantifier-free formula to contain free variables?

A first-order language must specify its signature to fix its alphabet of non-logical symbols. A signature $\Sigma$ contains the set $\Sigma^F$ of function symbols and the set $\Sigma^P$ of predicate ...
0
votes
0answers
51 views

Let $T=\{17\}, U=\{6\}, V=\{24\}$ and $W=\{2,3,7,26\}$. In which of these four different universes is the statement true?

sLet $T=\{17\}, U=\{6\}, V=\{24\}$ and $W=\{2,3,7,26\}$. In which of these four different universes is the statement true? a) $(\exists x)(x\,odd\implies x>8)$ b) $(\exists x)(x\, odd\wedge ...
1
vote
1answer
43 views

Is it possible to characterize the theory of Integral domains with first-order logic alone ?

Is it possible to characterize general ring theory with first-order logic alone ? Is it possible to do so for the theory of Integral domains ?
0
votes
0answers
18 views

Least finite linear orders with same theory in monadic second order logic.

Today I want to ask a relaxed version of my last question. So if somebody finds a solution to that question he will immediately get a solution for this question here. Question. Let $m<\omega$ ...
2
votes
0answers
32 views

When do finite linear orders have the same theory in MSO?

Let $\mathfrak A$ and $\mathfrak B$ be finite linears orders and $m<\omega$. Then we have $$\mathfrak A \equiv^m_{FO}\mathfrak B \quad\text{iff}\quad |A|=|B| \,\, \text{or}\,\, |A|,|B|\ge 2^m-1.$$ ...
2
votes
0answers
62 views

$\overline{\mathbb Q}$ and $\mathbb C$ same first order theory

How do you show that $\overline{\mathbb Q}$ (the algebraic closure of $\mathbb Q$) and $\mathbb C$ have the same first order theory over the signature $(0,1,+,\cdot)$?
0
votes
1answer
66 views

First Order Logic prove there exists a Model that has an infinite member

I'm doing some extra self-exercises on first order logic (I'm taking the course through open university) and I've come across this question: Let there be a language $L = \{ +, \cdot, 0, 1, < ...
1
vote
2answers
64 views

Why cant AND and NOT represented only with IMPLICATION?

Can someone please explain why can't I use only implication to represent AND and NOT with proof as well? I know that I can represent OR simply by using implication. Was thinking if I could find ...
1
vote
0answers
17 views

Does this statement generalize to inductive inference?

The following statement is true for deductive logic (e.g. in a boolean algebra): $$a\wedge b \Rightarrow \neg c \quad \text{if and only if }\quad a \Rightarrow \neg(b\wedge c).$$ It seems like you ...
10
votes
1answer
218 views

First Order Logic: Prove that the infinitely many twin primes conjecture is equivalent to existence of infinite primes

I'm learning First Order Logic independently using a college textbook. I've been doing some self exercise question in it and came across this one, which I can't seem to figure out how to do: Let ...
2
votes
1answer
67 views

How to rewrite a theorem in symbolic logic?

I'm currently working on some discrete mathematics work and I've encountered a question I'm not sure how to answer exactly. Precisely, I'm trying to translate or re-write a division algorithm into ...
1
vote
2answers
46 views

First Order Logic and groups: Prove that no $T$ exists such that $M \vDash T \cup T_{grp}$ **IFF**

I'm learning First Order Logic by myself using a University textbook, and it has the following question in it (as a self exercise): Let $L = \{\cdot, e \}$ the language of Groups and let $T_{grp}$ be ...
0
votes
1answer
35 views

Determining the negation of a logical statement?

I'm currently working on some first order logic questions as a brush up for a discrete mathematics course and I'm having a bit of trouble remembering exactly how to find the negation of a logical ...
1
vote
2answers
97 views

The definition of term in Enderton's Logic book

In page 74 of Enderton's book A Mathematical Introduction to Logic (Second Edition), Enderton defines term as follows: "The terms are defined to be those expressions that can be built up from ...
1
vote
1answer
93 views

Prove that for an arbitrary (possibly infinite) language, that for a finite L-structure $M$, if $M \equiv N$ then $ M \cong N$ [duplicate]

Prove that for an arbitrary (possibly infinite) language, that for a finite L-structure $M$, if $M \equiv N$ then $ M \cong N$ I'm struggling to think of what to do, I presume the best thing is ...
1
vote
0answers
47 views

Would a “Prenex Sum of Products” be canonical?

I know that prenex normal form (PNF) is not canonical, and there is an example in Wikipedia showing two equivalent formulae in PNF that differ in their prefixes, but have equal matrices: $\forall x ...
0
votes
0answers
41 views

Would a “prenex Blake normal form” be canonical?

I know that prenex normal form (PNF) is not canonical, and there is an example in Wikipedia showing two equivalent formulae in PNF that differ in their prefixes, but have equal matrices: $\forall x ...
1
vote
1answer
20 views

Definable relations in given structure (first order logic)

I'm bothering with this problem. I'm given a first order predicate language with only one ternary predicate symbol $p$ (no equality sign). Also there is structure for the language $\mathcal{A}$ over ...
0
votes
1answer
28 views

Show that: A is consistent iff Ded(A) does not equal Fml(L)

For a language L and set of L-formulas A we must show that A is consistent iff $Ded(A) \ne Fml(L)$ where $Ded(A)$ = set of all formulas deduced from A $Fml(L)$ = set of all L formulas The => ...
2
votes
1answer
49 views

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map.

Let $M$ and $N$ be $L$-Structures, $h\colon M \cong N$ an isomorphism. Show $h$ is an elementary map. I'm not even sure where to begin at the moment. I was informed of "induction on the ...
3
votes
2answers
49 views

What does “decidability” of a Model mean exactly?

I'm looking at the theorem concerning the Model of Arithmetic: M arith = (Integers, +, *, <) is undecidable. What does the "decidability" of a model mean exactly? Does that mean that "the ...
0
votes
1answer
28 views

For an L-structure $M$, and a formula $\phi$, in which of the cases does $M \models \phi(x/2)$?

For a) $\phi(x)$ is $(\forall y(y=1+1 \implies x=y))$ b) $\phi(x)$ is $(\forall x(x=1+1 \implies x=y))$ The answer is supposed to be a) but I don't know why. I guess I don't fully understand the ...
10
votes
2answers
166 views

How to prove that Gödel's Incompleteness Theorems apply to ZFC?

Let us denote Robinson Arithmetic as Q and Primitive Recursive Arithmetic as PRA. Let $T$ be a formal theory formulated in the language of arithmetic. According to this page on the Stanford ...
-1
votes
1answer
113 views

Can someone explain Godel's Completeness theorem in the simplest terms?

I wrote a blog on logic. http://deepturtel.blogspot.com/2014/12/logic.html I may need to correlate this with Godel's Completeness Theorem. I understand Principia Mathematica (without the formal ...
3
votes
2answers
219 views

Good recommendations to study Algebraic logic

I've asked before about good recommendations to study algebra for the sake of algebraic logic and I've got very good recommendations. I wonder if you have some recommendations to start studying ...
1
vote
2answers
80 views

First Order Logic - coming up with an example

I'm learning First order logic using a university textbook and it has the following question: Give an example of languages $L'$ and $L$, $L \subseteq L'$, as well as formulas $A$ and $B$ in ...
11
votes
3answers
391 views

Axiom of Choice: What exactly is a choice, and when and why is it needed?

I'm having trouble understanding the necessity of the Axiom of Choice. Given a set of non-empty subsets, what is the necessity of a function that picks out one element from each of those subsets? For ...
0
votes
1answer
32 views

Looking for counter example - compactness theorem

Let $S$ be a family of sets. We say a subset $S'\subseteq S$ is good if we can choose from every set $A\in S'$ a representative $x_A$ s.t.: For every three sets $A,B,C\in S'$ it holds that $(x_A + ...
5
votes
3answers
242 views

What is the first order axiom characterizing a field having characteristic zero?

In this thread on the axioms of $\mathbb Q$ it's stated that a field having characteristic zero can be written down in first-order logic. The definition in the logic lecture notes I work with (by ...
0
votes
1answer
53 views

Indiscernibility of indiscernibles in second order logic

It is not clear to me if the statements in $0^\#$ remain indiscernible when we move to second order logic. Or are there second logic formulas that can discriminate between first order indiscernibles?
1
vote
1answer
32 views

Stuck on basics: How to prove that {subst($\alpha$,s)} is well defined?

So I feel like this is a really basic point that I'm missing and I can't really manage to prove that: So I have a substitution function $s: Var \rightarrow WFF$ and a subst function: $WFF \times ...
4
votes
0answers
89 views

Is there a logic to formalize the concept of “understanding”

The question may seem little bit weird given that philosophers have been struggling to have a full grasp on the concept of "understanding". But I'm wondering if there are any logics (modal-based or ...
2
votes
1answer
50 views

Flattening quantification over relations

I already asked this question in stack overflow here and somebody suggested to post it here. I repeat the question again: I have a Relation f defined as $f: A \to B × C$. I would like to write a ...
2
votes
1answer
44 views

Consistency vs Inconsistency in a set of sentences: which is more common

I'm curious whether there is any research in the "probability" that a set of sentences in a first-order logic is consistent. Obviously, there are an infinite number of inconsistent sets and an ...
2
votes
2answers
50 views

Robinson's Consistency Theorem for first order languages

Is there a simple proof for the case of first order languages for this theorem? Let $L_1$,$L_2$ be first order languages and $L$=$L_1$ $\cap$ $L_2$. Let $T_1$, $T_2$ be consistent ...
0
votes
1answer
49 views

Well-foundedness is not a first order property.

In the book 'Logic, Induction and Sets' by Thomas Foster I read the following in page 100 (Section 'The language of predicate logic'): "We can show that well-foundedness is not a first-order property ...
2
votes
1answer
48 views

What does not having a first-order frame imply for models?

There are formulas in modal logic which which do not have a first-order frame condition, as stated here (Non-Sahlqvist formulas, Wikipedia). An example is the McKinsey formula for $p$: ...
0
votes
1answer
16 views

Definable with and without parameters with one unary predicate symbol

Suppose you have a structure with universe $M =\{a,b,c,d,e\}$ with unary predicate symbol $P$. Suppose $I(P)$ is the set containing $a$ and $b$. I found the set of definable sets without parameters ...