Questions tagged [first-order-logic]

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

2,911 questions
12 views

Are there non-linear forms of arithmetic that is logically axiomatized?

Informal idea: I'll visualize Peano arithmetic "PA" as arithmetic rising from a linear structure, we can call it in graph terms a linear directed path with a beginning and no end. The numbers are the ...
39 views

Restrictions on Existential Introduction in first-order logic

I'm trying to understand the restrictions on Existential Introduction (EI) as defined by the Stanford introduction to logic. Three separate restrictions are mentioned: The term being replaced cannot "...
25 views

First order logic and conjective normal form [on hold]

Consider the following paragraph and please answer these questions below “Anyone who eats junk food or drink carbonated beverages will be a cancer victim. It is not the case that some people eat ...
33 views

Can ZFC be interpreted in this sole class theory about ordinals?

Informally the following theory is about classes of ordinals, so only von Neumann ordinals can be elements of classes. It has a primitive partial binary function of ordered pairing over ordinals, so ...
44 views

63 views

The theory of (Z, s) has quantifier elimination

Let $T = \text{Th}(\mathbb{Z}, s)$ where $s$ is the successor function. I want to show quantifier elimination (QE) for $T$ and construct a concrete $\omega$-saturated model. However, I am unsure ...
26 views

Is this formula an atomic formula?

For example, the formula $\forall x.\;P(x)\wedge∃y.\;Q(y,f(x))\vee∃z.\;R(z)$ contains the atoms $$P(x),\;Q(y,f(x)),\;R(z)$$ I'm reading definition from wikipedia but I'm somehow confused if this ...
53 views

A theorem of Skolem

I believe the following is a theorem of Skolem. How is it proved, or where may I find a proof? Suppose $\mathscr A$ is a formula of first-order logic in which no constants or function symbols occur ...
42 views

Mistake in $A \times B \subseteq C \times D \rightarrow A \subseteq C \wedge B \subseteq D$

I am currently going through Velleman's How to prove it and I am trying to understand exercise 12 from chapter 4.1. The exercise asks to show whether the theorem in the title is correct. It is ...
24 views

51 views

43 views

What is the first order logic statement of “this field is of characteristic zero”?

I want to state that a field $F$ is of characteristic zero in logical notation to an audience without referring them to the meaning of the characteristic of a field. My first thought was the ...
75 views

Is having models with ever increasing cardinality of the power set of $\omega$ is a theorem of ZFC?

I'll present this claim informally and try to write it formally as much as I can. Statement: every model of $\sf ZFC$ that statisfies the statement that the power set of $\omega$ is equal to a ...
86 views

Had $\sf Con(ZFC)$ been explicitly written in first order language?

One always hear of $\sf Con(ZFC)$ and what is meant by that is an arithmetical sentence that is equivalent to $\sf ZFC \text { is consistent }$ that is written in the language of first order $\sf ZFC$....
Can we have a strong class theory in which all sets are Dedekindian finite, and that has some of its sets being Tarski infinite? By strong I mean that it can interpret $\sf ZFC$ and its extensions. ...
The universal $(\forall)$ and existential $(\exists)$ quantifiers are the normal quantifiers which one comes across frequently. Others like uniqueness quantifier $(\exists !)$ are also there. But in ...