# Phil 455: Homework 2

This homework is due by the end of the day on Fri, Feb 2.

One kind of mistake students are liable to with some of these problems is assuming that the domains of some relation have a given number of elements in it (such as more than one, or more than zero). Or assuming that the domain definitely would have an `a`, `b`, and `c` in it such that `aRb` and `bRc`. These assumptions could well be false. Arguments you give need to be hypothetical on if it’s the case that there are elements such that so-and-so…

1. If a set `Α` is finite, then any total function from `Α` into `Α` will be, if injective then onto (surjective); and vice versa. Give an example of a function from `ℕ` into `ℕ` that is injective but not onto. Give an example that’s onto but not injective.

Injective but not onto: the function that maps each `k` to `2k`.

Onto but not injective: the function that maps each of `2k` and `2k + 1` to `k`.

2. Prove that the set of pairs `{(x,y) | x ∈ ℕ and y ∈ ℕ}` has the same cardinality as the set of strings (of length `≥ 0`) made from the letters `"a"` and `"b"` that never have an `"a"` occurring after a `"b"`.

Any such string will have `n` copies of `"a"` followed by `m` copies of `"b"`. We form a bijection that maps each pair `(n,m) ∈ ℕ²` to that string.

3. We said that a set `Α` is no larger than a set `Β` (`|Α| ≤ |Β|`) when there’s a way of mapping `Α`s to `Β`s that’s injective (so each `Β` is paired with at most one `Α`) and includes all the `Α`s. We allow that not every `Β` is paired with an `Α` (that is, the mapping doesn’t need to be onto the `Β`s). If `Α`s are only ever paired with one `Β`, then this injective mapping will be a total function (total because it includes all the `Α`s). If we allow an `Α` to be paired with multiple `Β`s, then it will instead be a relation between `Α`s and `Β`s, and its including all the `Α`s will mean that it’s “total” in the sense of being a serial relation.

In the special case where the set `Β` is `ℕ`, some literature instead talks about the inverse mapping, from `Β` back to `Α`. We’re still articulating what it takes for `|Α| ≤ |Β|`. Being no larger than `Β` when `Β` is `ℕ` is what’s also called being countable. Here are the various features we just described the mapping from `Α` to `Β` having, and what the corresponding features would be for the inverse mapping from `Β` back to `Α`:

From `Α` to `Β` From `Β` to `Α`
injective functional
may be non-surjective may be partial (gappy)
total or serial surjective
perhaps functional perhaps injective (ruling out repeats)

When theorists talk about enumerations of a set `Α`, they’re talking about `Β` being `ℕ` and these inverse mappings from `ℕ` back to `Α`. Insisting that this mapping be injective would be the same as saying that as you “count” through the `Α`s (consider which is paired with `0`, then which is paired with `1`, and so on), you never repeat an `Α`. Sometimes one wants to insist on that, but often not.

This problem will ask you to prove that a certain set `Α` is countable, by building one of these enumeration mappings from `ℕ` back into the set. We’re allowing the enumeration mappings to have repeats but not gaps: that is, the surjective function from `ℕ` to `Α` need not be injective but must be total.

To help you out, I’ll first show you what these kinds of proof look like.

Our example proof wants to establish that any infinite subset `Α` of a countably infinite set `Δ` must also be countable. What the proof needs to do is (a) specify a function from `ℕ` into the `Α`s; and (b) show that the mapping is surjective, that is that every `a ∈ Α` gets included. We’ll do (a) by defining a sequence of ais, and our enumeration will be understood to map each `i ∈ ℕ` to the specified ai.

Here is the basic idea of the example proof: If `Δ` is countable, then there must be an enumeration `d₀`, `d₁`, … dk, … of its members, with `k ∈ ℕ`. That enumeration includes each member of `Δ` (at least) once. The members of `Α` can then also be enumerated `a₀`, `a₁`, … ai, …, where intuitively we take things in the same order as in the `d` enumeration of the `Δ`s, skipping members of `Δ` that aren’t in `Α`.

Spelling this out more precisely: For every `i ∈ ℕ`, let Γi be {dk | dk ∈ Α and ∀ j < i (aj ≠ dk)}. This set will always be non-empty, since for each `i` there must be infinitely many members of `Α` that haven’t yet been enumerated, and each of them will also be in `Δ` (since `Α ⊆ Δ`) and so correspond to some one (or more) dk. Since the indices `k` are `∈ ℕ`, there will be a least `k` where dk ∈ Γi. Define ai to be that dk. Observe that the Γis are constructed so that Γi+1 will be Γi — {ai}. Each is a proper subset of its predecessors. We know every `a ∈ Α` will be included in this enumeration, because it will correspond to some dk, and for each dk ∈ Α, there can be only finitely many dk′ ∈ Α with `k′ < k`. Since the `Γ`s keep taking away these lesser dk′s, and never add new elements, there must be some Γi where dk is the element with the least `k`. Then a = ai.

