GenesisNemesis
I am a proud hedonist.
- Joined
- Jul 24, 2006
- Messages
- 4,093
- Location
- California
- Basic Beliefs
- Secular Humanist, Scientific Skepticism, Strong Atheism
SOUNDS LIKE PROOF OF GOD TO ME (insert bullshit argument here)
-
Features
Are there really infinite transcendental numbers?
- Thread starter SLD
- Start date
Jarhyn
Wizard
- Joined
- Mar 29, 2010
- Messages
- 15,254
- Gender
- Androgyne; they/them
- Basic Beliefs
- Natural Philosophy, Game Theoretic Ethicist
My response to the bullshit argument which you neither believe nor support:
Honestly, assuming that there are an indescribably infinite number of indescribable Grothendiek Universes which may still among some portion of them occasionally be approximately accessed according to some process of measurements, then this is approximately the description of Ohr Ein Sof.
The thing is, yet again, these universes cannot be described without access by some means, so the very notion of there being some sense to describing the set of all of them is just as nonsensical as the attempt to prove the set of all sets from simple ZFC: it's a contradiction. And lo and behold if you Google Ohr Ein Sof, you will see "contradiction, simultaneously truth and falseness, +1 and -1 at the same time and not 0" and different ways of saying "trying to say 'this is the lot of it' is fucking nonsense". That too is a fact of nature and math, that it's nonsense to think there's ever any end to how big it is.
The thing is, no Grothendiek Universe that fails to be revealed as a product of our investigations into interactions of nature happening within nature constrain the nature of nature but at the same time, we can't be certain from any point in nature what the limit of that is. As a result we can say "we have this much math", but we cannot prove or disprove "more".
Stated in different words "we cannot prove nor disprove the boundaries of U; we can only prove some given content, and only disprove certain things, but not the existence of 'more'. 'More' will happen as it does or doesn't."
This is an idea that in fact makes very deep discussion of the concept of God, capital G and all that, goes right to the very heart of what a lot of the crazies that roll through here often claim.
I think in some ways No Robots is right insofar as we atheists need to actually disassemble the various claims of God and dissect them, vivisect them, classify them, and reference them heavily when people come in claiming they are God, god, Jesus, or the like.
The thing is, yet again, these universes cannot be described without access by some means, so the very notion of there being some sense to describing the set of all of them is just as nonsensical as the attempt to prove the set of all sets from simple ZFC: it's a contradiction. And lo and behold if you Google Ohr Ein Sof, you will see "contradiction, simultaneously truth and falseness, +1 and -1 at the same time and not 0" and different ways of saying "trying to say 'this is the lot of it' is fucking nonsense". That too is a fact of nature and math, that it's nonsense to think there's ever any end to how big it is.
The thing is, no Grothendiek Universe that fails to be revealed as a product of our investigations into interactions of nature happening within nature constrain the nature of nature but at the same time, we can't be certain from any point in nature what the limit of that is. As a result we can say "we have this much math", but we cannot prove or disprove "more".
Stated in different words "we cannot prove nor disprove the boundaries of U; we can only prove some given content, and only disprove certain things, but not the existence of 'more'. 'More' will happen as it does or doesn't."
This is an idea that in fact makes very deep discussion of the concept of God, capital G and all that, goes right to the very heart of what a lot of the crazies that roll through here often claim.
I think in some ways No Robots is right insofar as we atheists need to actually disassemble the various claims of God and dissect them, vivisect them, classify them, and reference them heavily when people come in claiming they are God, god, Jesus, or the like.
lpetrich
Contributor
I will give proofs of these cardinal-arithmetic results. ProofWiki is a good place to look. It is "an online compendium of mathematical proofs!"
Addition:
Union is Commutative - ProofWiki and Union is Associative - ProofWiki
Intersection is Commutative - ProofWiki and Intersection is Associative - ProofWiki
Both operations are thus like arithmetic addition and multiplication, and also boolean or (disjunction) and boolean and (conjunction). That makes them orderless in their args.
Union with Empty Set - ProofWiki - A union {} = A
Intersection with Empty Set - ProofWiki - A intersect {} = {}
|B| + |A| = |B union A| = |A union B| = |A| + |B]
It is commutative
|A| + (|B| + |C|) = |A| + |B union C| = |A union (B union C)| = |(A union B) union C| = |A union B| + |C| = (|A| + |B|) + |C|
It is associative
|A| + 0 = |A union {}| = |A|
It has an identity: 0
A, B, and C are mutually disjoint, and this carries over into unions of them, thus helping to make cardinal addition associative. A intersect (B union C) = (A intersect B) union (A intersect C) = {} union {} = {}
A union B is {x | x in A or x in B}
A intersect B is {x | x in A and x in B}
Their commutativity and associativity is a carryover from those properties of "or" and "and", something easily verified from their truth tables.
The empty set {} has the property x in {} = false, and
x or false = x
x and false = false
Also,
x or true = true
x and true = x
Addition:
Union is Commutative - ProofWiki and Union is Associative - ProofWiki
Intersection is Commutative - ProofWiki and Intersection is Associative - ProofWiki
Both operations are thus like arithmetic addition and multiplication, and also boolean or (disjunction) and boolean and (conjunction). That makes them orderless in their args.
Union with Empty Set - ProofWiki - A union {} = A
Intersection with Empty Set - ProofWiki - A intersect {} = {}
|B| + |A| = |B union A| = |A union B| = |A| + |B]
It is commutative
|A| + (|B| + |C|) = |A| + |B union C| = |A union (B union C)| = |(A union B) union C| = |A union B| + |C| = (|A| + |B|) + |C|
It is associative
|A| + 0 = |A union {}| = |A|
It has an identity: 0
A, B, and C are mutually disjoint, and this carries over into unions of them, thus helping to make cardinal addition associative. A intersect (B union C) = (A intersect B) union (A intersect C) = {} union {} = {}
A union B is {x | x in A or x in B}
A intersect B is {x | x in A and x in B}
Their commutativity and associativity is a carryover from those properties of "or" and "and", something easily verified from their truth tables.
The empty set {} has the property x in {} = false, and
x or false = x
x and false = false
Also,
x or true = true
x and true = x
Last edited:
lpetrich
Contributor
Multiplication:
The Cartesian product:
A*B = {(a,b) | a in A, b in B}
B*A = {(b,a) | a in A, b in B}
A bijection from reversing the elements in the pair.
|A*B| = |B*A|
|A|*|B| = |B|*|A|
It is commutative
A*(B*C) = {(a,(b,c)) | a in A, b in B, c in C}
(A*B)*C = {((a,b),c) | a in A, b in B, c in C}
A bijection from flattening the triplets to (a,b,c)
|A*(B*C)| = |(A*B)*C|
It is associative
So cardinal multiplication is commutative and associative, making it orderless.
A*{} = {}
|A|*0 = 0
It has a zero: 0
A*{e} = {(a,e) | a in A}
with a bijection to A
|A|*1 = |A|
It has an identity: 1
A*(B union C) = {(a,x) | a in A, x in B or C} = {(a,b) | a = A, b in B} union {(a,c) | a = A, c in C} = (A*B) union (A*C)
|A|*(|B| + |C|) = |A|*|B| + |A|*|C|
It is distributive over addition
So cardinal addition and multiplication carry over into infinite cardinals all the familiar properties of finite-number addition and multiplication.
The Cartesian product:
A*B = {(a,b) | a in A, b in B}
B*A = {(b,a) | a in A, b in B}
A bijection from reversing the elements in the pair.
|A*B| = |B*A|
|A|*|B| = |B|*|A|
It is commutative
A*(B*C) = {(a,(b,c)) | a in A, b in B, c in C}
(A*B)*C = {((a,b),c) | a in A, b in B, c in C}
A bijection from flattening the triplets to (a,b,c)
|A*(B*C)| = |(A*B)*C|
It is associative
So cardinal multiplication is commutative and associative, making it orderless.
A*{} = {}
|A|*0 = 0
It has a zero: 0
A*{e} = {(a,e) | a in A}
with a bijection to A
|A|*1 = |A|
It has an identity: 1
A*(B union C) = {(a,x) | a in A, x in B or C} = {(a,b) | a = A, b in B} union {(a,c) | a = A, c in C} = (A*B) union (A*C)
|A|*(|B| + |C|) = |A|*|B| + |A|*|C|
It is distributive over addition
So cardinal addition and multiplication carry over into infinite cardinals all the familiar properties of finite-number addition and multiplication.
Last edited:
lpetrich
Contributor
Now for ordering.
First consider addition. If B <= C, then how are (A union B) and (A union C) related?
Let C = B + D and the parts not in A be B', C', and D'.
A union B = A union B'
A union C = A union C' = A union B' union D'
Thus, (A union B) <= (A union C) and if |B| <= |C|, then |A|+|B| <= |A|+|C|
Now multiplication. How are A*B and A*C related?
A*C = A*(B union D) = (A*B) union (A*D)
Thus, |A|*|B| <= |A|*|C|
Collecting these results,
b <= c implies (a+b) <= (a+c) and (a*b) <= (a*c)
However < need not imply < for infinite sets, and it's easy to find counterexamples.
1 < A0, but A0 + 1 = A0 + A0 = A0
First consider addition. If B <= C, then how are (A union B) and (A union C) related?
Let C = B + D and the parts not in A be B', C', and D'.
A union B = A union B'
A union C = A union C' = A union B' union D'
Thus, (A union B) <= (A union C) and if |B| <= |C|, then |A|+|B| <= |A|+|C|
Now multiplication. How are A*B and A*C related?
A*C = A*(B union D) = (A*B) union (A*D)
Thus, |A|*|B| <= |A|*|C|
Collecting these results,
b <= c implies (a+b) <= (a+c) and (a*b) <= (a*c)
However < need not imply < for infinite sets, and it's easy to find counterexamples.
1 < A0, but A0 + 1 = A0 + A0 = A0
lpetrich
Contributor
For at least one of a and b infinite, and also the axiom of choice,
a + b = max(a,b)
and with the further condition of being greater than 0,
a*b = max(a,b)
I was unable to find a proof of that in ProofWiki, but I did find
Countable Union of Countable Sets is Countable - ProofWiki
Cartesian Product of Countable Sets is Countable - ProofWiki
One can prove these results by finding the element index number for every element in the resulting sets. That will produce duplicates for non-disjoint sets, and thus an upper limit on cardinality in that case.
One finds for finite n:
Shove forward or backward:
A0 + n = A0
A0 - n = A0
Interleave:
A0 + A0 = A0
n*A0 = A0
Zigzag:
A0*A0 = A0
A0^n = A0
For the continuum cardinality C, one can prove that
C + C = C
by considering two line segments R[0,1) and R[1,2) and combining them, making R[0,2). Extending this result to n segments, one finds
n*C = C
By using one segment for every integer, one finds
A0*C = C
By pushing in points in R[0,1] with 1 -> 1/2, 1/2 -> 1/4, 1/4 -> 1/8, ... and replacing each hole with an element from a countably infinite set, one finds
C + A0 = C
C - A0 = C
By cardinal-operation inequalities,
C + n = C
C - n = C
By interleaving digits in R[0,1] for 0.000... to 0.999..., an argument that works in every number base, one finds
C*C = C
and more generally,
C^n = C
For a countable number of segments, one can do a zigzag argument: 1st digit of 1st number, 2nd digit of 1st number, 1st digit of 2nd number, 3rd digit of 1st number, 2nd digit of 2nd number, 1st digit of 3rd number, ... and one finds
C^(A0) = C
a + b = max(a,b)
and with the further condition of being greater than 0,
a*b = max(a,b)
I was unable to find a proof of that in ProofWiki, but I did find
Countable Union of Countable Sets is Countable - ProofWiki
Cartesian Product of Countable Sets is Countable - ProofWiki
One can prove these results by finding the element index number for every element in the resulting sets. That will produce duplicates for non-disjoint sets, and thus an upper limit on cardinality in that case.
One finds for finite n:
Shove forward or backward:
A0 + n = A0
A0 - n = A0
Interleave:
A0 + A0 = A0
n*A0 = A0
Zigzag:
A0*A0 = A0
A0^n = A0
For the continuum cardinality C, one can prove that
C + C = C
by considering two line segments R[0,1) and R[1,2) and combining them, making R[0,2). Extending this result to n segments, one finds
n*C = C
By using one segment for every integer, one finds
A0*C = C
By pushing in points in R[0,1] with 1 -> 1/2, 1/2 -> 1/4, 1/4 -> 1/8, ... and replacing each hole with an element from a countably infinite set, one finds
C + A0 = C
C - A0 = C
By cardinal-operation inequalities,
C + n = C
C - n = C
By interleaving digits in R[0,1] for 0.000... to 0.999..., an argument that works in every number base, one finds
C*C = C
and more generally,
C^n = C
For a countable number of segments, one can do a zigzag argument: 1st digit of 1st number, 2nd digit of 1st number, 1st digit of 2nd number, 3rd digit of 1st number, 2nd digit of 2nd number, 1st digit of 3rd number, ... and one finds
C^(A0) = C
lpetrich
Contributor
Finite Union of Finite Sets is Finite - ProofWiki
Product of Finite Sets is Finite - ProofWiki
logic - Countably infinite Cartesian product of finite sets is infinite - Mathematics Stack Exchange
Cartesian Product of Infinite Set Equivalent to Itself implies Axiom of Choice - ProofWiki
For some set X, if every element is associated with some set, then if the sets are nonempty and disjoint with maximum cardinality M, then the set union's cardinality is at least X and at most M*X.
Likewise, if every set has cardinality at least 2 and at most M, then the set product's cardinality is at least 2^X and at most M^X.
Product of Finite Sets is Finite - ProofWiki
logic - Countably infinite Cartesian product of finite sets is infinite - Mathematics Stack Exchange
Cartesian Product of Infinite Set Equivalent to Itself implies Axiom of Choice - ProofWiki
For some set X, if every element is associated with some set, then if the sets are nonempty and disjoint with maximum cardinality M, then the set union's cardinality is at least X and at most M*X.
Likewise, if every set has cardinality at least 2 and at most M, then the set product's cardinality is at least 2^X and at most M^X.
lpetrich
Contributor
Exponentiation:
A^B = {every function from B to A}
where the functions need not be surjections, going to every element of A.
|A|^|B| = |A^B|
|A| > 0:
Empty function:
|A|^0 = 1
No function:
0^|A| = 0
{e}^A: f(a) = e for all a in A -- a constant function
1^|A| = 1
A^{e}: f(e) = a for all a in A -- a separate function for each a
|A|^1 = |A|
A^(B+C): f(x) = a in A where x is either b in B or c in C
f(b) = a in A for b in B and f(c) = a in A for c in C
f can be broken into two parts that are independent of each other
f1(b) = a in A for b in B
f2(c) = a in A for c in C
Thus, one gets something with a bijection to (A^B) * (A^C)
|A|^(|B|+|C|) = (|A|^|B|) * (|A|^|C|)
(A*B)^C: f(c) = (a,b) for a in A, b in B, c in C
Can be split up into f1(c) = a, f2(c) = b, making
(A^C) * (B^C)
Thus,
(|A|*|B|)^|C| = (|A|^|C|) * (|B|^{C})
(A^B)^C: f{b) = a for a in A, b in B, then g(c) = f for c in C
This is equivalent to there being functions h(b,c) = a for a in A, b in B, c in C
Thus,
(|A|^|B|)^|C| = |A|^(|B|*|C|)
If B <= C, then A^B <= A^C
f(b) = a in A for b in B <= g(c) = a in A for c in C
Because f's domain is a subset of g's domain, and these functions are not restricted to be constant.
Thus,
For |A| > 1 and |B| <= |C|,
|A|^|B| <= |A|^|C|
If A <= B, then A^C <= B^C
f(c) = a in A for c in C <= g(c) = b in B for c in C
Because f's codomain is a subset of g's codomain
Thus,
For |B| <= |C|,
|A|^|C| <= |B|^|C|
Thus behaving like finite-number exponentiation.
A^B = {every function from B to A}
where the functions need not be surjections, going to every element of A.
|A|^|B| = |A^B|
|A| > 0:
Empty function:
|A|^0 = 1
No function:
0^|A| = 0
{e}^A: f(a) = e for all a in A -- a constant function
1^|A| = 1
A^{e}: f(e) = a for all a in A -- a separate function for each a
|A|^1 = |A|
A^(B+C): f(x) = a in A where x is either b in B or c in C
f(b) = a in A for b in B and f(c) = a in A for c in C
f can be broken into two parts that are independent of each other
f1(b) = a in A for b in B
f2(c) = a in A for c in C
Thus, one gets something with a bijection to (A^B) * (A^C)
|A|^(|B|+|C|) = (|A|^|B|) * (|A|^|C|)
(A*B)^C: f(c) = (a,b) for a in A, b in B, c in C
Can be split up into f1(c) = a, f2(c) = b, making
(A^C) * (B^C)
Thus,
(|A|*|B|)^|C| = (|A|^|C|) * (|B|^{C})
(A^B)^C: f{b) = a for a in A, b in B, then g(c) = f for c in C
This is equivalent to there being functions h(b,c) = a for a in A, b in B, c in C
Thus,
(|A|^|B|)^|C| = |A|^(|B|*|C|)
If B <= C, then A^B <= A^C
f(b) = a in A for b in B <= g(c) = a in A for c in C
Because f's domain is a subset of g's domain, and these functions are not restricted to be constant.
Thus,
For |A| > 1 and |B| <= |C|,
|A|^|B| <= |A|^|C|
If A <= B, then A^C <= B^C
f(c) = a in A for c in C <= g(c) = b in B for c in C
Because f's codomain is a subset of g's codomain
Thus,
For |B| <= |C|,
|A|^|C| <= |B|^|C|
Thus behaving like finite-number exponentiation.
lpetrich
Contributor
reference request - Overview of basic results on cardinal arithmetic - Mathematics Stack Exchange
For sets A and B
|A| = |B| is equivalent to there being a bijection between A and B
|A| <= |B| is equivalent to there being an injection from A to B
elementary set theory - How to Understand the Definition of Cardinal Exponentiation - Mathematics Stack Exchange
Inequalities a <= b and b <= a give a = b (Cantor-Schröder-Bernstein). At least one of them being true is equivalent to the Axiom of Choice:
set theory - Is the class of cardinals totally ordered? - Mathematics Stack Exchange
set theory - For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$ - Mathematics Stack Exchange
elementary set theory - Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$ - Mathematics Stack Exchange
functions - There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$. - Mathematics Stack Exchange
A consequence of the Axiom of Choice.
Power set?
elementary set theory - How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic? - Mathematics Stack Exchange
functions - Finding a correspondence between $\{0,1\}^A$ and $\mathcal P(A)$ - Mathematics Stack Exchange
elementary set theory - What's the meaning of a set to the power of another set? - Mathematics Stack Exchange
elementary set theory - What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to? - Mathematics Stack Exchange
That is almost absurdly trivial: 0 -> not a member of a subset, 1 -> member of a subset.
elementary set theory - Does $a \le b$ imply $a+c\le b+c$ for cardinal numbers? - Mathematics Stack Exchange
Yes. Cardinal addition partially preserves ordering.
elementary set theory - A bijection between $X \times (Y \times Z)$ and $ (X \times Y) \times Z$ - Mathematics Stack Exchange
Pairs with pairs (x,(y,z)) and ((x,y),z) can be flatten to triplets: (x,y,z)
elementary set theory - Proof of cardinality inequality: $m_1\le m_2$, $k_1\le k_2$ implies $k_1m_1\le k_2m_2$ - Mathematics Stack Exchange
elementary set theory - Will $\kappa_1, \kappa_2, m$ cardinals. Given $\kappa_1 \leq \kappa_2$. prove: $\kappa_1 \cdot m \leq \kappa_2 \cdot m$ - Mathematics Stack Exchange
Cardinal multiplication partially preserves ordering: a <= b and c <= d gives us a*c <= b*d
For sets A and B
|A| = |B| is equivalent to there being a bijection between A and B
|A| <= |B| is equivalent to there being an injection from A to B
elementary set theory - How to Understand the Definition of Cardinal Exponentiation - Mathematics Stack Exchange
Inequalities a <= b and b <= a give a = b (Cantor-Schröder-Bernstein). At least one of them being true is equivalent to the Axiom of Choice:
set theory - Is the class of cardinals totally ordered? - Mathematics Stack Exchange
set theory - For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$ - Mathematics Stack Exchange
elementary set theory - Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$ - Mathematics Stack Exchange
functions - There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$. - Mathematics Stack Exchange
A consequence of the Axiom of Choice.
Power set?
elementary set theory - How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic? - Mathematics Stack Exchange
functions - Finding a correspondence between $\{0,1\}^A$ and $\mathcal P(A)$ - Mathematics Stack Exchange
elementary set theory - What's the meaning of a set to the power of another set? - Mathematics Stack Exchange
elementary set theory - What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to? - Mathematics Stack Exchange
That is almost absurdly trivial: 0 -> not a member of a subset, 1 -> member of a subset.
elementary set theory - Does $a \le b$ imply $a+c\le b+c$ for cardinal numbers? - Mathematics Stack Exchange
Yes. Cardinal addition partially preserves ordering.
elementary set theory - A bijection between $X \times (Y \times Z)$ and $ (X \times Y) \times Z$ - Mathematics Stack Exchange
Pairs with pairs (x,(y,z)) and ((x,y),z) can be flatten to triplets: (x,y,z)
elementary set theory - Proof of cardinality inequality: $m_1\le m_2$, $k_1\le k_2$ implies $k_1m_1\le k_2m_2$ - Mathematics Stack Exchange
elementary set theory - Will $\kappa_1, \kappa_2, m$ cardinals. Given $\kappa_1 \leq \kappa_2$. prove: $\kappa_1 \cdot m \leq \kappa_2 \cdot m$ - Mathematics Stack Exchange
Cardinal multiplication partially preserves ordering: a <= b and c <= d gives us a*c <= b*d
lpetrich
Contributor
elementary set theory - What's the meaning of a set to the power of another set? - Mathematics Stack Exchange
Functions of the exponent set to the base set.
elementary set theory - How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$) - Mathematics Stack Exchange
C^C = 2^C
Proof: C^C = (2^A0)^C = 2^(A0*C) = 2^C
elementary set theory - Let $\alpha, \beta, \gamma$ be cardinals, $\beta \leq \gamma$, prove $\alpha ^{\beta}\le \alpha ^{\gamma}$ - Mathematics Stack Exchange
For b <= c, one finds for every a that a^b <= a^c
elementary set theory - Let $A,B,C$ be sets, and $B \cap C=\emptyset$. Show $|A^{B \cup C}|=|A^B \times A^C|$ - Mathematics Stack Exchange
elementary set theory - Notation on proving injectivity of a function $f:A^{B\;\cup\; C}\to A^B\times A^C$ - Mathematics Stack Exchange
a^(b+c) = (a^b) * (a^c)
elementary set theory - How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers? - Mathematics Stack Exchange
(a^b)^c = a^(b*c)
(A^B)^C -- functions from C to functions from B to A. Thus one gets functions from B and C to A: B*C to A.
elementary set theory - Equinumerousity of operations on cardinal numbers - Mathematics Stack Exchange
functions - How to prove $|{^A}{(K \times L)}| =_c |{^A}{K} \times {^A}{L}|$? - Mathematics Stack Exchange
(a*b)^c = (a^c)*(b^c)
elementary set theory - Cardinal equalities: $\aleph_0^\mathfrak c=2^\mathfrak c$ - Mathematics Stack Exchange
A0^C = 2^C
This is because 2 < A0 < C, meaning that 2^C <= A0^C <= C^C. That last one is (2^A0)^C = 2^(A0*C) = 2^C. Thus, 2^C <= A0^C <= 2^C, giving A0^C = 2^C.
a < 2^a -- Cantor's theorem
Functions of the exponent set to the base set.
elementary set theory - How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$) - Mathematics Stack Exchange
C^C = 2^C
Proof: C^C = (2^A0)^C = 2^(A0*C) = 2^C
elementary set theory - Let $\alpha, \beta, \gamma$ be cardinals, $\beta \leq \gamma$, prove $\alpha ^{\beta}\le \alpha ^{\gamma}$ - Mathematics Stack Exchange
For b <= c, one finds for every a that a^b <= a^c
elementary set theory - Let $A,B,C$ be sets, and $B \cap C=\emptyset$. Show $|A^{B \cup C}|=|A^B \times A^C|$ - Mathematics Stack Exchange
elementary set theory - Notation on proving injectivity of a function $f:A^{B\;\cup\; C}\to A^B\times A^C$ - Mathematics Stack Exchange
a^(b+c) = (a^b) * (a^c)
elementary set theory - How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers? - Mathematics Stack Exchange
(a^b)^c = a^(b*c)
(A^B)^C -- functions from C to functions from B to A. Thus one gets functions from B and C to A: B*C to A.
elementary set theory - Equinumerousity of operations on cardinal numbers - Mathematics Stack Exchange
functions - How to prove $|{^A}{(K \times L)}| =_c |{^A}{K} \times {^A}{L}|$? - Mathematics Stack Exchange
(a*b)^c = (a^c)*(b^c)
elementary set theory - Cardinal equalities: $\aleph_0^\mathfrak c=2^\mathfrak c$ - Mathematics Stack Exchange
A0^C = 2^C
This is because 2 < A0 < C, meaning that 2^C <= A0^C <= C^C. That last one is (2^A0)^C = 2^(A0*C) = 2^C. Thus, 2^C <= A0^C <= 2^C, giving A0^C = 2^C.
a < 2^a -- Cantor's theorem
lpetrich
Contributor
elementary set theory - Is the class of subsets of integers countably infinite? - Mathematics Stack Exchange
elementary set theory - Understanding the proof for $ 2^{\aleph_0} > \aleph_0$ - Mathematics Stack Exchange
elementary set theory - Cardinality of a set A is strictly less than the cardinality of the power set of A - Mathematics Stack Exchange
The second one asks about the proof that 2^A0 > A0 -- but this is a special case of Cantor's theorem.
elementary set theory - Let $X$ and $Y$ be countable sets. Then $X\cup Y$ is countable - Mathematics Stack Exchange
elementary set theory - Bijecting a countably infinite set $S$ and its cartesian product $S \times S$ - Mathematics Stack Exchange
elementary set theory - How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$? - Mathematics Stack Exchange
elementary set theory - The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable - Mathematics Stack Exchange
elementary set theory - Proving the Cantor Pairing Function Bijective - Mathematics Stack Exchange
The addition one can be proved by interleaving. The multiplication one can be proved by zigzagging, though another method is to find 2^i*3^j for original-set indices i and j -- this produces a subset of the positive integers.
elementary set theory - Prove that the union of countably many countable sets is countable. - Mathematics Stack Exchange
A0 of them: A0*A0 = A0
elementary set theory - Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? - Mathematics Stack Exchange
set theory - What is $\aleph_0$ powered to $\aleph_0$? - Mathematics Stack Exchange
elementary set theory - What's the cardinality of all sequences with coefficients in an infinite set? - Mathematics Stack Exchange
2^A0 and A0^A0
A0 < 2^A0 -- to power A0: A0^A0 <= (2^A0)^A0 = 2^(A0*A0) = 2^A0
Thus, A0^A0 = 2^A0
elementary set theory - Understanding the proof for $ 2^{\aleph_0} > \aleph_0$ - Mathematics Stack Exchange
elementary set theory - Cardinality of a set A is strictly less than the cardinality of the power set of A - Mathematics Stack Exchange
The second one asks about the proof that 2^A0 > A0 -- but this is a special case of Cantor's theorem.
elementary set theory - Let $X$ and $Y$ be countable sets. Then $X\cup Y$ is countable - Mathematics Stack Exchange
elementary set theory - Bijecting a countably infinite set $S$ and its cartesian product $S \times S$ - Mathematics Stack Exchange
elementary set theory - How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$? - Mathematics Stack Exchange
elementary set theory - The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable - Mathematics Stack Exchange
elementary set theory - Proving the Cantor Pairing Function Bijective - Mathematics Stack Exchange
The addition one can be proved by interleaving. The multiplication one can be proved by zigzagging, though another method is to find 2^i*3^j for original-set indices i and j -- this produces a subset of the positive integers.
elementary set theory - Prove that the union of countably many countable sets is countable. - Mathematics Stack Exchange
A0 of them: A0*A0 = A0
elementary set theory - Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? - Mathematics Stack Exchange
set theory - What is $\aleph_0$ powered to $\aleph_0$? - Mathematics Stack Exchange
elementary set theory - What's the cardinality of all sequences with coefficients in an infinite set? - Mathematics Stack Exchange
2^A0 and A0^A0
A0 < 2^A0 -- to power A0: A0^A0 <= (2^A0)^A0 = 2^(A0*A0) = 2^A0
Thus, A0^A0 = 2^A0
lpetrich
Contributor
set theory - About a paper of Zermelo - Mathematics Stack Exchange
Axiom of choice: equivalent to a bijection between A and A*A existing for every infinite set A: |A|^2 = |A|
set theory - For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice - Mathematics Stack Exchange
How to prove that from "Every infinite cardinal satisfies 𝑎 2 = 𝑎 a 2 = a a^2=a " we can prove that 𝑏 + 𝑐 = 𝑏 𝑐 b + c = b c b+c=bc for any two infinite cardinals 𝑏 , 𝑐 b , c b,c ?
Proof, assuming the Axiom of Choice:
Take b <= c.
b*c <= c*c = c <= b+c <= c+c <= 2*c <= b*c
Thus, b + c = b*c
In fact, both b + c and b*c equal max(b,c)
Whew. The end of that page. Some more:
Axiom of choice: equivalent to a bijection between A and A*A existing for every infinite set A: |A|^2 = |A|
set theory - For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice - Mathematics Stack Exchange
How to prove that from "Every infinite cardinal satisfies 𝑎 2 = 𝑎 a 2 = a a^2=a " we can prove that 𝑏 + 𝑐 = 𝑏 𝑐 b + c = b c b+c=bc for any two infinite cardinals 𝑏 , 𝑐 b , c b,c ?
Proof, assuming the Axiom of Choice:
Take b <= c.
b*c <= c*c = c <= b+c <= c+c <= 2*c <= b*c
Thus, b + c = b*c
In fact, both b + c and b*c equal max(b,c)
Whew. The end of that page. Some more:
lpetrich
Contributor
Some set-theory paradoxes.
Consider all sets that are not members of themselves: "normal sets". Is the set of them a normal set? If so, then it must be a member of itself, and thus not a normal set. If not, then it must be a normal set. Self-contradiction. Published by Bertrand Russell in 1901.
This is a version of the liar paradox, and a version of that is also the basis of Kurt Gödel's incompleteness theorems: a formal system that includes numbers contains true statements that cannot be proved within the system: theorem T: T is not a theorem.
Another one is the set of all sets. But whatever set one can come up with, one can come up with a larger one by taking its power set. Thus, there is no such set.
Consider all sets that are not members of themselves: "normal sets". Is the set of them a normal set? If so, then it must be a member of itself, and thus not a normal set. If not, then it must be a normal set. Self-contradiction. Published by Bertrand Russell in 1901.
This is a version of the liar paradox, and a version of that is also the basis of Kurt Gödel's incompleteness theorems: a formal system that includes numbers contains true statements that cannot be proved within the system: theorem T: T is not a theorem.
Another one is the set of all sets. But whatever set one can come up with, one can come up with a larger one by taking its power set. Thus, there is no such set.
lpetrich
Contributor
The number of permutations or self-bijections of a set satisfy certain inequalities, and those inequalities can be useful for infinite sets.
For a set A with number of elements or cardinality a = |A|: the number of permutations is a! (factorial)
A lower limit comes from whether or not each element of A is mapped onto itself. Every configuration is possible except those where only one element is not mapped onto itself, because if all but one element is mapped onto itself, then the only element available for that one element is that element itself. Thus, the lower limit is
2^a - a
An upper limit comes from A being mapped onto itself:
a^a
So, 2^a-a <= a! <= a^a
2^A0-A0 <= A0! <= A0^A0
2^A0 <= A0! <= 2^A0
A0! = 2^A0 = C
Real numbers:
2^C-C <= C! <= C^C
2^C < C! < 2^C
C! = 2^C
In general, for infinite a = 2^p,
2^a - a <= a! <= a^a = (2^p)^a = 2^(p*a) = 2^a
2^a <= a! <= 2^a
a! = 2^a
For a set A with number of elements or cardinality a = |A|: the number of permutations is a! (factorial)
A lower limit comes from whether or not each element of A is mapped onto itself. Every configuration is possible except those where only one element is not mapped onto itself, because if all but one element is mapped onto itself, then the only element available for that one element is that element itself. Thus, the lower limit is
2^a - a
An upper limit comes from A being mapped onto itself:
a^a
So, 2^a-a <= a! <= a^a
- 0: 1 <= 1 <= 1
- 1: 1 <= 1 <= 1
- 2: 2 <= 2 <= 4
- 3: 5 <= 6 <= 27
- 4: 12 <= 24 <= 256
- ...
2^A0-A0 <= A0! <= A0^A0
2^A0 <= A0! <= 2^A0
A0! = 2^A0 = C
Real numbers:
2^C-C <= C! <= C^C
2^C < C! < 2^C
C! = 2^C
In general, for infinite a = 2^p,
2^a - a <= a! <= a^a = (2^p)^a = 2^(p*a) = 2^a
2^a <= a! <= 2^a
a! = 2^a
Jarhyn
Wizard
- Joined
- Mar 29, 2010
- Messages
- 15,254
- Gender
- Androgyne; they/them
- Basic Beliefs
- Natural Philosophy, Game Theoretic Ethicist
Speaking of the relationships between AND and OR...
AND is:
00| 0
01| 0
10| 0
11| 1
OR is:
00| 0
01| 1
10| 1
11| 1
One is simply the negation of all inputs and all outputs of the other.
I find this funny because, at least in binary, you could represent "true" as 0 instead of as 1 in a circuit, and get the same result using the other kind of gate structure to drive the logic, and NOT works the same either way regardless, so the concepts of AND/OR are anti-gates.
Could you talk about this, actually?
Also, could you with a small set show an example using {1,2,3} an example of when every element is mapped onto itself vs not?
I think you if you were to pair one of {1,2,3} with {1,2,3} for example, but I'm unsure. I would like to see this count done for the 3^2 bijection just to be sure I understand well.
lpetrich
Contributor
How many elements mapped onto themselves:
1 - 1
12 - 2
21 - 0
123 - 3
132 - 1
213 - 1
231 - 0
312 - 0
321 - 1
1 - 1
12 - 2
21 - 0
123 - 3
132 - 1
213 - 1
231 - 0
312 - 0
321 - 1
Jarhyn
Wizard
- Joined
- Mar 29, 2010
- Messages
- 15,254
- Gender
- Androgyne; they/them
- Basic Beliefs
- Natural Philosophy, Game Theoretic Ethicist
Thank you! This illustrates the concept very succinctly!
Swammerdami
Squadron Leader
The study of very large cardinal numbers and very large ordinal numbers gets very weird.
For example (www.uni-muenster.de/imperia/md/content/MathematicsMuenster/woodin-opening-colloquium.pdf) :
Those "Woodin cardinals" aren't even particularly large; Woodin suggests these types of cardinal numbers (all "inaccessible") in increasing order of size:
(1) Ordinal numbers and their elegant definition. "An ordinal number is simply the set of all smaller ordinal numbers." (If there's interest I'll expand on this a bit.)
(2) There is a scenario where an infinite number of prisoners face execution and it's rather clear that about 50% of them will almost certainly die. BUT, assuming the Axiom of Choice to be true they have a strategy which ensures that at most a single one of them will die.
For example (www.uni-muenster.de/imperia/md/content/MathematicsMuenster/woodin-opening-colloquium.pdf) :
If there are infinitely many Woodin cardinals, then the projective Continuum Hypothesis and the projective Axiom of Choice both hold.
Those "Woodin cardinals" aren't even particularly large; Woodin suggests these types of cardinal numbers (all "inaccessible") in increasing order of size:
- Measurable cardinals
- Woodin cardinals
- Superstrong cardinals
- Supercompact cardinals
- Extendible cardinals
- Huge cardinals
- ω-Huge cardinals
- Axiom I0 cardinals.
(1) Ordinal numbers and their elegant definition. "An ordinal number is simply the set of all smaller ordinal numbers." (If there's interest I'll expand on this a bit.)
(2) There is a scenario where an infinite number of prisoners face execution and it's rather clear that about 50% of them will almost certainly die. BUT, assuming the Axiom of Choice to be true they have a strategy which ensures that at most a single one of them will die.
Swammerdami
Squadron Leader
In the YouTube each prisoner has a hat bearing either the number 0 or 1. However essentially the same solution applies if the hat numbers can be any integer from 1 to a million, or 1 to a googol. (Instead of even/odd parity, compute sums modulo 1 million, or 1 googol.)
I just noticed that, in a sense the infinite-prisoner case, which requires Axiom of Choice, may not be fully counter-intuitive. The finite problem can be solved with a thousand prisoners, or a googol, or a googol-plex, etc. To leap from there to countably infinite isn't such a huge stretch intuitively!
lpetrich
Contributor
Returning to transcendental numbers, they are all real numbers that are not algebraic. But how many algebraic numbers are there?
They are solutions of integer-coefficient polynomial equations, equivalent to rational-number-coefficient ones.
abstract algebra - Prove that the set of all algebraic numbers is countable - Mathematics Stack Exchange
and
Algebraic Numbers are Countable - ProofWiki
using
Set of Polynomials over Infinite Set has Same Cardinality - ProofWiki
using
Cardinality of Infinite Union of Infinite Sets - ProofWiki
Essentially A0*A0 = A0, provable by zigzagging. Counting all coefficients is somewhat redundant, because a polynomial's coefficients may have a nontrivial greatest common divisor, and polynomials may share roots. Also, the rational numbers are a subset of the algebraic numbers. Thus,
{Rational numbers} < {Algebraic numbers} < {Solutions for each integer-coefficient polynomial, tagged by polynomial}
Their cardinalities have <= instead of <:
A0 <= |algebraic numbers| <= A0
Thus, |algebraic numbers| = A0.
That is true of complex ones, and for real ones, it's easy:
{Rational numbers} < {Real algebraic numbers} < {Complex algebraic numbers}
A0 <= |real algebraic numbers| <= A0
Thus, |real algebraic numbers| = A0.
But transcendental numbers are real numbers that are not algebraic, and their cardinality is C - A0 = C. Thus, there are infinitely more of them than there are algebraic numbers.
They are solutions of integer-coefficient polynomial equations, equivalent to rational-number-coefficient ones.
abstract algebra - Prove that the set of all algebraic numbers is countable - Mathematics Stack Exchange
and
Algebraic Numbers are Countable - ProofWiki
using
Set of Polynomials over Infinite Set has Same Cardinality - ProofWiki
using
Cardinality of Infinite Union of Infinite Sets - ProofWiki
Essentially A0*A0 = A0, provable by zigzagging. Counting all coefficients is somewhat redundant, because a polynomial's coefficients may have a nontrivial greatest common divisor, and polynomials may share roots. Also, the rational numbers are a subset of the algebraic numbers. Thus,
{Rational numbers} < {Algebraic numbers} < {Solutions for each integer-coefficient polynomial, tagged by polynomial}
Their cardinalities have <= instead of <:
A0 <= |algebraic numbers| <= A0
Thus, |algebraic numbers| = A0.
That is true of complex ones, and for real ones, it's easy:
{Rational numbers} < {Real algebraic numbers} < {Complex algebraic numbers}
A0 <= |real algebraic numbers| <= A0
Thus, |real algebraic numbers| = A0.
But transcendental numbers are real numbers that are not algebraic, and their cardinality is C - A0 = C. Thus, there are infinitely more of them than there are algebraic numbers.