Set Theory Practice Questions

The operation $\Delta$ is defined as $A \Delta B = (A-B) \cup (B-A)$, which is the symmetric difference.

1. Closure: For any $A, B \in 2^X$, $A \Delta B$ is also a subset of $X$, so $A \Delta B \in 2^X$. Thus, $H$ is closed under $\Delta$.
2. Associativity: The symmetric difference operation is associative, i.e., $(A \Delta B) \Delta C = A \Delta (B \Delta C)$.
3. Identity element: The empty set $\phi$ is the identity element, because $A \Delta \phi = (A-\phi) \cup (\phi-A) = A \cup \phi = A$.
4. Inverse element: For any $A \in 2^X$, its inverse is $A$ itself, because $A \Delta A = (A-A) \cup (A-A) = \phi \cup \phi = \phi$. Since every element has an inverse, and all other group properties hold, $H$ is a group. Statement (A) is TRUE.
5. Inverse of A is A: As shown above, $A \Delta A = \phi$, so $A$ is its own inverse. Statement (D) is TRUE.
   The complement of $A$ is $X-A$. $A \Delta (X-A) = (A-(X-A)) \cup ((X-A)-A) = (A \cap A) \cup (X-A) = A \cup (X-A) = X$. This is not $\phi$ unless $X = \phi$. So, the inverse of $A$ is not its complement. Statement (C) is FALSE.
   Since $H$ is a group, statement (B) is FALSE.

Let $S$ be a set with 10 elements. We need to find the number of tuples $(A, B)$ such that $A \subseteq B \subseteq S$.
For each element $x \in S$, there are three possibilities:

1. $x \notin B$ (which implies $x \notin A$ since $A \subseteq B$).
2. $x \in B$ but $x \notin A$.
3. $x \in A$ (which implies $x \in B$ since $A \subseteq B$).

Since there are 10 elements in $S$, and each element has 3 independent choices, the total number of such tuples $(A, B)$ is $3^{10}$.
$3^{10} = 59049$.

The logical formula states that for any prime number $x$ in a given set, there must exist another prime number $w$ in the same set such that $w > x$.

• For S1 ({1, 2, ..., 100}), the statement is false. If we take the prime number $x=97$, there is no larger prime number within the set S1.
• For S2 (set of all positive integers) and S3 (set of all integers), the statement is true. Euclid's theorem proves that there are infinitely many prime numbers. Therefore, for any prime $x$, there is always a larger prime $w$ in these sets.

The set A contains pairs (x, X) where X is a non-empty subset of U and x is an element of X. We can find the size of A by summing over all possible subset sizes, k. For a given k, there are $\binom{n}{k}$ subsets of size k. For each such subset, there are k choices for the element x. Thus, $|A| = \sum_{k=1}^{n} k \binom{n}{k}$, which validates statement II. By the combinatorial identity $\sum_{k=1}^{n} k \binom{n}{k} = n2^{n-1}$, statement I is also true. Therefore, both statements are correct.

Let's analyze the countability of each set:
P: The set of rational numbers ($\mathbb{Q}$) is countable. This can be demonstrated by creating a one-to-one correspondence with the natural numbers.
Q: The set of functions from $\{0, 1\}$ to $\mathbb{N}$. Each function is uniquely determined by the pair of values $(f(0), f(1))$. This set is equivalent to $\mathbb{N} \times \mathbb{N}$, which is the Cartesian product of two countable sets and is therefore countable.
R: The set of functions from $\mathbb{N}$ to $\{0, 1\}$. This set is equivalent to the set of all infinite binary sequences, which has the same cardinality as the power set of $\mathbb{N}$. By Cantor's theorem, this set is uncountable.
S: The set of all finite subsets of $\mathbb{N}$ is countable.
Thus, the countable sets are P, Q, and S.

This problem can be modeled using graph theory. Let the 23 compounds be vertices and a reaction between two compounds be an edge. The degree of a vertex is the number of compounds it reacts with. We are given that 9 vertices (compounds in set S) have a degree of 3, which is an odd number.

A fundamental theorem in graph theory states that the number of vertices with an odd degree in any graph must be even. Since we already have 9 vertices with an odd degree, there must be at least one more vertex with an odd degree among the remaining 14 vertices (in U \ S) to make the total count of odd-degree vertices even. Therefore, at least one compound in U \ S must react with an odd number of compounds. This makes statement II always true.

The function's behavior is analyzed by tracing values. For any even number $n$, $f(n) = f(n/2)$. For any odd number $n$, $f(n) = f(n+5)$.

