Tying Up Loose Pairs

In our previous post, we discussed nested quantifiers, and preceding that, sets. We briefly mention the notion of ordered pairs that abbreviated our discussions on predicate logic. We will define them properly here. Firstly, we need the proving technique proof by cases.

Lemma 1. Let $p, q, r$ be propositional variables. Then

$(p \lor q) \wedge (p \to r) \wedge (q \to r) \to ((p \lor q) \to r).$

Theorem 1. Let $K, L$ be sets. Fix $x \in K, y \in L$ . Using the axiom of pairing, define the set

$(x, y) := \{\{x\}, \{x,y\}\}.$

Then $(x,y) = (x',y')$ if and only if $x= x'$ and $y=y'$ .

Proof. We will first prove the direction $(\Leftarrow)$ . Suppose $x= x'$ and $y=y'$ . By the axiom of extensionality, we can show that $\{x\} = \{x'\}$ and $\{x,y\} = \{x,y'\}$ . Hence,

$(x, y) = \{\{x\}, \{x,y\}\} = \{\{x'\}, \{x',y'\}\} = (x',y').$

as required.

We will next prove the direction $(\Rightarrow)$ . Suppose $(x,y) = (x',y')$ . By definition,

$\{\{x\}, \{x,y\}\} = (x,y) = (x',y') = \{\{x'\}, \{x',y'\}\}.$

Therefore, $\{x\} \in \{\{x'\}, \{x',y'\}\}$ .

There are two cases to consider.

For the first case, if $\{x\} = \{x'\}$ , then $x = x'$ . This implies that

$\{\{x\}, \{x,y\}\} = \{\{x\}, \{x,y'\}\}.$

There are two more sub-cases. If $\{x,y\} = \{x\}$ , then we must have $x = y$ . This implies that

$\{\{x\}, \{x,y'\}\} = \{\{x\}, \{x,y\}\} = \{\{x\}, \{x,x\}\} = \{\{x\}, \{x\}\} = \{\{x\}\},$

where we agree that $\{x,x\} = \{x\}$ by convention. This implies that $\{x, y'\} = \{x\}$ , so that $y' = x = y$ . Therefore,

$x = x' \wedge y= y',$

as required.

For the second case, if $\{x\} =\{x', y'\}$ , then we must have $x' = y' = x$ . Following a similar argument as above, we are forced to conclude that $y = x = y'$ . Therefore,

$x = x' \wedge y= y',$

as required.

Proving by cases, we have proven the result.

Definition 1. Let $K, L$ be sets. By the axiom schema of specification, define the cartesian product of $K$ and $L$ by

$K \times L := \{(x,y) : x \in K \wedge y \in L\}.$

This can be shown to be a consequence of the axiom of power set, which we will omit for now.

Note that $K \times L \neq K \cap L$ . The idea is this, fix $z \in K \times L$ . Then $z = (x,y) = \{\{x\}, \{x,y\}\}$ . However, $\{x\} \notin K$ and $\{x,y\} \notin K$ , so that $z \notin K$ . Hence, $z \notin K \cap L$ .

This turns out to help us define relations, and in turn, functions—the most pervasive object in mathematics. We will discuss them in further detail next time.

—Joel Kindiak, 27 Nov 24, 2307H

Responses

How to Nest Your Predicates – KindiakMath

December 28, 2025 at 12:33 am

[…] is a predicate over (we will properly define this later on when discussing sets). This nested proposition means that for any fixed , the proposition holds. […]

LikeLike

Mathematical Relationships – KindiakMath

December 28, 2025 at 12:36 am

[…] the cartesian product of and […]

LikeLike

What is a Negative Number? – KindiakMath

December 28, 2025 at 12:52 am

[…] 1. Denote . For ordered pairs , […]

LikeLike

Tying Up Loose Pairs

Share this:

Responses

Leave a comment Cancel reply