# Tagged Questions

37 views

### Proving by induction, if the base case fails to meet the main condition, what do we do?

I have to determine the number $x$ of subsets with odd cardinalities of a set $S$ and then prove that I'm correct. I determined the number $x$ is obtained using the formula $2^{n-1}$ where $|S| = n$. ...
69 views

### If all mappings $f: A\to B$ are many-to-one, does there exist surjective $g: A\to B$?

Suppose sets $A$ and $B$ are such that all mappings $f: A\to B$ are many-to-one (i.e. not injective). Can we prove that there must exist a surjective $g: A\to B$? Ideally, I am hoping to be able to ...
95 views

### Proof Question involving Binary Strings & Sets

I'm just wondering about this question I've been working on for my review homework. I tried to solve it on my own and I feel my proof makes decent sense but not the best sense. Please try to give any ...
23 views

### Help explain the set being constructed in this Cantor-Schroder-Berstein proof

The Cantor-Schroder-Bernstein theorem states that: Suppose $A$ and $B$ are sets. If $|A|\le |B|$ and $|B|\le |A|$, then $|A|=|B|$ Proof: So, $|A|\le|B|$ implies we can choose an injection ...
36 views

### How to prove this version of the Cantor-Schroder-Bernstein theorem?

My text states the Cantor-Schroder-Bernstein theorem as follows: Suppose that $X$ and $Y$ are non-empty sets such that $|X|>|Y|$. Then, any function $f:X\rightarrow Y$ is not an injection, i.e. ...