TechnobladeNeverDies's blog

The Ultimate Equation List
By TechnobladeNeverDies, history, 3 years ago, In English

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

  1. Axiom of extensionality: $$$\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y]$$$
  2. 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))]$$$
  3. 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)]$$$
  4. Axiom of pairing: $$$\forall x\forall y\exists z((x\in z)\land(y\in z))$$$
  5. Axiom of union: $$$\forall\mathcal F\exists A\forall Y\forall x[(x\in Y\land Y\in\mathcal F)\Rightarrow x\in A]$$$
  6. 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))]$$$
  7. 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)]$$$
  8. Axiom of power set: $$$\forall x\exists y\forall z[z\subseteq x\Rightarrow z\in y]$$$
  9. 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 .

  • Vote: I like it
  • +365
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Sir, can you give proofs please?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    axiom: noun. a statement or proposition which is regarded as being established, accepted, or self-evidently true.

    -Oxford Languages Dictionary

    → Reply
»
3 years ago, # |
  Vote: I like it +88 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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:

    A countably infinite number of prisoners with either black or white hats are seated in a line ordered $$$1,2,\dots$$$. Each prisoner can see all prisoners ahead of them: prisoner $$$i$$$ can see prisoner $$$i+1,i+2,\dots$$$. The prisoners can communicate before they are seated, but cannot communicate afterwords. Then all but a finite number of prisoners can correctly guess their hat color.

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

How to understand these symbols.

→ Reply
»
3 years ago, # |
  Vote: I like it +103 Vote: I do not like it

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)

→ Reply
»
3 years ago, # |
  Vote: I like it -20 Vote: I do not like it

You forgot this one

$$$\displaystyle \sum_{i = 0}^{32} 210000 \cdot \frac{50}{2^i}$$$
→ Reply
»
3 years ago, # |
  Vote: I like it +166 Vote: I do not like it

This is a collection of all important equations in number theory:

  1. $$$0\in\mathbb{N}$$$.
  2. $$$x\in\mathbb{N}\Rightarrow S(x)\in\mathbb{N}$$$.
  3. $$$\nexists x\in\mathbb{N}\,(S(x) = 0)$$$.
  4. $$$\left(S(b) = a\wedge S(c) = a\right)\Rightarrow (b = c)$$$.
  5. $$$\left(P(0)\wedge(\forall x\in\mathbb{N}\,(P(x)\to P(S(x))))\right)\Rightarrow(\forall x\in\mathbb{N}\,(P(x))).$$$
→ Reply
»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Subscribe to technoblade!

→ Reply