3
$\begingroup$

I've looked at a few Q/A and not found a satisfactory answer to even the basic question. The extended question is:

Given a set of sets, or a set of tuples:

  • Is there a standard way of denoting whether an object is an element of one of the inner sets/tuples?
  • Is there a standard way of identifying these objects?
  • Is there a standard way of denoting the multiplicity across inner sets/tuples?

By way of example, we'll take the set of primitive Pythagorean triples as tuples:

$$S := \{(a,b,c) \in \mathbb{N}^3 \mid [a^2 + b^2 = c^2] \land [\gcd (a,b,c) = 1] \land [a < b < c] \}$$

$$S = \{(3,4,5), (5,12,13), (8, 15, 17), \cdots\}$$

Obviously $5 \not \in S$, because every element of $S$ is a tuple. But $5$ appears in two of the tuples, as does every $4k+1$ prime, and other integers appear more than twice. Is it correct to write, for instance, "$5 \in \in S$" and "$6 \not \in \in S$"? If not, is there a standard correct method?

I think that if we have indexed/ordered sets and tuples, we can identify individual elements with typical notation. For instance, if we use $c$ to order the tuples, we could say that $s_{1,3} = s_{2,1} = 5$. But how does one specify the ordering of the tuples mathematically? Or is a well-ordered set of tuples a mathematical impossibility?

And is there any notation for the multiplicity of an object across the inner sets/tuples of the set? One can certainly imagine uses for it, but I don't think I've ever seen it notated. Obviously, one can calculate it using a computer if need be, but is there something like $\text{mult}(5) = 2$ that is commonly used, or even correctly used, for this?

