This is a collection of all important equations in Competitive Programming.
Motivation
Do you find it bad if you couldn’t solve a problem just because you didn’t know about a certain equation?
Do you find it difficult to take a quick look at an equation that you know exists but forgot about it while solving a problem?
Do you think that all the equations that are important in CP are just cluttered and you are too lazy to collect them in one place?
Well, then you are in the right place! I am here to solve all of the aforementioned problems. I believe you should not waste your precious time searching the internet for important equations. You should solve more problems. I am here to undertake the nasty task of collecting things.
The Equation List
- Axiom of extensionality: $$$\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y]$$$
- Axiom of regularity: $$$\forall x[\exists a(a\in x)\Rightarrow\exists y(y\in x\land\lnot\exists z(z\in y\land z\in x))]$$$
- Axiom schema of specification: $$$\forall z\forall w_1\forall w_2\dots\forall w_n\exists y\forall x[x\in y\Leftrightarrow((x\in z)\land\phi)]$$$
- Axiom of pairing: $$$\forall x\forall y\exists z((x\in z)\land(y\in z))$$$
- Axiom of union: $$$\forall\mathcal F\exists A\forall Y\forall x[(x\in Y\land Y\in\mathcal F)\Rightarrow x\in A]$$$
- Axiom schema of replacement: $$$\forall A\forall w_1\forall w_2\dots\forall w_n[\forall x(x\in A\Rightarrow\exists!y\phi)\Rightarrow\exists B\forall x(x\in A\Rightarrow\exists y(y\in B\land\phi))]$$$
- Axiom of infinity: $$$\exists X[\exists e(\forall z\lnot(z\in e))\land e\in X\land \forall y(y\in X\Rightarrow y\cup\{y\}\in X)]$$$
- Axiom of power set: $$$\forall x\exists y\forall z[z\subseteq x\Rightarrow z\in y]$$$
- Axiom of choice: $$$\forall X[\emptyset\not\in X\Rightarrow\exists f:X\to\bigcup x(\forall A\in X(f(A)\in A))]$$$
Outro
A good life is just a series of good days. So make sure to have a good day, friend 
.
Sir, can you give proofs please?
axiom: noun. a statement or proposition which is regarded as being established, accepted, or self-evidently true.
-Oxford Languages Dictionary
:rage:
At least, prove consistency.
10. Axiom of consistency: The previous 9 axioms are consistent.
Now prove consistency of all 10 axioms.
It is controversial to include equation 9 in the equation list, so I would suggest its removal from this list, lest some authors make problems that intentionally abuse equation 9, which would be unfair to people who don't include equation 9 in their garden-variety axiom list. Legendary blog btw.
Equation 9 states that for every set of nonempty sets it is possible to choose one element from each of those sets. This seems reasonable.
On the other hand, this is equivalent to the existence of a choice function $$$f$$$ for any set of sets $$$X$$$ that maps elements of $$$X$$$ to elements in the union of $$$X$$$ such that $$$f(S)\in S$$$ for $$$S\in X$$$.
It's commonly claimed that Banach-Tarski is a counterargument to the Axiom of Choice, but that is incorrect: it only provides a series of steps of partitioning of a sphere into some sets, followed by affine transformations on each set, and merging these sets together pefectly duplicates the sphere. It's much more intuitive when one considers it from e.g. the perspective of the set of integers: we can duplicate it, by splitting it into the set of even and odd integers, and then applying an affine transformation.
A more mind-bending argument against the Axiom of Choice arises from equivalence classes. Consider the following problem:
How is this possible? It seems that it is impossible to obtain any information on the color of your own hat; because you cannot hear the guesses of other prisoners no information can be conveyed between prisoners about what they see.
Consider the binary sequence of hat colors $$$c_1,c_2,\dots$$$. Let two sequences be equivalent if they are identical except for a finite number of positions. This clearly forms an equivalence relation and thus partitions the set of hat colors into disjoint subsets where any two pair of elements in each subset are equivalent.
Now, invoking the Axiom of Choice, it is possible to select a representative sequence of hat colors from every equivalence class. The prisoners will agree on all representative sequences beforehand. Each prisoner, upon seeing the infinite number of hats ahead of them, will uniquely determine the equivalence class the entire sequence of hat colors they are in. Thus if they all guess according to the representative sequence they agreed on, their sequence of guesses $$$g_1,g_2,\dots$$$ will be equivalent to $$$c_1,c_2,\dots$$$ and thus all prisoners, except a finite number, will guess thier hat color correctly.
Is this argument correct? Discuss.
How to understand these symbols.
[Quantifiers](https://en.wikipedia.org/wiki/Quantifier_(logic))
https://en.wikipedia.org/wiki/Boolean_algebra#Operations
Enjoy.
https://www.logicmatters.net/resources/pdfs/IFL2_LM.pdf
Why are you revealing the ultimate secret of becoming red? I had to sell my house and all my organs to obtain these equations. Please delete the blog. (or give my organs back)
Looks like you've been living fine w/o organs for the last two years. Why do you want them back then?
They weren't his
do you guys think about these equations when solving problems?
You forgot this one
This is a collection of all important equations in number theory:
Dude, you've just proved Fermat's last theorem...
left as exercise for the reader
everyone be like: assume S(x) = x + 1 smh
Subscribe to technoblade!