Follow by Email

Tuesday, February 22, 2011

Vacuously true

A sentence like $$ \forall a \in A : P(a) $$ is said to be Vacuously true if $A$ is the empty set, no matter what the predicate $P$ was. For example the sentence $$ \forall x \in \mathbb{R}$$ such that $$x^2 < 0 : x = 23 $$ is true (vacuously).

This could be tricky in some cases. An example I found in the exercises of the book Topology 2nd Ed. by Munkres (which is an awesome book btw), showed this sentence and asked if is true or not, if the two sets $A,B$ are guaranteed to be non-empty or not: $$ (A \times B) \subseteq ( C\times D) \implies A \subseteq C \mbox{ and } B \subseteq D $$.

After some time brushing the rust off my brain, this statement turned out to be true (as the intuition would expect) only if $A$ and $B$ are non-empty. Quiet a surprising result. A counter example case occurs when $A$ is empty but $B$ isn't, in which case $ A\times B$ is empty, in which case the statement holds vacuously although $B$ might not be a subset of $D$.

Wednesday, February 16, 2011

voting system

For each registered voter
1- print 2D barcode for the value of an cryptographically authenticated, semantically-secure-encrypted ID of each of the nominees, along with a signature to allow the voter to check if his vote was counted.
2- send to each voting room exactly the number of registered voters to vote in it
3- when a voter votes his video is recorded with a newspaper of the day so that he can't claim later he didn't vote. he is required to leave the encrypted IDs for the nominees he didn't vote for as a proof against him that he didn't vote for anyone other than the one who he did vote for him (while not-revealing to anyone but the central computer)
4- counts is checked for each room
5- after collecting the votes, an automated scanner scans the numbers and sends them to a secured server to check the authentication of each printed encrypted ID and then using homomorphic properties to tally the votes
6- the tally is once decrypted (so only the counts is revealed and privacy of each voter is preserved), the list of signatures of votes counted is kept so that each use can guarantee his vote was counted (zero-knowledge proofs might get involved her as well)

conclusion:
to the end use this is mostly as basic as cutting a piece of paper
only one central computer needed
privacy, authenticity, counting, checking, proofs, is guaranteed