Questions tagged [first-order-logic]

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

2,898 questions
7k views

429 views

Defining new symbols (abbreviations) in first-order logic

In first order logic it is common (and just about necessary) to introduce new symbols which have been defined in terms of the "fundamental" symbols of a given theory. For instance, the signature of ...
448 views

Infinitely many axioms of ZFC vs. finitely many axioms of NBG

It is known that ZFC needs infinitely many axioms, but NBG (Neuman-Bernays-Gödel set theory) is finitely axiomatizable (as first-order theories of course). But both theories agree completely on the ...
696 views

What happens if the empty set is not a subset of every set? [duplicate]

$\hskip8pt$ Definition. If $A$ and $B$ are sets, then $A$ is a subset of $B$ iff every element of $A$ is also an element of $B$. The empty set $\{\}$ is a subset of every set because, if $A$ is an ...
677 views

Why does Skolemming not preserve validity?

I'm wondering what exactly is meant when people say "Skolemization preserves satisfiability but not validity". I'm having trouble wrapping my brain around it because I think of Skolemization, when ...
201 views

Where are the model theory concepts from?

Look at the following definition. Definition. Let $\kappa$ be an infinite cardinal. A theory $T$ is called $\kappa$-stable if for all model $M\models T$ and all $A\subset M$ with $|A|\leq \kappa$ we ...
744 views

Are these formal formulas equivalent?

My textbook gave the following $\forall x_0 (\exists x_1 \ x_0=(\mathbf{O''} \cdot x_1) \vee \exists x_1 \ x_0=((\mathbf{O''} \cdot x_1)+\mathbf{O'}))$, then commented on the syntax and why the ...
579 views

Is the set of PA theorems the same as the set of solvable halting problems?

I am not sure if this is a trivial question. By Post's theorem we know that every PA (first order logic) theorem is equivalent to stating that a given input C in a given Turing machine halts or doesn'...
840 views

Uncountable Dense Linear Orders

Is there an example of two uncountable equipollent dense linear orders without endpoints that don't satisfy the same first order properties? Or is it true that two uncountable equipollent dense linear ...
Is the term $$\forall x p(x) \rightarrow \forall x q(x)$$ equal to $$\forall x (p(x) \rightarrow \forall x q(x))$$ or $$(\forall x p(x)) \rightarrow (\forall x q(x))$$ In other words: What is the ...
Given a first-order logic theory $T$ and and a formula $F$, suppose I have semantically proved that $T\vdash F$. That is, I have proved that any model $M$ of $T$ satisfies $F$ and I conclude by Gödel'...