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…

Sample answers in purple.

16. 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.

17. 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.

18. 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 a_is, and our enumeration will be understood to map each i ∈ ℕ to the specified a_i.

    Here is the basic idea of the example proof: If Δ is countable, then there must be an enumeration d₀, d₁, … d_k, … of its members, with k ∈ ℕ. That enumeration includes each member of Δ (at least) once. The members of Α can then also be enumerated a₀, a₁, … a_i, …, 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 {d_k | d_k ∈ Α and ∀ j < i (a_j ≠ d_k)}. 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) d_k. Since the indices k are ∈ ℕ, there will be a least k where d_k ∈ Γ_i. Define a_i to be that d_k. Observe that the Γ_is are constructed so that Γ_i+1 will be Γ_i — {a_i}. Each is a proper subset of its predecessors. We know every a ∈ Α will be included in this enumeration, because it will correspond to some d_k, and for each d_k ∈ Α, there can be only finitely many d_k′ ∈ Α with k′ < k. Since the Γs keep taking away these lesser d_k′s, and never add new elements, there must be some Γ_i where d_k is the element with the least k. Then a = a_i.

    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 g_k be the kth element of the enumeration of Γ, and d_k be the kth element of the enumeration of Δ. We define an enumeration of Γ ∪ Δ as a₀, a₁, … a_2k, a_2k+1, …, where each a_2k is g_k and each a_2k+1 is d_k. 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) g_k, or be in Δ and so be identical to (at least one) d_k, or both. It’s clear from the definition of the enumeration that nothing appears in it that isn’t an element of Γ ∪ Δ.

19. 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.

20. 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.

21. 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.

22. 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").

23. 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.

24. 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

25. 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.

26. 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

27. 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)}

28. 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.

29. 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.

30. 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

31. 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)}.