New answers tagged first-order-logic
2
votes
Accepted
$\mathcal{Z}\models \phi(13)$ if and only if $\mathcal{Z}\models\phi(-13)$
The function $f(n) = -n$ is an automorphism of $\mathcal{Z}$. Since isomorphisms preserve satisfaction of formulas, for any formula $\varphi(x)$, $\mathcal{Z}\models \varphi(13)$ if and only if $\...
- 73.8k
3
votes
Accepted
Classification of $\beth_1$-sized models of DLOWE.
The $\aleph_0$-categoricity of DLOWE is misleading. In fact, DLOWE is unstable and so in general has as many models of a given uncountable cardinality $\kappa$ as it possibly could, namely $2^\kappa$. ...
- 240k
4
votes
Open source program that generate "random" theorems by exploration
I highly doubt you ever get any interesting theorem, even if you were to run such software for the remainder of your lifetime!
Let's take something like Peano Arithmetic (PA). How do we enumerate its ...
- 98.1k
2
votes
Accepted
Axiomatize the class of existentially closed structures
For inductive theories $T$, $T$ has a model companion if and only if the class of existentially closed models of $T$ is elementary (axiomatized by a first-order theory). An inductive theory satisfying ...
- 73.8k
3
votes
Count the number of non-isomorphic models for a theory $T$ describing infinitely branching equivalence classes, each class infinite
I am still a little lost on how to intuitively understand the following definition of a type
A type (relative to $T$) is just a set of formulas which can be simultaneously satisfied by a tuple from a ...
- 73.8k
0
votes
Accepted
Expand a model to have a well ordering. Prove that the set of all definable elements over a subset $X$ is the universe of an elementary substructure
When in doubt, induct on the number of quantifiers.
Let's call our substructure $\mathcal{H}$.
Let $\varphi(z)$ be a formula with parameters in $X$ with one free variable $z$.
I claim that $\mathcal{...
- 10.2k
1
vote
Accepted
$tp^\mathbb{Q}(a/\mathbb N) = tp^\mathbb{Q}(b/\mathbb N)$ iff there is an automorphism $\sigma$ of $\mathbb Q$ fixing $\mathbb N$ and $\sigma(a)=b$
Let $a,b\in\Bbb Q$ such that $\text{tp}^{\mathbb Q}(a/\mathbb N) = \text{tp}^{\mathbb Q}(b/\mathbb N)$.
Your proof that
$$\forall n\in\Bbb N\quad(n<a\iff n<b)$$
is correct,
and similarly
$$\...
- 29.5k
2
votes
Accepted
Prove that divisibility between two natural numbers is not definable in arithmetic
We can do this by showing that the resulting theory is Peano Arithmetic and thus incomplete, while Presburger Arithmetic is complete.
We'll do this by showing that we can define multiplication if we ...
- 10.2k
0
votes
Why is the cardinality of a first-order language max{$\aleph_0, k$}?
Consider some language $\mathcal{L}$ of an arbitrary type $\langle (r_i)_n; (a_j)_m; \kappa\rangle$.
Let us begin with an analysis of its set of terms:
$\mathrm{TERM}_\mathcal{L} = \bigcup \mathrm{...
- 152
1
vote
Accepted
Proof that Skolem Arithmetic is a complete theory
As is the case with Presburger arithmetic, Skolem arithmetic satisfies a weak version of quantifier elimination (see e.g. Emil Jerabek's old MO answer), and this can be used to prove completeness. ...
- 240k
11
votes
Understanding ZFC
You asked:
If one is to do mathematics rigorously, they would like every concept they mention, such as a function or relation, to have a precise definition. How can we do that with ZFC if ZFC does ...
- 40k
3
votes
Accepted
Axiomatizing ZFC+Con(ZFC) without adding a constant symbol
Even though ZFC is not finitely axiomatizable, it is recursively axiomatizable: there is an algorithm to determine whether a given formula is an axiom of ZFC. Using this, we can define a predicate $\...
- 3,707
15
votes
Understanding ZFC
ZFC does generate a “theory”. Formally speaking, a theory is simply a set of sentences in the given formal language. Any set of axioms generates a theory, namely the collection of sentences provable ...
- 1,489
0
votes
Axiomatizing ZFC+Con(ZFC) without adding a constant symbol
Use compactness.
You get the existence of a model $w$ if every finite subset of ZFC is finitely satisfiable. That can be asserted without adding a constant symbol.
For concreteness, for all finite ...
- 10.2k
5
votes
Is there a first-order sentence defining a cardinal?
Yes, here's one way to do it. It's kind of unsatisfying because it isn't succinct like the first-order characterization of an ordinal.
As has been established, being an ordinal is a first-order ...
- 10.2k
0
votes
$\varphi$ is quantifier free sentence, $T$ a theory, $\vec{c} \not\in T$. $T \vdash \varphi(\vec{c})$ implies $T \vdash \forall x \varphi(\vec{x})$?
The result is known as Generalization on constant.
The "trick" is simple: if you have a proof of $\varphi(c)$ and $c$ is not used in the set $T$ of assumptions (axioms), you can replace ...
- 93k
1
vote
Accepted
How to prove these three properties about sets?
You are correct about (b), it is likely a typo and they meant A × B ≠ ∅, instead. ( try proving (b) under the assumption that A × B ≠ ∅)
As for (a) your proof if fine, it relies on the fact that (p ⟺...
- 677
-1
votes
Proof of contraposition theorem using logical (semantic) entailment definition
$W \cup \{\phi\} \models \neg \psi \iff W \cup \{\psi\} \models \neg \phi$ means: $\mathrm{Mod}(W \cup \{\phi\}) \subset \mathrm{Mod}(\neg \psi) \iff \mathrm{Mod}(W \cup \{\psi\}) \subset \mathrm{Mod}(...
- 152
2
votes
Accepted
Prove that the set of nonprime numbers $>0$ is a spectrum
Here's an argument that generalizes nicely to similar sets in place of the composites, at the cost of resulting in less natural structures:
Take as our language $\{U,V,f\}$ where $U,V$ are unary ...
- 240k
3
votes
Accepted
Is ZFC independent of the logic used?
Classical first order logic has many different equivalent presentations (not all of which are based on axioms!). One axiomatic variation can be found here, but really if you want to learn it you ...
- 56.7k
8
votes
Nonstandard infinite / hyperfinite sum in IST
You asked several questions that should really be separate posts, but let me start by answering one. You asked:
"If anyone could provide a detailed proof that a sum indexed by an unlimited ...
- 40k
15
votes
Accepted
Nonstandard infinite / hyperfinite sum in IST
Welcome to Math.SE!
You did not indicate how much background you have in Internal Set Theory (IST) - but based on what you wrote, it seem like you have a few misconceptions about it. Let us start by ...
- 9,897
4
votes
Accepted
When we say "cardinality of first order language L" and "cardinality of a structure or model" what we are meaning?
The cardinality of a structure means the cardinality of the underlying set of the structure. This is exactly what you should expect from ordinary mathematical usage: the cardinality of a group or a ...
- 73.8k
4
votes
When we say "cardinality of first order language L" and "cardinality of a structure or model" what we are meaning?
The cardinality of the structure is the cardinality of the domain set of the structure.
The cardinality of the language can mean one of two things:
The cardinality of the set of non-logicial symbols
...
- 56.7k
1
vote
Any formula is logically equivalent to a formula with all terms of height ≤ 1.
Long comment
The "height's def in this book may be a number of connective operations"; this is the height of a formula. Terms have no connectives.
For a term, the height (or depth) means in ...
- 93k
0
votes
Accepted
Is $x$ a free variable in sentences like "$x\lt 7\Rightarrow x\lt 5$"?
It depends on the context. If your statement here was a line in a formal proof, the $x$ would be a free variable in that statement since it is not quantified.
For readability in informal presentations ...
- 14.4k
0
votes
Is $x$ a free variable in sentences like "$x\lt 7\Rightarrow x\lt 5$"?
"$x<7\to x<5$" is not always TRUE. Because the logic behind it is $x<7$ implies $x\epsilon(-\infty,7)$ and $x<5$ implies $x\epsilon(-\infty,5)$ . Now according to your question &...
- 1,141
5
votes
If A is a substructure of B and A is isomorphic to B then A is an elementary substructure of B
The answer to your main question is no, and in fact $\mathbb{Z}$ itself gives us a counterexample: the substructure $\mathbb{E}$ of even integers is clearly isomorphic to $\mathbb{Z}$ itself, but is ...
- 240k
1
vote
Accepted
Enderton's "Mathematical Introduction to Logic": Is he proving second order induction?
When teaching "Intro to Proofs" if we want to go over induction on $\mathbb N$, we'll almost certainly opt to phrase everything in terms of full second-order induction, even though it's ...
- 56.7k
Top 50 recent answers are included