Question

Proposition 16.4 Let S be a non–empty finite set.

(a) There is a unique n 2 N1 such that there is a 1–1
correspondence from {1, 2,...,n} to S.

We write |S| = n. Also, we write |;| = 0.

(b) If B is a set and f : B ! S is a 1–1 correspondence, then B is
finite and |B| = |S|.

(c) If T is a proper subset of S, then T is finite and |T| <
|S|.

Prove part b.

Answer #1

we have to prove part (b)

is a one to one correspondence

we know the definition of one to one map if or

so image of i.e then is finite

and given set is finite , and there is a one to one correspondence between to finite set ,

hence

Let X be a non-empty finite set with |X| = n. Prove that the
number of surjections from X to Y = {1, 2} is (2)^n− 2.

Theorem 16.11 Let A be a set. The set A is infinite if and only
if there is a proper subset B of A
for which there exists a 1–1 correspondence f : A -> B.
Complete the proof of Theorem 16.11 as follows: Begin by
assuming that A is infinite.
Let a1, a2,... be an infinite sequence of distinct elements of A.
(How do we know such a sequence
exists?) Prove that there is a 1–1 correspondence between the...

Let S denote the set of all possible finite binary strings, i.e.
strings of finite length made up of only 0s and 1s, and no other
characters. E.g., 010100100001 is a finite binary string but
100ff101 is not because it contains characters other than 0, 1.
a. Give an informal proof arguing why this set should be
countable. Even though the language of your proof can be informal,
it must clearly explain the reasons why you think the set should...

Let A be a non-empty set and f: A ? A be a function.
(a) Prove that, if f is injective but not surjective (which
means that the set A is infinite), then f has at least two
different left inverses.

Let G be a non-trivial finite group, and let H < G be a
proper subgroup. Let X be the set of conjugates of H, that is, X =
{aHa^(−1) : a ∈ G}. Let G act on X by conjugation, i.e., g ·
(aHa^(−1) ) = (ga)H(ga)^(−1) .
Prove that this action of G on X is transitive.
Use the previous result to prove that G is not covered by the
conjugates of H, i.e., G does not equal...

Let V be a vector space: d) Suppose that V is
finite-dimensional, and let S be a set of inner products on V that
is (when viewed as a subset of B(V)) linearly independent. Prove
that S must be finite
e) Exhibit an infinite linearly independent set of inner
products on R(x), the vector space of all polynomials with real
coefficients.

Let A be a finite set and let f be a surjection from A to
itself. Show that f is an injection.
Use Theorem 1, 2 and corollary 1.
Theorem 1 : Let B be a finite set and let f be a function on B.
Then f has a right inverse. In other words, there is a function g:
A->B, where A=f[B], such that for each x in A, we have f(g(x)) =
x.
Theorem 2: A right inverse...

Let S be a finite set and let P(S) denote the set of all subsets
of S. Define a relation on P(S) by declaring that two subsets A and
B are related if A and B have the same number of elements.
(a) Prove that this is an equivalence relation.
b) Determine the equivalence classes.
c) Determine the number of elements in each equivalence
class.

We denote |S| the number of elements of a set S. (1) Let A and B
be two finite sets. Show that if A ∩ B = ∅ then A ∪ B is finite and
|A ∪ B| = |A| + |B| . Hint: Given two bijections f : A → N|A| and g
: B → N|B| , you may consider for instance the function h : A ∪ B →
N|A|+|B| defined as h (a) = f (a)...

Let (G,·) be a finite group, and let S be a set with the same
cardinality as G. Then there is a bijection μ:S→G . We can give a
group structure to S by defining a binary operation *on S, as
follows. For x,y∈ S, define x*y=z where z∈S such that μ(z) =
g_{1}·g_{2}, where μ(x)=g_{1} and μ(y)=g_{2}. First prove that
(S,*) is a group. Then, what can you say about the bijection μ?

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 30 minutes ago

asked 42 minutes ago

asked 49 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago