Can you make a Set Theory definition of tuples that has limited depth?

107 Views Asked by At

I was thinking about the set theory definitions of ordered pairs, such as $(a,b)=\{\{a\},\{a,b\}\}$. And I think people usually add elements to make longer ordered tuples using the definition $(a,b,c)=((a,b),c)$; $(a,b,c,d)=((a,b,c),d)$; etc.

But by these definitions, as you make longer and longer ordered tuples, you get deeper and deeper sets representing them, like $(a,b)$ has depth $2$, $(a,b,c)$ has depth $4$, $(a,b,c,d)$ has depth $6$, etc. Is it possible to make definitions for ordered pairs and tuples so that all tuples' depths are less than a constant $M$?

I do not want to use any non-set elements. However, in that case, there's a limited number of possible sets with less than depth $M$, while there's an unlimited number of possible tuples.

Therefore, we will ignore the depth within a tuple's own elements and pretend that they have $0$ depth. Like if $a$ is a set that has depth $M+1$, that does not mean $(a,b)$'s set form will break the limit, because we will pretend $a$ has $0$ depth. However, if $a$ is used in $(b,c)$'s set form, then in that case $a$ will have $M+1$ depth and it will break the limit.

3

There are 3 best solutions below

5
On

Can we use Natural Numbers ?
We might have Natural Number using Non-Standard Constructions without Sets.

If YES :

We can theoretically make tuples with Sets having Constant Depth !

Here is such a Construction :

$ (A,B) = \{ \{1,\{A\}\} , \{2,\{B\}\} \}$
$ (A,B,C) = \{ \{1,\{A\}\} , \{2,\{B\}\} , \{3,\{C\}\} \}$
$ (A,B,C,D) = \{ \{1,\{A\}\} , \{2,\{B\}\} , \{3,\{C\}\} , \{4,\{D\}\} \}$
$ (A,B,C,D,E) = \{ \{1,\{A\}\} , \{2,\{B\}\} , \{3,\{C\}\} , \{4,\{D\}\} , \{5,\{E\}\} \}$

The tuples have Equivalent Sets with Constant Depth !

Is it Practical ? It is useful ? How make build up the whole theory with that ? How to show 2 tuples are Equivalent in formal Syntax ? What Difficulties will we encounter ?
These are out of scope of the Question & this Answer , I have merely given a theoretical Construction !

If we can not use Natural Numbers & We want everything to be Sets :

It is not Possible.
Various Proofs are given in Various Answers & Comments.

Here is my Proof of the Same , which may be somewhat Similar to the others :
Let there be some way to have Max Depth $M$.
Let X be the set of all tuples with 1 to $M$ elements.
Two elements/tuples ( $x_1$ , $x_2$ ) in X will have to Differ in at least 1 Place in the Set Structure.
Estimate all the Potential Places which can Differ for $x_1$ , $x_2$ (over counting is not a concern) : let that be a large Number Y. It can be Polynomial , Exponential , what-ever.
Make a new Set Z with all tuples with $Y+1$ elements , which Differ in all $Y+1$ Places.
Z will have elements which will not fit in the Set Structure with Max Depth $M$.
Z will have elements which require more than $M$ Depth.

4
On

It is impossible to define ordered tuples in such a way so has to have bounded depth for all lengths. To see this note that there are finitely many depth-$M$ sets not using any variables (i.e. built solely from the empty set) and hence finitely many distinct ways to place a fixed finite number of "tuple element" sets into the depth-$M$ sets to obtain ordered tuples.

With sufficiently long tuples to make, there will not be enough depth-$M$ sets to represent all the ordered tuples (of unbounded length) using the given "tuple elements", even if there is only one "tuple element".

0
On

I figured out that it is impossible. Consider tuples that are made of only the same element $a$ repeated $n$ times. There are an unlimited number of such tuples: $(a),(a,a),(a,a,a),(a,a,a,a),(a,a,a,a,a),...$ However, for any depth $M$, there is a limited number of sets that those tuples can translate to.

$M=0$: there is $1$ option: $a$

$M=1$: there are $1+2^1$ options: $a$, and sets containing none, some, or all of the 0-depth elements.

$M=2$: there are $1+2^{1+2^1}$ options: $a$, and sets containing none, some, or all of the 0- or 1-depth elements.

It continues like this, it will always be 1 + 2 ^ the previous row. Whatever finite number $M$ we use, we can only make finitely many sets but we need to be able to translate infinitely many tuples uniquely into them.