11institutetext: Free University of Bozen-Bolzano 11email:
<EMAIL_ADDRESS>
# Strongly First Order, Domain Independent Dependencies: the Union-Closed Case

Pietro Galliani  0000-0003-2544-5332

###### Abstract

Team Semantics generalizes Tarski’s Semantics by defining satisfaction with
respect to sets of assignments rather than with respect to single assignments.
Because of this, it is possible to use Team Semantics to extend First Order
Logic via new kinds of connectives or atoms – most importantly, via
_dependency atoms_ that express dependencies between different assignments.

Some of these extensions are more expressive than First Order Logic proper,
while others are reducible to it. In this work, I provide necessary and
sufficient conditions for a dependency atom that is _domain independent_ (in
the sense that its truth or falsity in a relation does not depend on the
existence in the model of elements that do not occur in the relation) and
_union closed_ (in the sense that whenever it is satisfied by all members of a
family of relations it is also satisfied by their union) to be _strongly first
order_ , in the sense that the logic obtained by adding them to First Order
Logic is no more expressive than First Order Logic itself.

###### Keywords:

Team Semantics Dependence Logic First Order Logic.

##  1 Introduction

Team Semantics is a generalization of Tarskian Semantics in which formulas are
satisfied or not satisfied by sets of assignments (called _teams_) rather than
by single assignments. This semantics was developed by Hodges in [18] as a
compositional alternative to the game-theoretic semantics for Independence-
Friendly Logic [16], an extension of first order logic (related to _Branching
Quantifier Logic_ [15]) that adds to it _slashed quantifiers_ $\exists
x/\vec{y}$, with the meaning of “there exists some $x$, chosen independently
from all variables in $\vec{y}$, such that…”.

As observed by Jouko Väänänen, in Team Semantics this notion of
dependence/independence between variables corresponds precisely to database-
theoretic _functional dependence_ [1]. This observation led to the development
of _Dependence Logic_ [24], which separates the notion of dependency
restriction from the notion of quantification by means of (functional)
_dependence atoms_ $=\\!\\!(\vec{y},x)$ meaning “the value of $x$ is
_determined by_ the values of $\vec{y}$”; and, later, to the development of an
entire family of novel extensions of First Order Logic likewise obtained by
adding to it new atoms to express forms of dependence/independence between
variables.

The properties of some of the logics thus generated are, by now, fairly well
studied; but much is still not known about the general classification of the
logics obtainable from First Order Logic in this manner. In particular, no
full answer yet exists to the following question: which dependencies between
variables, if added to First Order Logic as new atoms, generate a logic that
is more expressive than First Order Logic, and which ones instead fail to do
so? Aside from being a natural starting point for a general classification of
these extensions of First Order Logic, this question is of philosophical
interest: after a fashion, a full answer to it would clarify how much we can
get away with adding to First Order Logic (in terms of novel atoms specifying
dependencies between variables) before the resulting logic becomes
unrecoverably second-order in nature.

This paper continues a series of works [5, 6, 9, 7, 8, 10] that attempt to
solve this problem with respect to restricted classes of dependencies, as part
of a program to eventually reach a general characterization. In particular,
here we will focus on dependencies that have the two properties of being
_domain-independent_ and _union-closed_ , which are shared by many of the
dependencies of interest in the literature, and provide a full solution to the
problem for their case.

##  2 Preliminaries

######  Definition 1 (Team)

Let $\mathfrak{M}$ be a first order model with domain $M$ and let $V$ be a set
of variables. Then a team over $\mathfrak{M}$ with domain $V$ is a set of
assignments $s:V\rightarrow M$. Given such a team $X$ and some tuple of
variables $\vec{v}=(v_{1}\ldots v_{k})\in V^{k}$, we will write $X(\vec{v})$
for the $|\vec{v}|$-ary relation $\\{s(\vec{v}):s\in X\\}\subseteq M^{|v|}$,
where $s(\vec{v})$ is the tuple $(s(v_{1})\ldots s(v_{k}))$.

######  Definition 2 (Team Semantics for First Order Logic)

Let $\mathfrak{M}$ be a first order model with domain $M$, let $\phi$ be a
first order formula in Negation Normal Form111In this work we will assume that
all expressions are in Negation Normal Form. Also, we will use the usual
abbreviations of First Order Logic, such as $\vec{x}=\vec{y}$ for
$\bigwedge_{i}(x_{i}=y_{i})$ where $\vec{x}=(x_{1}\ldots x_{k})$ and
$\vec{y}=(y_{1}\ldots y_{k})$ are tuples of variables of the same length. over
the signature of $\mathfrak{M}$, and let $X$ be a team over $\mathfrak{M}$
whose domain contains the free variables of $\phi$. Then we say that $X$
satisfies $\phi$ in $\mathfrak{M}$, and we write
$\mathfrak{M}\models_{X}\phi$, if this follows from the following rules:

TS-lit:

If $\phi$ is a first order literal, $\mathfrak{M}\models_{X}\phi$ if and only
if, for all assignments $s\in X$, $\mathfrak{M}\models_{s}\phi$ in the usual
sense of Tarskian Semantics;

TS-$\vee$:

$\mathfrak{M}\models_{X}\phi_{1}\vee\phi_{2}$ if and only if $X=Y\cup Z$ for
two $Y,Z\subseteq X$ such that $\mathfrak{M}\models_{Y}\phi_{1}$ and
$\mathfrak{M}\models_{Z}\phi_{2}$;

TS-$\wedge$:

$\mathfrak{M}\models_{X}\phi_{1}\wedge\phi_{2}$ if and only if
$\mathfrak{M}\models_{X}\phi_{1}$ and $\mathfrak{M}\models_{X}\phi_{2}$;

TS-$\exists$:

$\mathfrak{M}\models_{X}\exists v\psi$ if and only if there exists some
function222$\mathcal{P}(M)$ represents the powerset $\\{A:A\subseteq M\\}$ of
$M$. $H:X\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ such that
$\mathfrak{M}\models_{X[H/v]}\psi$, where $X[H/v]=\\{s[m/v]:s\in X,m\in
H(s)\\}$;

TS-$\forall$:

$\mathfrak{M}\models_{X}\forall v\psi$ if and only if
$\mathfrak{M}\models_{X[M/v]}\psi$, where $X[M/v]=\\{s[m/v]:s\in X,m\in M\\}$.

A sentence $\phi$ is true in a model $\mathfrak{M}$ if and only if
$\mathfrak{M}\models_{\\{\epsilon\\}}\phi$, where $\\{\epsilon\\}$ is the team
containing only the empty assignment $\epsilon$. In that case, we write that
$\mathfrak{M}\models\phi$.

Over First Order Logic, Team Semantics reduces to Tarskian Semantics:

###### Proposition 1

([24], Corollary 3.32) Let $\mathfrak{M}$ be a first order model, let $\phi$
be a first order formula in Negation Normal Form over the signature of
$\mathfrak{M}$, and let $X$ be a team over $\mathfrak{M}$ whose domain
contains the free variables of $\phi$. Then $\mathfrak{M}\models_{X}\phi$ if
and only if, for all $s\in X$, $\mathfrak{M}\models_{s}\phi$ in the sense of
Tarskian Semantics.

In particular, if $\phi$ is a first order sentence, $\mathfrak{M}\models\phi$
in the sense of Team Semantics if and only if $\mathfrak{M}\models\phi$ in the
sense of Tarskian Semantics.

However, the framework of Team Semantics allows one to extend First Order
Logic in novel ways, for example via _functional dependence atoms_ [24],
_inclusion and exclusion atoms_ [4], _anonymity atoms_ [3, 22, 23]333Anonymity
atoms were called ”non-dependence atoms” and briefly studied in Section 4.6 of
[3], in which their equidefinability with inclusion atoms was also proved; but
their interpretation and their properties are discussed more in depth in [22,
23]. or _independence atoms_ [13]

TS-$=\\!\\!(\cdot;\cdot)$:

If $\vec{x}$ and $\vec{y}$ are tuples of variables in the domain of $X$,
$\mathfrak{M}\models_{X}=\\!\\!(\vec{x};\vec{y})$ if and only if, for all
$s,s^{\prime}\in X$, $s(\vec{x})=s^{\prime}(\vec{x})\Rightarrow
s(\vec{y})=s^{\prime}(\vec{y})$;

TS-$\subseteq$:

If $\vec{x}$ and $\vec{y}$ are tuple of variables in the domain of $X$ of the
same length, $\mathfrak{M}\models_{X}\vec{x}\subseteq\vec{y}$ if and only if
$X(\vec{x})\subseteq X(\vec{y})$;

TS-$|$:

If $\vec{x}$ and $\vec{y}$ are tuple of variables in the domain of $X$ of the
same length, $\mathfrak{M}\models_{X}\vec{x}\mid\vec{y}$ if and only if
$X(\vec{x})\cap X(\vec{y})=\emptyset$;

TS-:

If $\vec{x}$ and $\vec{y}$ are tuples of variables in the domain of $X$,
$\mathfrak{M}\models_{X}\vec{x}\mbox{\textUpsilon}\vec{y}$ if and only if for
every $s\in X$ there exists some $s^{\prime}\in X$ with
$s(\vec{x})=s^{\prime}(\vec{x})$ but $s(\vec{y})\not=s^{\prime}(\vec{y})$

TS-$\bot$:

If $\vec{x}$ and $\vec{y}$ are tuples of variables in the domain of $X$,
$\mathfrak{M}\models_{X}\vec{x}\bot\vec{y}$ if and only if
$X(\vec{x}\vec{y})=X(\vec{x})\times X(\vec{y})$, i.e., for all
$s,s^{\prime}\in X$ there is some $s^{\prime\prime}\in X$ with
$s^{\prime\prime}(\vec{x})=s(\vec{x})$ and
$s^{\prime\prime}(\vec{y})=s^{\prime}(\vec{y})$.

The logics obtained by adding these dependencies to First Order Logic
$\mathbf{FO}$ are all more expressive than it: in particular, (Functional)
Dependence Logic $\mathbf{FO}(=\\!\\!(\cdot;\cdot))$, Exclusion Logic
$\mathbf{FO}(|)$ and Independence Logic $\mathbf{FO}(\bot)$ are all equivalent
to444In the sense that every sentence of any of these logics is equivalent to
some Existential Second Order sentence, and vice versa. As we will see, it is
however not the case that every _formula_ of $\mathbf{FO}(\bot)$ is equivalent
to some formula of $\mathbf{FO}(|)$. Existential Second Order Logic [24, 4,
13, 12], while Inclusion Logic $\mathbf{FO}(\subseteq)$ and Anonimity Logic
$\mathbf{FO}(\mbox{\textUpsilon})$ are both equivalent to the positive
fragment of Greatest Fixpoint Logic [11, 3]. On the other hand, the
_nonemptiness atoms_

TS-NE:

$\mathfrak{M}\models_{X}\texttt{NE}(\vec{v})$ if and only if555The choice of
$\vec{v}$ in the atom $\texttt{NE}(\vec{v})$ is indifferent as long as it is
contained in the domain of $X$. Thus, one could define NE as a single $0$-ary
dependency instead of a family of dependencies of all arities, as we do here
for simplicity and uniformity. $X(\vec{v})\not=\emptyset$

do not increase the expressive power of First Order Logic if added to it, as
per Theorem 11 of [5],666Theorem 2.1 in this work. even though it follows
easily from Proposition 1 that such an atom is not definable by any first
order formula over Team Semantics.777Of course there is a first order sentence
$\exists\vec{x}R\vec{x}$ that says that $R$ is not empty; however, there is no
first order formula $\phi(\vec{w})$ such that
$\mathfrak{M}\models_{X}\phi(\vec{w})$ if and only if
$X(\vec{w})\not=\emptyset$.

Extensions of First Order Logic with Team Semantics via additional connectives
have also been studied. One such connective that will be of some importance in
this work is the _Global_ (or _Boolean_) _Disjunction_

TS-$\sqcup$:

$\mathfrak{M}\models_{X}\phi\sqcup\psi$ if and only if
$\mathfrak{M}\models_{X}\phi$ or $\mathfrak{M}\models_{X}\psi$.

There is by now a considerable amount of research, that cannot be summarized
here, concerning the classification of logics based on Team Semantics. One
useful tool for such research has been the following general definition of
dependency [21]:

######  Definition 3 (Dependency)

Let $k\in\mathbb{N}$. Then a $k$-ary dependency $\mathbf{D}$ is a class,
closed under isomorphisms, of models $\mathfrak{A}=(A,R)$, where $R$ is a
$k$-ary relation over $A$. Given a first order model $\mathfrak{M}$ with
domain $M$, a team $X$ over it and a tuple $\vec{x}$ of variables in the
domain of $X$ such that $|\vec{x}|=k$,

TS-D:

$\mathfrak{M}\models_{X}\mathbf{D}\vec{x}$ if and only if
$(M,X(\vec{x}))\in\mathbf{D}$.

Given any such dependency $\mathbf{D}$, we write $\mathbf{FO}(\mathbf{D})$ for
the logic obtained by adding $\mathbf{D}$ to First Order Logic with Team
Semantics; and likewise, if $\mathcal{D}$ is a family of such dependencies we
write $\mathbf{FO}(\mathcal{D})$ for the logic obtained by adding all
dependencies in $\mathcal{D}$ to First Order Logic with Team Semantics.

This definition is somewhat more general than the examples given so far in
that it allows an instance $\mathbf{D}\vec{x}$ of a dependency $\mathbf{D}$ to
be satisfied or not satisfied by a team $X$ over a model $\mathfrak{M}$
depending on the existence in $\mathfrak{M}$ of elements that do not occur in
$X(\vec{x})$. In other words, all dependencies mentioned so far (and nearly
all other dependencies considered in the literature) are _domain independent_
in the sense of the following definition from [19]:888In [19], this property
is called ”Universe Independence”.

######  Definition 4 (Domain Independence)

A $k$-ary dependency $\mathbf{D}$ is _domain independent_ if and only if, for
all models $\mathfrak{A}=(A,R)$,

$(A,R)\in\mathbf{D}\Leftrightarrow(\texttt{Fld}(R),R)\in\mathbf{D}$

where $\texttt{Fld}(R)=\bigcup_{i=1}^{k}\\{\vec{a}_{i}:\vec{a}\in R\\}$ is the
set of all elements that occur in an position of any tuple of $R$.

