Consider the boolean poset $2^{[n]}$. Is it true that for each rank $k< \frac{n}{2}$ and each positive integer $t\le \binom{n}{k}$, there is a perfect matching between the first $t$ elements of level $k$ of the poset when written out in lexicographical order and the first $t$ elements of level $...

In discovering that Presburger's arithmetic is one of the weaker systems in PA that does not violate Godel's first incompleteness theorem. Upon reading the wiki article, it said that Presburger proved that his arithmetic is decidable, complete, and consistent. The part that I've been trying to fi...

Is it possible to define pairing function (and the inverses) in Presburger arithmetic? I would guess no but I can't locate a reference nor construct a proof to one way or another.

I'm learning about model theory and first order logic. Recently, I read about finite model property and Presburger arithmetic, and I have two questions about them: Does Presburger arithmetic has finite model property? Given a Presburger formula. Clearly, it is SAT. Does it have finite number of...

Is there anything expressible in Presburger arithmetic that would seem impressive to students at an undergraduate level?

Peano arithmetic defines multiplication recursivly as: $$\begin{gather}a\cdot0=a\\a\cdot S(b)=a+(a\cdot b)\end{gather}$$ Why is this not possible in Presburger arithmetic?

I have a question about nonstandard models of Presburger Arithmetic. I read that an example of a nonstandard model is the set of polynomials with rational coefficients with positive leading coefficient and a (positive) integer constant coefficient. It is obvious that all axioms other than the ind...

Presburger Arithmetic is a decidable theory but if multiplication is added to it would that theory remain decidable? UPDATE: I began to write out the axioms that would distinguish Presburger Arithmetic from Peano Arithmetic and realized that adding the Peano axioms which give semantics for mult...

From Wikipedia's article on Presburger arithmetic: Then Fischer and Rabin (1974) proved that any decision algorithm for Presburger arithmetic has a worst-case runtime of at least $2^{2^{cn}}$, for some constant $c>0$. Hence, the decision problem for Presburger arithmetic is an example of a d...

Suppose I want to decide whether the statement $$\exists x.(x+x+x+1+1+1=1+1+1+1+1)$$ is part of the set of consequences of Presburger arithmetic. In more readable language, this is saying that $$\exists x.(3x+3=5)$$ or $$3 \equiv_3 5$$ Using some metatheory, it is easy to compute the r...

I have done an exercise that goes like this: Consider the operator $\Phi: \ell_1\to(\ell_\infty)'$ that associates each $x=(x_j)_j\in\ell_1$ to $\Phi (x)\in (\ell_\infty)'$ given by $\Phi(x)(y)=\sum x_j y_j$, for all $y=(y_j)_j\in\ell_\infty$. Show that $\Phi$ is well defined, is linear and b...