AskSia

Plus

Week 12 In-Class Exercises 1. Suppose that

A

and

B

are sets. If

A

and

B

...

Nov 27, 2024

Hi Quentin! It looks like you have some exercises related to set cardinalities. Let's break down the questions one by one. (a) Show that if

A

and

B

are finite, then the sum and product definitions above agree with the sum and product of non-negative integers. To show this, you can consider the definitions of the cardinalities. If

A

has

m

elements and

B

has

n

elements, then: - The cardinality of their union (since they are disjoint) is

|A \cup B| = |A| + |B| = m + n

. - The cardinality of their Cartesian product is

|A \times B| = |A| \cdot |B| = m \cdot n

. Thus, the definitions of sum and product of cardinalities align with the standard arithmetic of non-negative integers. (b) Explain why these operations are commutative and associative. - Commutativity: For the sum,

|A| + |B| = |B| + |A|

holds because the union of disjoint sets does not depend on the order of the sets. For the product,

|A| \cdot |B| = |B| \cdot |A|

holds because the Cartesian product is also independent of the order of the sets. - Associativity: For the sum,

(|A| + |B|) + |C| = |A| + (|B| + |C|)

holds because you can group the sets in any way when taking their union. For the product,

|A| \cdot (|B| \cdot |C|) = (|A| \cdot |B|) \cdot |C|

holds because the Cartesian product can be grouped in any way. (c) Show that if

|A| \leq |C|

and

|B| \leq |D|

then

|A| + |B| \leq |C| + |D|

. You can use the definition of cardinality and the properties of inequalities. Since

|A| \leq |C|

means there exists an injection from

A

C

, and similarly for

B

D

, you can construct a combined injection from

A \cup B

C \cup D

to show that the sum of the cardinalities holds. (d) Show that if

|A| \leq |C|

and

|B| \leq |D|

then

|A| \cdot |B| \leq |C| \cdot |D|

. Similar to part (c), you can use the definition of cardinality. If there are injections from

A

C

and from

B

D

, you can create a function that pairs elements from

A

and

B

to elements in

C

and

D

, showing that the product of the cardinalities holds. If you need more detailed explanations or examples for any of these parts, feel free to ask!