Now it’s your turn. What you should prove is that the union of any two countably infinite sets `Γ` and `Δ` will itself be countable. It’s enough for your proof to be at the “basic idea” level of detail. You may find it easiest to allow elements of sets to be repeated in enumerations.

We let gk be the `k`th element of the enumeration of `Γ`, and dk be the `k`th element of the enumeration of `Δ`. We define an enumeration of `Γ ∪ Δ` as `a₀`, `a₁`, … a2k, a2k+1, …, where each a2k is gk and each a2k+1 is dk. Elements that are in both of `Γ` and `Δ` (as well as elements that appear multiple times in the enumeration of `Γ`, or the enumeration of `Δ`) will appear multiple times in this enumeration; but that’s okay. It doesn’t detract from the demonstration that the set being enumerated is countable. We know that every `a ∈ Γ ∪ Δ` has to appear in our enumeration, because it has to either be in `Γ` and so be identical to (at least one) gk, or be in `Δ` and so be identical to (at least one) dk, or both. It’s clear from the definition of the enumeration that nothing appears in it that isn’t an element of `Γ ∪ Δ`.

4. Explain why, if `Β` is a countable set and `Α` is uncountable, there can be no surjective function from `Β` onto `Α`.

If `Β` is countable, then there’s a bijection surjective function `b` from `ℕ` into `Β`. For the sake of argument, suppose there were a surjective function `a` from `Β` onto `Α`. Then the composition `a ∘ b` would be a surjective function from `ℕ` onto `Α`. But then as explained in the previous Problem, `Α` would have to be countable. So there can be no such function `a`.

This answer helps itself to the assumptions: if a set is uncountable, it can’t also be countable. And that: the composition `a ∘ b` of a surjective function `a` and a surjective function `b` is a surjective function. It’s fine for you to help yourself to assumptions like this, so long as you know they’re true, and they’re not what the Homework Problem is about.

5. Here is a presentation of the proof that the powerset of a set `Β` always has a larger cardinality than set `Β` does. The presentation has some gaps/questions in it, which you need to fill in.

Let Γ = 𝟚Β, and suppose for reductio that `|Γ| ≤ |Β|`. Then by definition of “no larger than (`≤`)” for sets, there must be a total function `f: Γ → Β` that’s injective. (Explain what this consequence amounts to. `f` maps each subset of `Β` to an element of `Β`, and never maps distinct subsets to the same element of `Β`.) The members of `Γ` will be sets `Α ⊆ Β`. For each such `Α`, `f(Α)` will be some `b ∈ Β`, and either `b ∈ Α` or `b ∉ Α`. In the first case, call `Α` “introverted”, else call `Α` “extraverted.” Every `Α` is either introverted or extraverted, and is never both. (Why? Because either `b ∈ Α` or `b ∉ Α`, but never both.)

Now let `Δ` be the image under `f` of all the extraverted members of `Γ`, that is, the set `{b ∈ Β | ∃Α ∈ Γ (f(Α) = b and b ∉ Α)}`. `Δ` is a member of `Β`’s powerset `Γ` (Why? Because `Δ` is a set of some elements of `Β`.), so `Δ` must be either introverted or extraverted.

Suppose `Δ` is introverted; then `f(Δ) ∈ Δ`. (Why? By definition of “introverted.”) But by definition of `Δ`, it includes only those `f(Α)` where `Α` is extraverted. So `Δ` is extraverted.

Suppose `Δ` is extraverted; then `f(Δ)` must be `∈ Δ`. (Why? By definition of `Δ`, it includes `f(Α)` for every extraverted `Α`.) But if `f(Δ) ∈ Δ`, then by definition of “introverted”, `Δ` is introverted.

So `Δ` is introverted iff `Δ` is extraverted. But as we said, no member of `Γ` can be both introverted and extraverted.

So our supposition that there is such a total injective function `f` fails. So the powerset `Γ` of `Β` must after all be larger than `Β`.

In addition to answering all the parenthetical questions in this proof, there is a step in the proof that implicitly relied on `f`’s being an injection, and would fail if that could not be assumed. Identify what step in the proof this is, and explain why `f`’s being an injection justifies it.

The step that is underlined relies on `f`’s being injective. The definition of `Δ` only says it includes all `f(Α)` where `Α` is extraverted. If `f` weren’t injective, then some `f(Α)` may also be `f(Α′)` for distinct `Α′` which is introverted. If `f` is injective, this can be excluded, and for every `f(Α) ∈ Δ` there’s a unique `Α` that `f` maps to it, so by definition of `Δ` that `Α` will have to be extraverted.

6. Let `Γ` be `{"a","b","c"}` and `Δ` be `{1,2}`. How many different relations are there from `Γ` to `Δ`? How many of them are “functional”? In those cases, how many of the corresponding partial functions (the functions with the same graph) are surjective? How many are injective? Do any of the functional relations have inverses that are also functional?

There are 64 relations in total. For each element of `Γ`, a relation can do one of four things: relate it to no elements of `Δ`, relate it only to element `1`, relate it only to element `2`, relate it to both of `1` and `2`. (4 options for `"a"`) times (4 options for `"b"`) times (4 options for `"c"`) gives 64 options.

Here are the 8 of those relations that are functional and correspond to a total function, with an indication of which are surjective. None are injective.

1. One relation has the graph `{("a",1),("b",1),("c",1)}`
2. One relation has the graph `{("a",1),("b",1),("c",2)}` – surjective
3. One relation has the graph `{("a",1),("b",2),("c",1)}` – surjective
4. One relation has the graph `{("a",1),("b",2),("c",2)}` – surjective
5. One relation has the graph `{("a",2),("b",1),("c",1)}` – surjective
6. One relation has the graph `{("a",2),("b",1),("c",2)}` – surjective
7. One relation has the graph `{("a",2),("b",2),("c",1)}` – surjective
8. One relation has the graph `{("a",2),("b",2),("c",2)}`

Here are the 19 additional relations that are functional and correspond to a merely partial function, again with an indication of which are injective and/or surjective.

1. One relation has the graph `∅` – injective
2. One relation has the graph `{("c",1)}` – injective
3. One relation has the graph `{("c",2)}` – injective
4. One relation has the graph `{("b",1)}` – injective
5. One relation has the graph `{("b",1),("c",1)}`
6. One relation has the graph `{("b",1),("c",2)}` – injective and surjective
7. One relation has the graph `{("b",2)}` – injective
8. One relation has the graph `{("b",2),("c",1)}` – injective and surjective
9. One relation has the graph `{("b",2),("c",2)}`
10. One relation has the graph `{("a",1)}` – injective
11. One relation has the graph `{("a",1),("c",1)}`
12. One relation has the graph `{("a",1),("c",2)}` – injective and surjective
13. One relation has the graph `{("a",2)}` – injective
14. One relation has the graph `{("a",2),("c",1)}` – injective and surjective
15. One relation has the graph `{("a",2),("c",2)}`
16. One relation has the graph `{("a",1),("b",1)}`
17. One relation has the graph `{("a",1),("b",2)}` – injective and surjective
18. One relation has the graph `{("a",2),("b",1)}` – injective and surjective
19. One relation has the graph `{("a",2),("b",2)}`

Any functional relation `R` (corresponding to a partial function) will have an inverse that’s functional iff `R` is injective. Above there are 13 such cases. 6 of those are also surjective, and so the inverse will correspond to a total function.

7. Unlike with functions, the composition of a relation and its inverse need not be an identity. Give an example that demonstrates this.

Consider the relation `R` whose graph is `{("a",1),("b",1)}`. Let `R⁻¹` be `R`’s inverse. The composition `(R⁻¹ ∘ R)` does relate the pair `("a","a")`, but also relates the pair `("a","b")`.

8. Is the relation “is at least as old as” symmetric, anti-symmetric, or asymmetric? Tricky! None of the above. Don’t say it’s anti-symmetric, as that implies that if you and I are as old as each other (that is, have the same age), we are numerically identical.

9. Is the relation “is a brother of” symmetric? it depends on what the domain is: amongst boys, yes, amongst children who aren’t all boys, no

10. If a relation is transitive and symmetric, must it be reflexive?

Tricky! No, because transitivity and symmetry permit the existence of objects that don’t stand in the relation to anything, even themselves.

11. Let `Α` be the set `{1,2,3,4}`. Determine the properties of each of the relations whose graphs are specified, and also each of their inverses.

``````R1: { (1,1), (2,1), (3,4), (2,2), (3,3), (4,4), (4,1) }
R2: { (3,4), (1,2), (1,4), (2,3), (2,4), (1,3) }
R3: { (2,4), (3,1), (3,4), (2,2), (1,3), (4,3), (4,2) }
R4: { (1,1), (2,4), (1,3), (2,2), (3,1), (4,4), (3,3), (4,2) }``````

That is, for each relation you should say: (a) is it reflexive, irreflexive, or neither? (b) is it symmetric and/or anti-symmetric, asymmetric, or none of these? (c) is it transitive? (d) is it weakly or strongly connected, or neither?

• R1 is reflexive, anti-symmetric, not transitive, and not even weakly connected
• R2 is irreflexive, asymmetric, transitive, and weakly connected (a strict linear order)
• R3 is neither reflexive nor irreflexive, symmetric, not transitive, and not even weakly connected
• R4 is an equivalence relation, and not even weakly connected
12. Using a universe of `{0,1,2}`, give examples of a binary relation having the following features. (You can specify the relations by their graph.)

1. transitive but not reflexive lots of options here, for example the relation whose graph is `{(0,1), (1,2), (0,2), (2,2)}`, or the relation whose graph is `{(2,2)}`, or the relation whose graph is empty
2. reflexive and symmetric but not transitive for example, the relation whose graph is `{(0,0), (1,1), (2,2), (0,1), (1,0), (1,2), (2,1)}`
13. A relation `R` is called right-Euclidean when `∀u ∀x ∀y ((uRx & uRy) ⊃ x` and `y` have `R` to each other`)`. Prove that for any relation that’s symmetric, the relation will be transitive iff it’s right-Euclidean.

Proof that if the relation is transitive, it’s also right-Euclidean: consider any `u,x,y` in the relation’s domain such that `uRx` and `uRy` (these objects need not be distinct, and there need not be any such triple). We have to show that `xRy`. Since the relation is symmetric and `uRx`, it would also have to be the case that `xRu`. Since the relation is transitive, from `xRu` and `uRy` it would follow that `xRy`. Hence the relation is right-Euclidean. (If you want to explicitly also prove that `yRx`, you could do that in the same manner; but it’s not necessary since it would already follow from switching the roles of `x` and `y`.)

Proof that if the relation is right-Euclidean, it’s also transitive: consider any `u,x,y` in the relation’s domain such that `xRu` and `uRy` (again these objects need not be distinct, and there need not be any such triple). We have to show that `xRy`. Since the relation is symmetric and `xRu`, it would also have to be the case that `uRx`. Since the relation is right-Euclidean, from `uRx` and `uRy` it would follow that `xRy`. Hence the relation is transitive.

14. Prove that for any relation that’s symmetric and transitive, the relation will be serial iff it’s reflexive.

It’s trivial that if the relation is reflexive it’s also serial.

Proof that if the relation is serial it’s also reflexive: consider any `x` in the relation’s domain. Since the relation is serial there must be some `y` such that `xRy`. Since the relation is symmetric it would also have to be the case that `yRx`. Since the relation is transitive, from `xRy` and `yRx` it follows that `xRx`. So the relation is reflexive.

15. Give an example of an equivalence relation on the set of all pairs of living human beings (describe the relation in a short English phrase, please — don’t try to enumerate its graph!). Explain why it’s an equivalence relation. for example, “is the same age as (at some fixed time t)”; this relation is obviously reflexive, obviously symmetric, and obviously transitive

16. Specify the equivalence relation on the set `{1,2,3,4}` that generates the following partition: `{ {1}, {2,3}, {4} }`. (For example, by giving its graph.)

The relation whose graph is `{(1,1),(2,2),(3,3),(4,4),(2,3),(3,2)}`.

1. Where `x ∈ ℕ`, `y ∈ ℕ` and `y > 0`, say that `x mod y` is the remainder you get when dividing `x` by `y`. That is, it’s the `r ∈ ℕ` where `r < y` and `∃q ∈ ℕ (x = q⋅y + r)`. Some examples: `3 mod 5 = 3`, `15 mod 5 = 0`, `5 mod 3 = 2`.

For any `n ∈ ℕ` and `n > 0`, show that the relation whose graph is `{(u,v) | u mod n = v mod n}` is an equivalence relation, and that the partition it generates on `ℕ` has exactly `n` members.

The relation is reflexive because `u mod n = u mod n` always holds. It’s symmetric because whenever `u mod n = v mod n`, it’s true that `v mod n = u mod n`. It’s transitive because whenever `u mod n = v mod n`, and `v mod n = w mod n`, it’s true that `u mod n = w mod n`.

The natural numbers `x` such that `0 ≤ x < n` are each of the form `0⋅n + x`, and so have themselves as remainders when dividing by `n`. So the relation in question partitions `ℕ` into at least `n` different cells, `[0]...[n-1]`. By the definition of `mod`, the result of `u mod n` for any `u ∈ ℕ` is always less than `n`, so there can’t be any additional cells.

2. In the webnotes on relations, we gave a definition of the “transitive closure” of a relation `R` in terms of a relation whose graph was the union of all the Rks (where each of those is the composition of `k` instances of `R`). Prove that the relation R+ defined in this way is transitive.

If (a,b) ∈ R+ and (b,c) ∈ R+, then by def of R+, (a,b) ∈ Rj and (b,c) ∈ Rk for some `j,k ∈ `positive `ℕ`. By def of `∘`, (Rk ∘ Rj) must then contain `(a,c)`, and by associativity of `∘`, this will be Rk+j, which by def of R+, will be such that its graph ⊆ R+’s. So `(a,c)` also ∈ R+.