Question

In: Advanced Math

Recognizing partitions - sets of strings. (b) Let A be the set of words in the...

Recognizing partitions - sets of strings.

(b) Let A be the set of words in the Oxford English Dictionary (OED). For each positive integer j, define Aj to be the set of all words with j letters in the OED. For example, the word "discrete" is an element of A8 because the word "discrete" has 8 letters. The longest word in the OED is "pneumonoultramicroscopicsilicovolcanoconiosis" which has 45 letters. You can assume that for any integer i in the range 1 through 45, there is at least one word in the OED that has i letters. Do the sets A1, …, A45 form a partition of the set of words in the OED?

(don't give explanation with reflexive, symmetric and transitive because we haven't learn it yet)

Solutions

Expert Solution

Recognizing partitions - sets of strings.

(b) Let A be the set of words in the Oxford English Dictionary (OED). For each positive integer j, define Aj to be the set of all words with j letters in the OED


Related Solutions

A)Let S = {1,2,3,...,18,19,20} be the universal set. Let sets A and B be subsets of...
A)Let S = {1,2,3,...,18,19,20} be the universal set. Let sets A and B be subsets of S, where: Set A={3,4,9,10,11,13,18}A={3,4,9,10,11,13,18} Set B={1,2,4,6,7,10,11,12,15,16,18}B={1,2,4,6,7,10,11,12,15,16,18} LIST the elements in Set A and Set B: {  } LIST the elements in Set A or Set B: {  } B)A ball is drawn randomly from a jar that contains 4 red balls, 5 white balls, and 9 yellow balls. Find the probability of the given event. Write your answers as reduced fractions or whole numbers. (a) PP(A...
Let A and B be sets. Then we denote the set of functions with domain A...
Let A and B be sets. Then we denote the set of functions with domain A and codomain B as B^A. In other words, an element f∈B^A is a function f:A→B. Prove: Let ?,?∈?^? (that is, ? and ? are real-valued functions with domain ?) and define a relation ≡ on ?^? by ?≡?⟺?(0)=?(0). (That is, ? and ? are equivalent if and only if they share the same value at ?=0) Then ≡ is an equivalence relation on  ?^?. Prove:...
2. Let S be the set of strings over the alphabet Σ = {a, b, c}...
2. Let S be the set of strings over the alphabet Σ = {a, b, c} defined recursively by (1) λ ∈ S and a ∈ S; and (2) if x ∈ S, then bxc ∈ S. Recall that λ denotes the empty string which has no letters and has length 0. List all strings of S which are length at most seven. 3. Prove the following theorem by induction: For every integer n ≥ 1, 1 · 2 +...
Let A and B be sets, and let R be a relation from A to B....
Let A and B be sets, and let R be a relation from A to B. Prove that Rng(R^-1) = Dom(R)
Let A, B be sets and f : A → B and g : B →...
Let A, B be sets and f : A → B and g : B → C . Characterize when g ◦ f : A → C is a bijection.
Let A and B be sets of real numbers such that A ⊂ B. Find a...
Let A and B be sets of real numbers such that A ⊂ B. Find a relation among inf A, inf B, sup A, and sup B. Let A and B be sets of real numbers and write C = A ∪ B. Find a relation among sup A, sup B, and sup C. Let A and B be sets of real numbers and write C = A ∩ B. Find a relation among sup A, sup B, and sup...
Let A and B be finite sets. Prove the following: (a) |A∪B|=|A|+|B|−|A∩B| (b) |A × B|...
Let A and B be finite sets. Prove the following: (a) |A∪B|=|A|+|B|−|A∩B| (b) |A × B| = |A||B| (c) |{f : A → B}| = |B||A|
Recall that the set {0,1}∗ is the set of all finite-length binary strings. Let f:{0,1}∗→{0,1}∗ to...
Recall that the set {0,1}∗ is the set of all finite-length binary strings. Let f:{0,1}∗→{0,1}∗ to be f(x1x2…xk)=x2x3…xkx1. That is, f takes the first bit of a string x and moves it to the end of x, so for example a string 100becomes 001; if |x|≤1, then f(x)=x Also, suppose that g:{0,1}∗→{0,1}∗ is a function such that g(x1…xk)=0x1…xk (that is, gg puts an extra 0 in front of the given string, so for example g(100)=0100. Everywhere in this question we...
Let A be an infinite set and let B ⊆ A be a subset. Prove: (a)...
Let A be an infinite set and let B ⊆ A be a subset. Prove: (a) Assume A has a denumerable subset, show that A is equivalent to a proper subset of A. (b) Show that if A is denumerable and B is infinite then B is equivalent to A.
Let N(n) be the number of all partitions of [n] with no singleton blocks. And let...
Let N(n) be the number of all partitions of [n] with no singleton blocks. And let A(n) be the number of all partitions of [n] with at least one singleton block. Prove that for all n ≥ 1, N(n+1) = A(n). Hint: try to give (even an informal) bijective argument.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT