Articles of first order logic

Need help with first order logic

I’m trying to understand first-order-logic and have this simple question. Given the following predicates: $Thing(t)$, which states that $t$ is a thing; $Word(w)$, which states that $w$ is a word; and $HurtsYouMoreThan(x,y)$, which states that $x$ hurts you more than $y$, I need to create a first-order-logic statement that says “There is nothing that hurts […]

How can universal quantifier manipulation rules be made redundant by the generalization rule (metatheorem)?

On the Wikipedia page for Hilbert style axioms, in the “Logical axioms” section, it gives the axioms to manipulate universal quantifiers : $Q5. \forall x(\phi)\rightarrow \phi[x:=t] $ $Q6. \forall x(\phi \rightarrow \psi)\rightarrow (\forall x(\phi) \rightarrow \forall x (\psi) )$ $Q7. \phi\rightarrow \forall x (\phi) $ where x is not free in $\phi$ and then says […]

There exists no zero-order or first-order theory for connected graphs

Prove that no zero-order theory (i.e. propositional calculus, without quantification) or first-order theory can describe the “connected graph” (i.e. from any point one can reach each other point in finite steps). The only weapon I know in these situations is the compactness theorem: so I would like to prove that 1) such a theory is […]

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my “proof” of “ZF is inconsistent” was that I was not considering that there are models with non-standard integers. However now I think I developed an actual deduction of $T \vdash \text{Cons} T$ for any sufficiently powerful theory $T$ thus implying by Godel’s […]

expressability of finite and infinite ramsey theorems in Peano arithmetic

Finite Ramsey theorem: $ \def\nn{\mathbb{N}} $ For any $e,k,r \in \nn$, there exists a least natural number $m=R(e,r,k)$ so that, for any set $M$ with cardinality at least $m$, with each of the $e$-sets of $M$ coloured with one of $r$ colours, there exists a subset $H$ of $M$ with cardinality $k$ so that all […]

Is there a name for this principle of logic? From $\exists a P(a), !bQ(b), \forall a(P(a) \rightarrow Q(a)),$ infer $\forall a(Q(a) \rightarrow P(a))$

In set theory, we have the following: Observation 0. Let $X$ denote a set. Let $A$ and $B$ denote subsets of $X$. Then if $A$ has at least one element, $B$ has at most one element, and $A \subseteq B$, then $B \subseteq A$. Rehashing this into logical language, we have: Observation 1. $$\frac{\exists a […]

When is de-Skolemizing statements appropriate?

In first order logic we often convert prenex normal form statements to Skolem normal form statements to eliminate the existential quantifier: $\exists$x$\forall$y$\exists$z$\phi$(x,y,z) becomes $\forall$x$\phi$(a,x,f(x)) Where a is a ‘Skolem constant’ and f is a ‘Skolem function’ Because we remove all the existential quantifiers, we can drop all quantifiers and consider all variables implicitly universally quantified […]

Does using constant symbols in a first-order theory implicitely induce an existence axiom?

If I have a first-order theory $T$ with a constant symbol $c$ in its language, does this implicitely imply that I have to include the following axiom into $T$? $$\exists x[x=c]$$ More generally, for an n-ary function symbol $f$, do we have to include the following axiom? $$\forall y_1,…,y_n\exists x[f(y_1,…,y_n)=x]$$

A first order theory whose finite models are exactly the $\Bbb F_p$

Is there a first order theory $T$ in the language of rings such that its finite models are exactly the fields $\Bbb F_p$ with $p$ prime (but no $\Bbb F_q$ with $q$ a proper prime power is a model of $T$)? EDIT: Since this question turned out to be trivial, I asked if it is […]

How to find out if a set of formulas in first order language is inconsistent?

What is the best and quickest way to find out if a set of formulas in first order logic is inconsistent? I really have no idea how to do that. As an example the $\forall x \exists y \forall z$ $ \phi$ is inconsistent with $\exists x \neg \exists y \exists z$ $ \phi$ but it is […]