6
$\begingroup$

Simple examples of sets are often described via roster notation (aka enumeration notation) like $\{0,1,4,9\}$ - simply write down the elements of the set between the two set delimiters (curly brackets) and separate them by commas.

In axiomatic set theory this notation also occurs in the Axiom of Pairing:

For any $a$ and $b$ there exists a set $\{a, b\}$ that contains exactly $a$ and $b$.

It is then easy to see that $\{a, b\} = \{b, a\}$. More generally one can usually read that ordering and multiple listing of the elements in roster notation is irrelevant, for example we have $\{0,1,2\} = \{1,0,2,1,0\}$.

In axiomatic set theory the concept of an ordered pair $(a,b)$ is not introduced by a separate axiom, but it is somehow defined based on the existing axioms, for example by $(a,b) = \{\{a\},\{a,b\}\}$. More generally, the concept of an ordered tuple $(a_1,\ldots,a_n)$ can be introduced in that way.

Here are my doubts:

It seems to me that roster notation is based on an intuitively pre-existing concept of an ordered tuple. Writing down elements sequentially from left to right does not really produce a set, but a tuple. We then have a certain equivalence relation for such tuples which says us when to regard two tuples as the "same set". But set theory should not be based on such an intuitive prerequisite. In fact even the axiom of pairing is based on an intuitive concept of a pair. Later re-introducing this concept via a definition seems to be circular.

One might argue that $\{a,b\}$ is short for $\{x : x = a \vee x = b\}$. But even in this notation we actually have a pair of conditions, separated by a $\vee$ instead of a comma. Yes, $x = a \vee x = b$ and $x = b \vee x = a$ are equivalent, but alone to state this fact requires an intuitive understanding of "ordering" which axiomatic set theory claims to be reducible to more elementary concepts.

In other words: We start with an intuitive concept of pairs or tuples as ingredients of the axioms and later "cleanly" re-introduce these concepts using the axioms based on the same (but beforehand unclean) concept.

My question:

Usually roster notation occurs at the very beginning of texts on set theory. But it involves ingredients which are not really available in a precise sense at that point:

  1. Finite sequences of elements, i.e. ordered tuples

  2. Permutations of ordered tuples

  3. A reduction process eliminating duplicates in tuples

One can argue that at the beginning an intuitive understanding of these ingredients is sufficient to get the idea what roster notation means. The precise meaning will be clear after having introduced the necessary ingredients via an axiomatic approach.

But the Axiom of Pairing involves roster notation before the above ingredients have been properly defined. Is this a vicious circle? Do we need a new axiomatic approach avoiding this problem? More precisely, do we need an additional axiomatic concept of an ordered pair?

$\endgroup$
7
  • 3
    $\begingroup$ What is your question? $\endgroup$
    – Somos
    Oct 29, 2021 at 11:34
  • 1
    $\begingroup$ Yes, in genral the so-called set-builder notation has the logical form $\{ x \mid \varphi(x) \}$ where $\varphi(x)$ is a formula of the language with variable $x$ free. Thus, the case $x=a \lor x=b$ used for pair fits with this general form and every finite list can be defined this way. $\endgroup$ Oct 29, 2021 at 11:40
  • 1
    $\begingroup$ And do, the formula $\varphi(x)$ does not presupposes some "circular" understanding of sets properties; obviously, it presupposes the "general" understanding of language (natural and symbolic). $\endgroup$ Oct 29, 2021 at 11:42
  • 4
    $\begingroup$ There is a metamathematical concept of order in the sense that even writing down a formula presupposes a left to right order etc. In set theory we can do an abstract theory of orders on sets using pairs and relations. One has to separate these things. $\endgroup$ Oct 29, 2021 at 11:50
  • $\begingroup$ See also this post $\endgroup$ Oct 29, 2021 at 12:24

1 Answer 1

-1
$\begingroup$

We have Axiom of Extensionality and Axiom of Paring in set theory which together could solve your question.

Axiom of Extensionality. For any $a,b$ we have $x\in a$ if and only if $x\in b$ for any $x$, i.e., in formals of set theory language

$$\forall a\forall b\forall x(x\in a\leftrightarrow x\in b).$$

Axiom of Extensionality shows that ordering and multiple listing of the elements in roster notation is irrelevant in identifying sets.

Axiom of Pairing. For any $a,b$ there is some $c$ such that $x\in a$ and $x\in b$, i.e., in formals of set theory language

$$\forall a\forall b\exists c(a\in c\wedge b\in c).$$

By Axiom of Extensionality and Axiom of Pairing, we have

Proposition 1. For any $a,b$,

(1) there is a least $c$ such that $x\in a$ and $x\in b$, i.e., $c=\{a,b\}$, and

(2) there is a least $c$ such that $x\in a$, i.e., $c=\{a\}$.

With Axiom of Pairing in hand, we can define ordered pairs.

Definition 2. For any $a,b$, set $(a,b)=_\mathsf{df}\{\{a\},\{a,b\}\}$.

By Axiom of Extensionality we can show that $(a,b)$ is indeed an ordered pair.

Proposition 3. For any $a,b,c,d$ we have $(a,b)=(c,d)$ if and only if $a=b$ and $c=d$.

Hope this useful for you.

$\endgroup$
3
  • 2
    $\begingroup$ In the Axiom of Extensionality you cannot say for any $a,b$. It characterizes $a = b$. And what is the role of $c$ in your statement of the Axiom of Pairing? And $x \in a$ and $x \in b$ characterizes $a \cap b$. $\endgroup$
    – Paul Frost
    Oct 30, 2021 at 22:46
  • $\begingroup$ @PaulFrost I revised the typos. $\endgroup$
    – M. Logic
    Oct 31, 2021 at 1:11
  • 3
    $\begingroup$ Still not okay. In the Axiom of Extensionality you should have "For any $a,b$ we have $a = b$ iff ($x∈a$ if and only if $x∈b$ for any $x$)." In the Axiom of Pairing (btw typo): "such that $a \in c$ and $b \in c$." $\endgroup$
    – Paul Frost
    Oct 31, 2021 at 9:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .