13958482
Description
Flashcards by Tom Tonner, updated more than 1 year ago
|
Created by Tom Tonner
almost 6 years ago
|
|
| Question | Answer |
| Russell's Paradox: Prove that the set of all sets which are not elements of themselves is self-contradictory: | If S∈S then by definition of S S∉S. If S∉S, then by definition of S S∈S. |
| Two functions are equal if: | -Same domain and co-domain -For all a∈A, we have f(a)=g(a) |
| -Negation of A: -Contra-positive of A⇒B: | ¬A ¬A ⇒ ¬B |
| Equivalence of: ¬(∀x ∈ X, P(x)) ¬(∃x ∈ X s.t P(x)) | ∃x ∈ X s.t ¬P(x) ∀x ∈ X, ¬P(x) |
| Euclid's Theorem | There are infinitely many prime numbers. |
| Definitions: -Greatest common divisor: -Least common multiple: -Co-prime: | -gcd(a,b) is the largest positive integer which is a divisor of both a and b. -lcm(a,b) is the smallest positive integer which is a multiple of both a and b. -Two integers a and b are said to be co-prime if the gcd(a,b) = 1. |
| gcd properties: | gcd(a,b) = gcd(b,a) gcd(a,0) = gcd(a,a) = a gcd(a,1) = 1 gcd(a,b) = gcd(a,-b) gcd(a,b) = gcd(a + kb, b) |
| a ≡ b (mod m) | m | (a-b) |
| Congruence properties: | - a ≡ a (mod m) - a ≡ b (mod m) ⇒ b ≡ a (mod m) - a ≡ b & b ≡ c ⇒ a ≡ c (mod m) - a ≡ b & c ≡ d ⇒ a+c ≡ b+d & a-c ≡ b-d & ac ≡ bd (mod m) |
| Fermat's little theorem | a^(p-1)≡1 (mod m) |
| Fermat-Euler Theorem | Let a, n be integers w/ gcd(a,n)=1 a^φ(n)≡1 (mod n). Where φ(n) is the number of integers between 1 to n which are co-prime to n |
| Wilson's Theorem | (n-1)! ≡1 (mod m) iff n is prime |
| x is irrational y is rational | Then: x+y is irrational xy is irrational (if y≠0) |
| Convergence definition: | A sequence a_i converges to x if: ∀ε>0, ∃N∈N s.t. ∀n>N, |a_n - x|<ε |
| The four group axioms: | G1 (Closure): ab∈G G2 (Associativity): (ab)c = a(bc) G3 (Neutral Element): ∃e s.t eg = g = ge G4 (Inverse): gh = e = hg |
| Albanian Group | ab = ba |
| (gh)^-1 | h^-1g^-1 |
| Homomorphism: Isomorphism: | f(xy) = f(x)f(y) Isomorphism is a bijective Homomorphism |
| Subgroup Criteria | SG1: H ≠ ∅ SG2: gh∈H SG3: h^-1∈H |
| Group Actions | GA1: e*x =x GA2: g(hx) = (gh)x |
| Orbit Counting Theorem | n = 1/|G|*∑ |fix(g)| |
| Equivalence relations | Reflexivity: a~a for all a Symmetry: if a~b then b~a for all a,b Transitivity: a~b and b~c then a~c |
Want to create your own Flashcards for free with GoConqr? Learn more.