Let $\mathcal P$ be the set of finite subsets of $\mathbb Z_{\geq 0}$ , each of them contains $0$. We say that $A \in \mathcal P$ is indecomposable if it is not $B+C$ (the sum set of $B,C$) with $B,C\in \mathcal P$ and $B,C\neq \{0\}$.
It is easy to see which small cardinality sets are indecomposable. If $|A|=2$, then it is indecomposable. If $A=\{0, x, y\}$ with $0<x<y$, A is indecomposable iff $y\neq 2x$. If $A=\{0<x<y<z\}$, A is indecomposable iff $z\neq x+y$.
My questions are:
Questions: have these sets been studied before? Are there nice characterizations? Do they have interesting counts, for instance, the number of indecomposable sets whose largest element is $n$?
Best Answer
There are three questions in the OP, and I'll try to address each of them in as comprehensive a way as I can. I'll be glad to add in further details (and references) if requested.
◇ Preliminaries on free monoids.
We write $\mathscr F(X)$ for the free monoid on an alphabet $X$. We refer to the elements of $\mathscr F(X)$ as $X$-words (or simply words), and to the identity of $\mathscr F(X)$, denoted by $\varepsilon_X$, as the empty word. We use the symbol $\ast$ for the operation of $\mathscr F(X)$, and assume that $\mathscr F(X)$ has been realized in such a way that $X \subseteq \mathscr F(X)$. In so doing, a non-empty $X$-word $\mathfrak z$ can be uniquely factored as $z_1 \ast \cdots \ast z_n$ for some $z_1, \ldots, z_n \in X$, where $n$ is a positive integer called the length of $\mathfrak z$ and denoted by $\|\mathfrak z\|$. Besides, we set $\|\varepsilon_X\| := 0$.
◇ Pills of factorization theory.
Let $H$ be a multiplicatively written monoid; in particular, one may want to think about the case where $H$ is the multiplicative monoid of a (unital) ring, or the multiplicative monoid of the non-zero elements of a domain (note that $H$ need not be commutative).
An atom of $H$ is a non-unit $a \in H$ with the property that $a \ne xy$ for all non-units $x, y \in H$ (see Note (0)). Atoms are basically a monoid-theoretic abstraction of what (most) people in commutative algebra keep calling irreducible elements; the origins of the term are commonly traced back to the early work of P.M. Cohn on unique factorization in non-commutative domains (see Note (1)).
Let $\mathscr A(H)$ be the set of atoms of $H$. An atomic factorization of an element $x \in H$ is a word $\mathfrak a \in \mathscr F(\mathscr A(H))$ such that $\pi_H(\mathfrak a) = x$, where $\pi_H$ is the unique monoid homomorphism $\mathscr F(H) \to H$ such that $\pi_H(z) = z$ for every $z \in H$ (see Note (2)); we write $\mathsf L_H(x)$ for the set of (atomic) lengths of $x$, that is, the set of all integers $k \ge 0$ for which there is an atomic factorization $\mathfrak a$ of $x$ with $\|\mathfrak a\| = k$. We refer to $$ \mathscr L(H) := \{\mathsf L_H(x): x \in H\} \setminus \{\emptyset\} $$ as the system of sets of (atomic) lengths of $H$; this is probably the most fundamental invariant commonly used in factorization theory to describe the departure of $H$ from a condition of "factoriality".
◇ Power monoids.
Given a monoid $H$, the set of all subsets of $H$ is itself a monoid, herein denoted by $\mathcal P(H)$ and called the full power monoid of $H$, when endowed with the binary operation of setwise multiplication $$ (X, Y) \mapsto \{xy: x \in X,\, y \in Y\}. $$ Apart from trivial cases, the structure of $\mathcal P(H)$ is rather complicated, and a first step towards understanding it better is to consider submonoids of this object that are in some sense tamer, including the reduced power monoid $$ \mathcal P_{{\rm fin}, 1}(H) := \{X \in \mathcal P(H): 1_H \in X \text{ and } |X| < \infty\}. $$ In a way, "power monoids" have been around for a while; after all, they are the "natural framework" beyond some of the main questions of interest in arithmetic combinatorics (see Seva's answer for some references). However, it's only very recently that, to the best of my knowledge, power monoids have been explicitly considered as (algebraic) structures in their own right; in particular, this is definitely true if we restrict attention to the study of their properties from the point of view of factorization theory.
The OP is about the special case where $H$ is the additive monoid $(\mathbf N, +)$ of the non-negative integers; in fact, what the OP is calling an indecomposable subset of $\mathbf N$ is but an atom of the restricted power monoid of $(\mathbf N, +)$, which I'll denote herein by $\mathcal P_{{\rm fin},0}(\mathbf N)$ and write additively (in contrast with the previous section). One open problem in this area is the conjecture formulated in Sect. 5 of
The conjecture states that every non-empty finite subset $L$ of $\mathbf N_{\ge 2}$ belongs to the system of sets of lengths of $\mathcal P_{{\rm fin},0}(\mathbf N)$; that is, there exists a finite subset $X$ of $\mathbf N$ with $0 \in X$ such that $k \in L$ if and only if $X = A_1 + \cdots + A_k$ for some atoms $A_1, \ldots, A_k$ of $\mathcal P_{{\rm fin},0}(\mathbf N)$. Not much is known about this problem, apart from the fact that the conjecture is true when $L$ is either the (discrete) interval $[\![2, n ]\!]$, the singleton $\{n\}$, or the two-element set $\{2, n+1\}$, where $n$ is an arbitrary integer $\ge 2$. Related questions are discussed in
where, in particular, one can read a lot more about minimal atomic factorizations in the restricted power monoid of a finite group (see Note (3)).
◇ Questions (freely quoted from the OP).
Q1: Have indecomposable subsets of the non-negative integers been studied before?
All sorts of questions about atomic factorizations require, in the first place, an adequate understanding of the atoms of the monoid under consideration. So I'd say that the answer to this question is rather yes than no.
Q2: Are there nice characterizations of the indecomposable subsets of the non-negative integers?
I'm afraid this question is hopeless, at least if taken literally. In a sense (see the next question), there are way too many atoms in $\mathcal P_{{\rm fin}, 0}(\mathbf N)$ for any sensible characterization to be feasible. However, it's possible to construct (infinite) families of "well-structured atoms", which can often be used to prove a number of cute little things; the two papers cited in the section "Power monoids" discuss some of these constructions.
Q3: Is there anything in the know about the number of indecomposable subsets of the non-negative integers whose maximum is $\leq n$?
Given $n \in \mathbf N$, let $\alpha(n)$ be the number of atoms of $\mathcal P_{{\rm fin}, 0}(\mathbf N)$ in the interval $[\![0, n ]\!]$. Qinghai Zhong and I have a manuscript (resting in peace in our drawers for a couple of years or so) where we prove a lower bound on $\alpha(n)$ that, in particular, implies that $\alpha(n)/2^n \to 1$ as $n \to \infty$. This is a "density result", suggesting that most elements of $\mathcal P_{{\rm fin}, 0}(\mathbf N)$ are in fact atoms (note that $2^n$ is the total number of subsets of $[\![0, n ]\!]$ containing $0$).
◇ Notes.
(0) A unit of $H$ is an element $u \in H$ with $uv = vu = 1_H$ for some $v \in H$, where $1_H$ is the identity of $H$; and a non-unit is, unsurprisingly, an element that is not a unit.
(1) Out of the "comfort zone" of integral domains (and, more generally, of commutative "nearly cancellative" monoids), it is useful and, to some extent, even necessary to distinguish atoms from the related notion of "irreducible", where we take an irreducible of $H$ to be a non-unit element $a \in H$ such that, if $a = xy$ for some $x, y \in H$, then either $a$ and $x$ generate the same principal $s$-ideal (i.e., $HaH = HxH$), or so do $a$ and $y$. To my knowledge, the significance of this distinction was first realized by D.D. Anderson and S. Valdes-Leon in
However, Anderson and Valdes-Leon's paper (as most of the papers in this business) is entirely about the case where $H$ is a commutative monoid (more precisely, the multiplicative monoid of a commutative ring). For the non-commutative part of the story and beyond, I can only address the interested reader to a recent preprint of mine on monoids and preorders (arXiv link).
(2) In this context, $\pi_H$ is usually referred to as the factorization homomorphism of $H$.
(3) Power monoids are "highly non-cancellative" monoids, so much so that the classical theory of factorization breaks down dramatically when applied to them (if, for instance, $H$ is a finite monoid, then $XH = HX = H$ for every non-empty $X \subseteq H$); this "conceptual breakdown" doesn't even spare the notion of atomic factorization defined in the section "Pills of factorization theory", which has eventually led to the introduction of the refined notion of minimal atomic factorization in the PJM paper I'm referring to. The good news is that $\mathcal P_{{\rm fin}, 0}(\mathbf N)$ is commutative and "nearly cancellative", which implies that, in this particular case, atomic factorizations and minimal atomic factorizations are one and the same thing.