(I considered adding "soft-question" as a tag but uncertain whether it'd be correct here.)

$\endgroup$
1
  • $\begingroup$ If $S$ was a set of sets, you could say $6 \in \bigcup_{A \in S} A$. I personally wouldn't use $\in$ for tuples - if I think of the point $(3,4) \in \mathbb{R}^2$, I wouldn't say that 3 is a member of that point. In this case, you could probably get away with replacing your tuples with sets, if you wanted - take $S:=\{\{a,b,c\}:a.b.c \in \mathbb{N},a^2+b^2=c^2,\mathrm{gcd}(a,b,c)=1\}$. If you want to keep $S$ as a set of tuples, maybe ask a separate question about how to represent the "set of elements of a tuple"? I'd be curious as well. $\endgroup$
    – 1Rock
    Aug 20 at 1:49
2
$\begingroup$

In set theory, given a set $S$ and a set $x$ which belongs to an element of $S$, you can use the following way to represent the relation of $x$ and $S$:

\begin{equation*} x\in\bigcup S=\bigcup_{X\in S} X, \end{equation*} where $\bigcup S$ is a collection of all the elements of all the elements of $S$. Formally, $\bigcup$ is a generalized union which is defined as

$$\bigcup S:=\{x\mid x\in X\text{ for some } X\in S\}.$$

For example, if $x=0$ and $S=\{\{0,1\},\{1,2,3\}\}$, then $\bigcup S=\{0,1\}\cup\{1,2,3\}=\{0,1,2,3\}$, and hence $x=0\in \{0,1\}$ and $x=0\in\bigcup S$.


But for your question, note that it's a little complicated because the definition of tuples. In set theory, we define 2-tuples as

$$(a,b):=\{\{a\},\{a,b\}\},$$

and 3-tuples as

\begin{align*} (a,b,c):=&((a,b),c)\\ =&\{\{(a,b)\},\{(a,b),c\}\}\\ =&\{\{\{\{a\},\{a,b\}\}\},\{\{\{a\},\{a,b\}\},c\}\}. \end{align*}

and $n$-tuples ($n\geq 2$) as

\begin{align*} (a_0,\cdots,a_{n-1}):=((a_0,\cdots,a_{n-2}),a_{n-1}). \end{align*}

So when using $\bigcup$ notations to show the belonging relations you talked about, be careful of the numbers of $\bigcup$ to be used. For example, if $S=\{(a_0,a_1)\mid \cdots\}$ then

\begin{align*} x=a_0\in &\bigcup(\bigcup S)=\bigcup\textstyle^2~S,\\ x=a_1\in &\bigcup(\bigcup S)=\bigcup\textstyle^2~S, \end{align*}

and so

\begin{align*} x=a_i\in &\bigcup(\bigcup S)=\bigcup\textstyle^2~S; \end{align*}

if $S=\{(a_0,a_1,a_2)\mid\cdots\}$, then

\begin{align*} x=a_2\in &\bigcup(\bigcup S)=\bigcup\textstyle^2~S,\\ x=a_1\in &\bigcup(\bigcup(\bigcup S))=\bigcup\textstyle^3~S,\\ x=a_0\in &\bigcup(\bigcup(\bigcup S))=\bigcup\textstyle^3~S,\\ \end{align*}

and so

\begin{align*} x=a_i\in\bigcup_{2\leq j\leq 3}(\bigcup\textstyle^j S). \end{align*}

And more generally, for $S$ whose elements are $n$-tuples such as $(a_0,\cdots,a_{n-1})$ you can show that

\begin{align*} x=a_i\in\bigcup_{2\leq j\leq n}(\bigcup\textstyle^j S). \end{align*}


If you don't want to count the numbers of $\bigcup$, maybe the following way is better: suppose $x$ is related to some element of $S$, saying $x\in Y$ and $\phi(Y)\in S$ (for which given $S$ both the $Y$ and $\phi(Y)$ are usually easy to be found), then

$$x\in \bigcup\{Y\mid \phi(Y)\in S\}=\bigcup_{\phi(Y)\in S}Y.$$

Note that @1Rock 's $5 \in \bigcup_{(a,b,c) \in S} \{a,b,c\}$ is a practice over this idea where $x=5$, $Y=\{a,b,c\}$ and $\phi(Y)=(a,b,c)$, and that in particular when $Y=\phi(Y)$ we have

\begin{align*} x\in \bigcup\{Y\mid \phi(Y)\in S\}&=\bigcup_{\phi(Y)\in S}Y\\ &=\bigcup_{Y\in S}Y=\bigcup S. \end{align*}

$\endgroup$
8
  • $\begingroup$ @1Rock See the ending of the post which maybe a uniform way to your question. $\endgroup$
    – M. Logic
    Aug 20 at 13:29
  • $\begingroup$ More commonly, once we have defined ordered pairs (either as you do, with the Kuratowski definition, or any other definition that accomplishes it), we define general $X$-tuples as functions $f\colon X\to Y$, where $Y$ is a set that contains the entries. $\endgroup$ Aug 21 at 3:49
  • $\begingroup$ @Arturo Magidin In fact, 2-tuples, i.e., ordered pairs, must be defined in Kuratowski's way only, and $n$-tuples ($n>2$) could be defined either in terms of 2-tuples or as functions $f$ with domain $n$. $\endgroup$
    – M. Logic
    Aug 21 at 3:54
  • $\begingroup$ There are many possible ways of defining ordered pairs in a way that preserves the "defining characteristic" (that $(a,b)=(x,y)$ if and only if $a=x$ and $b=y$). Kuratowski's definition is the most common, but it is not the only way of doing it, so saying that ordered pairs "must" be defined that way is incorrect. For instance, in the presence of Regularity you can define $(x,y) = \{x,\{x,y\}\}$. Wiener defined it as $(x,y)=\{\{\{a\},\emptyset\},\{\{b\}\}\}$, which also satisfies the defining characteristic. There is no "must", but of course you define ordered pairs first, somehow. $\endgroup$ Aug 21 at 4:09
  • 1
    $\begingroup$ @Eric Snyder From a more general view, families of sets (equivalent to function) are generalizations of sequences, while sequences are (not necessarily strict) generalizations of tuples. For ordered set, for example, a partial order $<$, although its' elements are ordered pairs, usually it's not necessary to use the definition of ordered pairs (i.e., $2$ tuples). $\endgroup$
    – M. Logic
    Sep 1 at 1:02
2
$\begingroup$

From a vocabulary perspective, you can distinguish the two levels by describing higher levels as a family, see the Wikipedia article on family of sets. This terminology isn't unambiguous though, the family might be a proper class or might be a multiset depending on the context.

If $\mathcal{F}$ is your family of sets, then you can name the set of all elements of members of $\mathcal{F}$, for example $V = \cup \mathcal{F}$.

In this setting a "second-order element" of $\mathcal{F}$ would just be an element of $V$.

I don't know of a way of defining the number of sets that contain a specific element that you can just use without explaining it, but here's one that's reasonably succinct.

$$ \mu(x) = \left|\left\{ v : x \in v \land v \in \mathcal{F} \right\}\right| $$

And, if you want $\mathcal{F}$ to be an indexed family of sets, indexed by the index set $I$, you can do the following.

$$ \mu(x) = \left|\left\{ i : i \in I \land x \in \mathcal{F}_i \right\}\right| $$

$\endgroup$
1
$\begingroup$

You can order your tuples by what is called a lexographical order - sort them first by the smallest element, then by the next-smallest element, and so on. Then you can write $5 \in \{s_{ij}:i\in \mathbb{N},j\in \{1,2,3\}\}$ and $|\{(i,j) \in \mathbb{N} \times \{1,2,3\} : s_{ij}=5\}|=2$.

If $S$ was a set of sets, you could say $6 \in \bigcup_{A \in S} A$. I personally wouldn't use $\in$ for tuples - if I think of the point $(3,4) \in \mathbb{R}^2$, I wouldn't say that 3 is a member of that point. In this case, you could probably get away with replacing your tuples with sets, if you wanted - take $$ S:=\{\{a,b,c\}:a,b,c \in \mathbb{N},a^2+b^2=c^2,\mathrm{gcd}(a,b,c)=1\}. $$ If you want to keep $S$ as a set of tuples, you could say $5 \in \bigcup_{(a_1,a_2,a_3) \in S} \{a_1,a_2,a_3\}$. Otherwise, maybe ask a separate question about how to represent the "set of elements of a tuple"? I'd be curious as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.