bijection between parity preserving subsets and subsets without consecutive pairs 
Define $B_n$ to be the set of subsets of $\{1,\cdots, n\}$ that have no consecutive elements and $A_n$ to be the set of subsets of $\{1,\cdots, n\}$ that are parity-preserving (this includes the empty set). Here's my attempt to define a bijection $f : A_n \to B_n$. Let $P\in A_n.$ We let $f(P) = P',$ where $P'$ is obtained by the following algorithm: If $P$ has no consecutive elements, we stop. Otherwise, if there is an odd-length consecutive block that ends, then all elements with even-numbered positions are removed, and the process repeats. If there is an even-length consecutive block that ends, then all elements with odd-numbered positions are removed, and the process repeats.

Here is a demonstration of the algorithm for the case $\{1,2,5,6,7,8\}.$ There is an even-length consecutive block $\{1,2\}$ that ends (in $5$), so we remove the $1$ as it's in an odd-numbered position. We repeat the process on $\{2,5,6,7,8\}.$ There is an even-length consecutive block $\{5,6,7,8\},$ so we remove the odd-numbered elements to obtain $\{2,6,8\}.$ Below is a mapping from $A_5$ to $B_5$.
$\{5\}\mapsto \{5\}\\
\{1,4,5\} \mapsto \{1,5\}\\
\{3,4,5\}\mapsto \{3,5\}\\
\{1,2,5\}\mapsto \{2,5\}\\
\{1,2,3,4,5\}\mapsto \{1,3,5\}\\
\{\}\mapsto \{\}\\
\{1\}\mapsto \{1\}\\
\{3\}\mapsto \{3\}\\
\{1,2\}\mapsto \{2\}\\
\{1,4\}\mapsto \{1,4\}\\
\{3,4\}\mapsto \{4\}\\
\{1,2,3\}\mapsto \{1,3\}\\
\{1,2,3,4\}\mapsto \{2,4\}.$
Now here's my attempt to define the inverse. Let $B := \{\alpha_1,\cdots, \alpha_k\}\in B_n.$ We define the result of $f^{-1}(\{\alpha_1,\cdots, \alpha_k\})$ for $1\leq i \leq k.$ If $B$ is parity preserving, we return $B$. If $i$ and $\alpha_i$ differ in parity, then insert $\alpha_i - 1$ directly before $\alpha_i,$ and repeat. Here is a demonstration for $\{2,6,8\}.$ $2$ is even but in position $1$, so we insert $2-1 = 1$ before it, obtaining $\{1,2,6,8\}.$ Similarly, we insert $5$ before $6$ to get $\{1,2,5,6\}$. And we insert $7$ before $8$ to obtain $f^{-1}(\{2,6,8\}) = \{1,2,5,6,7,8\}.$

Are these attempts correct? If not, what would be a correct bijection?


Edit: For clarification and completeness, here is the definition of a parity preserving subset of $\{1,\cdots, n\}.$ A parity-preserving subset of $\{1,\cdots, n\}$ is a subset $\{\alpha_1,\cdots, \alpha_k\}$ of $\{1,\cdots, n\}$ so that for every $i, \alpha_i < \alpha_{i+1}$ and $\alpha_i \cong i \mod 2.$

 A: Yes, what you have appears to work, but I would start with your second algorithm: it’s actually a bit simpler, since it works one element at a time.
Define $g:B_n\to A_n$ as follows. Let $P=\{a_1,\ldots,a_m\}$ have no consecutive members, where $a_1<\ldots<a_m$. If $a_1$ is odd, let $P_1=\{a_1\}$; otherwise, let $P_1=\{a_1-1,a_1\}$. Suppose that $1\le k<m$, and we’ve defined $P_k$. If $P_k\cup\{a_{k+1}\}$ is parity-preserving, let $P_{k+1}=P_k\cup\{a_{k+1}\}$; otherwise, let $P_{k+1}=P_k\cup\{a_{k+1}-1,a_{k+1}\}$. Then $g(P)=P_m$ is parity-preserving. This really is just your insertion algorithm.
Now let $P=\{a_1,\ldots,a_m\}$ be parity-preserving, where $a_1<\ldots<a_m$. Partition $P$ into maximal subsets of consecutive integers.

For instance, $\{1,2,5,6,7,8,11,14,15,16\}$ is partitioned into the sets $\{1,2\}$, $\{5,6,7,8\}$, $\{11\}$, and $\{14,15,16\}$.

If $S$ is one of these sets, let $S'=\{k\in S:k\equiv\max S\pmod2\}$; this has the effect of omitting every second member of $S$ counting down from $\max S$. Let $f(P)$ be the union of the sets $S'$; then $f(P)$ has no consecutive elements.

In the example we have $\{1,2\}'=\{2\}$, $\{5,6,7,8\}'=\{6,8\}$, $\{11\}'=\{11\}$, $\{14,15,16\}'=\{14,16\}$, and $f(P)=\{2,6,8,11,14,16\}$.

It’s not too hard to check now that $f$ and $g$ are mutual inverses and hence bijections.
