Finite Sets—What Kind of Finite?

Abstract

In mathematics, philosophy, cosmology, and theology, the notion of infinity has generated ample debate. Much less discussion has been generated by the notion of finiteness. However, when we consider finitely supported sets, the notion of finiteness becomes more interesting and richer. We present several independent definitions of finite sets within the framework of finitely supported structures, emphasizing the differences between these definitions.

1. Finitely Supported Sets

The theory of finitely supported structures was presented in [1,2]; it deals with a finitary representation of infinite sets containing sufficient symmetry to be handled in a concise way. More precisely, this theory considers as equivalent the objects of a structure that have a certain degree of similarity, focusing only on those objects that are ‘essentially different’. The theory of finitely supported sets is related to the permutation models of Zermelo–Fraenkel set theory with atoms (ZFA); these models were introduced by Fraenkel, Lindenbaum, and Mostowski [3] to prove the independence of the axiom of choice from the other axioms of ZFA (see [4]). More recently, finitely supported sets have been developed in the classical set theory of Zermelo-Fraenkel (ZF) by equipping ZF sets with actions of a group of bijections of some basic elements called atoms [5,6]. These sets with permutation actions were used to investigate the renaming of the bound variables by fresh names in the theory of programming, as well as in describing automata, languages and Turing machines operating over infinite alphabets [7,8] or in computation [9].

In this paper, we present various independent definitions for finite sets in the framework of finitely supported structures, and emphasize the connections and differences between them. This approach extends our previous article [10].

The first step is to present some basic notions regarding finitely supported sets (more details can be found in [1,2]). We work with a fixed infinite set A of atoms; the elements of A have no internal structure, they can only be compared for equality. A transposition is a function $\left(ab\right):A\to A$ defined by $\left(ab\right)\left(a\right)=b$, $\left(ab\right)\left(b\right)=a$, and $\left(ab\right)\left(c\right)=c$ for $c\ne a,b$. A finitary permutation of A is defined as a bijection of A generated by composing finitely many transpositions, i.e., a bijection of A leaving invariant all but finitely many elements of A. The set of all finitary permutations of A is denoted by $S_A$. Considering a ZF set X, we define an $S_A$-action on X as a group action of $S_A$ on X, namely a function $·:S_A\times X\to X$ having the properties that $1_A·x=x$ and $\pi ·({\pi }^{\prime }·x)=(\pi \circ {\pi }^{\prime })·x$ for all $\pi ,{\pi }^{\prime }\in S_A$ and $x\in X$. An $S_A$-set is a pair $(X,·)$, where X is a ZF set and $·:S_A\times X\to X$ is an $S_A$-action on X. If $(X,·)$ is an $S_A$-set, we say that $S\subset A$ supports x if for each $\pi \in Fix\left(S\right)$ we have $\pi ·x=x$, where $Fix\left(S\right)=\{\pi \in S_A|\pi \left(a\right)=a$ for all $a\in S\}$.

An element of X that is supported by a finite subset of atoms is called finitely supported. If $(X,·)$ is an $S_A$-set, we say that set X is an invariant set whenever each $x\in X$ is finitely supported. If there is a finite set supporting x, then there exists a least finite set $supp\left(x\right)$ supporting x, defined as the intersection of all sets supporting x; this set is called the support of x. An empty supported element is equivariant. If an element x of an $S_A$-set X is finitely supported, then $\pi ·x$ is finitely supported and $supp(\pi ·x)=\pi \left(supp\right(x\left)\right):=\left\{\pi \right(a\left)\right|a\in supp\left(x\right)\}$ for all $\pi \in S_A$.

Let $(X,·)$ and $(Y,▹)$ be $S_A$-sets. According to [2], the set A of atoms is an invariant set with the $S_A$-action $\mathrm{\diamond }:S_A\times A\to A$ defined by $\pi \diamond a:=\pi \left(a\right)$ for all $\pi \in S_A$ and $a\in A$. The Cartesian product $X\times Y$ is an $S_A$-set with the $S_A$-action ⊗ defined by $\pi \otimes (x,y)=(\pi ·x,\pi ▹y)$ for all $\pi \in S_A$ and all $x\in X$, $y\in Y$. The disjoint union $X+Y=\left\{\right(0,x\left)\right|x\in X\}\cup \{(1,y)|y\in Y\}$ is an $S_A$-set with the $S_A$-action ★ defined by $\pi ★z=(0,\pi ·x)$ if $z=(0,x)$ and $\pi ★z=(1,\pi ▹y)$ if $z=(1,y)$. For $(X,·)$ and $(Y,▹)$ invariant sets, $(X\times Y,\otimes )$ and $(X+Y,★)$ are also invariant sets. The powerset $\mathcal{P}\left(X\right)$ is an $S_A$-set with the $S_A$-action $★:S_A\times \mathcal{P}\left(X\right)\to \mathcal{P}\left(X\right)$ defined by $\pi ★Z:=\{\pi ·z|z\in Z\}$ for all $\pi \in S_A$ and $Z\subseteq X$. We denote by ${\mathcal{P}}_{fs}\left(X\right)$ the set formed from those subsets of X that are finitely supported as elements in $\mathcal{P}\left(X\right)$ with respect to the action ★; $({\mathcal{P}}_{fs}\left(X\right),★{|}_{{\mathcal{P}}_{fs}\left(X\right)})$ is also an invariant set, where ${★|}_{{\mathcal{P}}_{fs}\left(X\right)}$ represents the action ★ restricted to ${\mathcal{P}}_{fs}\left(X\right)$. Non-atomic sets are trivially invariant, i.e., they are equipped with the action ⋄ defined as $(\pi ,x)\mapsto x$. A subset Z of an invariant set $(X,·)$ is called finitely supported (or simply, that $(Z,·)$ is a finitely supported set) if and only if $Z\in {\mathcal{P}}_{fs}\left(X\right)$. A subset Z of an invariant set $(X,·)$ is uniformly supported if all of its elements are supported by the same finite set of atoms. In particular, if $X\subset A$ and X is finite, then $supp\left(X\right)=X$. If $Y\subseteq A$ and Y has a finite complement, then $supp\left(Y\right)=A\setminus Y$. Whenever $Z\subseteq A$ is neither finite nor has a finite complement, then Z is not finitely supported. Furthermore, the set $S_A$ of all finitary permutations of A coincide with the set of all bijections of A [2].

Due to the fact that all functions are relations (namely, subsets of the Cartesian product of two sets), we say that a function $f:Z\to T$ is finitely supported if $f\in {\mathcal{P}}_{fs}(X\times Y)$, for any invariant sets $(X,·)$ and $(Y,▹)$ such that $Z\in {\mathcal{P}}_{fs}\left(X\right)$ and $T\in {\mathcal{P}}_{fs}\left(Y\right)$. The set of all finitely supported functions from Z to T is denoted by $T_{fs}^Z$. Notice that $Y^X$ is an $S_A$-set with the $S_A$-action $\widetilde{★}:S_A\times Y^X\to Y^X$ defined by $\left(\pi \widetilde{★}f\right)\left(x\right)=\pi ▹\left(f({\pi }^{-1}·x)\right)$ for all $\pi \in S_A$, $f\in Y^X$ and $x\in X$. A function $f:Z\to T$ is finitely supported if and only if it is finitely supported with respect to the $S_A$-action $\widetilde{★}$. A function $f:Z\to T$ is supported by a finite set $S\subset A$ if and only if for all $x\in Z$ and all $\pi \in Fix\left(S\right)$ we have $\pi ·x\in Z$, $\pi ▹f\left(x\right)\in T$, and $f(\pi ·x)=\pi ▹f\left(x\right)$. A finitely supported function $f:A\to A$ is bijective if and only if it is a finitary permutation.

Two finitely supported sets X and Y are called equipollent if there exists a finitely supported bijection between them. The equipollence relation is an equivariant equivalence relation on the family of all finitely supported sets [10]. The cardinality of X is the equivalence class of all finitely supported sets that are equipollent to X, which is denoted by $\left|X\right|$. Two finitely supported sets X and Y have the same cardinality, i.e., $\left|X\right|=\left|Y\right|$, if and only if there exists a finitely supported bijection $f:X\to Y$. In the family of cardinalities, we can define the relations ≤ and ${\le }^{*}$ by $\left|X\right|\le \left|Y\right|$ if and only if there is a finitely supported injective function $f:X\to Y$, and by $\left|X\right|{\le }^{*}\left|Y\right|$ if and only if there is a finitely supported surjective function $g:Y\to X$, respectively. The relation ≤ is equivariant, reflexive, anti-symmetric, and transitive, but it is not total, while the relation ${\le }^{*}$ is equivariant, reflexive, and transitive, but it is not anti-symmetric and not total. If $\left|X\right|\le \left|Y\right|$ then $\left|X\right|{\le }^{*}\left|Y\right|$, but the reverse implication is not necessarily valid [2]. The product of cardinalities is defined by $\left|X\right|·\left|Y\right|=|X\times Y|$, the sum of cardinalities is defined by $\left|X\right|+\left|Y\right|=|X+Y|$, while the exponent of a cardinality is defined by ${\left|X\right|}^{\left|Y\right|}=|X_{fs}^Y|=|\{f:Y\to X|f\mathit{is}\mathit{finitely}\mathit{supported}\}|$. These definitions are correct in the framework of finitely supported structures. If $X,Y,Z$ are finitely supported sets, it is proved that ${\left|Z\right|}^{\left|X\right|·\left|Y\right|}={\left(\right|Z|}^{\left|Y\right|}{)}^{\left|X\right|}$, ${\left|Z\right|}^{\left|X\right|+\left|Y\right|}={\left|Z\right|}^{\left|X\right|}·{\left|Z\right|}^{\left|Y\right|}$, $\left(\right|X|·{\left|Y\right|)}^{\left|Z\right|}={\left|X\right|}^{\left|Z\right|}·{\left|Y\right|}^{\left|Z\right|}$. and $|{\mathcal{P}}_{fs}{\left(Z\right)|=|\{0,1\}|}^{\left|Z\right|}$. If $\left|X\right|\le \left|Y\right|$, then ${\left|X\right|}^{\left|Z\right|}\le {\left|Y\right|}^{\left|Z\right|}$ and ${\left|Z\right|}^{\left|X\right|}\le {\left|Z\right|}^{\left|Y\right|}$ [10].

