What I want to do is formalize a general way to present a pair of tuples (tupleA and tupleB) such that:

  1. the potential values of both tuples are the natural numbers (0 included).

  2. No duplicate elements in either tuple.

  3. The values (and size) of tupleB are restricted in 3 ways with the first two depending upon the size of tupleA.

    -If tupleA has a size of n, then the size of tupleB can not be greater than 3n.

    -Each element of tupleB must be less than or equal to 3n.

    -If 0 is an element of any given tupleB, then it must be the sole element in tupleB.

  4. There is an order to the elements of any given tupleB, with this order being a regular less-than ordering (there are no order restrictions on tupleA)

  5. Both tupleA and tupleB should be presented as some sort of cohesive unit which itself is referable (say as simply "expression 1", "expression 2", etc...). Also note, the syntax--by this I mean their position on paper relative to one another isn't really of any concern, but the situation must simply be such that one can distinguish between tupleA and tupleB of the whole expression so as to be able to refer to just a single one of them. This is because I want to be able to eventually define an operation * by saying (tupleB_of_expression1) * (tupleB_of_expression2) = ...

Examples of expressions meeting this criteria (where the syntax is that of: tupleA.tupleB) :

  • (0,2,3).(1,3,5,6,7,9)
  • (3,0,2).(1,3,5,6,7,9)
  • (3).(2,3)
  • (7,6,3,9).(12)
  • (2,0).(1,2,3,4)

the following expressions would not meet the criteria:

  • (1,4).(7) ...'7' in tupleB is greater than 3(size_of_tupleA)=6
  • (5,3,6).(0,4) ....'0' is in tupleB which means it should be the only element in tupleB, but it is not
  • (1).(6,4,3,6,2) ...size of tupleB is too big (values of elements are also too large and not ordered properly)

Here is my attempt at doing this:

First note that I treat functions as being defined as tuples.

Let [n] ={0,1,2,...,n-1}

Let [n]$^*$ = {1,2,3,...,n}

$\mathbb{N}$ = {0,1,2,3,...}

Note: $X^{\underline{Y}}$ denotes the set of all injective functions, $f$, from the set $Y$ to the set $X$

Let $\mathcal{T_a}$ = $\bigcup\limits_{ n=1}^\infty \mathbb{N}^{\underline{[ n]}}$

So $\mathcal{T_a}$ is full of elements like (1), (32), (0,2,4) etc..

The elements of $\mathcal{T_a}$ are considered to be the tupleA's.

side question: Since functions can be defined as tuples--and since that is how
I will be treating them here--is it ok to refer to the size of one of the injective functions and say:

$\forall$ t $\in \mathcal{T_a}$, |t| denotes the size of t

...it just feels odd treating the elements of $\mathcal{T}$ as both functions and tuples. But then again, functions are indeed defined here according to their tuple definition, so I will be using that notation.

For a given t $\in \mathcal{T_a}$,

Let $\mathcal{T_b}$ = {(0)} $\cup$ $\bigcup\limits_{ n=1}^{3|t|} {[ 3|t| ]^*}^{\underline{[n]}}$ such that $\forall j,k \in [n]$ ($j<k \rightarrow (f(j) < f(k)))$

  • I feel like starting from the "such that" part above may not be how one usually adds such a restriction, or is it?

The elements of $\mathcal{T_b}$ are to be considered as the valid tupleB's corresponding to some tupleA, t.

Now to formalize what expressions are considered to be well-formed, would the following be acceptable?

For all $t_a$ $\in$ $\mathcal{T_a}$,


is considered well-formed for all $t_b$ $\in$ $\mathcal{T_b}$ (which is of course, defined in part via the supplied $t_a$).

I'm struggling on how to define the well-formed expression and making explicit that tupleB depends on tupleA. I'm not sure if the above is sufficient.


Consider $t_a$ = (1)

This would be our "tupleA" part of the overall expression to which (1) belongs.

then the well-formed expressions corresponding to $t_a$ are determined first by determining $\mathcal{T_b}$. Since $t_a$ is of size 1, $\mathcal{T_b}$ would be the the union of the following sets:

  • the set whose sole element is the tuple: (0)

For my co-domain I am using sets of the form [n]$^*$ so that the restriction of there not being any tuples which have both '0' as an element as well as some other distinct element is met. And so I would need to add this set whose sole element is the tuple '(0)' separately since it wouldn't be included otherwise, correct?

  • the set of all injective functions from [1] to [3]$^*$ meeting the restriction given
  • the set of all injective functions from [2] to [3]$^*$ meeting the restriction given
  • the set of all sets of injective functions from [3] to [3]$^*$ meeting the restriction given

So our $\mathcal{T_b}$ would = {(0),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}

Thus the following are all those well-formed expressions which has a tupleA part of (1):

  • (1).(0)
  • (1).(1)
  • (1).(2)
  • (1).(3)
  • (1).(1,2)
  • (1).(1,3)
  • (1).(2,3)
  • (1).(1,2,3)

So what is the best way to achieve what I am trying to achieve ?Would what has been provided here be sufficient?

Thanks for reading.

  • $\begingroup$ I think you are overcomplicating things. The description you have in the beginning of the question is formal enough for most discourse. But anyway, for $\mathcal T_a$ you could use $\mathbb N^*$, the set of all finite strings over $\mathbb N$. $\endgroup$ – user856 Nov 23 '16 at 6:25
  • $\begingroup$ Using $\mathbb{N}^*$ is a good insight, I will update the post in the morning, thanks. As for complicating things, this is probably true to an extent, however I would nonetheless like something as formal as possible and not just something worthy of most discourse. $\endgroup$ – Boolean_functions Nov 23 '16 at 6:38

If I were you, I'd just write

A [thing/object/whatever] is a pair $(a,b)$, where $a = (a_1,\ldots,a_n)$ is an $n$-tuple of natural numbers without duplicates, and $b \subseteq \{0,\ldots,3n\}$ is a nonempty set of natural numbers between $0$ and $3n$, with the condition that $0 \in b$ if and only if $b = \{0\}$.

We extend the notation $|a|$ to denote the number of entries in a tuple, $|(a_1,\ldots,a_n)| = n$.

This is analogous to how graphs are defined as pairs $(V,E)$ where $V$ is a set and $E$ is a subset of $V^2$, subject to certain conditions.

  • $\begingroup$ I would need to add a bit to your example in regards to the restrictions (both a and b cannot have duplicates (not just a),and the elements of b must be ordered according to some relation), but this seems like a great way of going about what I am trying to do. Very simple (not nearly as over-complicated) and concise. Thanks. $\endgroup$ – Boolean_functions Nov 23 '16 at 19:16
  • $\begingroup$ Sorted sequences without duplicates are essentially the same as sets, so $b\subseteq\{0,\ldots,3n\}$ takes care of both your additional restrictions. By "essentially the same" I mean that any sorted sequence without duplicates can be uniquely associated with a set and vice versa. $\endgroup$ – user856 Nov 23 '16 at 21:06
  • $\begingroup$ Also I just realized that the condition $1 \le |b| \le 3n$ is redundant: If $b \subseteq \{0,\ldots,3n\}$, then the only ways the condition can be violated are if $|b| = 0$ or $|b| = 3n+1$. The former can be avoided by specifying that $b$ is nonempty, and the latter is not allowed because then $0\in b$. Though you should consider whether you do want to allow $|a| = 0$ or $|b| = 0$. $\endgroup$ – user856 Nov 23 '16 at 21:11

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.