# Relations, Functions and Power Sets

Philosophy I · Logic · https://tryals.app/learn/philosophy-i/relations-functions-and-power-sets

## Structure From Bare Collections

Sets alone have no structure, but structure can be built from them.

The **ordered pair** $(a, b)$ is the first step, and unlike a set it *is* sensitive to order: $(1, 2) \neq (2, 1)$. The **Cartesian product** $A \times B$ is the set of all ordered pairs with first element from $A$ and second from $B$, so $|A \times B| = |A| \cdot |B|$.

A **relation** from $A$ to $B$ is any subset of $A \times B$, nothing more. Relations on a single set are classified by three properties:

| Property | Holds when |
|---|---|
| Reflexive | Every element relates to itself |
| Symmetric | If $a$ relates to $b$ then $b$ relates to $a$ |
| Transitive | If $a$ to $b$ and $b$ to $c$ then $a$ to $c$ |

A relation with all three is an **equivalence relation**, and it partitions the set into disjoint **equivalence classes**. "Has the same birthday as" is an equivalence relation; "is taller than" is transitive but neither reflexive nor symmetric.

A **function** from $A$ to $B$ is a relation assigning *exactly one* element of $B$ to each element of $A$. It is **injective** if distinct inputs give distinct outputs, **surjective** if every element of $B$ is hit, and **bijective** if both.

Two counting results carry surprising weight. The **power set** $\mathcal{P}(A)$ is the set of all subsets of $A$, and

$$|\mathcal{P}(A)| = 2^{|A|}$$

because each element is independently in or out. A 3-element set has 8 subsets. And the number of functions from $A$ to $B$ is $|B|^{|A|}$, since each of the $|A|$ inputs independently gets one of $|B|$ outputs.

**Cantor's theorem** says $|\mathcal{P}(A)| > |A|$ for *every* set, finite or infinite. Since $2^n > n$ always, there is no largest set and no largest infinity, the power set of any infinity is a strictly bigger one. This is where set theory stops being bookkeeping and starts producing results nobody expected.

> **Common pitfall:** thinking every relation is a function. A function must assign exactly one output to each input, no more, no fewer. "Is a parent of" relates one person to several children, so it is a perfectly good relation and not a function at all.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Why is not every relation a function?

A. A function must always be an equivalence relation, whereas relations need not
B. A function must assign exactly one output to each input, and relations need not
C. A function must map distinct elements in the domain to distinct codomain outputs
D. A relation is restricted to a single set, whilst a function maps between two sets

**Answer:** B. A function must assign exactly one output to each input, and relations need not

**Why:** A relation is any subset of the Cartesian product, with no constraint. A function adds the requirement of exactly one output per input, "is a parent of" relates one person to several children, so it is a relation and not a function.

Page: https://tryals.app/practice/philosophy-i/relations-functions-and-power-sets/why-is-not-every-relation-a-function

### 2. Cantor’s theorem shows there is no largest infinite set.

**Answer:** True

**Why:** True, the power set of any set is strictly larger, so no set can be maximal. Applying the theorem repeatedly generates an endless hierarchy of infinities, which is where set theory stops being bookkeeping.

Page: https://tryals.app/practice/philosophy-i/relations-functions-and-power-sets/cantors-theorem-shows-there-is-no-largest-infinite-set

### 3. Which are true of an equivalence relation?

A. It partitions the set into disjoint classes
B. It is reflexive
C. It is symmetric
D. It orders the set from smallest to largest

**Answer:** A. It partitions the set into disjoint classes; B. It is reflexive; C. It is symmetric

**Why:** An equivalence relation is reflexive, symmetric and transitive, and it carves the set into disjoint classes. Ordering needs *anti*-symmetry, which is incompatible with the symmetry an equivalence relation has.

Page: https://tryals.app/practice/philosophy-i/relations-functions-and-power-sets/which-are-true-of-an-equivalence-relation

### 4. An equivalence relation is said to partition a set into disjoint classes. What structural consequence follows when two elements share a single equivalence class?

A. They necessarily relate symmetrically to all other elements in the whole set
B. They share identical relation pairs with every element across the domain
C. The Cartesian product of their classes collapses into a single ordered pair
D. The elements are bound to be identical under the formal equality of the set

**Answer:** B. They share identical relation pairs with every element across the domain

**Why:** Belonging to the same equivalence class means two elements are mutually related and share identical relational behaviour across the partition. It does not mean they are identical objects, nor does it force relations with external elements outside their class.

Page: https://tryals.app/practice/philosophy-i/relations-functions-and-power-sets/an-equivalence-relation-is-said-to-partition-a-set-into-disjoint

### 5. Sort each expression by what it counts.

**Answer:**

- Counts subsets: Two to the power of the size of A
- Counts ordered pairs: The size of A times the size of B
- Counts functions: Each input independently picks one of the outputs

**Why:** Subsets go as $2^{|A|}$ because each element is in or out; pairs as $|A|\cdot|B|$; functions as $|B|^{|A|}$ because each input independently picks an output. All three are the same independence argument applied differently.

Page: https://tryals.app/practice/philosophy-i/relations-functions-and-power-sets/sort-each-expression-by-what-it-counts

### 6. Arrange these sets in order of increasing size.

**Answer:**

1. A set with 2 elements
2. The power set of a set with 2 elements
3. The power set of a set with 3 elements
4. The power set of a set with 4 elements

**Why:** Sizes 2, 4, 8, 16. Each power set is strictly larger than the set it came from, which is Cantor’s theorem in its finite and least surprising form.

Page: https://tryals.app/practice/philosophy-i/relations-functions-and-power-sets/arrange-these-sets-in-order-of-increasing-size