Proof that the cardinality of the cipher text set is greater than or equal to the cardinality of the plaintext set for a symmetric cryptosystem I have been working on this problem and would appreciate some help
Consider a symmetric cryptosystem with non-empty finite sets $P, C, K$ of plaintexts, ciphertexts, and keys, respectively and with encryption functions $e_k : P \rightarrow C$ and decryption functions $d_k : C \rightarrow P$ indexed by keys $k \in  K$.
Show that $|C| \geqq |P|$

Here is my attempt:
Since $d_k$ is the left inverse of $e_k$ by definition of a cipher
Suppose $e_k(x) = e_k(y)$ then $x = d_k(e_k(x)) = d_k(e_k(y)) = y$ for $x \in P$ and $y \in C$
meaning $e_k$ is injective $\forall k \in K$
Also, $e_k(p) = c \in C, \forall p \in P$
Suppose, for finite sets $P$ and $C$, $|P| \gt |C|$
And, since both $P$ and $C$ are non-empty, then $|C|$ is at least 1 and $|P|$ is at least 2.
Then $\exists a,b \in P$ s.t $a \neq b$ and $e_k(x) = e_k(y)$ which raises a contradiction (as it would mean $e_k$ isnt injective)
Thus, $P \not\gt C$ i.e $|P| \leqq |C|$ or $|C| \geqq |P|$
The start of the proof, concluding $e_k$ is injective for all $k$, is fine. Only the ultra picky would add that $d_k$ is the left inverse of $e_k$ by definition of a cipher, and that the rest of that part considers $x$ and $y$ elements of $P$.
By my taste, the rest using proof by contradiction is on the overly complex and circular side, and less than rigorous: the &quot;Then $\exists a,b \in P$ s.t $a \neq b$ and $e_k(x) = e_k(y)$&quot; is not crystal clear (at least it it does not follow from a stated definition or theorem).
I would change the whole second part to: The cardinality of the destination set of an injection is at least the cardinality of it's source set, by definition of cardinality.
Or, if cardinality is not yet formally defined in the academic context: The size of the destination set of an injection is at least the size of it's source set, by a counting argument. The notion of counting argument is often invoked in crypto, in the context of hash collision, or proof of existence.
If we do want to make a proof by contradiction, one could invoke the pigeonhole principle, also common in crypto, on the tune of: $\lvert C\rvert&lt;\lvert P\rvert$ and $e_k$ injective would contradict the pigeonhole principle.