An example of a dependency that is not domain-independent is given by the
_Totality Atoms_ from [5]

TS-All:

$\mathfrak{M}\models_{X}\textbf{All}(\vec{x})$ if and only if
$X(\vec{x})=M^{|\vec{x}|}$

that state that a certain tuple of variables $\vec{x}$ takes _all_ possible
values in the current team. Domain independence is a very natural condition
that is satisfied by the majority of the dependencies studied in the
literature, and it can be argued that it should be included in the definition
of a ”proper” dependency.

All dependencies mentioned so far, including totality, are also _First Order_
in the sense that, if seen as properties of relations, they are first order
definable:

######  Definition 5 (First Order Dependency)

A $k$-ary dependency $\mathbf{D}$ is First Order if and only if there exists a
first order sentence $\mathbf{D}(R)$ such that

$(A,R)\in\mathbf{D}\Leftrightarrow(A,R)\models\mathbf{D}(R)$

for all models $\mathfrak{A}=(A,R)$, where $R$ is a $k$-ary relation.

Ultimately, the fact that adding first order dependencies to First Order Logic
may lead to logics more expressive than First Order Logic itself is a
consequence of the second-order nature of the Team Semantics rules TS-$\vee$
and TS-$\exists$ for disjunction and existential quantification.999The FOT
logic of [20], which is a Team Semantics-based logic with no higher order
quantifications in the rules for its connectives, is no stronger than First
Order Logic and can define all first order dependencies.

There are some general classes of dependencies that have also been useful in
the study of Team Semantics:

######  Definition 6 (Empty Team Property, Downwards, Union- and Upwards
Closures)

Let $\mathbf{D}$ be a $k$-ary dependency. Then $\mathbf{D}$

  * •

has the _Empty Team Property_ if $(A,\emptyset)\in\mathbf{D}$ for all domains
$A$;

  * •

is _Downwards Closed_ if whenever $(A,R)\in\mathbf{D}$ and $S\subseteq R$ we
also have that $(A,S)\in\mathbf{D}$;

  * •

is _Union Closed_ if whenever $(R_{i})_{i\in I}$ is a family of relations over
$A$ such that $(A,R_{i})\in\mathbf{D}$ for all $i\in I$ then
$\left(A,\bigcup_{i}R_{i}\right)\in\mathbf{D}$ as well;

  * •

is _Upwards Closed_ if whenever $(A,R)\in\mathbf{D}$ and $R\subseteq S$ then
$(A,S)\in\mathbf{D}$.

Note that union closure implies the empty team property, because for
$I=\emptyset$ we have that $\bigcup_{i\in I}R_{i}=\emptyset$.

Table 1 summarizes the properties of the dependencies mentioned so
far.101010NE and All are not union closed because the union of the empty
family of relations is the empty relation, which does not satisfy these
dependencies. If we restricted the definition of union closure to nonempty
families $I$, they would be union closed..

Table 1: Closure Properties of Dependencies Dependency | Empty Team |  Downwards |  Union |  Upwards |  Domain Ind.
---|---|---|---|---|---
$=\\!\\!(\cdot;\cdot)$ | $+$ | $+$ | $-$ | $-$ | $+$
$\subseteq$ | $+$ | $-$ | $+$ | $-$ | $+$
$|$ | $+$ | $+$ | $-$ | $-$ | $+$
| $+$ | $-$ | $+$ | $-$ | $+$
$\bot$ | $+$ | $-$ | $-$ | $-$ | $+$
NE | $-$ | $-$ | $-$ | $+$ | $+$
All | $-$ | $-$ | $-$ | $+$ | $-$

It can be seen, by structural induction on formulas, that if $\mathcal{D}$ is
a family of downwards closed dependencies then all formulas
$\phi\in\mathbf{FO}(\mathcal{D})$ are downwards closed, in the sense that if
$\mathfrak{M}\models_{X}\phi$ and $Y\subseteq X$ then
$\mathfrak{M}\models_{Y}\phi$. Likewise, if all dependencies in $\mathcal{D}$
are union closed and
$\mathfrak{M}\models_{X_{i}}\phi\in\mathbf{FO}(\mathcal{D})$ for all $i\in I$,
where $(X_{i})_{i\in I}$ is a family of teams over $\mathfrak{M}$ with the
same domain, then $\mathfrak{M}\models_{\bigcup_{i\in I}X_{i}}\phi$; and if
all dependencies in $\mathcal{D}$ have the empty team property then
$\mathfrak{M}\models_{\emptyset}\phi$ for all models $\mathfrak{M}$ and all
formulas $\phi\in\mathbf{FO}(\mathcal{D})$ over the signature of
$\mathfrak{M}$. This implies at once that, for example, independence atoms are
not definable in terms of exclusion atoms: even though every
$\mathbf{FO}(\bot)$ sentence is equivalent to some $\mathbf{FO}(|)$ sentence
and vice versa, there exists no $\mathbf{FO}(|)$ formula that is equivalent to
the independence atom $\vec{x}\bot\vec{y}$. This discrepancy between
definability and expressivity in Team Semantics – i.e., the fact that logics
based on Team Semantics may be equiexpressive despite the corresponding atoms
not being reciprocally definable – is one of the most intriguing phenomena of
Team Semantics.

The property of upwards closure, instead, is not preserved by Team Semantics
as first order literals are not upwards closed. However,

######  Theorem 2.1 ([5], Theorem 11)

Let $\mathcal{D}$ be a family of upwards closed, first order dependencies.
Then every sentence of $\mathbf{FO}(\mathcal{D})$ is equivalent to some first
order sentence.

In other words, the set $\mathcal{D}^{\uparrow}$ of all upwards closed first
order dependencies is _strongly first order_ in the sense of the following
definition:

######  Definition 7 (Strongly First Order Dependencies)

Let $\mathbf{D}$ be a dependency [let $\mathcal{D}$ be a family of
dependencies]. Then $\mathbf{D}$ [$\mathcal{D}$] is strongly first order if
and only if every sentence of $\mathbf{FO}(\mathbf{D})$
[$\mathbf{FO}(\mathcal{D})$] is equivalent to some first order sentence.

It is easy to see that all strongly first order dependencies are first order
in the sense of Definition 5, since by the rules of Team Semantics
$(M,R)\in\mathbf{D}$ if and only if $(M,R)\models\forall\vec{x}(\lnot
R\vec{x}\vee(R\vec{x}\wedge\mathbf{D}\vec{x}))$ and if $\mathbf{D}$ is
strongly first order this is equivalent to some first order sentence; but this
is certainly no sufficient condition, since as we saw there exist first order
dependencies that are not strongly first order.

On the other hand, being first order and upwards closed is a sufficient
condition for a dependency to be strongly first order, but it is not
necessary: for example, as shown already in Section 3.2 of [4], _constancy
atoms_

TS-$=\\!\\!(\cdot)$:

$\mathfrak{M}\models_{X}=\\!\\!(\vec{x})$ if and only if for all
$s,s^{\prime}\in X$, $s(\vec{x})=s^{\prime}(\vec{x})$,

that can be seen as degenerate cases of functional dependencies stating that
$\vec{x}$ depends on _nothing_ (i.e. its value is determined by the empty
tuple of variables), are strongly first order despite not being upwards
closed.111111We could consider only _unary_ constancy atoms, as
$=\\!\\!(\vec{x})\equiv\bigwedge_{x\in\vec{x}}=\\!\\!(x)$; but, similarly to
the NE case, for simplicity and uniformity we define constancy atoms for all
arities. We can say more:

###### Proposition 2

Every sentence of $\mathbf{FO}(=\\!\\!(\cdot),\mathcal{D}^{\uparrow},\sqcup)$
– i.e. of First Order Logic augmented with constancy atoms, upwards closed
first order dependencies, and global disjunctions – is equivalent to some
first order sentence.

###### Proof

By Theorem 21 of [5], $\mathcal{D}^{\uparrow}\cup=\\!\\!(\cdot)$ is strongly
first order. By Proposition 14 of [8], if $\mathcal{D}$ is a strongly first
order family of dependencies, every sentence of
$\mathbf{FO}(\mathcal{D},\sqcup)$ is equivalent to some first order sentence.
The result follows at once.

These observations led to the following

Problem: Provide necessary and sufficient conditions for a dependency or a
family of dependencies to be strongly first order.

and to the related

Conjecture: A family of dependencies $\mathcal{D}$ is strongly first order if
and only if all $\mathbf{D}\in\mathcal{D}$ are strongly first order.

A partial answer was found in [7]:

######  Theorem 2.2 ([7], Theorem 4.5)

Let $\mathbf{D}$ be a downwards closed, domain independent121212The result of
[7] actually requires a weaker condition than domain independence called
_relativizability_. This property is implied by domain independence, and in
this work we will focus on domain independent dependencies. Totality All is an
example of a dependency that is relativizable but not domain independent.
dependency with the empty team property. Then $\mathbf{D}$ is strongly first
order if and only if it is definable in Constancy Logic
$\mathbf{FO}(=\\!\\!(\cdot))$

In [8], a characterization was found for the strongly first order dependencies
that are domain independent131313Again, relativizability suffices for this
result. and have the (somewhat technical) property of being _non-jumping_ ,
which in particular is true of strongly first order downwards closed
dependencies (even of those without the empty team property):

######  Theorem 2.3 ([8], Corollary 31)

Let $\mathbf{D}$ be a non-jumping (or, in particular, downwards closed),
domain independent141414Or relativizable., strongly first order dependency.
Then $\mathbf{D}$ is definable in
$\mathbf{FO}(=\\!\\!(\cdot),\mathcal{D}^{\uparrow},\sqcup)$.

Finally, in [10], a characterization was found for dependencies that are
domain-independent151515Again, or just relativizable. and _doubly_ strongly
first order, in the sense that they and their negation can be added to First
Order Logic (separately or jointly) without increasing its expressive power.

In the next section we will find a necessary and sufficient condition for
_union-closed_ , domain-independent dependencies to be relativizable, thus
completing the characterization of “strong first-orderness” with respect to
dependencies satisfying the main closure properties discussed in the
literature, modulo the condition of domain independence (which, as mentioned,
is a natural condition that could be argued to apply to any sensible
dependency notion).161616Nonetheless, there are dependencies of interest, such
as independence atoms $\bot$, which satisfy none of these closure properties;
and thus, the problem of fully characterizing strongly first order
dependencies remains not entirely solved yet.

##  3 Characterizing Union-Closed Dependencies

A key insight for our characterization is the observation that if $\mathbf{D}$
is domain-independent and strongly first order then there cannot exist a chain
of models satisfying and not satisfying $\mathbf{D}$ as per Figure 1:

$A_{1}$$A_{2}$$A_{3}$$R_{1}$$R_{2}$$R_{3}$$S_{1}$$S_{2}$ Figure 1:  A
forbidden elementary chain. As per Lemma 1, if $\mathbf{D}$ is domain
independent and strongly first order, it cannot be the case that, for all
$i\in\mathbb{N}$, $(A_{i},R_{i})\preceq(A_{i+1},R_{i+1})$,
$(A_{i},R_{i})\in\mathbf{D}$, and $(A_{i+1},S_{i})\not\in\mathbf{D}$ for
$R_{i}\subseteq S_{i}\subseteq R_{i+1}$.

###### Lemma 1

Let $\mathbf{D}$ be a $k$-ary domain-independent dependency and suppose that
there exists an elementary chain $(\mathfrak{A}_{i})_{i}\in\mathbb{N}$, where
each $\mathfrak{A}_{i}$ is of the form $(A_{i},R_{i})$ for some domain $A_{i}$
and some $k$-ary relation $R_{i}$ over $A_{i}$, such that

  * •

$\mathfrak{A}_{i}=(A_{i},R_{i})\in\mathbf{D}$ for all $i\in\mathbb{N}$;

  * •

$\mathfrak{A}_{i}$ is an elementary substructure of $\mathfrak{A}_{i+1}$
($\mathfrak{A}_{i}\preceq\mathfrak{A}_{i+1}$) for all $i\in\mathbb{N}$;

  * •

For all $i\in\mathbb{N}$ there exists some $k$-ary relation $S_{i}$ over
$A_{i+1}$ such that $R_{i}\subseteq S_{i}\subseteq R_{i+1}$ and
$(A_{i+1},S_{i})\not\in\mathbf{D}$.

Then $\mathbf{D}$ is not strongly first order.

###### Proof

By the Löwenheim-Skolem Theorem, we can assume that all $(A_{i},R_{i})$ are
countable. Then let
$\mathfrak{A}=(A,R)=\left(\bigcup_{i}A_{i},\bigcup_{i}R_{i}\right)$ be the
union of the elementary chain. By the Elementary Chain Theorem we have that
$\mathfrak{A}\succeq\mathfrak{A}_{i}$ for all $i\in\mathbb{N}$, and therefore
in particular $(A,R)\models\mathbf{D}(R)$; and furthermore since $A$ is the
countable union of countable sets it is countable and we can identify it up to
isomorphism with the set of natural numbers $\mathbb{N}$.

Then let $\mathfrak{B}$ be a model, with the same domain $\mathbb{N}$, whose
signature $\Sigma$ contains the binary predicate $<$, the unary function
$\mathfrak{s}$, and the $(k+1)$-ary predicate $\hat{S}$, such that $<$ is
interpreted as the usual ordering over $\mathbb{N}$, $\mathfrak{s}$ is
interpreted as the corresponding successor function $n\mapsto n+1$, and
$\hat{S}$ is interpreted as the relation $\\{(i,\vec{m}):\vec{m}\in S_{i}\\}$.

I state that if $\mathbf{D}$ is strongly first order and domain independent
then $\mathfrak{B}$ has no uncountable elementary extensions. This is
impossible by the Löwenheim-Skolem Theorem; therefore, if I can prove this I
can conclude that $\mathbf{D}$ cannot be strongly first order.

If the dependency $\mathbf{D}$ is strongly first order and domain-independent,
the complete first order theory of $\mathfrak{B}$ contains the sentence
$\forall v\lnot\phi(v)$, where $\phi(d)$ is the first order sentence over the
signature $\Sigma\cup\\{d\\}$ that is equivalent to the
$\mathbf{FO}(\mathbf{D})$ sentence

$\exists
t(t<d\wedge\forall\vec{w}(\lnot\hat{S}t\vec{w}\vee(\hat{S}t\vec{w}\wedge\mathbf{D}(\vec{w}))))$

that, as we will later verify, states that there exists some nonempty set of
indices $I\subseteq\\{1\ldots d\\}$ such that $\left(\mathbb{N},\bigcup_{i\in
I}S_{i}\right)\in\mathbf{D}$. Indeed, for any such set we have that
$\bigcup_{i\in I}S_{i}=S_{q}$ for $q=\max(I)$, and by domain independence
$(\mathbb{N},S_{q})\not\in\mathbf{D}$ since
$(A_{q+1},S_{q})\not\in\mathbf{D}$.

Now let $\mathfrak{B}^{\prime}$ be an uncountable elementary extension of
$\mathfrak{B}$ with domain $B^{\prime}\supsetneq\mathbb{N}$, let $d\in
B^{\prime}\backslash\mathbb{N}$ be a non-standard element of it, and choose
$I=\mathbb{N}$. Then $i<d$ for all $i\in\mathbb{N}$, and furthermore since
$\bigcup_{i\in\mathbb{N}}S_{i}=\bigcup_{i\in\mathbb{N}}R_{i}$ and since as we
already observed $(\bigcup_{i}A_{i},\bigcup_{i}R_{i})\in\mathbf{D}$ we have
that $(\bigcup_{i}A_{i},\bigcup_{i}S_{i})\in\mathbf{D}$. But then, as
$\mathbf{D}$ is domain independent,
$(B^{\prime},\bigcup_{i}S_{i})\in\mathbf{D}$. Therefore
$\mathfrak{B}^{\prime}\models\phi(d)$, which contradicts the claim that
$\mathfrak{B}^{\prime}$ is an elementary extension of $\mathfrak{B}$.

It remains to check that the formula $\phi(d)$ indeed specifies the required
property. Suppose that $\mathfrak{M}\models\phi(d)$. Then, by the rules of
Team Semantics, there exists some function
$H:\\{\epsilon\\}\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ such that
$\mathfrak{M}\models_{\\{\epsilon\\}[H/t]}t<d\wedge\forall\vec{w}(\lnot\hat{S}t\vec{w}\vee(\hat{S}t\vec{w}\wedge\mathbf{D}(\vec{w})))$.
Now let $X=\\{\epsilon\\}[H/t]$ and let $I=X(t)$.

Then $I\not=\emptyset$; and since $\mathfrak{M}\models_{X}t<d$, $i<d$ for all
$i\in I$, as required.

For $Y=X[M/\vec{w}]$,171717This is a shorthand for
$X[M/\vec{w}_{1}][M/\vec{w}_{2}]\ldots[M/\vec{w}_{k}]$. we furthermore have
that
$\mathfrak{M}\models_{Y}\lnot\hat{S}t\vec{w}\vee(\hat{S}t\vec{w}\wedge\mathbf{D}(\vec{w}))$.
Therefore, $Y=Y_{1}\cup Y_{2}$, where

  * •

For all $s\in Y_{1}$, $s(\vec{w})\not\in S_{s(t)}$;

  * •

For all $s\in Y_{2}$, $s(\vec{w})\in S_{s(t)}$;

  * •

$(M,Y_{2}(\vec{w}))\in\mathbf{D}$.

Then necessarily $Y_{1}=\\{s\in Y:s(\vec{w})\not\in S_{s(t)}\\}$ and
$Y_{2}=\\{s\in Y:s(\vec{w})\in S_{s(t)}\\}$; but by construction, in $Y$ the
tuple $\vec{w}$ takes all possible values in $M^{k}$ for all possible values
$i\in I$ of $t$, and therefore $Y_{2}(\vec{w})=\\{\vec{m}:\exists i\in I\text{
s.t. }\vec{m}\in S_{i}\\}=\bigcup_{i\in I}S_{i}$. Therefore $(M,\bigcup_{i\in
I}S_{i})\in\mathbf{D}$ as required.

Conversely, suppose that there exists a nonempty set $I$ of elements less than
$d$ such that $(M,\bigcup_{i\in I}S_{i})\in\mathbf{D}$. Then let
$H:\\{\epsilon\\}\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ be such
that $H(\epsilon)=I$, and let $X=\\{\epsilon\\}[H/t]$ so that $X(t)=I$.

Clearly $\mathfrak{M}\models_{X}t<d$, and I only need to prove that – for
$Y=X[M/\vec{w}]$ –
$\mathfrak{M}\models_{Y}\lnot\hat{S}t\vec{w}\vee(\hat{S}t\vec{w}\wedge\mathbf{D}(\vec{w}))$.
Now let $Y_{1}=\\{s\in Y:s(\vec{w})\not\in S_{s(t)}\\}$ and $Y_{2}=\\{s\in
Y:s(\vec{w})\in S_{s(t)}\\}$: then $Y=Y_{1}\cup Y_{2}$,
$\mathfrak{M}\models_{Y_{1}}\lnot\hat{S}t\vec{w}$ and
$\mathfrak{M}\models_{Y_{2}}\hat{S}t\vec{w}$. Moreover,
$Y_{2}(\vec{w})=\\{s(\vec{w})\in X[M/\vec{w}]:s(\vec{w})\in
S_{s(t)}\\}=\bigcup_{i\in X(t)}S_{i}=\bigcup_{i\in I}S_{i}$, and therefore
$(M,Y_{2}(\vec{w}))\in\mathbf{D}$ and
$\mathfrak{M}\models_{Y_{2}}\mathbf{D}\vec{w}$ as required.

In fact, if $\mathbf{D}$ is strongly first order and domain independent even
one single ”step” (as depicted in Figure 2) of the chain of Figure 1 cannot
occur:

$A_{1}$$A_{2}$$R_{1}$$R_{2}$$S_{1}$ Figure 2:  A forbidden elementary ”step”.
As per Proposition 3, if $\mathbf{D}$ is domain independent and strongly first
order, it cannot be the case that $(A_{1},R_{1})\preceq(A_{2},R_{2})$,
$(A_{1},R_{1})\in\mathbf{D}$, $(A_{2},R_{2})\in\mathbf{D}$, and
$(A_{2},S_{1})\not\in\mathbf{D}$ for some $S_{1}$ such that $R_{1}\subseteq
S_{1}\subseteq R_{2}$.

###### Proposition 3

Let $\mathbf{D}$ be a domain independent, strongly first order dependency and
suppose that $(A_{1},R_{1})\in\mathbf{D}$ and that
$(A_{1},R_{1})\preceq(A_{2},R_{2})$. Then for all relations $S_{1}$ with
$R_{1}\subseteq S_{1}\subseteq R_{2}$, $(A_{2},S_{1})\in\mathbf{D}$ as well.

###### Proof

Suppose that this is not the case, i.e. that – as per Figure 2 –
$(A_{1},R_{1})\preceq(A_{2},R_{2})$, $R_{1}\subseteq S_{1}\subseteq R_{2}$ and
$(A_{2},S_{1})\not\in\mathbf{D}$.

Then we can build a chain as per Figure 1 as follows: start by with the given
$A_{1}$, $R_{1}$, $A_{2}$, $R_{2}$, and $S_{1}$. Then consider the theory

$\displaystyle T:=\\{\phi(R_{3},\vec{a}):\vec{a}\subseteq
A_{2},(A_{2},R_{2})\models\phi(R_{2},\vec{a}),\phi\in\mathbf{FO}\\}\cup\\{S_{2}\vec{b}:\vec{b}\in
R_{2}\\}\cup$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\\{\forall\vec{x}(S_{2}\vec{x}\rightarrow
R_{3}\vec{x}),\lnot\mathbf{D}(S_{2})\\}.$

By compactness, this theory is satisfiable. Indeed, any finite subset $T_{0}$
of $T$ is entailed by some first order sentence of the form
$\phi(R_{3},\vec{a})\wedge\bigwedge_{i=1}^{n}S_{2}\vec{b}_{i}\wedge\forall\vec{x}(S_{2}\vec{x}\rightarrow
R_{3}\vec{x})\wedge\lnot\mathbf{D}(S_{2})$, where
$(A_{2},R_{2})\models\phi(R_{2},\vec{a})\wedge\bigwedge_{i=1}^{n}R_{2}\vec{b}_{i}$.

But then
$(A_{2},R_{2})\models\exists\vec{z}\vec{w}_{1}\ldots\vec{w}_{n}(\phi(R_{2},\vec{z})\wedge\bigwedge_{i=1}^{n}R_{2}\vec{w}_{i}\wedge\tau(\vec{z}\vec{w}_{1}\ldots\vec{w}_{n}))$,
where $\tau(\vec{z}\vec{w}_{1}\ldots\vec{w}_{n})$ describes the identity type
of $\vec{a}\vec{b}_{1}\ldots\vec{b}_{n}$, and so since
$(A_{1},R_{1})\preceq(A_{2},R_{2})$ there exists a tuple $\vec{c}$ in $A_{1}$
and tuples $\vec{d}_{1}\ldots\vec{d}_{n}$ in $R_{1}$ such that
$\vec{c}\vec{d}_{1}\ldots\vec{d}_{n}$ has the same identity type as
$\vec{a}\vec{b}_{1}\ldots\vec{b}_{n}$ and
$(A_{1},R_{1})\models\phi(R_{1},\vec{c})$. But then
$(A_{2},R_{2})\models\phi(R_{2},\vec{c})$ as well, and moreover
$\vec{d}_{1}\ldots\vec{d}_{n}\in R_{1}\subseteq S_{1}\subseteq R_{2}$, and so
$T_{0}$ can be satisfied by choosing a model with domain $A_{2}$ in which
$\vec{a}\vec{b}_{1}\ldots\vec{b}_{n}$ are interpreted as
$\vec{c}\vec{d}_{1}\ldots\vec{d}_{n}$, $S_{2}$ is interpreted as $S_{1}$, and
$R_{3}$ is interpreted as $R_{2}$.

Now, any model of $T$ is an elementary extension $(A_{3},R_{3})$ of
$(A_{2},R_{2})$ with some $S_{2}$ with $R_{2}\subseteq S_{2}\subseteq R_{3}$
and $(A_{3},S_{2})\not\in\mathbf{D}$.181818Instead
$(A_{3},R_{3})\in\mathbf{D}$, because
$(A_{3},R_{3})\succeq(A_{2},R_{2})\in\mathbf{D}$ and $\mathbf{D}$ is first
order. Iterating this procedure, we can find an infinite chain as per Figure
1; but by Lemma 1 this is impossible.

Now we can find a ”local characterization” of strongly first order, domain
independent, union closed dependencies:

######  Definition 8 (U-Sentences)

Let $R$ be a $k$-ary relation symbol and let $\vec{a}$ be a tuple of constant
symbols. Then a first order sentence over the signature $\\{R,\vec{a}\\}$ is a
U-sentence if and only if it is of the form

$\exists\vec{x}(\eta(\vec{x})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{x},\vec{y})))$

where $\vec{x}$ and $\vec{y}$ are disjoint tuples of variables, $\eta(x)$ is a
conjunction of first order literals over the signature $\\{R,\vec{a}\\}$ in
which $R$ occurs only positively, and $\theta(\vec{x},\vec{y})$ is a first
order formula over the signature $\\{\vec{a}\\}$ (i.e. in which $R$ does not
appear).

Given two models $\mathfrak{A}$ and $\mathfrak{B}$ with the same signature, we
will write $\mathfrak{A}\Rrightarrow_{U}\mathfrak{B}$ if, for every
$U$-sentence $\phi$,
$\mathfrak{A}\models\phi\Rightarrow\mathfrak{B}\models\phi$.

###### Proposition 4

The conjunction of two U-sentences is equivalent to some U-sentence; and if
$a$ is a constant symbol occurring on some $U$-sentence $\chi$ and $v$ is a
new variable not occurring in $\chi$, $\exists v\chi[v/a]$ is also a
U-sentence.191919Here $\chi[v/a_{\lambda}]$ represents the formula obtained
from $\chi$ by replacing the constant $a_{\lambda}$ with the variable $v$.

###### Proof

Let
$\chi=\exists\vec{x}(\eta(\vec{x})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{x},\vec{y})))$
and
$\chi^{\prime}=\exists\vec{z}(\eta^{\prime}(\vec{z})\wedge\forall\vec{w}(R\vec{w}\rightarrow\theta^{\prime}(\vec{z},\vec{w})))$
be two U-sentences over the same signature $\\{R,\vec{a}\\}$. Renaming
variables as necessary, we can assume that $\vec{x}$ is disjoint from
$\vec{z}$ and that $\vec{y}=\vec{w}$.

Then $\chi\wedge\chi^{\prime}$ is equivalent to
$\exists\vec{x}\vec{z}((\eta(\vec{x})\wedge\eta^{\prime}(\vec{z}))\wedge\forall\vec{y}(R\vec{y}\rightarrow(\theta(\vec{x},\vec{y})\wedge\theta^{\prime}(\vec{z},\vec{y}))))$,
which is also a $U$-sentence.

Moreover, if $a$ be any constant symbol occurring in $\chi$ and $v$ is a
variable that does not occur in $\chi$, $\exists v(\chi[v/a])$ is the
U-sentence

$\exists
v\exists\vec{x}(\eta(\vec{x})[v/a]\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{x},\vec{y})[v/a]))$

###### Proposition 5

Let $\mathbf{D}$ be domain independent, strongly first order and union closed,
and suppose that $(A,R)\in\mathbf{D}$.

Then there exists some U-sentence $\chi(R)$ over the signature $\\{R\\}$ such
that

  1. 1.

$(A,R)\models\chi(R)$;

  2. 2.

$\chi(R)\models\mathbf{D}(R)$.

###### Proof

Suppose that this is not the case. Then $R$ (and, therefore, $A$) must be
infinite, because otherwise there would exist a $U$-sentence
$\exists\vec{x}(\bigwedge_{i=1}^{n}R\vec{t}_{i}\wedge\forall\vec{y}(R\vec{y}\rightarrow\bigvee_{i}\vec{y}=\vec{t}_{i}))$
that fixes $R$ and thus - by domain independence - entails $\mathbf{D}$.

