Intereting Posts

Show that the $\max{ \{ x,y \} }= \frac{x+y+|x-y|}{2}$.
Simply this exponential integral
Combinatorics/Probability – Why does this equation work?
no cycles if and only if has $n-m$ connected components
Correspondence between Ext group and extensions (from Weibel's book)
$TT^*=T^2$, show that $T$ is self-adjoint
An Example of a Nested Decreasing Sequence of Bounded Closed Sets with Empty Intersection
Prove that – for every positive $x \in \mathbb{Q}$, there exists positive $y \in \mathbb{Q}$ for which $y \lt x$
If ring $B$ is integral over $A$, then an element of $A$ which is a unit in $B$ is also a unit in $A$.
How to prove the ring of Laurent polynomials over a field is a principal ideal domain?
existence of sequence of polynomial
Meaning of correlation
How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?
Existence of a Riemannian metric inducing a given distance.
A graph of all of mathematics

Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$.

I know that the number of elements of the power set of $A$ is $2^n$, i.e. $|\mathcal{P}(A)|=2^n$.

I came across the fact that exactly half of the elements of $\mathcal{P}(A)$ contain an odd number of elements, and half of them an even number of elements.

- How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?
- Is $\{\emptyset\}$ a subset of $\{\{\emptyset\}\}$?
- de morgan law $A\setminus (B \cap C) = (A\setminus B) \cup (A\setminus C) $
- If A, B, and C are set and $A \subset B ,B \subset C \rightarrow A \subset C$
- Division of cardinals
- Proof of the definition of cardinal exponentiation

Can someone prove this? Or hint at a proof?

- If $g \circ f$ is surjective, show that $f$ does not have to be surjective?
- Do Cantor's Theorem and the Schroder-Bernstein Theorem Contradict?
- A set is a finite chain if every subset has a top and bottom element
- To characterize uncountable sets on which there exists a metric which makes the space connected
- Is this a valid proof of $f(S \cap T) \subseteq f(S) \cap f(T)$?
- Proving a set is uncountable
- Correct formulation of axiom of choice
- Show the inverse of a bijective function is bijective
- Overview of basic results on cardinal arithmetic
- Bijection between $\mathbb{R}^n$ and $\mathbb{R}^m$

Fix an element $a\in A$ (this is the point where $A\ne\emptyset$ is needed).

Then $$S\mapsto S\operatorname{\Delta}\{a\}$$ (symmetric difference) is a bijection from the set of odd subsets to the set of even subsets.

**Hint:** One can prove this by induction on the size of $A$. Assume it was true for sets of size $n$ and let $A=\{a_1,\ldots,a_{n+1}\}$. Then every subset of $A$ is either a subset of $\{a_1,\ldots,a_n\}$ or it is a copy of such subset with the addition of $\{a_{n+1}\}$. Use the induction hypothesis to conclude that the sets which do not contain $a_{n+1}$ have this property (with respect to $\{a_1,\ldots,a_n\}$, by adding $a_{n+1}$ you send exactly the same number of odd sets to even size sets, and vice versa; therefore the ratio remains true for $A$.

For $n\in\Bbb Z^+$ let $[n]=\{1,2,\dots,n\}$. Clearly $[1]$ has one even subset and one odd subset. Suppose that $[n]$ has equal numbers of odd and even subsets for some $n\in\Bbb Z^+$. The even subsets of $[n+1]$ are of two types:

- the even subsets of $[n]$; and
- the sets of the form $A\cup\{n+1\}$, where $A$ is an odd subset of $[n]$.

By the induction hypotheses there are the same number of sets of the second type as there are of the first, so $[n+1]$ has twice as many even subsets as $[n]$. But $[n+1]$ also has twice as many subsets altogether as $[n]$, so it must have twice as many odd subsets as well, which clearly implies that it has equal numbers of odd and even subsets.

Suppose $n=|A|$. Then there are $$\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}=2^{n-1}$$ sets with even cardinality. Thus, there are exactly half of the sets with an even number of elements.

When $n$ is odd, look at each set and its complement: one will have even number of elements and the other, odd (because odd number can only be written as a sum of an odd and an even number).

When $n$ is even, remove an element to obtain a set with odd number of elements. By the first part, half of its subsets have even cardinality and half odd. Now to form the full $\mathcal P(A)$, we need to join the remainin element to each of the previous subsets: those with odd cardinality with become even, and viceversa.

You can use proprieties of the binomial coefficients.

Denote $\mathcal{P}_k(A)$ the family of subsets of $A$ containing $k$ elements and observe

$|\mathcal{P}_k(A)| = {n \choose k}$ .

Now by a propriety of binomial coefficients $\sum_{k=0}^{n/2} {n \choose 2k} =\sum_{k=0}^{n/2} ({n-1 \choose 2k-1} + {n-1 \choose 2k}) = \sum_{k=0}^{n-1} {n-1 \choose k}$ and similarly $\sum_{k=0}^{n/2-1} {n \choose 2k+1} =\sum_{k=0}^{n/2-1} ({n-1 \choose 2k} + {n-1 \choose 2k+1}) = \sum_{k=0}^{n-1} {n-1 \choose k}$ .

This shows that $\sum_{k=0}^{n/2}|\mathcal{P}_{2k}(A)| = \sum_{k=0}^{n/2-1}|\mathcal{P}_{2k+1}(A)|$ .

Number the members of the set $1,2,3,4,\ldots,n$.

For every subset with an even number of elements, there is a corresponding set with an odd number of elements, that corresponds in this way:

- If $1$
**is**a member of the set with an even number of elements, then delete $1$ from the set to get a set with an odd number of elements. - If $1$ is
**not**a member of the set with an even number of elements, then add $1$ to the set to get a set with an odd number of elements.

For example, suppose the set is $\{1,2,3,4\}$. Then we have this correspondence between sets with an even number of elements and sets with an odd number of elements:

$$

\begin{array}{rcl}

\text{even} & & \text{odd} \\

\hline

\varnothing & \leftrightarrow & \{1\} \\

\{1,2\} & \leftrightarrow & \{2\} \\

\{1,3\} & \leftrightarrow & \{3\} \\

\{1,4\} & \leftrightarrow & \{4\} \\

\{2,3\} & \leftrightarrow & \{1,2,3\} \\

\{2,4\} & \leftrightarrow & \{1,2,4\} \\

\{3,4\} & \leftrightarrow & \{1,3,4\} \\

\{1,2,3,4\} & \leftrightarrow & \{2,3,4\}

\end{array}

$$

This won’t work with the empty set because we don’t have an element to which we can assign the number $1$.

- Are all fields vector spaces?
- How to detect when continued fractions period terminates
- Does finite expectation imply bounded random variable?
- Extension of regular function
- Does there exist a matrix $\mathbf{A}\in\mathbb{R}^{3\times3}$ such that $\mathbf{A}^{2}=-\mathbf{I}$?
- Show that the area of a triangle is given by this determinant
- Drawing a thickened Möbius strip in Mathematica
- Quaternion – Angle computation using accelerometer and gyroscope
- Could the concept of “finite free groups” be possible?
- Intuitive Aproach to Dolbeault Cohomology
- Why is the Hilbert Cube homogeneous?
- Prove $\int_{0}^{\pi/2} x\csc^2(x)\arctan \left(\alpha \tan x\right)\, dx = \frac{\pi}{2}\left$
- How to solve exact equations by integrating factors?
- Asymmetric Random Walk / Prove that $T:= \inf\{n: X_n = b\}$ is a $\{\mathscr F_n\}_{n \in \mathbb N}$-stopping time
- 4-Manifolds of which there exist no Kirby diagrams