1. $f(1) = f(6) = f(3) = f(8) = f(4) = f(2) = f(1)$. Also $f(7)=f(12)=f(6)$, and $f(9)=f(14)=f(7)$. This group of values all map to a single output value, let's call it $v_1$.
2. $f(5) = f(10) = f(5)$. This forms a second distinct output value, $v_2$.
3. The values explored in point 1, such as $f(6), f(7), f(9)$, form a third distinct value group, $v_3$.
   Any integer $n$ will eventually fall into one of these three recursive patterns. Therefore, the set $R$ of distinct values contains a maximum of 3 elements.

Given the set A = {5, {6}, {7}}, its power set $2^A$ contains all possible subsets of A.
$2^A = \{\phi, \{5\}, \{\{6\}\}, \{\{7\}\}, \{5, \{6\}\}, \{5, \{7\}\}, \{\{6\}, \{7\}\}, \{5, \{6\}, \{7\}\}\}$.

I. $\phi \in 2^A$: True. The empty set is an element of every power set.
II. $\phi \subseteq 2^A$: True. The empty set is a subset of every set.
III. $\{5, \{6\}\} \in 2^A$: True. This is an element of the power set as listed above.
IV. $\{5, \{6\}\} \subseteq 2^A$: False. This would require 5 and {6} to be elements of $2^A$, which they are not.
Thus, statements I, II, and III are true.

An onto (surjective) function from a set X of size 4 to a set Y of size 3 requires that every element in Y is mapped to. This means one element in Y must be the image of two elements from X, and the other two elements in Y will be images of one element each.

First, choose the two elements from X that will map to the same element in Y. This can be done in $^4C_2 = \frac{4 \times 3}{2} = 6$ ways.
Now, we have three groups to map to the three distinct elements of Y: the pair of elements chosen, and the two remaining single elements. These three groups can be mapped to the three elements of Y in $3! = 6$ ways.
The total number of onto functions is the product of these two values: $6 \times 6 = 36$.

Let $S = \{1, 2, 3, 4, 5, 6\}$ and $U$ be the power set of $S$. This means $|S|=6$.

Let's evaluate each option:

A. $\forall X \in U \; (|X|=|X'|)$
This statement claims that for every subset $X$, its size is equal to the size of its complement. This would imply $|X| = |S| - |X|$, so $2|X| = |S|$. For $S=\{1,2,3,4,5,6\}$, we need $2|X|=6$, which means $|X|=3$. This is not true for all $X \in U$. For example, if $X=\{1\}$, $|X|=1$ and $|X'|=5$, so $|X| \neq |X'|$.

B. $\exists X \in U \; \exists Y \in U \; (|X|=5,\; |Y|=5 \; \text{and} \; X \cap Y=\phi )$
This statement claims there exist two subsets $X$ and $Y$ such that $|X|=5$, $|Y|=5$, and they are disjoint. If $|X|=5$ and $|Y|=5$, and $X \cap Y = \phi$, then $|X \cup Y| = |X| + |Y| = 5+5=10$. However, $X \cup Y$ must be a subset of $S$, so $|X \cup Y| \le |S|=6$. Since $10 \not\le 6$, this statement is false.

C. $\forall X \in U \; \forall Y \in U \; (|X|=2,\; |Y|=3 \; \text{and} \; X \setminus Y=\phi )$
This statement claims that for all subsets $X$ and $Y$ with $|X|=2$ and $|Y|=3$, $X \setminus Y = \phi$. The condition $X \setminus Y = \phi$ means that $X$ is a subset of $Y$ ($X \subseteq Y$). It is not true that every set $X$ of size 2 is a subset of every set $Y$ of size 3. For example, let $X=\{1,2\}$ and $Y=\{3,4,5\}$. Then $X \setminus Y = \{1,2\} \neq \phi$.

D. $\forall X \in U \; \forall Y \in U \; (X \setminus Y=Y' \setminus X')$
Let's analyze the expression $X \setminus Y$. This represents the set of elements in $X$ that are not in $Y$, which is equivalent to $X \cap Y'$.
Now consider $Y' \setminus X'$. This represents the set of elements in $Y'$ that are not in $X'$, which is equivalent to $Y' \cap (X')'$.
Since $(X')'$ is $X$, the expression becomes $Y' \cap X$.
By the commutativity of intersection, $Y' \cap X = X \cap Y'$.
Therefore, $X \setminus Y = Y' \setminus X'$ is always true.

The final answer is $\boxed{D}$

The question in the provided PDF refers to the set {0, 1, 2, 10}. This set contains 4 distinct elements.
The cardinality of the power set of a finite set with 'n' elements is given by the formula $2^n$.
In this case, n = 4.
Therefore, the number of elements in the power set is $2^4 = 16$.

Let $S = \{1, 2, \ldots, 2014\}$. The relation $U < V$ means that the minimum element in the symmetric difference $U \Delta V = (U \setminus V) \cup (V \setminus U)$ is in $U$.

For statement S1: We are looking for a subset $U$ such that $V < U$ for all other distinct subsets $V$. This means that for any $V \neq U$, the minimum element of $U \Delta V$ must be in $V$. If we choose $U = \emptyset$ (the empty set), then for any $V \neq \emptyset$, $U \Delta V = (\emptyset \setminus V) \cup (V \setminus \emptyset) = \emptyset \cup V = V$. The minimum element of $V$ is in $V$, so $V < \emptyset$ is true for all $V \neq \emptyset$. Thus, the empty set is larger than every other subset, making S1 true.

For statement S2: We are looking for a subset $U$ such that $U < V$ for all other distinct subsets $V$. This means that for any $V \neq U$, the minimum element of $U \Delta V$ must be in $U$. If we choose $U = S$ (the universal set), then for any $V \neq S$, $U \Delta V = (S \setminus V) \cup (V \setminus S) = (S \setminus V) \cup \emptyset = S \setminus V$. The minimum element of $S \setminus V$ is in $S \setminus V$. Since $S \setminus V \subseteq S = U$, its minimum element is also in $U$. So $S < V$ is true for all $V \neq S$. Thus, the universal set is smaller than every other subset, making S2 true.

Since both statements S1 and S2 are true, option A is correct.

Let's analyze the properties of the function $f$ and its inverse image $f^{-1}$. Statements A, B, and C are generally false and only hold under specific conditions (e.g., injectivity for B). A simple counterexample for B is a non-injective function: let $X=\{1,2\}, Y=\{3\}$, $f(1)=f(2)=3$, and $A=\{1\}, B=\{2\}$. Then $f(A \cap B) = f(\emptyset) = \emptyset$, but $f(A) \cap f(B)=\{3\} \cap \{3\}=\{3\}$.

We will prove statement D is true by showing that an element belongs to the left-hand set if and only if it belongs to the right-hand set. By definition of the inverse image, an element $x \in X$ belongs to $f^{-1}(S \cap T)$ if and only if its image $f(x)$ is in $S \cap T$.

The condition $f(x) \in S \cap T$ is equivalent to the conjunction $f(x) \in S$ and $f(x) \in T$.

Again, by the definition of the inverse image, this is equivalent to $x \in f^{-1}(S)$ and $x \in f^{-1}(T)$.

Since an element $x$ is in $f^{-1}(S \cap T)$ if and only if it is in $f^{-1}(S) \cap f^{-1}(T)$, the two sets are equal. This property holds for any function.

To check for commutativity, we evaluate $x \oplus y$ and $y \oplus x$:

1. Commutativity:
   $x \oplus y = x^2 + y^2$
   $y \oplus x = y^2 + x^2$
   Since addition of integers is commutative, $x^2 + y^2 = y^2 + x^2$. Thus, $x \oplus y = y \oplus x$, and the operation is commutative.

To check for associativity, we evaluate $(x \oplus y) \oplus z$ and $x \oplus (y \oplus z)$:
2. Associativity:
$(x \oplus y) \oplus z = (x^2 + y^2) \oplus z = (x^2 + y^2)^2 + z^2$
$x \oplus (y \oplus z) = x \oplus (y^2 + z^2) = x^2 + (y^2 + z^2)^2$
For the operation to be associative, $(x^2 + y^2)^2 + z^2$ must equal $x^2 + (y^2 + z^2)^2$ for all integers $x, y, z$.
Let $x=1, y=2, z=3$:
$(1 \oplus 2) \oplus 3 = (1^2 + 2^2) \oplus 3 = (1+4) \oplus 3 = 5 \oplus 3 = 5^2 + 3^2 = 25 + 9 = 34$.
$1 \oplus (2 \oplus 3) = 1 \oplus (2^2 + 3^2) = 1 \oplus (4+9) = 1 \oplus 13 = 1^2 + 13^2 = 1 + 169 = 170$.
Since $34 \neq 170$, the operation is not associative.

The operation is commutative but not associative.