The class of finitely supported sets contains both the family of non-atomic ZF sets, and the family of atomic sets with finite (possibly non-empty) supports (note that the non-atomic ZF sets are trivially invariant because all their elements are empty supported). An interesting problem arises: whether a classical result can be adequately reformulated by replacing a ’non-atomic structure’ with an ’atomic, finitely supported structure’. It is proved that this is not true; there exist ZF results that lose their validity when transferring them into the atomic framework of a finitely supported structure (see [2] for more details). For example, a ZF result stating that the maximal antichain principle (MAP) implies the full axiom of choice does not hold in ZFA because MAP holds in the first Fraenkel model, while choice is not valid in this model. Another example of how permutation models are used to show the invalidity of various results in the absence of choice is presented in [11]. The technique for the translation of the classical results into the framework of finitely supported sets is based on the closure property for finite supports in an hierarchical construction called ‘S-finite support principle (SFSP)’. It claims that ‘for any finite set S of atoms, anything that can be defined in higher-order logic from structures supported by S, by using each time only constructions supported by S, is also supported by S′ [1]. Basically, this S-finite support principle implies a step-by-step construction of the support of a structure by using (at every step) the previously constructed supports of its substructures.

2. Several Definitions of Finite Sets

One hundred years ago, Alfred Tarski introduced various definitions of finiteness [12], paving the way for further research into the understanding and study of finite sets [13]. Here, we present several forms of finiteness (of Tarski type, of Dedekind type, of Mostowski type, etc.) in the framework of finitely supported sets, and provide several relationship results between them. Since the axiom of choice does not hold in the framework of finitely supported sets, we cannot state that the related forms of finite are equivalent [14,15]. To show that the definitions of finiteness are pairwise non-equivalent in the world of finitely supported structures, we provide some atomic sets satisfying a certain definition of finiteness, while they do not satisfy other such definitions.

Let X be a finitely supported set:

• X is called Cantor finite (Ca f) if X corresponds bijectively to a finite ordinal (it can be represented in the form $\{x_1,\dots ,x_n\}$).
• X is called Ascending finite (A f) if for every finitely supported increasing countable chain of finitely supported sets $Y_0\subseteq Y_1\subseteq \dots \subseteq Y_i\subseteq \dots$ with $X\subseteq \cup Y_i$, there exists $j\in \mathbb{N}$ such that $X\subseteq Y_j$;
• X is called Chain finite (C f) if every finitely supported family of finitely supported subsets of X, totally ordered by inclusion, has a maximal element.
• X is called Amorphous (Am) if X does not contain two disjoint, infinite, finitely supported subsets, i.e., any finitely supported subset of X is either finite or it has a finite complement.
• X is called Dedekind finite (D f) if every finitely supported injective function $f:X\to X$ is also surjective.
• X is called Mostowski finite (M f) if every finitely supported, totally ordered subset of X is finite.
• X is called Uniform finite (U f) if X does not contain an infinite uniformly supported subset.
• X is called Tarski I finite (T1 f) if there does not exist a finitely supported bijective function between X and $X\times X$, i.e., if $|X\times X|\ne \left|X\right|$.
• X is called Tarski II finite (T2 f) if there does not exist a finitely supported bijective function between X and $X+X$, i.e., if $|X+X|\ne \left|X\right|$.

Examples of sets satisfying these forms of finiteness are presented in the table.

Remark 1. 

Since the Cantor–Bernstein theorem holds for finitely supported cardinalities, i.e., the relation ≤ is antisymmetric on the family of finitely supported cardinalities (see [10]), it is worth noting that

• If X is a finitely supported set that is not Tarski II finite (i.e. $|X+X|=\left|X\right|$), then $|X+Y|=\left|X\right|$ whenever Y is a finitely supported non-empty set such that there is a finitely supported injection from Y to X. Indeed, it is obvious that $\left|X\right|\le |X+Y|$. Moreover, because there is a finitely supported injection $f:Y\to X$, we can naturally define a finitely supported injection (by $supp\left(f\right)\cup supp\left(X\right)$) $g:Y+X\to X+X$ by taking $g\left(\right(0,y\left)\right)=(0,f(y\left)\right)$ for all $y\in Y$ and $g\left(\right(1,x\left)\right)=(1,x)$ for all $x\in X$. Thus, $|Y+X|\le |X+X|=\left|X\right|$, and so, $|Y+X|=\left|X\right|$.
• If X is a finitely supported set that is not Tarski I finite (i.e. $|X\times X|=\left|X\right|$), then $|X\times Y|=\left|X\right|$ whenever Y is a finitely supported non-empty set such that there is a finitely supported injection from Y to X. Indeed, it is obvious that $\left|X\right|\le |X\times Y|$. Moreover, because there is a finitely supported injection $f:Y\to X$, we can naturally define a finitely supported injection (by $supp\left(f\right)\cup supp\left(X\right)$) $g:Y\times X\to X\times X$ by taking $g(y,x)=\left(f\right(y),x)$. Thus, $|Y\times X|\le |X\times X|=\left|X\right|$, and so, $|Y\times X|=\left|X\right|$.
• If X is a finitely supported set that is not Tarski I finite (i.e. $|X\times X|=\left|X\right|$), then ${\left|Y\right|}^{\left|X\right|}=\left|{\mathcal{P}}_{fs}\left(X\right)\right|$ whenever Y is a finitely supported set with at least two elements such that there is a finitely supported injection from Y to ${\mathcal{P}}_{fs}\left(X\right)$. Indeed, we have $|{\mathcal{P}}_{fs}\left(X\right)|=$  ${\left|\{0,1\}\right|}^{\left|X\right|}\le$  ${\left|Y\right|}^{\left|X\right|}\le$  ${\left|{\mathcal{P}}_{fs}\left(X\right)\right|}^{\left|X\right|}=$  ${\left(\right|\{0,1\}|}^{\left|X\right|}{)}^{\left|X\right|}=$  ${\left|\{0,1\}\right|}^{\left|X\right|·\left|X\right|}=$  ${\left|\{0,1\}\right|}^{|X\times X|}={\left|\{0,1\}\right|}^{\left|X\right|}=$  $\left|{\mathcal{P}}_{fs}\left(X\right)\right|$ and the desired result follows from the antisymmetry of ≤.

3. Properties of the Dedekind Finite Sets

Here, we present some properties of Dedekind finite sets within the framework of finitely supported structures.

Theorem 1. 

Let $X,Y$ be finitely supported sets.

1. 

X is Dedekind finite if and only if there does not exist a finitely supported injective function $f:\mathbb{N}\to X$. Equivalently, X is Dedekind finite if and only if X does not contain a finitely supported, countable infinite subset.

2. 

If there does not exist a finitely supported surjection $g:X\to \mathbb{N}$, then X is Dedekind finite. The reverse implication is not valid because ${\mathcal{P}}_{fin}\left(A\right)$ is Dedekind finite, but the function $h:{\mathcal{P}}_{fin}\left(A\right)\to \mathbb{N}$ defined by $h\left(Z\right)=\left|Z\right|$ for all $Z\in {\mathcal{P}}_{fin}\left(A\right)$ is equivariant and surjective.

3. 

If ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite, then it does not exist a finitely supported surjection $g:X\to \mathbb{N}$, and the reverse implication is also valid.

4. 

If X is not Cantor finite (i.e., X is infinite), then ${\mathcal{P}}_{fs}\left({\mathcal{P}}_{fin}\left(X\right)\right)$ is not Dedekind finite, where ${\mathcal{P}}_{fin}\left(X\right)$ is the family of all finite subsets of X.

5. 

If X is uniform finite, then ${\mathcal{P}}_{fin}\left(X\right)$ is also Uniform finite, and so (since every finitely supported countable set should be uniformly supported) ${\mathcal{P}}_{fin}\left(X\right)$ is Dedekind finite.

6. 

If X is Uniform finite, then the exponent sets $X_{fs}^{A^k}$ and $X_{fs}^{kA}$ are also Uniform finite, and so they are Dedekind finite, whenever $k\in \mathbb{N}$.

