advanced math 3

what does |A|=|B| mean?

A and B have the same cardinality, meaning the two sets are the same size. there exists f:A→B that is bijective.

Schroder-Bernstein Theorem

A and B are sets. Suppose f: A→B and g: B→A are both injective. Then there exists some h: A→B that is bijective and so |A|=|B|. 

when is set S countably infinite?

when |S| = |N|

If |A|=|B|=|N|, then

|A x B| = |N|. Proven with (a1, b1) → all the subscripts that add to 2, (a1, b2) and (a2, b1) → subscripts that add to 3 and so on.

If A1, A2, A3, … are countably infinite, then

A1 x … x An is countably infinite

Let A1, A2, A3, … be pairwise disjoint, finite, nonempty sets. Then

A1 U A2 U A3 U… is countably infinite.

If A is a proper subset of B, can |A| = |B|?

Yes

sequence lemma

if a set can be written in the form of a list with no duplications or ommissions

what is the diagonal argument?

proof technique showing a set of all infinite sequences fitting some criteria is uncountable. Done by constructing a new sequnce that modifies the nth sequence at position n, thus making it differ from all other sequences. That means no list can contain all the sequences and so it is uncountable.

cantor’s theorem

If A is a set, then the cardinality of A = cardinality of the power set of A. “There is no surjective function S → P(S), so |S| ≠ |P(S)|

Proof that the real numbers are uncountably infinite

prove the set of irrationals is uncountably infinite.

Suppose I is countably infinite. I U Q results in the set of real numbers. Q is countably infinite and the union of a countable number of countably infinite sets is itself countably infinite, but the real numbers are not countably infinite so a contraditction is reached. the set of irrationals must be uncountably infinite.

banach-tarski paradox

result of axiom of choice. end up with 2 spheres from 1 sphere (IDK)

group

set of G elements

binary operation

represented by *. Has the following properties: associative, an identity element e, every element has an inverse.

properites of binary operators

identity is unique, inverse is unique, inverses are reverses (so (a*b)^-1 = b^-1*a^-1), there’s a cancellation law ( a*b = a*c → a can cancel and b = c)

properties of cayley tables

rows have a one-to-one association of elements of the group G to G. each row is a permutation of G.

order (considering some g in group G)

saying g has order n means that gⁿ results in the identity element while all values less than n do not

generator

an element or a set of elements from which all other elements in a structure, like a group, can be derived using the structure's operations

A_n

given some aⁱ * a^j = a^(i+j)%n

dihedral group

a symmetry based group. a symmetry motion describes some sort of tranforming motion that preserves something, such as the appearance of an equilateral triangle. the elements of a dihedral group are the motions/actions that can be taken and the product is a composition of these motions.

D₆ elements

has six elements: {e, r, r², f, rf, r²f} where r is a counter clockwise rotation and f is a flip.

D₆ generators

r, f

subgroup

given a group G, S is a subgroup if it is itself a group using the same product. this mean for elements a, b to be in S, a*b must also be in S. The identity must also be an element of S and so if a is an element of S, its inverse must also be an element of S.

cosets

given group G and subgroup S, a coset of S is gS = {g * s : s is an element of S}. The coset and subgroup are disjoint. Say that S imposes an order. A function that maps S onto gS is bijective.

a R b iff a * s = b, s is an element of S is an equivalence relation iff

S is a subgroup of G

Legrange’s Theorem (use group G and subgroup S)

G is a finite group, S a subgroup then |S| divides |G|