Intereting Posts

Does there exist a function that is continuous at every rational point and discontinuous at every irrational point? And vice versa?
Smooth affine plane curve with non-trivial cotangent sheaf?
Finding points on ellipse
Help with null hypothesis
Aunt and Uncle's fuel oil tank dip stick problem
Find all integer solutions to Diophantine equation $x^3+y^3+z^3=w^3$
Lines in the plane and recurrence relation
Nets – preoredered sets or posets?
Interval of definition of the solutions of $\dot x=e^x\sin x$
Prove if $f(x) = g(x)$ for each rational number x and $f$ and $g$ are continuous, then $f = g$
Is there exists a $k$-iso-regular ($k \ge 3$) non-planar graph of degree at most three?
Choosing from multiple bins
What kind of matrix norm satisifies $\text {norm} (A*B)\leq \text {norm} (A)*\text {norm} (B)$ in which A is square?
Reconciling Different Definitions of Solvable Group
If $a+b=1$ so $a^{4b^2}+b^{4a^2}\leq1$

I’m stuck on a problem using recursive definitions:

Let $X$ be a finite set. Give a recursive definition of the set of all subsets of $X$. Use Union as the operator in the definition.

I can see how the union of all subsets separately gives a set of all subsets, but I don’t understand how to prove it. I’m not even sure what the base case would be in this situation.

- Why does $\bigcap_{m = 1}^\infty ( \bigcup_{n = m}^\infty A_n)$ mean limsup of sequence of set?
- $f\cap f\supsetneq f$ - Where does the string of equivalences fail ?
- An Intuition to An Inclusion: “Union of Intersections” vs “Intersection of Unions”
- Order preserving bijection from $\mathbb{Q}$ to $\mathbb{Q}\backslash\lbrace{0}\rbrace$
- Why is an empty function considered a function?
- Element of a set?

- The way into set theory
- Induction for statements with more than one variable.
- Why does Cantor's diagonal argument not work for rational numbers?
- How to prove that $\mathbb{Q}$ is not the intersection of a countable collection of open sets.
- What is the result of $\bigcap_{n=1}^{\infty}{(-1/n; 1/n)}$
- how to prove a parametric relation to be a function
- If $(W,<)$ is a well-ordered set and $f : W \rightarrow W$ is an increasing function, then $f(x) ≥ x$ for each $x \in W$
- If $s_{k,m}(n) =\sum_{i=n+1}^{kn+m} \frac1{i} $ show that for $k \ge 2m+1$, $s_{k,m}(n+1)>s_{k,m}(n)$ and $s_{k,m}(n+1)-s_{k,m}(n) <\frac1{n(n+1)} $
- Prove, formally that: $\log_2 n! \ge n$ , for all integers $n>3$.
- Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$

For induction you have to define some explicit base case, what is the smallest finite set? The empty set. Define its power set explicitly.

Now suppose that you defined the power set of a set with $n$ elements, and $A=\{a_0,\ldots,a_n,a_{n+1}\}$, find a way to write $A$ as the union of $A’$ and a singleton, with $A’$ having $n$ elements; now ask yourself, what sort of subsets of $A$ are there, and how do they relate to subsets of $A’$ and that additional singleton?

Since you’re a computer science student (according to the user’s profile), here is another way to think about it.

Recall that there is a canonical identification between subsets of $\{0,\ldots,n-1\}$ and binary strings of length $n$. Namely, $A\subseteq\{0,\ldots,n-1\}$ is mapped to the string $\langle a_0,\ldots,a_{n-1}\rangle$ such that $a_i=0$ if and only if $i\notin A$.

Now you can think about this as defining a string of length $n+1$ as a concatenation of a string of length $n$ with either $0$ or $1$.

Let $X_n = \{1, 2, \dotsc, n\}$ be the finite set of $n$ elements (unique up to a bijective morphism). Denote the power set of a set $X_i$ as $\mathcal{P}(X_i)$. Let’s write out the first few power sets of these finite sets:

$$\begin{align}

\mathcal{P}(X_0) = \mathcal{P}(\{\}) &= \{\{\}\} \\

\mathcal{P}(X_1) = \mathcal{P}(\{1\}) &= \{\{\},\{1\}\} \\

\mathcal{P}(X_2) = \mathcal{P}(\{1,2\}) &= \{\{\},\{1\},\{2\},\{1,2\}\} \\

\mathcal{P}(X_3) = \mathcal{P}(\{1,2,3\}) &= \{\{\},\{1\},\{2\},\{1,2\},

\{3\},\{1,3\},\{2,3\},\{1,2,3\},\} \\

\end{align}$$

We can see that each $\mathcal{P}(X_i)$ consists of elements $s$ and $s\cup \{i\}$ for each $s \in \mathcal{P}(X_{i-1})$. In other words:

$$

\mathcal{P}(X_i) \;=

\bigcup_{s \in \mathcal{P}(X_{i-1})} \Big\{s, s\cup\{i\}\Big\} \;\;=\;\;

\mathcal{P}(X_{i-1}) \cup \big\{s\cup\{i\} \mid s \in \mathcal{P}(X_{i-1})\big\}

$$

Since the set is finite, without loss of generality, assume that $X_n = \{1,2, \ldots, n\}$. Then, note that:

$$\mathcal{P}(X_1) = \mathcal{P}(\{1\}) = \{\phi,\{1\} \} = \{\phi, X_1\}$$

$$\mathcal{P}(X_n) = \mathcal{P}(X_{n-1}) \cup \{Y \cup \{n\} : Y \in\mathcal{P}(X_{n-1})\}\; \forall \; n \ge 2$$

This is a recursive definition of $\mathcal{P}(X_n)$ with only union as the operation in the definition. In language of sets, the power set of $X = X_n$ is just the union of power set of $X_{n-1}$ and the set of unions of $\{n\}$ with elements of $\mathcal{P}(X_{n-1}) \; \forall \; n \ge 2$.

One can show that:

$$P(A\cup B)=\{a\cup b : (a,b)\in P(A)\times P(B)\}$$

which is a recursive definition (very clearly if we take $B$ to be a singleton disjoint from $A$). It states that to get the power set of a union $A\cup B$, we choose any pair of a subset $a\subseteq A$ and $b\subseteq B$ and take their union. In particular, for disjoint $A$ and $B$, we can show, using the above definition, that:

$$|P(A\cup B)| = |P(A)|\cdot |P(B)|$$

implying that the size of a power set is exponential in the size of the original set. Computing the power set of a singleton set $\{s\}$ tells you the base of the exponent.

- Proof that Newton Raphson method has quadratic convergence
- Lie algebras and roots systems
- How to solve this recurrence Relation – Varying Coefficient
- Uniform continuity of $x^3+ \sin x$
- How can I write the Axiom of Specification as a sentence?
- Inequality involving absolute values and square roots
- Is my understanding of antisymmetric and symmetric relations correct?
- How can I show that $\sup(AB)\geq\sup A\sup B$ for $A,B\subset\mathbb{R}$ where $A\cup B$ is positive and bounded?
- How does one derive Radial Basis Function (RBF) Networks as the smoothest interpolation of points?
- Finding $\int^1_0 \frac{\log(1+x)}{x}dx$ without series expansion
- Are projections onto closed complemented subspaces of a topological vector space always continuous?
- Weak/strong law of large numbers for dependent variables with bounded covariance
- Why can you chose how to align infinitely long equations when adding them?
- Is it possible for a function to be smooth everywhere, analytic nowhere, yet Taylor series at any point converges in a nonzero radius?
- A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$