7. 

If X is Uniform finite, then the exponent set $X_{fs}^{{\mathcal{P}}_n\left(A\right)}$ is also Uniform finite, and so it is Dedekind finite, whenever $n\in \mathbb{N}$, where ${\mathcal{P}}_n\left(A\right)$ is the set of all n-sized subsets of A. Consequently, ${\mathcal{P}}_{fs}\left({\mathcal{P}}_n\left(A\right)\right)$ is Uniform finite.

8. 

If ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite, then each finitely supported surjective function $f:X\to X$ is injective. The reverse implication is not valid because any finitely supported surjective function $f:{\mathcal{P}}_{fin}\left(A\right)\to {\mathcal{P}}_{fin}\left(A\right)$ is also injective, but ${\mathcal{P}}_{fs}\left({\mathcal{P}}_{fin}\left(A\right)\right)$ is not Dedekind finite.

9. 

If X and Y are Dedekind finite, then the Cartesian product $X\times Y$ and the disjoint union $X+Y$ are Dedekind finite.

10. 

If ${\mathcal{P}}_{fin}\left(X\right)$ is not Dedekind finite, then X contains two infinite, disjoint uniformly supported subsets.

11. 

If ${\mathcal{P}}_{fs}\left(X\right)$ is not Dedekind finite, then X contains two infinite, disjoint finitely supported supported subsets. The reverse implication is not valid. As a consequence, if X is amorphous, then ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite, and so each finitely supported surjective function $f:X\to X$ should be injective.

12. 

If X is not Dedekind finite and C is a finitely supported countable set, then $|X\cup C|=\left|X\right|$

13. 

X is not Dedekind finite if and only if $\left|X\right|+1=\left|X\right|$.

Proof. 

1. Assume that $(X,·)$ is Dedekind finite. By contradiction, suppose that $f:\mathbb{N}\to X$ is finitely supported and injective. We consider $h:X\to X$ by $h\left(x\right)=\left\{\begin{array}{cc}f(n+1),\hfill & \mathrm{if}x=f\left(n\right)\mathrm{for}\mathrm{some}n\in \mathbb{N};\hfill \\ x,\hfill & \mathrm{if}x\notin f\left(\mathbb{N}\right).\hfill \end{array}\right.$. From SFSP, we have that h is supported by $supp\left(X\right)\cup supp\left(\mathbb{N}\right)\cup supp\left(f\right)=supp\left(X\right)\cup supp\left(f\right)$. Since f is injective, we have that h is injective. Moreover, $h\left(X\right)=X\setminus \left\{f\right(0\left)\right\}⊊X$, a contradiction. Conversely, assume that there does not exist a finitely supported injection from $\mathbb{N}$ into X. Let $g:X\to X$ be a finitely supported injection. By contradiction, suppose that $g\left(X\right)⊊X$. Thus, there is $x\in X$ with $x\notin g\left(X\right)$, and so $x\ne g\left(x\right)$. Since g is injective, we have that $g^n\left(x\right)\ne g^m\left(x\right)$ for all $n,m\in \mathbb{N}$. However, due to SFSP, $g^k\left(x\right)$ is supported by $supp\left(g\right)\cup supp\left(x\right)\cup supp\left(X\right)$ for all $k\in \mathbb{N}$, and so the function $f:\mathbb{N}\to X$ defined by $f\left(k\right)=g^k\left(x\right)$ for all $k\in \mathbb{N}$ is finitely supported by $supp\left(g\right)\cup supp\left(x\right)\cup supp\left(X\right)\cup supp\left(\mathbb{N}\right)=supp\left(g\right)\cup supp\left(x\right)\cup supp\left(X\right)$ and injective, a contradiction.

2. Let us suppose, by contradiction, that X is not Dedekind finite. Then, there exists a finitely supported injection $f:\mathbb{N}\to X$. We define the function $g:X\to \mathbb{N}$ by $g\left(x\right)=\left\{\begin{array}{cc}{f}^{-1}\left(x\right),\hfill & \mathrm{if}x\in f\left(\mathbb{N}\right);\hfill \\ n_0,\hfill & \mathrm{if}x\notin f\left(\mathbb{N}\right).\hfill \end{array}\right.$, where $n_0\in \mathbb{N}$ is fixed. According to SFSP, $f\left(\mathbb{N}\right)$ is supported by $supp\left(f\right)\cup supp\left(\mathbb{N}\right)\cup supp\left(X\right)=supp\left(f\right)\cup supp\left(X\right)$ and g is supported by $supp\left(f\right)\cup supp\left(\mathbb{N}\right)\cup supp\left(X\right)\cup supp\left(n_0\right)=supp\left(f\right)\cup supp\left(X\right)\cup supp\left(n_0\right)$. The function h in the theorem’s hypothesis is obviously surjective and equivariant since for $\pi \in S_A$ we have $h(\pi ★Z)=|\pi ★Z|=\left|Z\right|=h\left(Z\right)$ for all $Z\in {\mathcal{P}}_{fin}\left(A\right)$.

3. Assume that ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite. Let us suppose, by contradiction, there is a finitely supported surjection $g:X\to \mathbb{N}$. We define $f:\mathbb{N}\to {\mathcal{P}}_{fs}\left(X\right)$ by $f\left(n\right)=g^{-1}\left(\left\{n\right\}\right)$ for all $n\in \mathbb{N}$ which is supported by $supp\left(g\right)\cup supp\left(X\right)\cup supp\left(\mathbb{N}\right)=supp\left(g\right)\cup supp\left(X\right)$ according to SFSP, and injective, contradicting that ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite. Conversely, assume that there does not exist a finitely supported surjection $g:X\to \mathbb{N}$. Let us suppose, by contradiction that ${\mathcal{P}}_{fs}\left(X\right)$ is not Dedekind finite, that is there exists infinite countably many S-supported subsets of X, namely $Z_1,\dots Z_n,\dots$. We define a sequence ${\left(X_n\right)}_{n\in \mathbb{N}}$ as follows: for $n\in \mathbb{N}$, assume that $X_m$ is defined for any $m<n$ such that the set $\{Z_i\setminus \underset{m<n}{\cup }{X}_m|i\ge n\}$ is infinite. Define $k=min\left\{i\right|i\ge n,Z_i\setminus \underset{m<n}{\cup }{X}_m\ne \varnothing \mathrm{and}(Z\setminus Z_i)\setminus \underset{m<n}{\cup }{X}_m\ne \varnothing \}$. In addition, we define $X_n=\left\{\begin{array}{cc}{Z}_k\setminus \underset{m<n}{\cup }{X}_m,\hfill & \mathrm{if}\{Z_i\setminus (Z_k\cup \underset{m<n}{\cup }{X}_m)|i>k\}\mathrm{is}\mathrm{infinite};\hfill \\ (Z\setminus Z_k)\setminus \underset{m<n}{\cup }{X}_m,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$. According to SFSP, each $X_j$, $j\in \mathbb{N}$ is supported by $S\cup supp\left(X\right)$. Moreover, each $X_j$, $j\in \mathbb{N}$ is non-empty and $X_i\cap X_j=\varnothing$ whenever $i\ne j$. We define $g:X\to \mathbb{N}$ by $g\left(x\right)=\left\{\begin{array}{cc}n,\hfill & \mathrm{if}\mathrm{there}\mathrm{exists}n\mathrm{such}\mathrm{that}x\in X_n;\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$ which is well defined (since all $X_n$ are pairwise-disjoint), is supported by $S\cup supp\left(X\right)$ according to SFSP and surjective (since each $X_n$ is non-empty).

4. Let $X_i=\{Y\in {\mathcal{P}}_{fin}\left(X\right)\left|\right|Y|=i\}$. Since for $\pi \in Fix\left(supp\right(X\left)\right)$ we have $|\pi ★Z|=\left|Z\right|$ for all $Z\in {\mathcal{P}}_{fin}\left(X\right)$, we have that $X_i$ is supported by $supp\left(X\right)$ for all $i\in \mathbb{N}$. Hence, the function $f:\mathbb{N}\to {\mathcal{P}}_{fs}\left({\mathcal{P}}_{fin}\left(X\right)\right)$ by $f\left(k\right)=X_k$ for all $k\in \mathbb{N}$ is supported by $supp\left(X\right)$ and, obviously, it is injective.

5. Let U be an element of ${\mathcal{P}}_{fin}\left(X\right)$. Firstly, we prove $supp\left(U\right)=\underset{x\in U}{\cup }supp\left(x\right)$. Obviously, the finite set of atoms $\underset{x\in U}{\cup }supp\left(x\right)$ is one of the sets supporting U, and so, according to the definition of the support, $supp\left(U\right)\subseteq \underset{x\in U}{\cup }supp\left(x\right)$. Conversely, let $a\in \underset{x\in U}{\cup }supp\left(x\right)$. Thus, there is $x_0\in U$ with $a\in supp\left(x_0\right)$. Let $b\in A$ such that $b\notin supp\left(U\right)$ and $b\notin supp\left(x\right)$ whenever $x\in U$. Such an atom exists since A is infinite, while $supp\left(U\right)$, U and $supp\left(x\right)$ when $x\in U$ are all finite. We claim that $\left(ba\right)·x_0\notin U$. Indeed, let us suppose, by contradiction, that $\left(ba\right)·x_0=u\in U$. Since $a\in supp\left(x_0\right)$, we obtain $b=\left(ba\right)\left(a\right)\in \left(ba\right)\left(supp\left(x_0\right)\right)=supp(\left(ba\right)·x_0)=supp\left(u\right)$, contradicting the choice of b. Hence, $\left(ba\right)★U\ne U$. If we assume that $a\notin supp\left(U\right)$, since $b\notin supp\left(U\right)$, we get $\left(ba\right)\in Fix\left(supp\right(U\left)\right)$, meaning that $\left(ba\right)★U=U$. Thus, $a\in supp\left(U\right)$. We conclude that, for $S\in {\mathcal{P}}_{fin}\left(A\right)$, we have $supp\left(U\right)\subseteq S$ if and only if $\underset{x\in U}{\cup }supp\left(x\right)\subseteq S$. Therefore, $supp\left(U\right)\subseteq S$ if and only if $supp\left(x\right)\subseteq S$ for all $x\in U$. This means that U is supported by S if and only if all the elements of U are supported by S. If there is an infinite uniformly supported subset of ${\mathcal{P}}_{fin}\left(X\right)$, then there should be an infinite uniformly supported subset of X.

6. By induction on n we prove that $X_{fs}^{A^n}$ does not contain an infinite uniformly supported subset whenever X does not contain an infinite uniformly supported subset. Let $n=1$ and assume X does not contain an infinite uniformly supported subset. Let $S\in {\mathcal{P}}_{fin}\left(A\right)$. Let $\mathcal{H}$ be a family of functions from A to X, each of them being supported by S. Let $h\in \mathcal{H}$; for every $a\in S$ and $\pi \in Fix\left(S\right)$, we have $\pi \left(a\right)=a$ and $\pi ·h\left(a\right)=h\left(\pi \right(a\left)\right)=h\left(a\right)$, meaning that $supp\left(h\right(a\left)\right)\subseteq S$. Since there are only finitely many elements in X supported by S, $h\left(a\right)$ can be defined in only finitely many ways, meaning that $h\left(S\right)$ can be defined in finitely many ways. Let $b\in A\setminus S$. From SFSP, we have $supp\left(h\right(b\left)\right)\subseteq S\cup \left\{b\right\}$. Since there are are only finitely many elements in X supported by $S\cup \left\{b\right\}$, $h\left(b\right)$ can be defined in only finitely many ways. Thus, there is a finite family ${\mathcal{H}}^{\prime }=\{h_1,\dots ,h_k\}\subseteq \mathcal{H}$ such that $h\left(b\right)=h_i\left(b\right)$ for some $i\in \{1,\dots ,k\}$. For an arbitrary $c\in A\setminus S$, meaning that $\left(bc\right)\in Fix\left(S\right)$, we get $h\left(c\right)=h\left(\left(bc\right)\left(b\right)\right)=\left(bc\right)·h\left(b\right)=\left(bc\right)·h_i\left(b\right)=h_i\left(\left(bc\right)\left(b\right)\right)=h_i\left(c\right)$, and so ${h|}_{A\setminus S}=h_i{|}_{A\setminus S}$. Since ${\mathcal{H}}^{\prime }$ is finite and $h\left(S\right)$ can be defined only in finitely many ways, then $\mathcal{H}$ should also be finite, and so $X_{fs}^A$ does not contain an infinite uniformly supported subset. Assume that $Y_{fs}^{A^{n-1}}$ does not contain an infinite uniformly supported subset whenever Y does not contain an infinite uniformly supported subset. We have $|Y_{fs}^{A^n}|=|Y_{fs}^{A^{n-1}\times A}{|=|Y|}^{|A^{n-1}|·|A|}={\left(\right|Y|}^{|A^{n-1}|}{)}^{\left|A\right|}=\left|{\left(Y_{fs}^{A^{n-1}}\right)}_{fs}^A\right|$, and so there is a finitely supported bijection between $Y_{fs}^{A^n}$ and ${\left(Y_{fs}^{A^{n-1}}\right)}_{fs}^A$ where the last exponent set does not contain an infinite uniformly supported subset according to the inductive hypothesis ($Y_{fs}^{A^{n-1}}$ does not contain an infinite uniformly supported subset) and to the case $n=1$ with $X=Y_{fs}^{A^{n-1}}$. Furthermore, $|X_{fs}^{nA}|{=\left|X\right|}^{n\left|A\right|}=\left(\right|X^A{\left|\right)}^n$. Thus, there is a finitely supported bijection between $X_{fs}^{nA}$ and the n-times Cartesian product of $X_{fs}^A$ that does not contain an infinite uniformly supported subset.

7. Let us define a function $f:A^k\to {\mathcal{P}}_1\left(A\right)\cup \dots \cup {\mathcal{P}}_k\left(A\right)$ by $f\left((a_1,\dots ,a_k)\right)=\{a\in A|a=a_i\mathrm{for}\mathrm{some}$  $i\in \{1,\dots ,k\}\}$, for all $a_1,\dots ,a_k\in A$. For any $\pi \in S_A$, we have $f(\pi \otimes (a_1,\dots ,a_k))=f\left((\pi \left(a_1\right),\dots ,\pi \left(a_k\right))\right)=\{b\in A|b=\pi \left(a_i\right)\mathrm{for}\mathrm{some}$  $i\in \{1,\dots ,k\}\}=\{\pi \left(a\right)\in A|a=a_i\mathrm{for}\mathrm{some}$  $i\in \{1,\dots ,k\}\}=$  $\pi ★\{a\in A|a=a_i\mathrm{for}\mathrm{some}$  $i\in \{1,\dots ,k\}\}=\pi ★f\left((a_1,\dots ,a_k)\right)$. Therefore, f is equivariant. Clearly, f is surjective, and so, whenever $g,h$ are two different mappings from ${\mathcal{P}}_1\left(A\right)\cup \dots \cup {\mathcal{P}}_k\left(A\right)$ to X supported by a finite set of atoms S, we have that $g\circ f,h\circ f:A^k\to X$ are also different and supported by $S\cup supp\left(f\right)=S$ according to SFSP. Thus, if there are infinitely many functions from ${\mathcal{P}}_1\left(A\right)\cup \dots \cup {\mathcal{P}}_k\left(A\right)$ to X supported by S, there will be infinitely many functions from from $A^k$ to X supported by S. We obtain that the exponent set $X_{fs}^{{\mathcal{P}}_1\left(A\right)\cup \dots \cup {\mathcal{P}}_k\left(A\right)}$ does not contain an infinite uniformly supported subset, from which its subset $X_{fs}^{{\mathcal{P}}_k\left(A\right)}$ does not contain an infinite uniformly supported subset. Finally, ${\mathcal{P}}_{fs}\left({\mathcal{P}}_n\left(A\right)\right)$ does not contain an infinite uniformly supported subset because there is a finitely supported bijection between ${\mathcal{P}}_{fs}\left({\mathcal{P}}_n\left(A\right)\right)$ and ${\{0,1\}}_{fs}^{{\mathcal{P}}_n\left(A\right)}$.

8. Let $h:X\to X$ be a finitely supported surjection. Since h is surjective, according to SFSP the function $g:{\mathcal{P}}_{fs}\left(X\right)\to {\mathcal{P}}_{fs}\left(X\right)$ defined by $g\left(Z\right)=h^{-1}\left(Z\right)$ for all $Z\in {\mathcal{P}}_{fs}\left(X\right)$ is supported by $supp\left(X\right)\cup supp\left(h\right)$ and injective. Since ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite, then g is surjective, and hence h is injective. Let us consider now a finitely supported surjection $f:{\mathcal{P}}_{fin}\left(A\right)\to {\mathcal{P}}_{fin}\left(A\right)$. From SFSP, we have $f\left(Z\right)=supp\left(f\right(Z\left)\right)\subseteq supp\left(f\right)\cup supp\left(Z\right)=supp\left(f\right)\cup Z$ for all $Z\in {\mathcal{P}}_{fin}\left(A\right)$. Let us consider some arbitrary atoms $y_1,\dots ,y_k$ and consider the finite set $Z_{\{y_1,\dots ,y_k\}}=\left\{\{x_1,\dots ,x_n,y_1,\dots ,y_k\}\right|x_1,\dots ,x_n\in supp\left(f\right),n\ge 1\}$∪$\left\{\{y_1,\dots ,y_k\}\right\}$. Let $Y\in Z_{\{y_1,\dots ,y_k\}}$, that is, $Y\setminus supp\left(f\right)=\{y_1,\dots ,y_k\}$. Due to the surjectivity of f, there is $X\in {\mathcal{P}}_{fin}\left(A\right)$ such that $f\left(X\right)=Y$, with X being of form $X=\{z_1,\dots ,z_m,y_{i_1},\dots ,y_{i_l}\}$ with $z_1,\dots ,z_m\in supp\left(f\right)$ and $y_{i_1},\dots ,y_{i_l}\in A\setminus supp\left(f\right)$ or of form $X=\{y_{i_1},\dots ,y_{i_l}\}$ with $y_{i_1},\dots ,y_{i_l}\in A\setminus supp\left(f\right)$ and, in either case, $\{y_1,\dots ,y_k\}\subseteq \{y_{i_1},\dots ,y_{i_l}\}$. We claim that $l=k$. Let us suppose, by contradiction, that there exists $j\in \{1,\dots ,l\}$ with $y_{i_j}\notin \{y_1,\dots ,y_k\}$. Then, $\left(y_{i_j}{y}_1\right)★X=X$, since X is finite and contains both $y_{i_j}$ and $y_1$. Moreover, $y_{i_j},y_1\notin supp\left(f\right)$, meaning that $\left(y_{i_j}{y}_1\right)\in Fix\left(supp\left(f\right)\right)$, from which $f\left(X\right)=f(\left(y_{i_j}{y}_1\right)★X)=\left(y_{i_j}{y}_1\right)★f\left(X\right)$, which is a contradiction because $y_1\in f\left(X\right)$, while $y_{i_j}\notin f\left(X\right)$. Hence, $\{y_1,\dots ,y_k\}=\{y_{i_1},\dots ,y_{i_l}\}$, and so $X\in Z_{\{y_1,\dots ,y_k\}}$. Thus, $Z_{\{y_1,\dots ,y_k\}}\subseteq f\left(Z_{\{y_1,\dots ,y_k\}}\right)$, meaning that $|Z_{\{y_1,\dots ,y_k\}}|\le |f\left(Z_{\{y_1,\dots ,y_k\}}\right)|$. Since $Z_{\{y_1,\dots ,y_k\}}$ is finite, we also have $|f\left(Z_{\{y_1,\dots ,y_k\}}\right)|\le |Z_{\{y_1,\dots ,y_k\}}|$, and so $|Z_{\{y_1,\dots ,y_k\}}|=|f\left(Z_{\{y_1,\dots ,y_k\}}\right)|$ from which $Z_{\{y_1,\dots ,y_k\}}=f\left(Z_{\{y_1,\dots ,y_k\}}\right)$ (*), which is equivalent to saying that ${f|}_{Z_{\{y_1,\dots ,y_k\}}}:Z_{\{y_1,\dots ,y_k\}}\to Z_{\{y_1,\dots ,y_k\}}$ is well-defined and surjective (**). Since $Z_{\{y_1,\dots ,y_k\}}$ is finite, then ${f|}_{Z_{\{y_1,\dots ,y_k\}}}$ should be injective. Now, if $Y\in {\mathcal{P}}_{fin}\left(supp\left(f\right)\right)$, there is $T\in {\mathcal{P}}_{fin}\left(A\right)$ with $f\left(T\right)=Y$. From (**), we have $T\in {\mathcal{P}}_{fin}\left(supp\left(f\right)\right)$, from which ${\mathcal{P}}_{fin}\left(supp\left(f\right)\right)=f\left({\mathcal{P}}_{fin}\left(supp\left(f\right)\right)\right)$ and ${f|}_{{\mathcal{P}}_{fin}\left(supp\left(f\right)\right)}:{\mathcal{P}}_{fin}\left(supp\left(f\right)\right)\to {\mathcal{P}}_{fin}\left(supp\left(f\right)\right)$ is surjective and also injective (***). By combining (*), (**), and (***), since $y_1,\dots ,y_k$ were arbitrarily chosen from $A\setminus supp\left(f\right)$, it follows that f is injective in its entire domain of definition.

9. It follows by direct calculation, using the S-finite support principle (SFSP).

10. According to item 1, there exist a finite set of atoms S and the sets $X_n\in {\mathcal{P}}_{fin}\left(X\right)$ with $supp\left(X_n\right)\subseteq S$ for all $n\in \mathbb{N}$, forming a finitely supported countable subset of ${\mathcal{P}}_{fin}\left(X\right)$. According to item 5, since each $X_n$ is finite, we have $supp\left(X_n\right)=\underset{x\in X_n}{\cup }supp\left(x\right)$, $n\in \mathbb{N}$. Thus, each $X_n$ is uniformly supported by S, and also $\underset{n\in \mathbb{N}}{\cup }{X}_n$ is infinite and uniformly supported. If we define $Z_k=X_k\setminus \underset{i<k}{\cup }{X}_i$, then each $Z_k$ is uniformly supported by S and $\underset{k\in \mathbb{N}}{\cup }{X}_k=\underset{k\in \mathbb{N}}{\cup }{Z}_k$. Since each $Z_k$ is finite, and the union of all $Z_k$ is infinite, there should exist $T\subseteq \mathbb{N}$, T infinite, such that the sets $Z_k$, $k\in T$ are all different. The subsets $U,V$ of X, defined by $U=\{\cup Z_j|j\in T,j\mathrm{is}\mathrm{odd}\}$ and $V=\{\cup Z_i|i\in T,i\mathrm{is}\mathrm{even}\}$ are disjoint, uniformly supported by S, and infinite.

11. As in the proof of item 3, we can define a family ${\left(X_n\right)}_{n\in \mathbb{N}}$ of subsets of X having the properties that they are pairwise disjoint, non-empty, and there is a finite set of atoms S with $supp\left(X_n\right)\subseteq S$ for all $n\in \mathbb{N}$. We consider $U=\{\cup X_j|j\in \mathbb{N},j\mathrm{is}\mathrm{odd}\}$ and $V=\{\cup X_i|i\in \mathbb{N},i\mathrm{is}\mathrm{even}\}$. According to SFSP, U and V are supported by S. Obviously, U and V are infinite and disjoint. Conversely, the set $A+A$ is non-amorphous because $\left\{\right(1,a\left)\right|a\in A\}$ is infinite, equivariant, and its complementary $\left\{\right(0,b\left)\right|b\in A\}$ is also infinite and equivariant. However, $|{\mathcal{P}}_{fs}{(A+A)|=|\{0,1\}|}^{|A+A|}=2^{2\left|A\right|}={\left(2^{\left|A\right|}\right)}^2=|{\mathcal{P}}_f\left(A\right)\times {\mathcal{P}}_{fs}\left(A\right)|$, and so ${\mathcal{P}}_{fs}(A+A)$ is Dedekind finite.

12. There is a finitely supported injection $f:\mathbb{N}\to X$, and so $f:\mathbb{N}\to f\left(\mathbb{N}\right)$ is a finitely supported bijection. We claim that $f\left(\mathbb{N}\right)$ is uniformly supported by $supp\left(f\right)$. Indeed, according to SFPS and to the fact that $(\mathbb{N},\diamond )$ is trivially invariant, we have $\pi ·f\left(n\right)=f(\pi \diamond n)=f\left(n\right)$ for all $n\in \mathbb{N}$ and all $\pi \in Fix\left(supp\right(f\left)\right)$. More generally, we can remark that any finitely supported countable set is uniformly supported. Thus, $\left|f\right(\mathbb{N}\left)\right|=\left|\mathbb{N}\right|$, the bijection between these sets being uniformly supported by $supp\left(f\right)$. We first consider the case when C is represented by a certain B with $X\cap B=⌀$ and B countable (and so B is uniformly supported). We have $X=(X-f(\mathbb{N}\left)\right)\cup f\left(\mathbb{N}\right)$. Thus, $X\cup B=(X-f\left(\mathbb{N}\right))\cup f\left(\mathbb{N}\right)\cup B=(X-f\left(\mathbb{N}\right))\cup \underset{\mathrm{countable}}{\underbrace{\left(f\right(\mathbb{N})\cup B)}}.$ We know that $\exists \rho :f\left(\mathbb{N}\right)\to f\left(\mathbb{N}\right)\cup B$, which is bijective since $f\left(\mathbb{N}\right)$ and $f\left(\mathbb{N}\right)\cup B$ are countably infinite and finitely supported by $supp\left(f\right)\cup supp\left(\mathbb{N}\right)\cup supp\left(B\right)\cup supp\left(X\right)=supp\left(f\right)\cup supp\left(B\right)\cup supp\left(X\right)$ according to SFSP (since all the elements of $f\left(\mathbb{N}\right)$ and $f\left(\mathbb{N}\right)\cup B$ are supported by the same finite set of atoms $supp\left(f\right)\cup supp\left(B\right)\cup supp\left(X\right)$ we have $\pi ·\rho \left(u\right)=\rho \left(u\right)=\rho (\pi ·u)$ for all $u\in f\left(\mathbb{N}\right)$ and all $\pi \in Fix\left(supp\right(f)\cup supp(B)\cup supp(X\left)\right)$). We define the function $g:X\to X\cup B$ by $g\left(x\right)=\left\{\begin{array}{c}\rho \left(x\right),x\in f\left(\mathbb{N}\right)\hfill \\ x,x\in X-f\left(\mathbb{N}\right)\hfill \end{array}\right..$ We have that g is finitely supported by $supp\left(f\right)\cup supp\left(\mathbb{N}\right)\cup supp\left(B\right)\cup supp\left(X\right)\cup supp\left(\rho \right)\subseteq supp\left(f\right)\cup supp\left(B\right)\cup supp\left(X\right)$ according to SFSP. Furthermore, we claim that g is bijective, and so $\left|X\right|=|X\cup B|.$ Indeed, g is obviously surjective. If $x,y\in X$ with $g\left(x\right)=g\left(y\right)$ then either $x,y\in f\left(\mathbb{N}\right)$, or $x,y\in X-f\left(\mathbb{N}\right)$. If we have $x\in f\left(\mathbb{N}\right)$ and $y\in X-f\left(\mathbb{N}\right)$, then we would obtain $\rho \left(x\right)=y\in X-f\left(\mathbb{N}\right)$. However, $\rho \left(x\right)\in f\left(\mathbb{N}\right)\cup B$, a contradiction. Thus, g is injective, since $\rho$ is injective. Since $X\cap B=⌀$, we have $|X\cup B|=|X+B|.$ Thus, $|X+B|=\left|X\right|$. Now, let C be an arbitrary finitely supported countable set, and we have $X\cup C=X\cup (C\setminus X)$, where $C\setminus X$ is obviously countable and $X\cap (C\setminus X)=\varnothing$. Thus, $|X\cup C|=|X\cup (C\setminus X\left)\right|=|X+(C\setminus X\left)\right|=\left|X\right|$.

13. If X is not Dedekind finite, then, according to item 12, we have $\left|X\right|+1=|X\cup \{x_0\left\}\right|=\left|X\right|$, where $x_0$ is an arbitrary element from a finitely supported set such that $x_0\notin X$. Conversely, let $Y=X\cup \left\{x_0\right\}$ where $x_0\notin X$. We have $\left|Y\right|=\left|X\right|+1$. If $\left|X\right|=\left|Y\right|$, then $\exists f:Y\to X$ finitely supported and bijective. The function ${f|}_X:X\to X$ defined by ${f|}_X\left(x\right)=f\left(x\right),\forall x\in X$ is injective and finitely supported by $supp\left(f\right)\cup supp\left(X\right)$ according to SFSP, but $f\left(x_0\right)\in X$ and $f\left(x_0\right){\notin f|}_X\left(X\right)$, because, according to the injectivity of f, we have $f\left(x_0\right)\ne f\left(x\right),\forall x\in X$, and so ${f|}_X$ is not surjective, meaning that X is not Dedekind finite. □

4. Relationships between the Different Definitions of Finite Sets

Let X be a finitely supported set.

Theorem 2. 

 

1. 

If ${\mathcal{P}}_{fin}\left(X\right)$ is Ascending finite, then X is Cantor finite.

2. 

If X is Mostowski finite, then X is Dedekind finite.

3. 

If X is Uniform finite, then X is Mostowski finite.

4. 

${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite if and only if X is Ascending finite.

5. 

If X is Chain finite, then X is Ascending finite.

6. 

If X is Chain finite, then X is Mostowski finite. The reverse implication is not valid because ${\mathcal{P}}_{fin}\left(A\right)$ is Mostowski finite, but Chain infinite.

7. 

If X is Dedekind finite, then X is Tarski II finite. The converse does not hold because $A\cup \mathbb{N}$ is Tarski II finite, but it is not Dedekind finite. However if ${\mathcal{P}}_{fs}\left(X\right)$ is Tarski II finite, then X is Dedekind finite.

8. 

If X is Tarski II finite, then X is Tarski I finite. The converse does not hold because $A\times \mathbb{N}$ is Tarski I finite, but it is not Tarski II finite. However, if ${\mathcal{P}}_{fs}\left(X\right)$ is Tarski I finite, then X is Tarski II finite.

9. 

If ${\mathcal{P}}_{fs}\left(X\right)$ is Tarski II finite, then ${\mathcal{P}}_{fs}\left(X\right)$ is Tarski I finite. The converse does not hold because ${\mathcal{P}}_{fs}(A\cup \mathbb{N})$ is Tarski I finite, but not Tarski II finite.

Proof. 

1. Let us suppose, by contradiction, that X is infinite. Let us consider $Y_n=\{Y\in {\mathcal{P}}_{fin}\left(X\right)\left|\right|Y|\le n\}$. Clearly, $Y_0⊊Y_1⊊\dots$. Let us fix $n\in \mathbb{N}$. For every $\pi \in Fix\left(supp\right(X\left)\right)$, we have $\pi ★Y\in {\mathcal{P}}_{fin}\left(X\right)$, $|\pi ★Y|=\left|Y\right|$ for all $Y\in Y_n$, and so $\pi ★Y\in Y_n$ for all $Y\in Y_n$. Therefore, $supp\left(Y_n\right)\subseteq supp\left(X\right)$ for all $n\in \mathbb{N}$. Moreover, ${\mathcal{P}}_{fin}\left(X\right)=\underset{k\in \mathbb{N}}{\cup }{Y}_k$, but there is no n such that ${\mathcal{P}}_{fin}\left(X\right)\subseteq Y_n$, a contradiction.

2. Assume that X is Dedekind infinite. Then, it contains an infinite uniformly supported subset ${\left(x_n\right)}_{n\in \mathbb{N}}$, i.e., there is a finite set of atoms S such that $supp\left(x_n\right)\subseteq S$ for all $n\in \mathbb{N}$. On ${\left(x_n\right)}_{n\in \mathbb{N}}$, we define the strict total order relation ⊏ by: $x_k⊏x_l$ if and only if $k<l$, which is obviously supported by S according to SFSP.

3. Let $(Y,⊑)$ be a finitely supported, totally ordered subset of X. Let us consider $\pi \in Fix\left(supp\right(⊑)\cup supp(Y\left)\right)$ and let $y\in Y$. Hence, $\pi ·y\in Y$. Since ⊑ is a total order on Y we have either $y⊏\pi ·y$, $y=\pi ·y$ or $\pi ·y⊏y$. However, $\pi$ is a finitary permutation, meaning that it has a finite order, i.e., there is $n\in \mathbb{N}$ such that ${\pi }^n=1_A$. In the case $y⊏\pi ·y$, since $\pi \in Fix\left(supp\right(⊑\left)\right)$ and permutations are bijective, we will have $y⊏\pi ·y⊏\dots ⊏{\pi }^n·y=1_A·y=y$, a contradiction. Similarly, the case $\pi ·y⊏y$ leads to a contradiction, and then $y=\pi ·y$ for all $\pi \in Fix\left(supp\right(⊑)\cup supp(Y\left)\right)$ and $y\in Y$. Therefore, Y is uniformly supported by $supp(⊑)\cup supp\left(Y\right)$, and so it is finite.

4. Assume that ${\mathcal{P}}_{fs}\left(X\right)$ is Dedekind finite. Let us suppose, by contradiction, that X is Ascending infinite. Thus, there is a finitely supported chain of finitely supported sets $Y_0\subseteq Y_1\subseteq \dots \subseteq Y_m\subseteq \dots$ with $X\subseteq \cup Y_m$, but there is no $k\in \mathbb{N}$ such that $X\subseteq Y_k$. Therefore, this chain should contain infinitely many distinct terms of form $Y_j$, otherwise it should be stationary. These terms form a finitely supported countable subset of ${\mathcal{P}}_{fs}\left(X\right)$ (we proved in item 3 that every finitely supported chain of a finitely supported set should be uniformly supported, i.e., all $Y_m$ are supported by the same finite set of atoms), leading to a contradiction. Conversely, let X be Ascending finite and let us suppose, by contradiction, that ${\mathcal{P}}_{fs}\left(X\right)$ is not Dedekind finite, meaning that it contains an infinite uniformly supported subset. As in the proof of Theorem 1(3), we can define a family ${\left(X_n\right)}_{n\in \mathbb{N}}$ of subsets of X having the properties that they are pairwise disjoint, non-empty and there is a finite set of atoms S with $supp\left(X_n\right)\subseteq S$ for all $n\in \mathbb{N}$. Let $Y_i=X_0\cup \dots \cup X_i$ for all $i\in \mathbb{N}$. Clearly, $supp\left(Y_i\right)\subseteq S\cup supp\left(X\right)$, and $Y_0⊊Y_1⊊\dots ⊊X$. Let $Z_k=(X\setminus \underset{i\in \mathbb{N}}{\cup }{Y}_i)\cup Y_k$. We have $X=\underset{k\in \mathbb{N}}{\cup }{Z}_k$. Moreover, $supp\left(Z_k\right)\subseteq S\cup supp\left(X\right)$ for all $k\in \mathbb{N}$ and $Z_0⊊Z_1⊊\dots ⊊X$. However, there does not exist $k\in \mathbb{N}$ such that $X=Z_k$.

5. This is obvious.

6. Suppose that X is Chain finite. Then, every non-empty finitely supported family of finitely supported subsets of X that is totally ordered by inclusion has a maximal element under inclusion. Let $(Y,⊏)$ be a finitely supported, strictly totally ordered subset of X. In order to prove that Y is finite, it is enough to prove that ⊏ and ⊐ are well-ordered, i.e., any finitely supported subset of Y has a greatest and a least element with respect to ⊏ (or, equivalently, a maximal and a minimal element, since ⊏ is total). Let $Z\in {\mathcal{P}}_{fs}\left(Y\right)$. We consider $\downarrow u=\{z\in Z|z⊏u\}$, which is supported by $supp\left(u\right)\cup supp\left(Z\right)\cup supp(⊏)$ for all $u\in Z$. According to SFSP, the set $U=\{\downarrow u|u\in Z\}$ is supported by $supp\left(Z\right)\cup supp(⊏)$. Furthermore, U is totally ordered by the inclusion, and so it has a maximal element, meaning that Z has a maximal element. Dually, $\uparrow u=\{z\in Z|u⊏z\}$ is supported by $supp\left(u\right)\cup supp\left(Z\right)\cup supp(⊏)$ for all $u\in Z$. According to SFSP, the set $V=\{\uparrow u|u\in Z\}$ is supported by $supp\left(Z\right)\cup supp(⊏)$, it is totally ordered by inclusion, and it has a maximal element, meaning that Z has a minimal element.

7. Assume X is Dedekind finite. Let us suppose, by contradiction, that X is not Tarski II infinite. Then, $|X+X|=\left|X\right|$. Let us consider $x_0\notin X$. Then, $|X\cup \{x_0\left\}\right|\le |X+X|=\left|X\right|$ and, obviously, $\left|X\right|\le |X\cup \{x_0\left\}\right|$. Since ≤ is antisymmetric, we get $|X\cup \{x_0\left\}\right|=\left|X\right|$, and so there is a finitely supported bijection $f:X\cup \left\{x_0\right\}\to X$. The function ${g=f|}_X:X\to X$ is injective, finitely supported by $supp\left(f\right)\cup supp\left(X\right)\cup supp\left(x_0\right)$ and $f\left(x_0\right)\in X\setminus g\left(X\right)$, meaning that g is not surjective. Thus, we contradict the assumption that X is Dedekind finite. Now, assume X is Dedekind infinite, and so there is a finitely supported bijection f between X and a finitely supported proper subset of X. We take $x_0\notin X$. The function $g:X\cup \left\{x_0\right\}\to X$ defined by $g\left(x\right)=f\left(x\right)$ for all $x\in X$ and $g\left(x_0\right)=y$ with $y\in X\setminus f\left(X\right)$ is finitely supported by $supp\left(f\right)\cup supp\left(X\right)\cup supp\left(x_0\right)\cup supp\left(y\right)$ and injective, and so $|X\cup \{x_0\left\}\right|\le \left|X\right|$. Since $\left|X\right|\le |X\cup \{x_0\left\}\right|$, we have $\left|X\right|=|X\cup \{x_0\left\}\right|=\left|X\right|+1$. Then, $|{\mathcal{P}}_{fs}\left(X\right)+{\mathcal{P}}_{fs}\left(X\right)|=|{\mathcal{P}}_{fs}\left(X\right)|+|{\mathcal{P}}_{fs}{\left(X\right)|=|\{0,1\}|}^{\left|X\right|}+{\left|\{0,1\}\right|}^{\left|X\right|}=2·2^{\left|X\right|}={\left|\{0,1\}\right|}^{\left|X\right|+1}={\left|\{0,1\}\right|}^{\left|X\right|}=\left|{\mathcal{P}}_{fs}\left(X\right)\right|$, meaning that ${\mathcal{P}}_{fs}\left(X\right)$ is not Tarski II finite.

Clearly, $A\cup \mathbb{N}$ is not Dedekind finite. By contradiction, let us suppose that $|A\cup \mathbb{N}+A\cup \mathbb{N}|=|A\cup \mathbb{N}|$, that is, $\left|\right(A\times \{0,1\})\cup \mathbb{N}|=|A+A+\mathbb{N}|=|A+A+\mathbb{N}+\mathbb{N}|=|A\cup \mathbb{N}+A\cup \mathbb{N}|=|A\cup \mathbb{N}|$. Therefore, we may define a finitely supported injection $f:A\times \{0,1\}\to A\cup \mathbb{N}$. We claim that for a finitely supported injection $g:A\to A\cup \mathbb{N}$, we have that $x\notin supp\left(g\right)$ implies $g\left(x\right)\in A$. Let us suppose, by contradiction, that there is $x\notin supp\left(g\right)$ with $g\left(x\right)\in \mathbb{N}$. Let us consider $y\ne x$ with $y\notin supp\left(g\right)$, and so $\left(xy\right)\in Fix\left(supp\right(g\left)\right)$. Since $\mathbb{N}$ is trivially invariant, we have $g\left(y\right)=g\left(\right(xy\left)\right(x\left)\right)=\left(xy\right)\diamond g\left(x\right)=g\left(x\right)$, contradicting the injectivity of g. We define the functions $g_1,g_2:A\to A\cup \mathbb{N}$ by $g_1\left(x\right)=f(x,0)$ for all $x\in X$ and $g_2\left(x\right)=f(x,1)$ for all $x\in X$, which are finitely supported by $supp\left(f\right)$ and injective. Hence, $f(A\times \left\{0\right\})=g_1\left(A\right)$ and $f(A\times \left\{1\right\})=g_2\left(A\right)$ contain only finitely many elements from $\mathbb{N}$. Thus, $f(A\times \{0\left\}\right)$ contains an infinite finitely supported subset B of atoms and $f(A\times \{1\left\}\right)$ contains an infinite finitely supported subset of atoms C, with B and C disjoint due to the injectivity of f, contradicting the fact that A is amorphous.

8. Assume that $\left|X\right|\ge 2$, otherwise the proof is trivial and X is Tarski II finite. Let us suppose, by contradiction, that X is not Tarski I finite, i.e., $|X\times X|=\left|X\right|$. We obviously have $\left|X\right|\le |X+X|$, and $|X+X|=\left|\right\{0,1\}\times X|\le |X\times X|=\left|X\right|$. Since ≤ is antisymmetric, we get $|X+X|=\left|X\right|$, i.e., X is not Tarski II finite. However, if we assume that Y is not Tarski II finite, i.e., $|Y+Y|=\left|Y\right|$, then $|{\mathcal{P}}_{fs}\left(Y\right)\times {\mathcal{P}}_{fs}{\left(Y\right)|=|\{0,1\}|}^{\left|Y\right|}·{\left|\{0,1\}\right|}^{\left|Y\right|}={\left|\{0,1\}\right|}^{\left|Y\right|+\left|Y\right|}={\left|\{0,1\}\right|}^{|Y+Y|}={\left|\{0,1\}\right|}^{\left|Y\right|}=\left|{\mathcal{P}}_{fs}\left(Y\right)\right|$, which means ${\mathcal{P}}_{fs}\left(Y\right)$ is not Tarski I finite.

In order to complete the proof of this item, we claim that $|A\times \mathbb{N}\times A\times \mathbb{N}|\ne |A\times \mathbb{N}|$. Let us suppose, by contradiction, that $|A\times \mathbb{N}\times A\times \mathbb{N}|=|A\times \mathbb{N}|$, i.e., $|A\times A\times \mathbb{N}|=|A\times \mathbb{N}|$, since $\mathbb{N}\times \mathbb{N}$ is countable, meaning that $|A\times A|\le |A\times \mathbb{N}|$ and $|A\times A|{\le }^{*}|A\times \mathbb{N}|$. Therefore, there is a finitely supported surjective function $f:A\times \mathbb{N}\to A\times A$. Let $x,y,z\in A\setminus supp\left(f\right)$. There is $(a,n)\in A\times \mathbb{N}$ such that $f(a,n)=(x,y)$. However, $\left(xy\right)\in Fix\left(supp\right(f\left)\right)$ and so $f\left(\right(xy\left)\right(a),n)=f\left(\right(xy\left)\right(a),(xy)\diamond n)=\left(xy\right)f(a,n)=\left(xy\right)(x,y)=\left(\right(xy\left)\right(x),(xy\left)\right(y)=(y,x)$. Hence, we cannot have $x\ne a$ and $y\ne a$; otherwise $\left(xy\right)\left(a\right)=a$ and $f(a,n)=(y,x)$ contradicting the functionality of f. Assume $a=x$ (the other case is analogue). Then, $f(x,n)=(x,y)$ and $f(y,n)=f\left(\right(xy\left)\right(x),(xy)\diamond n)=\left(xy\right)f(x,n)=\left(xy\right)(x,y)=(y,x)$. Similarly, since $\left(xz\right),\left(yz\right)\in Fix\left(supp\right(f\left)\right)$ we have $f(z,n)=f\left(\right(xz\left)\right(x),(xz)\diamond n)=\left(xz\right)f(x,n)=\left(xz\right)(x,y)=(z,y)$ and $f(y,n)=f\left(\right(zy\left)\right(z),(zy)\diamond n)=\left(zy\right)f(z,n)=\left(zy\right)(z,y)=(y,z)$. However, $f(y,n)=(y,x)$, a contradiction, meaning that $A\times \mathbb{N}$ is Tarski I finite. Furthermore, $\left|\right(A\times \mathbb{N})+(A\times \mathbb{N}\left)\right|=|A\times \mathbb{N}|+|A\times \mathbb{N}|=\left|A\right|·\left|\mathbb{N}\right|+\left|A\right|·\left|\mathbb{N}\right|=\left|A\right|·\left(\right|\mathbb{N}|+|\mathbb{N}\left|\right)=\left|A\right|·\left|\mathbb{N}\right|=|A\times \mathbb{N}|$, meaning that $A\times \mathbb{N}$ is not Tarski II finite.

9. The direct implication results from item 8. Since $A\cup \mathbb{N}$ is not Dedekind finite, we have that ${\mathcal{P}}_{fs}(A\cup \mathbb{N})$ is not Tarski II finite. Let us suppose, by contradiction, that ${\mathcal{P}}_{fs}(A\cup \mathbb{N})$ is not Tarski I finite, i.e., $|{\mathcal{P}}_{fs}(A\cup \mathbb{N})\times {\mathcal{P}}_{fs}(A\cup \mathbb{N})|=|{\mathcal{P}}_{fs}(A\cup \mathbb{N})|$. Then, $|{\mathcal{P}}_{fs}\left(A\right)\times {\mathcal{P}}_{fs}\left(\mathbb{N}\right)\left)\right|={\left|\{0,1\}\right|}^{\left|A\right|}·{\left|\{0,1\}\right|}^{\left|\mathbb{N}\right|}={\left|\{0,1\}\right|}^{\left|A\right|+\left|\mathbb{N}\right|}={\left|\{0,1\}\right|}^{|A\cup \mathbb{N}|}=|{\mathcal{P}}_{fs}(A\cup \mathbb{N})|=$  $|{\mathcal{P}}_{fs}(A\cup \mathbb{N})\times {\mathcal{P}}_{fs}{(A\cup \mathbb{N})|=|\{0,1\}|}^{|A\cup \mathbb{N}|}·{\left|\{0,1\}\right|}^{|A\cup \mathbb{N}|}={\left|\{0,1\}\right|}^{\left|A\right|+\left|\mathbb{N}\right|+\left|A\right|+\left|\mathbb{N}\right|}=$  ${\left|\{0,1\}\right|}^{\left|A\right|+\left|A\right|+\left|\mathbb{N}\right|}=\left|{\mathcal{P}}_{fs}(A+A+\mathbb{N})\right|$, and so there is a finitely supported injection from ${\mathcal{P}}_{fs}(A+A)$ into ${\mathcal{P}}_{fs}\left(A\right)\times {\mathcal{P}}_{fs}\left(\mathbb{N}\right)$. However, $|{\mathcal{P}}_{fs}{(A+A)|=|\{0,1\}|}^{\left|A\right|+\left|A\right|}={\left|\{0,1\}\right|}^{\left|A\right|}·{\left|\{0,1\}\right|}^{\left|A\right|}|=|{\mathcal{P}}_{fs}\left(A\right)\times {\mathcal{P}}_{fs}\left(A\right)|$, meaning that there is a finitely supported injection from $A\times A$ into ${\mathcal{P}}_{fs}\left(A\right)\times {\mathcal{P}}_{fs}\left(\mathbb{N}\right)$, and hence there is a finitely supported surjection $\phi :{\mathcal{P}}_{fs}\left(A\right)\times {\mathcal{P}}_{fs}\left(\mathbb{N}\right)\to A\times A$. Let $x,y\in A\setminus supp\left(\phi \right)$ with $x\ne y$, and so $\left(xy\right)\in Fix\left(supp\right(\phi \left)\right)$. There exists $(X,N)\in {\mathcal{P}}_{fs}\left(A\right)\times {\mathcal{P}}_{fs}\left(\mathbb{N}\right)$ with $\phi (X,N)=(x,y)$. Since $\mathbb{N}$ is trivially invariant, we have $\phi \left(\right(xy)★X,N)=$  $\phi \left(\right(xy)★X,(xy)★N)=\phi \left(\right(xy)\otimes (X,N\left)\right)=\left(xy\right)\otimes \phi (X,N)=\left(xy\right)\otimes (x,y)=$  $\left(\right(xy\left)\right(x),(xy\left)\right(y\left)\right)=(y,x)$. Since $\phi$ is a function, we get $\left(xy\right)★X\ne X$. If both $x,y\in supp\left(X\right)$, then we claim that $\left(xy\right)★X=X$. Indeed, X is either finite or its complement is finite. If X is finite, we have $supp\left(X\right)=X$, and $x,y\in X$. Thus, $\left(xy\right)★X=X$ since x and y are interchanged in the finite set X, but there do not appear new elements in X under the effect of $\left(xy\right)$ meaning that the whole set X remains unchanged under the action of $\left(xy\right)$ with respect to ★. If the complement of X is finite, then $supp\left(X\right)=A\setminus X$, and $x,y\in A\setminus X$, i.e., $x,y\notin X$, and so $x,y\ne a$ for all $a\in X$, meaning that $\left(xy\right)\left(a\right)=a$ for all $a\in X$; we also get $\left(xy\right)★X=X$. Therefore, at least one of $x,y$ is outside $supp\left(\phi \right)$. If $y\notin supp\left(X\right)$, we choose $z\ne x,y$, $z\notin supp\left(\phi \right)$, $z\notin supp\left(X\right)$, and we have $\left(yz\right)\in Fix\left(supp\right(X\left)\right)$, and $\left(yz\right)★X=X$. Furthermore, $\left(yz\right)\in Fix\left(supp\right(\phi \left)\right)$, and we obtain $(x,y)=\phi (X,N)=\phi \left(\right(yz)★X,N)=$  $\phi \left(\right(yz)★X,(yz)★N)=\phi \left(\right(yz)\otimes (X,N\left)\right)=$  $\left(yz\right)\otimes \phi (X,N)$  $=\left(yz\right)\otimes (x,y)=$  $\left(\right(yz\left)\right(x),(yz\left)\right(y\left)\right)=$  $(x,z)$, contradicting the functionality of $\phi$. □

5. Conclusions

In

Table 1. Examples of sets satisfying various forms of finiteness.

The Set/Its Finiteness	T1 f	T2 f	D f	M f	U f	A f	C f	Am	Ca f
A	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No
$nA$, $n>1$	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No	No
$A^n$, $n>1$	Yes	Yes	Yes	Yes	Yes	Yes	Yes	No	No
${\mathcal{P}}_{fin}\left(A^n\right)$, $n>0$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fin}\left(nA\right)$, $n>0$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}\left(A^n\right)$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}\left(nA\right)$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fin}\left({\mathcal{P}}_{fs}\left(A^n\right)\right)$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fin}\left({\mathcal{P}}_{fs}\left(nA\right)\right)$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
$A_{fs}^{A^n}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
$A_{fs}^{nA}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}\left({\mathcal{P}}_n\left(A\right)\right)$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}{\left(A^k\right)}_{fs}^{{\mathcal{P}}_n\left(A\right)}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}{\left(kA\right)}_{fs}^{{\mathcal{P}}_n\left(A\right)}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}{\left(A\right)}_{fs}^{A^n}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\mathcal{P}}_{fs}{\left(A\right)}_{fs}^{nA}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
$X_{fs}^{A^n}$, $X_{fs}^{nA}$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\left({\mathcal{P}}_{fs}\left(A^n\right)\right)}_{fs}^Y$	Yes	Yes	Yes	Yes	Yes	No	No	No	No
${\left({\mathcal{P}}_{fs}\left(nA\right)\right)}_{fs}^Y$,	Yes	Yes	Yes	Yes	Yes	No	No	No	No
$A\cup \mathbb{N}$	Yes	Yes	No	No	No	No	No	No	No
${\mathcal{P}}_{fs}(A\cup \mathbb{N})$	Yes	No	No	No	No	No	No	No	No
$A\times \mathbb{N}$	Yes	No	No	No	No	No	No	No	No
${\mathcal{P}}_{fs}\left({\mathcal{P}}_{fs}\left(A\right)\right)$	?	No	No	No	No	No	No	No	No
${\mathcal{P}}_{fs}\left({\mathcal{P}}_{fs}\left({\mathcal{P}}_{fs}\left(A\right)\right)\right)$	No	No	No	No	No	No	No	No	No
$A_{fs}^{\mathbb{N}}$ and ${\mathbb{N}}_{fs}^A$	No	No	No	No	No	No	No	No	No

, we provide examples of finitely supported sets satisfying various forms of finiteness, while they do not satisfy others, assuring the independence of these forms of finiteness. We assume that X is a finitely supported set having at least two elements and it does not contain an infinite uniformly supported subset (i.e., X is Uniform finite), and that Y is a finitely supported set having at least two elements and ${\mathcal{P}}_{fs}\left(Y\right)$ does not contain an infinite uniformly supported subset (i.e., ${\mathcal{P}}_{fs}\left(Y\right)$ is Uniform finite).

Additionally, we can prove several implications between various forms of finiteness. Let X be a finitely supported set. Then,

• X Ca f ⇒X C f ⇒X M f ⇒X D f ⇒X T2 f ⇒X T1 f;
• X Ca f ⇒X U f ⇒X M f ⇒X D f ⇒X T2 f ⇒X T1 f;
• X Ca f ⇒X am ⇒X A f ⇔${\mathcal{P}}_{fs}\left(X\right)$ D f ⇒X D f ⇒X T2 f ⇒X T1 f;
• X Ca f ⇒X C f ⇒X A f.