1

I am reading Elements of set theory by Enderton. I am having a conceptual difficulty with why it seems that certain definitions almost have to be 'proved' to work?

Specifically, I am reading about defining an ordered pair set such that $$\langle x,y \rangle = \langle u,v \rangle$$ are identical objects.

He describes how it is defined as:

$$\langle x,y \rangle = \{\{x\},\{x,y\}\} $$

and also describes various definitions that do not work, such as $$\langle u,v \rangle = \{x,y\}$$

What I don't understand is why either of these are necessary. In his final remark on the section he states 'The preceeding theorem lets us unambiguously define the first coordinate of $\langle x,y \rangle$ to be $x$, and the second coordinate to be $y$'. If this is the ultimate goal, why does it matter that we 'show' the definition works in this way? Why can't we simply say, 'Whenever something of the form $\langle x,y \rangle$ is used, it is an ordered pair and $x$ is the first coordinate and $y$ is the second coordinate.'?

I am only just learning more formal mathematics now, such as the axiomatic approach and so forth, so apologies if I am missing something obvious.

Andrés E. Caicedo
  • 79,201
masiewpao
  • 2,217
  • 1
    It is essentially a formalisation to define ordered pairs in terms of sets. –  Sep 28 '18 at 16:21
  • 1
    If you just say that $<x,y>$ is just the ordered pair, then what are its properties ? How can you use this definition when all the axioms you have only applied to set ? – Zamarion Sep 28 '18 at 16:24
  • 2
    LaTeX pro tip: use \langle and \rangle for $\langle \text{angle brackets} \rangle$ instead of < and >. (I've updated the code in your question.) – Clive Newstead Sep 28 '18 at 17:00
  • 1
    It is very common all across mathematics that certain notions are introduced, with a name that suggests that they have some properties. One then proves that this is indeed the case. Of course, the choice of name was intentional, because the person suggesting it knows that the notion has the desired property. One is not proving the definition (which makes no sense) but rather justifying that the notion is sensible (i.e., it "captures" the properties one is interested in). – Andrés E. Caicedo Sep 28 '18 at 18:12

2 Answers2

3

We need to prove that something with the desired properties actually exists. For example, consider the statement:

We write "$\mathfrak{Q}$" to denote the set of all sets not containing themselves.

This "makes sense" linguistically, but hides a crucial assumption: that the set of all sets not containing themselves actually exists. And in fact it does not - this is the conclusion of Russell's paradox.

So we could talk "non-specifically" about some arbitrary ordered pairing notion, but we need to first prove that such a thing exists (and incidentally, even expressing "there is a pairing operation" precisely in the language of set theory is nontrivial, since this pairing operation isn't literally a function - its domain is too large). And the easiest way to show that (in fact, the only way I know) is to build one.

It might be a good idea at this point to consider situations where we want a pairing operator with certain additional properties, where it's not at all clear that such a thing exists. The standard example of such a thing is a flat pairing function.

Noah Schweber
  • 245,398
  • I understand that in the case of the set of all sets, it does no exist in the sense that its existence introduces a paradox. A question I didn't highlight in the main post is that I don't quite get why we need to 'check' if something exists? Doesn't it exist simply because we define it to? Or is it the case that 'checking if it exists' simply means to ensure it is not paradoxical? – masiewpao Sep 28 '18 at 16:32
  • 1
    @masiewpao That's the point of that example. I've defined the Russell set quite simply, but it clearly doesn't exist just because I've defined it. Think about it this way: all a definition does is introduce terminology or notation. Definitions don't generate facts, and just by writing a definition down we don't get to conclude that a thing satisfying it exists. – Noah Schweber Sep 28 '18 at 16:47
  • Ok I think I understand what you are saying. Is this a fair summary: We have some primitive notion or concept about a mathematical object, we evaluate certain axioms pertaining to this notion as true, this in turn gives information about such an object. We can begin making definitions pertaining to the object, however it is said to not exist if it either (a) is paradoxical, or (b) contradicts the initial axioms that define the mathematical object we are talking about? – masiewpao Sep 28 '18 at 17:11
  • 1
    @masiewpao That's in the right direction, but you have the emphasis a bit off. It's not that "it is said to not exist if it either (a) is paradoxical, or (b) contradicts the initial axioms that define the mathematical object we are talking about," but rather the burden of proof is on the definer to show that it does exist. For example, let $x$ be a counterexample to the Riemann hypothesis. I've made a perfectly meaningful definition, but I have no idea whether such an object exists, and it's even conceivable that the usual axioms of mathematics can't decide whether it does or not! (cont'd) – Noah Schweber Sep 28 '18 at 17:13
  • 1
    The point is that in order to say "let $x$ be a counterexample to the Riemann hypothesis," I need to prove that such a thing exists. You don't need to disprove it in order to be unhappy with me! – Noah Schweber Sep 28 '18 at 17:14
  • Ahhh, that example makes it very clear! Relating it back to the OP, this would be problematic since the assertion that this ordered set exists, is meaningless unless I can actually show it to exist in the established axiomatic system I have. Thank you very much! – masiewpao Sep 28 '18 at 17:21
  • 1
    @masiewpao Bingo. Glad I could help! – Noah Schweber Sep 28 '18 at 17:21
2

Definitions do not need proof. Constructions do, if they are to satisfy a requirement.

Definition: An ordered pair is an object $P(x,y)$ such that $P(x_1,y_1)=P(x_2,y_2)$ iff $x_1=x_2$ and $y_1=y_2$.

In principle, ordered pairs need not exist. But they do:

Theorem: $P(x,y)=\{\{x\},\{x,y\}\}$ is an ordered pair.

On the other hand, not all constructions work:

Theorem: $P(x,y)=\{x,y\}$ is not an ordered pair.

lhf
  • 216,483