Note that the theory $\\{\chi(S):\chi\text{
U-sentence},(A,R)\models\chi(R)\\}\cup\\{\lnot\mathbf{D}(S)\\}$ is finitely
satisfiable, since otherwise some finite conjunction of U-sentences that are
true of $(A,R)$ would entail $\mathbf{D}(R)$ and by Proposition 19 any such
finite conjunction is equivalent to some U-sentence. Therefore, by
compactness, there exists a model $(B,S)\not\in\mathbf{D}$ such that
$(A,R)\Rrightarrow_{U}(B,S)$. We can furthermore assume that $(B,S)$ is
$|A|$-saturated.

Now let $(a_{\alpha})_{\alpha<|A|}$ enumerate all elements of $A$ and let us
build a mapping $\mathfrak{h}:A\rightarrow B$ such that
$(A,R,(a_{\alpha})_{\alpha<|A|})\Rrightarrow_{U}(B,S,(\mathfrak{h}(a_{\alpha}))_{\alpha<|A|})$.

We can do so via transfinite induction on $\lambda<|A|$, by defining functions
$\mathfrak{h}_{\lambda}$ each of which maps
$a_{<\lambda}=(a_{\alpha})_{\alpha<\lambda}$ into some
$b_{<\lambda}=(b_{\alpha})_{\alpha<\lambda}$ such that

  * •

$(A,R,a_{<\lambda})\Rrightarrow_{U}(B,S,b_{<\lambda})$;

  * •

If $\lambda<\lambda^{\prime}$ then
$\mathfrak{h}_{\lambda}\subseteq\mathfrak{h}_{\lambda^{\prime}}$.

Then by taking $\mathfrak{h}=\bigcup_{\lambda<|A|}\mathfrak{h}_{\lambda}$ we
will obtain the required mapping.

  1. 1.

For $\lambda=0$, we already know that $(A,R)\Rrightarrow_{U}(B,S)$.

  2. 2.

Suppose that $\lambda+1$ is a successor ordinal and that, for all
$\gamma<\lambda+1$, mappings $\mathfrak{h}_{\gamma}$ exist with the required
properties. Then in particular $\mathfrak{h}_{\lambda}$ exists and maps
$\vec{a}_{<\lambda}$ into some $\vec{b}_{<\lambda}$ such that
$(A,R,\vec{a}_{<\lambda})\Rrightarrow_{U}(B,S,\vec{b}_{<\lambda})$. Now
consider the element $a_{\lambda}$ and the theory

$\Theta(R,\vec{a}_{<\lambda},a_{\lambda})=\\{\chi:\chi\text{ is a
U-sentence},(A,R,\vec{a}_{<\lambda},a_{\lambda})\models\chi\\}$

Now, if $\Theta_{0}$ is any finite subset of $\Theta$, by Proposition 19 the
expression $\xi_{0}:=\exists
v\bigwedge_{\chi\in\Theta_{0}}\chi[v/a_{\lambda}]$ is equivalent to some
$U$-sentence over $\\{R,\vec{a}_{<\lambda}\\}$ and
$(A,R,\vec{a}_{<\lambda})\models\xi_{0}$; and therefore, by induction
hypothesis, $(B,S,\vec{b}_{<\lambda})\models\xi_{0}$ and there exists some
$b^{\prime}\in B$ such that $(B,S,\vec{b}_{<\lambda},b^{\prime})\models\chi$
for all $\chi\in\Theta_{0}$. Since $(B,S)$ is $|A|$-saturated and
$\lambda<|A|$, this means that there exists some $b_{\lambda}\in B$ such that
$(B,S,\vec{b}_{<\lambda},b_{\lambda})\models\Theta$. But then
$(A,R,\vec{a}_{<\lambda+1})\Rrightarrow_{U}(B,S,\vec{b}_{<\lambda+1})$, and we
can define
$\mathfrak{h}_{\lambda+1}=\mathfrak{h}\cup\\{(a_{\lambda},b_{\lambda})\\}$.

  3. 3.

Suppose that $\lambda$ is a limit ordinal and that, for all $\gamma<\lambda$,
mappings $\mathfrak{h}_{\gamma}$ exist with the required properties. Then take
$\mathfrak{h}_{\lambda}=\bigcup_{\gamma<\lambda}\mathfrak{h}_{\beta}$.

The mapping $\mathfrak{h}$ thus built is in particular an embedding of $(A,R)$
into $(B,S)$. Indeed, it is injective, because expressions of the form
$a_{i}\not=a_{j}$ are $U$-sentences; and furthermore, for all $k$-tuples
$\vec{c}$ of elements in $A$, $\vec{c}\in
R\Leftrightarrow(\mathfrak{h}(c_{i}))_{i=1\ldots k}\in S$ since the sentences
$R\vec{c}$ and $\forall\vec{y}(R\vec{y}\rightarrow\vec{y}\not=\vec{c})$ (which
is equivalent to $\lnot R\vec{c}$) are also $U$-sentences.

Now, let $(A_{1},R_{1})$ be the image of $(A,R)$ over $\mathfrak{h}$. Then
$(A_{1},R_{1})$ is isomorphic to $(A,R)$, and so in particular
$(A_{1},R_{1})\in\mathbf{D}$, and furthermore $R_{1}=S\cap(A_{1})^{k}\subseteq
S$. Note additionally that, for every $U$-sentence $\phi$ with constants
$\vec{a}$ in $A_{1}$,
$(A_{1},R_{1},\vec{a})\models\phi\Leftrightarrow(A,R,\mathfrak{h}^{-1}(\vec{a}))\models\phi\Rightarrow(B,S,\vec{a})\models\phi$
and so every $U$-sentence with parameters in $A_{1}$ that holds of
$(A_{1},R_{1})$ also holds in $(B,S)$.

Now consider any tuple $\vec{b}\in S\backslash R_{1}$. I state that there
exists some $(A_{2},R_{2})\succeq(A_{1},R_{1})$ such that $\vec{b}\in R_{2}$,
as per Figure 3. Indeed, consider the elementary diagram
$\\{\phi(R_{2},\vec{a}):\vec{a}\subseteq
A_{1},\phi\in\mathbf{FO},(A_{1},R_{1},\vec{a})\models\phi(R_{1},\vec{a})\\}$
of $(A_{1},R_{1})$ together with the sentence $R_{2}\vec{b}$. If this theory
was not satisfiable, by compactness there would exist some tuple $\vec{a}$ of
elements of $A_{1}$ and some sentence $\phi(R_{1},\vec{a})$ such that
$(A_{1},R_{1},\vec{a})\models\phi(R_{1},\vec{a})$ and
$\phi(R,\vec{a})\models\lnot R\vec{b}$. But then, if $\vec{t}$ is the tuple of
terms obtained from $\vec{b}$ by replacing every constant symbol not in
$\vec{a}$ with some new variable, we have that
$\phi(R,\vec{a})\models\forall\vec{z}(\lnot R\vec{t})$, where $\vec{z}$ lists
all newly introduced variables,202020This follows from the so-called ”Lemma on
Constants” (e.g. Lemma 2.3.2. of [17]): if $T\models\phi(\vec{c})$, where
$\vec{c}$ is a tuple of constants not occurring in $T$, then
$T\models\forall\vec{x}\phi(\vec{x})$. and so
$(A_{1},R_{1},\vec{a})\models\forall\vec{z}(\lnot R_{1}\vec{t})$ and therefore
$(A_{1},R_{1},\vec{a})\models\forall\vec{y}(R_{1}\vec{y}\rightarrow\forall\vec{z}(\vec{y}\not=\vec{t}))$.
But since all $U$-sentences with parameters in $A_{1}$ that are true of
$(A_{1},R_{1})$ are also true of $(B,S)$ we would then have in particular that
$(B,S,\vec{a})\models\forall\vec{y}(S\vec{y}\rightarrow\forall\vec{z}(\vec{x}\not=\vec{t}))$,
which is impossible because $\vec{b}\in S$. Therefore the theory is
satisfiable, and any model $(A_{2},R_{2})$ of it is an elementary extension of
$(A_{1},R_{1})$ that contains $\vec{b}$, as required.

$A_{1}$$A_{2}$$R_{1}$$R_{2}$$\vec{b}$$B$$S$ Figure 3:  $(A_{1},R_{1})$ is
embedded in $(B,S)$, and $(A_{1},R_{1})\in\mathbf{D}$ while
$(B,S)\not\in\mathbf{D}$, and $\vec{b}\in S\backslash R_{1}$. Then we can
build some $(A_{2},R_{2})\succeq(A_{1},R_{1})$ such that $\vec{b}\in R_{2}$;
and then, via Proposition 3, we can show that
$(A_{2},R_{1}\cup\\{\vec{b}\\})\in\mathbf{D}$. But then by domain independence
$(B,R_{1}\cup\\{\vec{b}\\})\in\mathbf{D}$ for any such $\vec{b}$.

So we have that $(A_{1},R_{1})\preceq(A_{2},R_{2})$ and that $\vec{b}\in
R_{2}\backslash R_{1}$. Then $(A_{2},R_{2})\in\mathbf{D}$, because
$(A_{1},R_{1})\in\mathbf{D}$ and $(A_{2},R_{2})$ is elementarily equivalent to
it. Therefore, $(A_{2},R_{1}\cup\\{\vec{b}\\})\in\mathbf{D}$: indeed,
otherwise we would have that $(A_{1},R_{1})\in\mathbf{D}$,
$(A_{2},R_{1}\cup\\{\vec{b}\\})\not\in\mathbf{D}$,
$R_{1}\cup\\{\vec{b}\\}\subseteq R_{2}$ and
$(A_{2},R_{2})\succeq(A_{1},R_{1})$, which (taking
$S_{1}=R_{1}\cup\\{\vec{b}\\}$) is the configuration of Figure 2 that cannot
occur by Proposition 3. Then, by domain independence,
$(B,R_{1}\cup\\{\vec{b}\\})\in\mathbf{D}$ as well.

But if this is the case for all $\vec{b}\in S\backslash R_{1}$ and
$\mathbf{D}$ is union closed,
$(B,\bigcup_{\vec{b}\in S\backslash
R_{1}}R_{1}\cup\\{\vec{b}\\})=(B,S)\in\mathbf{D}$ which contradicts our
assumption that $(B,S)\not\in\mathbf{D}$.

We can now find a global characterization of domain independent, union-closed,
strongly first order dependencies via a simple application of compactness:

###### Theorem 3.1

Let $\mathbf{D}$ be a domain independent, union-closed, strongly first order
dependency. Then $\mathbf{D}(R)$ is equivalent to some finite disjunction of
U-sentences over the signature $\\{R\\}$.

###### Proof

For each countable $(A,R)\in\mathbf{D}$, let $\chi_{A,R}(R)$ be a U-sentence
over the signature $\\{R\\}$ such that $(A,R)\models\chi_{A,R}(R)$ and
$\chi_{A,R}(R)\models\mathbf{D}(R)$.

Then the theory $\\{\lnot\chi_{A,R}(R):(A,R)\in\mathbf{D},A\text{
countable}\\}\cup\\{\mathbf{D}(R)\\}$ has no countable models, and therefore
it has no models at all; and so, by compactness, there exists a finite number
of U-sentences $\chi_{1}\ldots\chi_{n}$ such that
$\mathbf{D}(R)\models\bigvee_{i=1}^{n}\chi_{i}(R)$. But every $\chi_{i}(R)$
entails $\mathbf{D}(R)$, and so $\mathbf{D}(R)$ is equivalent to
$\bigvee_{i=1}^{n}\chi_{i}(R)$.

###### Corollary 1

Let $\mathbf{D}$ be a domain independent, union-closed dependency. Then
$\mathbf{D}$ is strongly first order if and only if it is definable in terms
of constancy atoms, nonemptiness atoms and global disjunctions.

###### Proof

Suppose that $\mathbf{D}$ is strongly first order. Then by Theorem 3.1,
$\mathbf{D}(R)$ is equivalent to some $\bigvee_{i=1}^{n}\chi_{i}(R)$ where
each $\chi_{i}(R)$ is a $U$-sentence over the signature $\\{R\\}$. Now let
$\vec{w}$ be a $k$-tuple of distinct variables not occurring in any
$\chi_{i}$; and for each
$\chi_{i}=\exists\vec{x}(\eta(\vec{x})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{x},\vec{y})))$,
let

$\chi^{\prime}_{i}(\vec{w}):=\exists\vec{x}(=\\!\\!(\vec{x})\wedge\eta^{\prime}(\vec{x},\vec{w})\wedge\theta(\vec{x},\vec{w}))$

where $\eta^{\prime}(\vec{x},\vec{w})$ is obtained from $\eta(\vec{x})$ by
replacing each conjunct of the form $R\vec{t}$ with
$(\top\vee(\texttt{NE}(\vec{w})\wedge\vec{t}=\vec{w}))$.212121Here $\top$ can
be any literal that is always true, such as $w=w$ for some $w\in\vec{w}$.

I state that, for all models $\mathfrak{M}$ and teams $X$ over it with domain
containing $\vec{w}$, $\mathfrak{M}\models_{X}\mathbf{D}\vec{w}$ if and only
if $\mathfrak{M}\models_{X}\bigsqcup_{i=1}^{n}\chi^{\prime}_{i}(\vec{w})$. If
I can prove this then I am done: indeed, by Proposition 2 and by the fact that
$\texttt{NE}\subseteq\mathcal{D}^{\uparrow}$ every dependency that is
definable in $\mathbf{FO}(=\\!\\!(\cdot),\texttt{NE},\sqcup)$ is strongly
first order.

It suffices to prove that, for all models $\mathfrak{M}$,222222Note that the
signature of $\mathfrak{M}$ does not necessarily have to include the symbol
$R$, which is instead interpreted as $X(\vec{w})$ when evaluating
$\chi_{i}(R)$; and accordingly, $\chi^{\prime}_{i}(\vec{w})$ is a
$\mathbf{FO}(=\\!\\!(\cdot),\texttt{NE})$ formula over the _empty_ signature.
and all teams $X$ over $\mathfrak{M}$ whose domain contains $\vec{w}$,
$\mathfrak{M}\models_{X}\chi^{\prime}_{i}(\vec{w})$ if and only if
$(M,X(\vec{w}))\models\chi_{i}(R)$.

Suppose that $\mathfrak{M}\models_{X}\chi^{\prime}_{i}(\vec{w})$: then there
exists a tuple $\vec{a}$ of elements such that, for
$Y=X[\vec{a}/\vec{x}]$,232323More formally:
$Y=X[H_{1}/x_{1}]\ldots[H_{k}/x_{k}]$, where each $H_{j}$ picks the same
singleton $\\{a_{j}\\}$ for all assignments in its domain – indeed, only
choice functions of this type can ensure that
$\mathfrak{M}\models_{Y}=\\!\\!(\vec{x})$.
$\mathfrak{M}\models_{Y}\eta^{\prime}(\vec{x},\vec{w})\wedge\theta(\vec{x},\vec{w})$.

Then
$(M,X(\vec{w}))\models\eta(\vec{a})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{a},\vec{y}))$.
Indeed,

  1. 1.

If some literal of the form $x_{j}=x_{j^{\prime}}$
[$x_{j}\not=x_{j^{\prime}}$] occurs among the conjuncts of $\eta$, it occurs
unchanged also in $\eta^{\prime}$, and since $\mathfrak{M}\models_{Y}\eta$ we
have that $a_{j}=a_{j^{\prime}}$ [$a_{j}\not=a_{j^{\prime}}$];

  2. 2.

If some literal of the form $R\vec{t}$ occurs among the conjuncts of $\eta$,
where $\vec{t}$ is a tuple of variables in $\vec{x}$, the expression
$\top\vee(\texttt{NE}(\vec{w})\wedge\vec{t}=\vec{w})$ occurs among the
conjuncts of $\eta^{\prime}$. Therefore, $Y=Y_{1}\cup Y_{2}$, where
$Y_{2}\not=\emptyset$ and $s(\vec{t})=s(\vec{w})$ for all $s\in Y_{2}$. But
$s(\vec{t})=t[\vec{a}/\vec{x}]$ for all $s\in Y$. Therefore,
$t[\vec{a}/\vec{x}]\in Y_{2}(\vec{w})\subseteq X(\vec{w})$.

  3. 3.

Since $\mathfrak{M}\models_{X[\vec{a}/\vec{x}]}\theta(\vec{x},\vec{w})$ and
$\theta$ is first order, by Proposition 1 for all $s\in X$ we have that
$\mathfrak{M}\models_{s}\theta(\vec{a},\vec{w})$ in the usual Tarskian sense.
This means that, for all values $\vec{m}$ that $\vec{w}$ takes for some
assignment in $X$, $\mathfrak{M}\models\theta(\vec{a},\vec{m})$; and therefore
$(M,X(\vec{w}))\models\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{a},\vec{y}))$.

Therefore
$(M,X(\vec{w}))\models\eta(\vec{a})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{a},\vec{y}))$
and hence
$(M,X(\vec{w}))\models\exists\vec{x}(\eta(\vec{x})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{x},\vec{y})))$
as required.

Conversely, suppose that $(M,X(\vec{w}))\models\chi_{i}(R)$. Then there exists
a tuple $\vec{a}$ of elements of $M$ such that
$(M,X(\vec{w}))\models\eta(\vec{a})\wedge\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{a},\vec{y}))$.
Now let $Y=X[\vec{a}/\vec{x}]$: clearly,
$\mathfrak{M}\models_{Y}=\\!\\!(\vec{x})$. Moreover,
$\mathfrak{M}\models_{Y}\eta^{\prime}(\vec{x},\vec{w})\wedge\theta(\vec{x},\vec{w})$:
indeed,

  1. 1.

If some literal of the form $x_{j}=x_{j^{\prime}}$
[$x_{j}\not=x_{j^{\prime}}$] occurs among the conjuncts of $\eta^{\prime}$,
the same conjunct also occurs in $\eta$. Therefore $a_{j}=a_{j^{\prime}}$
[$a_{j}\not=a_{j^{\prime}}$] and $\mathfrak{M}\models_{Y}x_{j}=x_{j^{\prime}}$
[$\mathfrak{M}\models_{Y}x_{j}\not=x_{j^{\prime}}$].

  2. 2.

If some expression of the form
$\top\vee(\texttt{NE}(\vec{w})\wedge\vec{t}=\vec{w})$ is among the conjuncts
of $\eta^{\prime}$, $R\vec{t}$ is among the conjuncts of $\eta$. Therefore,
$\vec{t}[\vec{a}/\vec{x}]\in X(\vec{w})$, and so there exists some $s\in
Y=X[\vec{a}/\vec{x}]$ such that
$s(\vec{w})=\vec{t}[\vec{a}/\vec{x}]=s(\vec{t})$. But then $Y=Y\cup\\{s\\}$,
$\mathfrak{M}\models_{Y}\top$, and
$\mathfrak{M}\models_{\\{s\\}}\texttt{NE}(\vec{w})\wedge\vec{t}=\vec{w}$; and
therefore
$\mathfrak{M}\models_{Y}\top\vee(\texttt{NE}(\vec{w})\wedge\vec{t}=\vec{w})$,
as required.

  3. 3.

Since
$(M,X(\vec{w}))\models\forall\vec{y}(R\vec{y}\rightarrow\theta(\vec{a},\vec{m}))$,
for all $\vec{m}\in X(\vec{w})$ we have that
$\mathfrak{M}\models\theta(\vec{a},\vec{m})$. Therefore, for all $s\in X$,
$\mathfrak{M}\models_{s[\vec{a}/\vec{x}]}\theta(\vec{x},\vec{w})$ in the usual
Tarskian sense; and since $Y=X[\vec{a}/\vec{x}]$, by Proposition 1 we have
that $\mathfrak{M}\models_{Y}\theta(\vec{x},\vec{w})$.

Therefore,
$\mathfrak{M}\models_{X[\vec{a}/\vec{x}]}\eta^{\prime}(\vec{x},\vec{w})\wedge\theta(\vec{x},\vec{w})$
and $\mathfrak{M}\models_{X}\chi^{\prime}_{i}(\vec{w})$.

Thus, for every $\chi_{i}(R)$ we can find a
$\mathbf{FO}(=\\!\\!(\cdot),\texttt{NE})$ formula $\chi^{\prime}_{i}(\vec{w})$
such that $\mathfrak{M}\models_{X}\chi^{\prime}_{i}(\vec{w})$ if and only if
$(M,X(\vec{w}))\models\chi_{i}(R)$. But $\mathbf{D}(R)$ is equivalent to
$\bigvee_{i=1}^{t}\chi_{i}(R)$. Therefore $(M,X(\vec{w}))\models\mathbf{D}(R)$
if and only if there exists some $i\in 1\ldots t$ such that
$\mathfrak{M}\models_{X}\chi^{\prime}_{i}(\vec{w})$, that is, if and only if
$\mathfrak{M}\models_{X}\bigsqcup_{i=1}^{t}\chi^{\prime}_{i}(\vec{w})$; and
thus $\mathbf{D}$ is definable in
$\mathbf{FO}(=\\!\\!(\cdot),\texttt{NE},\sqcup)$.

###### Corollary 2

Let $\mathcal{D}$ be a family of domain-independent dependencies each of which
is union closed, upwards closed, or downwards closed242424Or non-jumping..
Then $\mathcal{D}$ is strongly first order if and only if all
$\mathbf{D}\in\mathcal{D}$ are individually strongly first order.

###### Proof

The left to right direction is obvious.

For the right to left direction, suppose that all $\mathbf{D}\in\mathcal{D}$
are individually strongly first order. By Theorem 14, every downwards closed
(or non-jumping) $\mathbf{D}\in\mathcal{D}$ is definable in
$\mathbf{FO}(=\\!\\!(\cdot),\mathcal{D}^{\uparrow},\sqcup)$, and by Corollary
1 every union closed $\mathbf{D}\in\mathcal{D}$ is definable in
$\mathbf{FO}(=\\!\\!(\cdot),\texttt{NE},\sqcup)$, and all upwards closed first
order dependencies (including all NE dependencies) are in
$\mathcal{D}^{\uparrow}$. Therefore, every sentence of
$\mathbf{FO}(\mathcal{D})$ is equivalent to some sentence of
$\mathbf{FO}(=\\!\\!(\cdot),\mathcal{D}^{\uparrow},\sqcup)$; but by
Proposition 2 every such sentence is equivalent to some first order sentence,
and therefore $\mathcal{D}$ is strongly first order.

##  4 Conclusion

In this work we found a full characterization of strongly first order
dependencies for the case of dependencies that are also domain-independent and
union-closed. This essentially completes the characterization of strongly
first order dependencies for all the main classes of dependencies studied in
the literature.

A general characterization, even modulo domain independence, of strongly first
order dependencies is however still missing; and it is the hope of the author
that the ideas and techniques developed in this work may be of some use for
proving such a characterization. Additionally, it would be interesting to
explore the same question with respect to richer languages than First Order
Logic, as it was done in [10] for the case of First Order Logic (with Team
Semantics) plus a restricted form of contradictory negation. For example,
which dependencies can be added to Inclusion Logic without increasing its
expressive power? This is not fully known at the moment, although it is known
that no first order union-closed dependency increases the expressive power of
Inclusion Logic [11].

Finally, there exist quantitative variants of Team Semantics such as
_Probabilistic Team Semantics_ [2] and _Multiteam Semantics_ [14]. The same
question about which dependencies increase the expressive power of First Order
Logic and which ones do not can be also asked for these interesting
generalizations of the basic framework of Team Semantics, and its answer would
also in their case provide a good starting point for the classification of the
corresponding extensions of First Order Logic.

## References

  * [1] Armstrong, W.W.: Dependency Structures of Data Base Relationships. In: Proc. of IFIP World Computer Congress. pp. 580–583 (1974)
  * [2] Durand, A., Hannula, M., Kontinen, J., Meier, A., Virtema, J.: Probabilistic team semantics. In: International Symposium on Foundations of Information and Knowledge Systems. pp. 186–206. Springer (2018)
  * [3] Galliani, P.: The Dynamics of Imperfect Information. Ph.D. thesis, University of Amsterdam (September 2012), http://dare.uva.nl/record/425951
  * [4] Galliani, P.: Inclusion and exclusion dependencies in team semantics: On some logics of imperfect information. Annals of Pure and Applied Logic 163(1), 68 – 84 (2012). https://doi.org/10.1016/j.apal.2011.08.005
  * [5] Galliani, P.: Upwards closed dependencies in team semantics. Information and Computation 245, 124–135 (2015). https://doi.org/10.1016/j.ic.2015.06.008
  * [6] Galliani, P.: On strongly first-order dependencies. In: Dependence Logic, pp. 53–71. Springer (2016). https://doi.org/10.1007/978-3-319-31803-5_4
  * [7] Galliani, P.: Characterizing downwards closed, strongly first-order, relativizable dependencies. The Journal of Symbolic Logic 84(3), 1136–1167 (2019). https://doi.org/10.1017/jsl.2019.12
  * [8] Galliani, P.: Characterizing strongly first order dependencies: The non-jumping relativizable case. Electronic Proceedings in Theoretical Computer Science 305, 66–82 (Sep 2019). https://doi.org/10.4204/eptcs.305.5, http://dx.doi.org/10.4204/EPTCS.305.5
  * [9] Galliani, P.: Safe dependency atoms and possibility operators in team semantics. Information and Computation p. 104593 (2020)
  * [10] Galliani, P.: Doubly strongly first order dependencies. In: International Workshop on Logic, Language, Information, and Computation. pp. 47–63. Springer (2021)
  * [11] Galliani, P., Hella, L.: Inclusion Logic and Fixed Point Logic. In: Rocca, S.R.D. (ed.) Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), vol. 23, pp. 281–295. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2013). https://doi.org/10.4230/LIPIcs.CSL.2013.281
  * [12] Galliani, P., Väänänen, J.: On dependence logic (2013), arXiv:1305.5948
  * [13] Grädel, E., Väänänen, J.: Dependence and independence. Studia Logica 101(2), 399–410 (2013). https://doi.org/10.1007/s11225-013-9479-2
  * [14] Grädel, E., Wilke, R.: Logics with multiteam semantics. ACM Transactions on Computational Logic (TOCL) 23(2), 1–30 (2022)
  * [15] Henkin, L.: Some Remarks on Infinitely Long Formulas. In: Infinitistic Methods. Proc. Symposium on Foundations of Mathematics, pp. 167–183. Pergamon Press (1961)
  * [16] Hintikka, J., Sandu, G.: Informational independence as a semantic phenomenon. In: Fenstad, J., Frolov, I., Hilpinen, R. (eds.) Logic, methodology and philosophy of science, pp. 571–589. Elsevier (1989). https://doi.org/10.1016/S0049-237X(08)70066-1
  * [17] Hodges, W.: A Shorter Model Theory. Cambridge University Press (1997)
  * [18] Hodges, W.: Compositional Semantics for a Language of Imperfect Information. Journal of the Interest Group in Pure and Applied Logics 5 (4), 539–563 (1997). https://doi.org/10.1093/jigpal/5.4.539
  * [19] Kontinen, J., Kuusisto, A., Virtema, J.: Decidability of Predicate Logics with Team Semantics. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, pp. 60:1–60:14 (2016). https://doi.org/10.4230/LIPIcs.MFCS.2016.60
  * [20] Kontinen, J., Yang, F.: Logics for first-order team properties. In: International Workshop on Logic, Language, Information, and Computation. pp. 392–414. Springer (2019)
  * [21] Kuusisto, A.: A double team semantics for generalized quantifiers. Journal of Logic, Language and Information 24(2), 149–191 (2015)
  * [22] Rönnholm, R.: Arity fragments of logics with team semantics (2018)
  * [23] Väänänen, J.: An atom’s worth of anonymity, To Appear
  * [24] Väänänen, J.: Dependence Logic. Cambridge University Press (2007). https://doi.org/10.1017/CBO9780511611193

## Appendix

In this appendix I report proof details that have not been included in the
article.

### Preservation of Closure Properties

In Section 2 it was stated that if all $\mathbf{D}\in\mathcal{D}$ are
downwards closed [union closed, with the empty team property] then all
formulas of $\mathbf{FO}(\mathcal{D})$ have this property.

This can be proven by structural induction on $\phi$. The base cases (i.e. if
$\phi$ is a dependence atom $\mathbf{D}\vec{v}$ or a first order literal
$\alpha$) are obvious (note that by Proposition 1, first order literals are
downwards closed _and_ union closed _and_ have the empty team property).

The other cases are as follows:

  * •

Let $\phi=\phi_{1}\vee\phi_{2}$.

Empty Team:

By induction hypothesis, for all models $\mathfrak{M}$ we have that
$\mathfrak{M}\models_{\emptyset}\phi_{1}$ and
$\mathfrak{M}\models_{\emptyset}\phi_{2}$. Then since
$\emptyset=\emptyset\cup\emptyset$,
$\mathfrak{M}\models_{\emptyset}\phi_{1}\vee\phi_{2}$.

Downwards Closure:

Suppose that $\mathfrak{M}\models_{X}\phi$ and $Y\subseteq X$. Then
$X=X_{1}\cup X_{2}$, where $\mathfrak{M}\models_{X_{1}}\phi_{1}$ and
$\mathfrak{M}\models_{X_{2}}\phi_{2}$. Now let $Y_{1}=Y\cap X_{1}$ and
$Y_{2}=Y\cap X_{2}$: by induction hypothesis,
$\mathfrak{M}\models_{Y_{1}}\phi_{1}$ and
$\mathfrak{M}\models_{Y_{2}}\phi_{2}$, and so — since $Y=Y_{1}\cup Y_{2}$ –
$\mathfrak{M}\models_{Y}\phi_{1}\vee\phi_{2}$.

Union Closure:

Suppose that $\mathfrak{M}\models_{X_{i}}\phi$ for all $i\in I$. Then every
$X_{i}$ is of the form $Y_{1}\cup Z_{i}$, where
$\mathfrak{M}\models_{Y_{i}}\phi_{1}$ and
$\mathfrak{M}\models_{Z_{i}}\phi_{2}$. Now let $Y=\bigcup_{i\in I}Y_{1}$ and
$Z=\bigcup_{i\in I}Z_{i}$: then by induction hypothesis
$\mathfrak{M}\models_{Y}\phi_{1}$ and $\mathfrak{M}\models_{Z}\phi_{2}$.
Therefore, for $X=\bigcup_{i\in I}X_{i}=Y\cup Z$,
$\mathfrak{M}\models_{X}\phi_{1}\vee\phi_{2}$ as required.

  * •

Let $\phi=\phi_{1}\wedge\phi_{2}$.

Empty Team:

By induction hypothesis $\mathfrak{M}\models_{\emptyset}\phi_{1}$ and
$\mathfrak{M}\models_{\emptyset}\phi_{2}$, and so
$\mathfrak{M}\models_{\emptyset}\phi_{1}\wedge\phi_{2}$.

Downwards Closure:

If $\mathfrak{M}\models_{X}\phi_{1}$ and $\mathfrak{M}\models_{X}\phi_{2}$ and
$Y\subseteq X$, by induction hypothesis $\mathfrak{M}\models_{Y}\phi_{1}$ and
$\mathfrak{M}\models_{Y}\phi_{2}$. But then
$\mathfrak{M}\models_{Y}\phi_{1}\wedge\phi_{2}.$

Union Closure:

If $\mathfrak{M}\models_{X_{i}}\phi$ for all $i\in I$,
$\mathfrak{M}\models_{X_{i}}\phi_{1}$ and
$\mathfrak{M}\models_{X_{i}}\phi_{2}$ for all such $i$. Now let
$X=\bigcup_{i\in I}X_{i}$: by induction hypothesis,
$\mathfrak{M}\models_{X}\phi_{1}$ and $\mathfrak{M}\models_{X}\phi_{2}$, and
so $\mathfrak{M}\models_{X}\phi_{2}\wedge\phi_{2}$.

  * •

Let $\phi=\exists v\psi$.

Empty Team:

By induction hypothesis, $\mathfrak{M}\models_{\emptyset}\psi$. Now let
$H_{0}$ be the trival choice function
$\emptyset\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$: then
$\emptyset[H_{0}/v]=\emptyset$, and so
$\mathfrak{M}\models_{\emptyset[H_{0}/v]}\psi$, and so
$\mathfrak{M}\models_{\emptyset}\exists v\psi$.

Downwards Closure:

