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…

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.

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

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.

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

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.) 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?)

    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?), so Δ must be either introverted or extraverted.

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

    Suppose Δ is extraverted; then f(Δ) must be ∈ Δ. (Why?) 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.

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?

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

23. Is the relation “is at least as old as” symmetric, anti-symmetric, or asymmetric?

24. Is the relation “is a brother of” symmetric?

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

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?

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
    2. reflexive and symmetric but not transitive

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.

29. Prove that for any relation that’s symmetric and transitive, the relation will be serial iff it’s 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.

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