In the preface to his Naive Set Theory, Paul Halmos explains that the "naive" in the title alludes in part to the fact that the book's

...language and notation are those of ordinary informal (but formalizable) mathematics.

Despite this declaration of informality, the book devotes a fair bit of space to notational questions, and I get the distinct impression that there is a sharp line between permissible and not permissible notations. This question is about how to cast a particular idea in a notatation that conforms to Halmos' rules.

Here's a summary of Halmos's notation. He first defines sentences (p. 5). These can be atomic sentences, namely, ones having either one of the following two forms: $$ \begin{array}\\ x &\in& A\\ A & = & B \end{array} $$ ...or sentences obtained by combinining other sentences using the following connectives (p. 5):

or (in the sense of "either—or—or—both"),
if—then—(or implies),
if and only if,
for some (or there exists),
for all.

Later (p. 6), he provides some notation for describing sets, based on the Axiom of Specification:

$$\{x\in A:S(x)\}$$

...where $x$ and $A$ are sets, and $S(x)$ is a sentence in which $x$ is free, meaning that

...$x$ occurs in $S(x)$ at least once without being introduced by one of the phrases "for some $x$" or "for all $x$".

Later (p. 10) adds a shorthand that can be used if $S(x)$ meets a certain requirement:

If ... $S(x)$ is a condition on $x$ such that the $x$'s that $S(x)$ specifies constitute a set, then we may denote that set by $$\{x:S(x)\}.$$

Now, I'm looking for an expression consistent with the rules given above and representing the set of all unordered (and non-degenerate) pairs of elements of some set $A$.

Informally (or semi-formally), I would have written this as

$$\{\{x,\;y\}:x \in A \textit{ and } y \in A \textit{ and } x \neq y\}$$

...but this does not conform to any of the two ways of specifying a set given above. I can write something like this:

$$\{z:z = \{x,\;y\} \textit{ and } T(z)\}$$

...but I have not figured out how to write the sentence $T(z)$ to express

$$x \in A \textit{ and } y \in A \textit{ and } x \neq y$$

In other words, the sentence $T(z)$ has to say something like "one element of $z$ belongs to $A$, the other element of $z$ belongs to $A$, and these two elements are distinct." How can I express this using Halmos' formalism?

It could be that Halmos' formalism (as described above) is not sufficient to express these concepts. If so, please let me know.


The formula will be :

$\{ z: \text { there is } x \text { and there is } y \text { such that } x∈A \text { and } y∈A \text { and } x \ne y \text { and } z= \{ x,y \} \}.$

Using symbols for quantifiers and logical connectives :

$\{ z : ∃x∃y(x∈A ∧ y∈A ∧ x \ne y \land z= \{ x,y \}) \}$.

  • 2
    $\begingroup$ Formally speaking, $z=\{x,y\}$ is a shorthand for $\forall u(u\in z\leftrightarrow u=x\lor u=y\})$. $\endgroup$ – Asaf Karagila Jun 11 '18 at 15:49
  • 1
    $\begingroup$ @AsafKaragila: FWIW, Halmos formalizes $z =\{x,y\}$ simply as $z = \{u:u=x \textit{ or } u=y\}$ (p. 10). Is there a significant difference? $\endgroup$ – kjo Jun 11 '18 at 16:29
  • 1
    $\begingroup$ @kjo: But $\{$ and $\}$ are not part of the language. If you want to be formal, be formal. $\endgroup$ – Asaf Karagila Jun 11 '18 at 16:34
  • $\begingroup$ @AsafKaragila: admittedly, Halmos' notation is "semi-formal", which makes translation even trickier somehow (though the results are easier to read). $\endgroup$ – kjo Jun 11 '18 at 16:42

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.