If $\mathfrak{M}\models_{X}\exists v\psi$ then there exists some
$H:X\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ such that
$\mathfrak{M}\models_{X[H/v]}\psi$. Now if $Y\subseteq X$, let
$H_{|Y}:Y\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ be the
restriction of $H$ to $Y$: then $Y[H_{|Y}/v]=\\{s[m/v]:s\in Y,m\in
H_{|Y}(s)\\}\subseteq X[H/v]$, and so by induction hypothesis
$\mathfrak{M}\models_{Y[H_{|Y}/v}\psi$ and finally
$\mathfrak{M}\models_{Y}\exists v\psi$.

Union Closure:

Suppose that $\mathfrak{M}\models_{X_{i}}\exists v\psi$ for all $i\in I$. Then
for all $i\in I$ there exists some
$H_{i}:X_{i}\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ such that
$\mathfrak{M}\models_{X_{i}[H_{i}/v]}\psi$. Now let $X=\bigcup_{i\in I}X_{i}$
and let $H:X\rightarrow\mathcal{P}(M)\backslash\\{\emptyset\\}$ be defined as

$H(s)=\bigcup\\{H_{i}(s):i\in I,s\in X_{i}\\}.$

Then $X[H/v]=\\{s[m/v]:\exists i\in I\text{ s.t. }s\in X_{i}\text{ and }m\in
H_{i}(s)\\}=\bigcup_{i\in I}\\{s[m/v]:s\in X_{i},m\in
H_{i}(s)\\}=\bigcup_{i\in I}X_{i}[H_{i}/v]$.

By induction hypothesis this implies that $\mathfrak{M}\models_{X[H/v]}\psi$,
and therefore $\mathfrak{M}\models_{X}\exists v\psi$.

  * •

Let $\phi=\forall v\psi$.

Empty Team:

By induction hypothesis, $\mathfrak{M}\models_{\emptyset}\psi$. But
$\emptyset[M/v]=\emptyset$, and so $\mathfrak{M}\models_{\emptyset}\forall
v\psi$.

Downwards Closure:

If $\mathfrak{M}\models_{X}\forall v\psi$ then
$\mathfrak{M}\models_{X[M/v]}\psi$. Now if $Y\subseteq X$, $Y[M/v]\subseteq
X[M/v]$: so by induction hypothesis

Union Closure:

If $\mathfrak{M}\models_{X_{i}}\forall v\psi$ for all $i\in I$ then
$\mathfrak{M}\models_{X_{i}[M/v]}\psi$ for all such $i$. Now let
$X=\bigcup_{i\in I}X_{i}$: then $X[M/v]=\\{s[m/v]:\exists i\in I\text{ s.t.
}s\in X_{i},m\in M\\}=\bigcup_{i}X_{i}[M/v]$, and so by induction hypothesis
$\mathfrak{M}\models_{X[M/v]}\psi$ and finally $\mathfrak{M}\models_{X}\forall
v\psi$.

### Relativizability and Domain Independence

Let $\mathbf{D}$ be any dependency and let $P$ be some fixed unary predicate
symbol. Then, for all models $\mathfrak{M}$ that contain the symbol $P$ in
their signature, the semantics of the _relativized dependency_
$\mathbf{D}^{(P)}$ is defined by.the rule

TS-$\mathbf{D}^{(P)}$:

$\mathfrak{M}\models_{X}\mathbf{D}^{(P)}\vec{x}$ if and only if
$(P^{\mathfrak{M}},X(\vec{x}))\in\mathbf{D}$.

A dependency $\mathbf{D}$ is said to be _relativizable_ if every sentence of
$\mathbf{FO}(\mathbf{D}^{(P)})$ (that is, of First Order Logic augmented with
the relativized atoms $\mathbf{D}^{(P)}\vec{x}$, for some _fixed_ choice of
the predicate $P$) is equivalent to some sentence of
$\mathbf{FO}(\mathbf{D})$.

###### Proposition 6

If $\mathbf{D}$ is domain independent, then it is relativizable.

###### Proof

It suffices to show that $\mathbf{D}^{(P)}\vec{x}$ is definable in
$\mathbf{FO}(\mathbf{D})$ as
$\mathbf{D}\vec{x}\wedge\bigwedge_{x\in\vec{x}}Px$.

Suppose that $\mathfrak{M}\models_{X}\mathbf{D}^{(P)}\vec{x}$. Then
$(P^{\mathfrak{M}},X(\vec{x}))\in\mathbf{D}$. Then, since $\mathbf{D}$ is
domain-independent, $(M,X(\vec{x}))\in\mathbf{D}$, and so
$\mathfrak{M}\models_{X}\mathbf{D}\vec{x}$. Moreover, for
$(P^{\mathfrak{M}},X(\vec{x}))$ to be a model it must be the case that
$X(\vec{x})\subseteq(P^{\mathfrak{M}})^{|\vec{x}|}$, i.e., $s(x)\in
P^{\mathfrak{M}}$ for all $s\in X$ and all $x\in\vec{x}$. Therefore
$\mathfrak{M}\models_{X}\bigwedge_{x\in\vec{x}}Px$ as well, and so
$\mathfrak{M}\models_{X}\mathbf{D}\vec{x}\wedge\bigwedge_{x\in\vec{x}}Px$.

Conversely, suppose that
$\mathfrak{M}\models_{X}\mathbf{D}\vec{x}\wedge\bigwedge_{x\in\vec{x}}Px$.
Then $(M,X(\vec{x}))\in\mathbf{D}$ and
$X(\vec{x})\subseteq(P^{\mathfrak{M}})^{|\vec{x}|}$, and so since $\mathbf{D}$
is domain independent $(P^{\mathfrak{M}},X(\vec{x}))\in\mathbf{D}$ as well.

Therefore, every sentence $\phi\in\mathbf{FO}(\mathbf{D}^{(P)})$ is equivalent
to the sentence $\phi^{\prime}\in\mathbf{FO}(\mathbf{D})$ obtained by
replacing each relativized atom $\mathbf{D}^{(P)}\vec{x}$ with the
corresponding $\mathbf{D}\vec{x}\wedge\bigwedge_{x\in\vec{x}}Px$.

### Non-Jumping Dependences and Downwards Closure

######  Definition 9 ($\mathbf{D}_{\max}$)

Let $\mathbf{D}$ be a dependency. Then $(M,R)\in\mathbf{D}_{\max}$ if and only
if $(M,R)\in\mathbf{D}$ and there is no $S\supsetneq R$ such that
$(M,S)\in\mathbf{D}$.

######  Proposition 7 ([8], Proposition 22)

If $\mathbf{D}$ is strongly first order and $(M,R)\in\mathbf{D}$ then there
exists some $R^{\prime}\supseteq R$ such that
$(M,R^{\prime})\in\mathbf{D}_{\max}$.

######  Definition 10 (Non-Jumping Dependency)

A dependency $\mathbf{D}$ is non-jumping if and only if, whenever
$(M,R)\in\mathbf{D}$, there exists some $R^{\prime}\supseteq R$ such that

  * •

$(M,R^{\prime})\in\mathbf{D}_{\max}$;

  * •

For all relations $S$ with $R\subseteq S\subseteq R^{\prime}$,
$(M,S)\in\mathbf{D}$.

###### Proposition 8

If $\mathbf{D}$ is downwards closed and strongly first order then $\mathbf{D}$
is non-jumping.

###### Proof

Suppose that $(M,R)\in\mathbf{D}$. Then by Proposition 7 there is some
$R^{\prime}\supseteq R$ such that $(M,R^{\prime})\in\mathbf{D}_{\max}$. Then
$(M,R^{\prime})\in\mathbf{D}$, and since $\mathbf{D}$ is downwards closed this
implies that $(M,S)\in\mathbf{D}$ for all $S\subseteq R^{\prime}$ (and so, in
particular, for all $S$ with $R\subseteq S\subseteq R^{\prime}$).


# Identities involving $q$-Genocchi numbers and polynomials

Serkan Aracı University of Gaziantep, Faculty of Science and Arts, Department
of Mathematics, 27310 Gaziantep, TURKEY<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Mehmet Acikgoz University of Gaziantep, Faculty of
Science and Arts, Department of Mathematics, 27310 Gaziantep, TURKEY
<EMAIL_ADDRESS>,  Hassan Jolany School of Mathematics, Statistics and
Computer Science, University of Tehran, Iran<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Yuan He Department of Mathematics, Kunming
University of Science and Technology, Kunming, Yuannan 650500, People’
Republic of China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we focus on the $q$-Genocchi numbers and polynomials. We shall
introduce new identities of the q-Genocchi numbers and polynomials by using
the fermionic $p$-adic integral on $\mathbb{Z}_{p}$ which are very important
in the study of Frobenius-Genocchi numbers and polynomials. Also, we give
Cauchy-integral formula for the $q$-Genocchi polynomials and moreover by using
measure theory on $p$-adic integral we derive the distribution formula
$q$-Genocchi polynomials. Finally, we present a new definition of $q$-Zeta-
type function by using Mellin transformation which is the interpolation
function of the $q$-Genocchi polynomials at negative integers.

###### Key words and phrases:

Genocchi numbers and polynomials, $q$-Genocchi numbers and polynomials,
$p$-adic $q$-integral on $\mathbb{Z}_{p}$, Mellin transformation, $q$-Zeta
function.

###### 2000 Mathematics Subject Classification:

Primary 05A10, 11B65; Secondary 11B68, 11B73.

##  1\. PRELIMINARIES

Recently, Kim and Lee have given some properties for the $q$-Euler numbers and
polynomials in [7]. Actually, this type numbers and polynomials and their
$q$-extensions or variously generalizations have been studied in several
different ways for a long time (for details, see [1-21]).

By using $p$-adic $q$-integral on $\mathbb{Z}_{p}$, Kim defined many new
generating functions of the $q$-Bernoulli poynomials, $q$-Euler polynomials
and $q$-Genocchi polynomials in his arithmetic works (for details, see
[6-19]). The works of Kim have been benefited for further works of many
mathematicians in Analytic numbers theory. Actually, we motivated from his
inspiring works to write this paper.

Assume that $p$ be a fixed odd prime number. Throughout this work, we require
the definitions of the some notations such that let $\mathbb{Q}_{p}$ be the
field $p$-adic rational numbers and let $\mathbb{C}_{p}$ be the completion of
algebraic closure of $\mathbb{Q}_{p}$. That is,

$\boldsymbol{\mathbb{Q}}_{p}=\left\\{x=\sum_{n=-k}^{\infty}a_{n}p^{n}:0\leq
a_{n}\leq p-1\right\\}\text{.}$

Then $\mathbb{Z}_{p}$ is integral domain which is defined by

$\boldsymbol{\mathbb{Z}}_{p}=\left\\{x=\sum_{n=0}^{\infty}a_{n}p^{n}:0\leq
a_{n}\leq p-1\right\\}$

or

$\boldsymbol{\mathbb{Z}}_{p}=\left\\{x\in\mathbb{Q}_{p}:\left|x\right|_{p}\leq
1\right\\}\text{.}$

We assume that $q\in\mathbb{C}_{p}$ with $\left|1-q\right|_{p}<1$ as an
indeterminate. The $p$-adic absolute value $\left|.\right|_{p}$, is normally
given by

$\left|x\right|_{p}=p^{-r}$

where $x=p^{r}\frac{s}{t}$ with
$\left(p,s\right)=\left(p,t\right)=\left(s,t\right)=1$ and $r\in\mathbb{Q}$.

The $q$-extension of $x$ with the display notation of $\left[x\right]_{q}$ is
introduced by

$\left[x\right]_{q}=\frac{1-q^{x}}{1-q}\text{.}$

We want to note that $\lim_{q\rightarrow 1}\left[x\right]_{q}=x$ (see[1-22]).

Also, we use notation $\mathbb{N}^{\ast}$ for the union of zero and natural
numbers.

We consider that $\eta$ is a uniformly differentiable function at a point
$a\in\mathbb{Z}_{p}$, if the difference quotient

$\Phi_{\eta}\left(x,y\right)=\frac{\eta\left(x\right)-\eta\left(y\right)}{x-y},$

have a limit $\eta{\acute{}}\left(a\right)$ as
$\left(x,y\right)\rightarrow\left(a,a\right)$ and denote this by $\eta\in
UD\left(\mathbb{Z}_{p}\right)$.

Then, for $\eta\in UD\left(\mathbb{Z}_{p}\right)$, we can discuss the
following

$\frac{1}{\left[p^{n}\right]_{q}}\sum_{0\leq\xi<p^{n}}\eta\left(\xi\right)q^{\xi}=\sum_{0\leq\xi<p^{n}}\eta\left(\xi\right)\mu_{q}\left(\xi+p^{n}\mathbb{Z}_{p}\right)\text{,}$

which represents as a $p$-adic $q$-analogue of Riemann sums for $\eta$. The
integral of $\eta$ on $\mathbb{Z}_{p}$ will be defined as the limit
$\left(n\rightarrow\infty\right)$ of these sums, when it exists. The $p$-adic
$q$-integral of function $\eta\in UD\left(\mathbb{Z}_{p}\right)$ is defined by
T. Kim in [6], [10], [15] by

(1.1)
$I_{q}\left(\eta\right)=\int_{\mathbb{Z}_{p}}\eta\left(\xi\right)d\mu_{q}\left(\xi\right)=\lim_{n\rightarrow\infty}\frac{1}{\left[p^{n}\right]_{q}}\sum_{\xi=0}^{p^{n}-1}\eta\left(\xi\right)q^{\xi}\text{.}$

The bosonic integral is considered as a bosonic limit $q\rightarrow 1,$
$I_{1}\left(\eta\right)=\lim_{q\rightarrow 1}I_{q}\left(\eta\right)$.
Similarly, the fermionic $p$-adic integral on $\mathbb{Z}_{p}$ is introduced
by T. Kim as follows:

(1.2)
$I_{-q}\left(\eta\right)=\int_{\mathbb{Z}_{p}}\eta\left(\xi\right)d\mu_{-q}\left(\xi\right)$

(for more details, see [16-18]). Obviously that

(1.3) $\lim_{q\rightarrow
1}I_{-q}\left(\eta\right)=I_{-1}\left(\eta\right)=\int_{\mathbb{Z}_{p}}\eta\left(\xi\right)d\mu_{-1}\left(\xi\right)=\lim_{n\rightarrow\infty}\sum_{\xi=0}^{p^{n}-1}\eta\left(\xi\right)\left(-1\right)^{\xi}\text{.}$

From (1.3), it is well-known as the useful property for the fermionic $p$-adic
$q$-integral on $\mathbb{Z}_{p}$:

(1.4)
$I_{-1}\left(\eta_{1}\right)+I_{-1}\left(\eta\right)=2\eta\left(0\right)\text{,}$

where $\eta_{1}\left(x\right)=\eta\left(x+1\right)$ (for details, see[2-4,
11-14, 16-22]).

The $q$-Genocchi polynomials can be introduced as follows:

(1.5)
$G_{n,q}\left(x\right)=n\int_{\mathbb{Z}_{p}}q^{\xi}\left(x+\xi\right)^{n-1}d\mu_{-1}\left(\xi\right)\text{.}$

From (1.5), we have

$G_{n,q}\left(x\right)=\sum_{l=0}^{n}\binom{n}{l}x^{l}G_{n-l,q}$

where $G_{n,q}(0):=G_{n,q}$ are called $q$-Genocchi numbers. Then,
$q$-Genocchi numbers can be given by

$G_{0,q}=0\text{ and
}q\left(G_{q}+1\right)^{n}+G_{n,q}=\left\\{\begin{array}[]{cc}2,&\text{if
}n=1\\\ 0,&\text{if\ }n\geq 1\end{array}\right.$

with the usual convention about replacing $\left(G_{q}\right)^{n}$ by
$G_{n,q}$ is used (for details, see [4]).

Our objective in the present paper is to derive not only new but also novel
and interesting properties of the $q$-Genocchi numbers and polynomials. Our
applications for the $q$-Genocchi polynomials seem to be useful in mathematics
for engineerings (on this subject, see [23]).

##  2\. SOME PROPERTIES ON THE $q$-GENOCCHI NUMBERS AND POLYNOMIALS

Let $\eta\left(x\right)=q^{x}e^{t\left(x+\xi\right)}$. Then, by using (1.4),
we see that

$t\int_{\mathbb{Z}_{p}}q^{\xi}e^{t\left(x+\xi\right)}d\mu_{-1}\left(\xi\right)=\frac{2t}{qe^{t}+1}e^{xt}\text{.}$

From the last equality and (1.5), we easily derive the following generating
function of the $q$-Genocchi polynomials:

(2.1)
$t\int_{\mathbb{Z}_{p}}q^{\xi}e^{t\left(x+\xi\right)}d\mu_{-1}\left(\xi\right)=\sum_{n=0}^{\infty}G_{n,q}\left(x\right)\frac{t^{n}}{n!}=\frac{2t}{qe^{t}+1}e^{xt}\text{,
}\left|\log q+t\right|<\pi\text{.}$

Substituting $x\rightarrow x+y$ into (2.1), then we write

$\displaystyle\sum_{n=0}^{\infty}G_{n,q}\left(x+y\right)\frac{t^{n}}{n!}=\frac{2t}{qe^{t}+1}e^{\left(x+y\right)t}$
$\displaystyle=\left(\sum_{n=0}^{\infty}G_{n,q}\left(x\right)\frac{t^{n}}{n!}\right)\left(\sum_{n=0}^{\infty}y^{n}\frac{t^{n}}{n!}\right)$
$\displaystyle=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\binom{n}{k}G_{k,q}\left(x\right)y^{n-k}\right)\frac{t^{n}}{n!}$

From the above, we easily express the following theorem:

######  Theorem 1.

The following holds:

(2.2)
$G_{n,q}\left(x+y\right)=\sum_{k=0}^{n}\binom{n}{k}G_{k,q}\left(x\right)y^{n-k}\text{.}$

By (2.2), we consider the following

$G_{n,q}\left(x+y\right)=\frac{2}{\left[2\right]_{q}}ny^{n-1}+\sum_{k=2}^{n}\binom{n}{k}G_{k,q}\left(x\right)y^{n-k}\text{.}$

From this, it follows that

$G_{n,q}\left(x+y\right)-\frac{2}{\left[2\right]_{q}}ny^{n-1}=\sum_{k=2}^{n}\binom{n}{k}G_{k,q}\left(x\right)y^{n-k}$

can be derived and so we reach the following theorem:

######  Theorem 2.

For $n\in\mathbb{N}^{\ast}$, one has

(2.3)
$\displaystyle\sum_{k=0}^{n}\frac{\binom{n}{k}}{\left(k+2\right)\left(k+1\right)}G_{k+2,q}\left(x\right)y^{n-k}$
$\displaystyle=\frac{G_{n+2,q}\left(x+y\right)-\frac{2}{\left[2\right]_{q}}\left(n+2\right)y^{n+1}}{\left(n+2\right)\left(n+1\right)}\text{.}$

Replacing $y$ by $-y$ into (2.3), then we get

(2.4)
$\displaystyle\frac{G_{n+2,q}\left(x-y\right)-\frac{2}{\left[2\right]_{q}}\left(n+2\right)\left(-1\right)^{n+1}y^{n+1}}{\left(n+2\right)\left(n+1\right)}$
$\displaystyle=\sum_{k=0}^{n}\frac{\binom{n}{k}\left(-1\right)^{n-k}}{\left(k+2\right)\left(k+1\right)}G_{k+2,q}\left(x\right)y^{n-k}\text{.}$

By (2.4), it follows that

(2.5)
$\displaystyle\sum_{k=0}^{n}\frac{\binom{n}{k}\left(-1\right)^{k}}{\left(k+2\right)\left(k+1\right)}G_{k+2,q}\left(x\right)y^{n-k}$
$\displaystyle=\frac{\left(-1\right)^{n}G_{n+2,q}\left(x-y\right)+\frac{2}{\left[2\right]_{q}}\left(n+2\right)y^{n+1}}{\left(n+1\right)\left(n+2\right)}\text{.}$

Therefore, from the expressions of (2.3) and (2.5), we procure the following
theorem:

######  Theorem 3.

The following holds true:

(2.6)
$\displaystyle\sum_{k=0}^{\left[\frac{n}{2}\right]}\frac{\binom{n}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)y^{n-2k}$
$\displaystyle=\frac{\left(-1\right)^{n}G_{n+2,q}\left(x-y\right)+G_{n+2,q}\left(x+y\right)}{\left(n+1\right)\left(n+2\right)}$

where $\left[.\right]$ is Gauss’ symbol.

By (2.4), we have the following identity

(2.7)
$\displaystyle\sum_{k=2}^{n}\frac{\binom{n}{k}\left(-1\right)^{k}}{k\left(k-1\right)}G_{k,q}\left(x\right)y^{n-k}$
$\displaystyle=\frac{\left(-1\right)^{n}G_{n,q}\left(x-y\right)+\frac{2}{\left[2\right]_{q}}ny^{n-1}}{n\left(n-1\right)}\text{.}$

By (2.4), (2.5) and (2.7), then we have the following theorem:

######  Theorem 4.

For $n\in\mathbb{N}^{\ast}$, we get

(2.8)
$\displaystyle\frac{\left(-1\right)^{n}G_{n+2,q}\left(x-y\right)+G_{n+2,q}\left(x+y\right)}{\left(n+2\right)\left(n+1\right)}$
$\displaystyle=\sum_{k=0}^{\left[\frac{n+1}{2}\right]}\frac{\binom{n}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)y^{n-2k}\text{.}$

Taking $y=1$ into (2.3), it follows that

(2.9)
$q\sum_{k=0}^{n}\frac{\binom{n}{k}}{\left(k+2\right)\left(k+1\right)}G_{k+2,q}\left(x\right)=\frac{qG_{n+2,q}\left(x+1\right)}{\left(n+1\right)\left(n+2\right)}-\frac{2q}{\left[2\right]_{q}\left(n+1\right)}\text{.}$

We need the following for sequel of this paper:

$2e^{tx}=\frac{1}{t}\left(q\frac{2t}{qe^{t}+1}e^{\left(x+1\right)t}+\frac{2t}{qe^{t}+1}e^{xt}\right)\text{.}$

From the above, we easily develop the following:

(2.10)
$qG_{n+1,q}\left(x+1\right)+G_{n+1,q}\left(x\right)=\left(n+1\right)2x^{n}\text{.}$

By (2.9) and (2.10), we state the following theorem:

######  Theorem 5.

The following holds:

(2.11)
$\displaystyle\sum_{k=0}^{n}\frac{\binom{n}{k}}{\left(k+2\right)\left(k+1\right)}G_{k+2,q}\left(x\right)$
$\displaystyle=\frac{2x^{n+1}}{qn+q}-\frac{G_{n+2,q}\left(x\right)}{\left(qn+q\right)\left(n+2\right)}-\frac{2}{\left[2\right]_{q}\left(n+1\right)}\text{.}$

Thanks to equality of $\lim_{q\rightarrow
1}G_{n,q}\left(x\right)=G_{n,1}\left(x\right):=G_{n}\left(x\right)$, where
$G_{n}\left(x\right)$ are known as Genocchi polynomials which is given via the
exponential generating function, as follows:

$\sum_{n=0}^{\infty}G_{n}\left(x\right)\frac{t^{n}}{n!}=\frac{2t}{e^{t}+1}e^{xt}\text{
}\left(\left|t\right|<\pi\right),$

(see [1-4, 12, 13, 21]). From the above, as $q\rightarrow 1$ in (2.11), we
discover the following corollary:

######  Corollary 1.

The following

$\displaystyle\sum_{k=0}^{n}\frac{\binom{n}{k}}{\left(k+2\right)\left(k+1\right)}G_{k+2}\left(x\right)$
$\displaystyle=\frac{2x^{n+1}}{n+1}-\frac{G_{n+2}\left(x\right)}{\left(n+1\right)\left(n+2\right)}-\frac{1}{n+1}$

is true.

Let us take $y=1$ and $n\rightarrow 2n$ into (2.6), becomes

(2.12)
$\displaystyle\sum_{k=0}^{n}\frac{\binom{2n}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)$
$\displaystyle=\frac{G_{2n+2,q}\left(x-1\right)+G_{2n+2,q}\left(x+1\right)}{\left(2n+1\right)\left(2n+2\right)}$
$\displaystyle=\frac{\frac{1}{q}\left(qG_{2n+2,q}\left(x+1\right)+G_{2n+2,q}\left(x\right)\right)+qG_{2n+2,q}\left(x\right)+G_{2n+2,q}\left(x-1\right)}{\left(2n+1\right)\left(2n+2\right)}$
$\displaystyle-\frac{G_{2n+2,q}\left(x\right)}{q\left(2n+1\right)\left(2n+2\right)}-\frac{qG_{2n+2,q}\left(x\right)}{\left(2n+1\right)\left(2n+2\right)}$
$\displaystyle=\frac{2\left(n+2\right)x^{n+1}}{\left(2n+1\right)\left(2n+2\right)}+\frac{2\left(n+2\right)\left(x-1\right)^{n+1}}{\left(2n+1\right)\left(2n+2\right)}-\frac{G_{2n+2,q}\left(x\right)}{q\left(2n+1\right)\left(2n+2\right)}-\frac{qG_{2n+2,q}\left(x\right)}{\left(2n+1\right)\left(2n+2\right)}$

After these applications, we conclude with the following theorem:

######  Theorem 6.

The following identity

(2.13)
$\displaystyle\sum_{k=0}^{n}\frac{\binom{2n}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)$
$\displaystyle=\frac{\left(n+2\right)x^{n+1}}{\left(2n+1\right)\left(n+1\right)}+\frac{\left(n+2\right)\left(x-1\right)^{n+1}}{\left(2n+1\right)\left(n+1\right)}-\frac{G_{2n+2,q}\left(x\right)}{q\left(2n+1\right)\left(2n+2\right)}-\frac{qG_{2n+2,q}\left(x\right)}{\left(2n+1\right)\left(2n+2\right)}$

is true.

Now, we analyse as $q\rightarrow 1$ for the equation (2.13) and so we readily
state the following corollary which seems to be interesting property for the
Genocchi polynomials.

######  Corollary 2.

The following equality holds:

(2.14)
$\displaystyle\sum_{k=0}^{n}\frac{\binom{2n}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2}\left(x\right)$
$\displaystyle=\frac{2\left(n+2\right)x^{n+1}}{\left(2n+1\right)\left(2n+2\right)}+\frac{2\left(n+2\right)\left(x-1\right)^{n+1}}{\left(2n+1\right)\left(2n+2\right)}-\frac{G_{2n+2}\left(x\right)}{\left(2n+1\right)\left(2n+2\right)}-\frac{G_{2n+2}\left(x\right)}{\left(2n+1\right)\left(2n+2\right)}\text{.}$

Substituting $n\rightarrow 2n+1$ and $y=1$ into (2.8), we compute

$\displaystyle\sum_{k=0}^{n}\frac{\binom{2n+1}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)$
$\displaystyle=\frac{G_{2n+3,q}\left(x+1\right)-G_{2n+3,q}\left(x-1\right)}{\left(2n+3\right)\left(2n+2\right)}$
$\displaystyle=\frac{\frac{1}{q}\left(qG_{2n+3,q}\left(x+1\right)+G_{2n+3,q}\left(x\right)\right)-\left(G_{2n+3,q}\left(x\right)+G_{2n+3,q}\left(x-1\right)\right)}{\left(2n+3\right)\left(2n+2\right)}$
$\displaystyle+\left(\frac{q-1}{q}\right)\frac{G_{2n+3,q}\left(x\right)}{\left(2n+3\right)\left(2n+2\right)}$
$\displaystyle=\frac{x^{2n+2}}{q\left(n+1\right)}-\frac{\left(x-1\right)^{2n+2}}{\left(n+1\right)}+\left(\frac{q-1}{q}\right)\frac{G_{2n+3,q}\left(x\right)}{\left(2n+3\right)\left(2n+2\right)}\text{.}$

Therefore, we obtain the following theorem:

######  Theorem 7.

The following equality holds:

$\displaystyle\sum_{k=0}^{n}\frac{\binom{2n+1}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)$
$\displaystyle=\frac{x^{2n+2}}{q\left(n+1\right)}-\frac{\left(x-1\right)^{2n+2}}{\left(n+1\right)}+\left(\frac{q-1}{q}\right)\frac{G_{2n+3,q}\left(x\right)}{\left(2n+3\right)\left(n+1\right)}\text{.}$

As $q\rightarrow 1$ in the above theorem, then we easily derive the following
corollary:

######  Corollary 3.

For $n\in\mathbb{N}^{\ast}$, then we have

$\displaystyle\sum_{k=0}^{n}\frac{\binom{2n+1}{2k}}{\left(k+1\right)\left(2k+1\right)}G_{2k+2,q}\left(x\right)$
$\displaystyle=\frac{2x^{2n+2}}{\left(2n+2\right)}-\frac{2\left(x-1\right)^{2n+2}}{\left(2n+2\right)}\text{.}$

##  3\. CONCLUSION

In this final section, we recall the generating function of the $q$-Genocchi
polynomials, as follows:

(3.1)
$\mathcal{F}_{q}\left(x,t\right)=\frac{2t}{qe^{t}+1}e^{xt}=\sum_{n=0}^{\infty}G_{n,q}\left(x\right)\frac{t^{n}}{n!}\text{.}$

Using the definition of the $k$-th derivative as $\frac{d^{k}}{dt^{k}}$ to
(3.1), then we easily see that

(3.2)
$\frac{d^{k}}{dt^{k}}\left(\frac{2t}{qe^{t}+1}e^{xt}\right)=\frac{d^{k}}{dt^{k}}\left(\sum_{n=0}^{\infty}G_{n,q}\left(x\right)\frac{t^{n}}{n!}\right)\text{.}$

By applying $\lim_{t\rightarrow 0}$ on the both sides in (3.2), then we
conclude with the following theorem:

######  Theorem 8.

The following identity

(3.3) $G_{k,q}\left(x\right)=\lim_{t\rightarrow
0}\left[\frac{d^{k}}{dt^{k}}\left(\frac{2t}{qe^{t}+1}e^{xt}\right)\right]$

is true.

We now consider Cauchy-integral formula of the $q$-Genocchi polynomials which
is a vital and important in complex analysis, is an important statement about
line integrals for holomorphic functions in the complex plane. So, by using
the equation of (3.3), we can state the following theorem:

######  Theorem 9.

The following Cauchy-integral holds true:

$G_{n,q}\left(x\right)=\frac{n!}{2\pi
i}\int_{C}\mathcal{F}_{q}\left(x,t\right)\frac{dt}{t^{n+1}}$

where $C$ is a loop which starts at $-\infty$, encircles the origin once in
the positive direction, and the returns $-\infty$.

Distribution formula for the $q$-Genocchi polynomials is important to study
regarding $p$-adic Measure theory. That is,

$\displaystyle\int_{\mathbb{Z}_{p}}q^{y}\left(x+y\right)^{n}d\mu_{-1}\left(y\right)$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\sum_{\xi=0}^{dp^{n}-1}\left(-1\right)^{\xi}\left(x+\xi\right)^{n}q^{\xi}$
$\displaystyle=$ $\displaystyle
d^{n}\sum_{a=0}^{d-1}\left(-1\right)^{a}q^{a}\left(\lim_{n\rightarrow\infty}\sum_{\xi=0}^{p^{n}-1}\left(-1\right)^{\xi}\left(\frac{x+a}{d}+\xi\right)^{n}q^{d\xi}\right)$
$\displaystyle=$ $\displaystyle
d^{n}\sum_{a=0}^{d-1}\left(-1\right)^{a}q^{a}\frac{G_{n+1,q}\left(\frac{x+a}{d}\right)}{n+1}.$

After the above applications, we procure the following theorem.

######  Theorem 10.

For $n\in\mathbb{N}^{\ast}$, then we have

$G_{n,q}\left(dx\right)=d^{n-1}\sum_{a=0}^{d-1}\left(-1\right)^{a}q^{a}G_{n,q}\left(x+\frac{a}{d}\right)\text{.}$

By utilizing from the definition of the geometric series in (3.1), we easily
see that

$\sum_{m=0}^{\infty}G_{m,q}\left(x\right)\frac{t^{m}}{m!}=\sum_{m=0}^{\infty}\left(2\left(m+1\right)\sum_{n=0}^{\infty}\left(-1\right)^{n}q^{n}n^{m}\right)\frac{t^{m+1}}{\left(m+1\right)!},$

by comparing the coefficients on the both sides, then we have, for
$m\in\mathbb{N}$

(3.4)
$\frac{G_{m+1,q}\left(x\right)}{m+1}=\left[2\right]_{q}\sum_{n=1}^{\infty}\left(-1\right)^{n}q^{n}n^{m}\text{.}$

Now also, we develop the following applications by using Mellin transformation
to the generating function of the $q$-Genocchi polynomaials: For
$s\in\mathbb{C}$ and $\Re e\left(s\right)>1$,

$\displaystyle\zeta\left(s,x:q\right)$ $\displaystyle=$
$\displaystyle\frac{1}{\Gamma\left(s\right)}\int_{0}^{\infty}t^{s-2}\left\\{-\mathcal{F}_{q}\left(x,-t\right)\right\\}dt$
$\displaystyle=$ $\displaystyle
2\sum_{n=0}^{\infty}\left(-1\right)^{n}q^{n}\left(\int_{0}^{\infty}t^{s-1}e^{-nt}dt\right)$
$\displaystyle=$ $\displaystyle
2\sum_{n=1}^{\infty}\frac{\left(-1\right)^{n}q^{n}}{n^{s}}$

Thus, we can state the definition of the $q$-Zeta-type function as follows:

(3.6)
$\zeta\left(s,x:q\right)=2\sum_{n=1}^{\infty}\frac{\left(-1\right)^{n}q^{n}}{n^{s}}\text{.}$

As $q\rightarrow 1$ in (3.6), turns into

$\lim_{q\rightarrow
1}\zeta\left(s,x:q\right)=\zeta\left(s,x:1\right):=\zeta\left(s,x\right)=2\sum_{n=1}^{\infty}\frac{\left(-1\right)^{n}}{n^{s}}$

which is well-known as Euler-Zeta function (see [6]). By (3.4) and (3.6), we
get

$\zeta\left(-n,x:q\right)=\frac{G_{n+1,q}\left(x\right)}{n+1}\text{.}$

## References

  * [1] S. Araci, D. Erdal, and J. J. Seo, A study on the fermionic $p$-adic $q$-integral representation on $\mathbb{Z}_{p}$ associated with weighted $q$-Bernstein and $q$-Genocchi polynomials, Abstract and Applied Analysis, Volume 2011, Article ID 649248, 10 pages.
  * [2] S. Araci, J. J. Seo, and D. Erdal, New Construction weighted ($h,q$)-Genocchi numbers and polynomials related to Zeta type function, Discrete Dynamics in Nature and Society, Volume 2011, Article ID 487490, 7 pages.
  * [3] S. Araci, M. Acikgoz, and Feng Qi, On the $q$-Genocchi numbers and polynomials with weight zero and their applications, Available at http://arxiv.org/abs/1202.2643
  * [4] H. Jolany and H. Sharifi, Some results for the Apostol-Genocchi polynomials of higher order, Bulletin of Malaysian Mathematical Sciences Society (Article in press).
  * [5] Yuan He and Chunping Wang, Some Formulae of Products of the Apostol-Bernoulli and Apostol-Euler Polynomials, Discrete Dynamics in Nature and Society, vol. 2012, Article ID 927953, 11 pages.
  * [6] T. Kim, Euler numbers and polynomials associated with Euler Zeta functions, Abstract and Applied Analysis, Volume 2008, Article ID 581582, 11 pages.
  * [7] T. Kim and S.-H. Lee, Some Properties on the $q$-Euler Numbers and Polynomials, Abstract and Applied Analysis, vol. 2012, Article ID 284826, 9 pages, 2012.
  * [8] D. Kim, T. Kim, S. -H. Lee, D. V. Dolgy, S.-H. Rim, Some new identities on the Bernoulli numbers and polynomials, Discrete Dynamics in Nature and Society, Volume 2011, Article ID 856132, 11 pages.
  * [9] T. Kim, J. Choi, and Y. H. Kim, Some identities on the $q$-Bernoulli numbers and polynomials with weight $0,$ Abstract And Applied Analysis, Volume 2011, Article ID 361484, 8 pages.
  * [10] T. Kim, On a$\ q$-analogue of the $p$-adic log gamma functions related integrals, J. Number Theory, 76 (1999) no. 2, 320-329.
  * [11] T. Kim, and J. Choi, On the $q$-Euler numbers and polynomials with weight $0$, Abstract and Applied Analysis, Volume 2012, Article ID 795304, 7 pages..
  * [12] T. Kim, On the $q$-extension of Euler and Genocchi numbers, J. Math. Anal. Appl. 326 (2007) 1458-1465.
  * [13] T. Kim, On the multiple $q$-Genocchi and Euler numbers, Russian J. Math. Phys. 15 (4) (2008) 481-486.
  * [14] T. Kim, On the weighted $q$-Bernoulli numbers and polynomials, Advanced Studies in Contemporary Mathematics 21(2011), no.2, p. 207-215.
  * [15] T. Kim, $q$-Volkenborn integration, Russ. J. Math. phys. 9 (2002) 288-299.
  * [16] T. Kim, $q$-Euler numbers and polynomials associated with $p$-adic $q$-integrals, J. Nonlinear Math. Phys., 14 (2007), no. 1, 15–27.
  * [17] T. Kim, New approach to $q$-Euler polynomials of higher order, Russ. J. Math. Phys., 17 (2010), no. 2, 218–225.
  * [18] T. Kim, Some identities on the $q$-Euler polynomials of higher order and $q$-Stirling numbers by the fermionic $p$-adic integral on $\mathbb{Z}_{p}$, Russ. J. Math. Phys., 16 (2009), no.4,484–491.
  * [19] D. Kim, T. Kim, J. Choi, and Y. H. Kim, Identities involving $q$-Bernoulli and $q$-Euler numbers, Abstract and Applied Analysis, Volume 2012 (2012), Article ID 674210, 10 pages.
  * [20] C. S. Ryoo, A note on the weighted $q$-Euler numbers and polynomials, Advan. Stud. Contemp. Math. 21(2011), 47-54.
  * [21] I. N. Cangul, V. Kurt, H. Ozden, and Y. Simsek, On the higher-order $w$-$q$-genocchi numbers, Advanced Studies in Contemporary Mathematics 19 (2009), no. 1, pp. 39–57.
  * [22] M. Acikgoz, S. Araci and I. N. Cangul, A note on the modified $q$-Bernstein polynomials for functions of several variables and their reflections on $q$-Volkenborn integration, Applied Mathematics and Computation, vol. 218 (2011), no. 3, pp. 707–712.
  * [23] L. C. Andrews, Special Functions of Mathematics for Engineerings, SPIE Press, 1992, pages 479.