lpetrich
Contributor
I don't know which of the angles is the 46d one.
That is correct for the total angles GHE and GFE, but not for their parts. You asked for x = GHF and y = FHE, but I could only find their sum x+y = GHE.
-
Features
The Math Thread
- Thread starter beero1000
- Start date
Bomb#20
Contributor
- Joined
- Sep 27, 2004
- Messages
- 8,244
- Location
- California
- Gender
- It's a free country.
- Basic Beliefs
- Rationalism
You're needlessly complicating the problem by choosing HG as your baseline. I used the same analytical geometry approach as you, but with the origin at E instead of H. That can't substantively change the result -- all it is is a change of coordinates and a change of scale, which means the lengths of the sides are all different but the angles are all the same. When you use EG as the baseline, the linear equations for each side are trivial. Then you can directly solve for the (x,y) coordinates of H: two linear equations in two unknowns. The fact that you can solve for the location of H means HG / HE isn't arbitrary. Then you do the same for the (x,y) coordinates of F, and arctan((Fy - Hy) / (Fx - Hx)) gives you the direction of HF.
beero1000
Veteran Member
Solved this problem today and enjoyed it. It's tricksome, but with a nice elementary solution.
View attachment 8153
Find x and y.
It's the one marked 46 degrees, angle EGF.
If points E, G are fixed then ASA fixes points F and H. Since all points E,F,G,H are fixed then angles GHF and FHE are fixed.
lpetrich
Contributor
Back to group theory, there is a very interesting result called the crystallographic restriction theorem. It states that the only allowable 2D rotations of a lattice are 2-fold, 3-fold, 4-fold, and 6-fold.
I'd earlier found the 2D rotation/reflection (rotoreflection) group elements: D(a) = {{cos(a), -s*sin(a)}, {sin(a), s*cos(a)}} -- s = +1 for rotations and -1 for reflections.
I'll now find all the finite 2D rotoreflection groups. Rotation first. Every element's generated subgroup must be finite, meaning that a = 2π*k/n for k and n relatively prime. Each a generates a cyclic group with order n, and all the a's thus generate a cyclic group with order gcd(all the n's). So we have C
with abstract group Z. Adding reflections means adding elements (one reflection) . (all the rotation elements). This gives us D with abstract group Dih, the dihedral group.
-
Now consider crystal lattices. They have form x(n(k)'s) = sum over k of n(k)*b(k) where each b(k) is a lattice basis vector. The vectors ought not to be collinear, for obvious reasons. There can be fewer basis vectors than space dimensions, and the basis vectors are not unique. Consider:
b1*n1 + b2*n2 = (b1+b2)*n1 + b2*(n2-n1)
changing both the b's and the n's.
For getting the crystallographic restriction theorem, let us consider what maximal symmetry groups that lattices can have. These groups must contain two elements, the identity element (x->x giving n->n) and the inversion element (x->-x giving n->-n), with abstract group Z2.
A 1D lattice is easy: x = n*b. Its MSG is {identity, inversion}, where the inversion is a reflection.
A 2D lattice is where it gets interesting. x(n1,n2) = n1*b1 + n2*b2. Each lattice's MSG contains C2, the group of {identity, inversion}, where the inversion is a 180-d rotation. That makes the possible MSG's C(2n) and D(2n).
Let us consider the shortest lattice distance b0, and let us consider rotating by angle a. Consider triangle OAB, where sides OA and OB have length b0 and angle OAB has value a. How long will AB be? If its length b1 is shorter than b0, then that violates the shortest-length condition. It's simple trigonometry to calculate it:
b1 = 2*b0*sin(a/2)
So a >= 60d. This means that the MSG's are limited to C2, C4, C6 and D2, D4, D6. Counting all their subgroups, the possible symmetry groups are C1, C2, C3, C4, C6, and D1, D2, D3, D4, D6.
Note the gap at n = 5. C5 is not a possible MSG because it does not include inversion. C5 + inversion gives C10, which violates the lattice minimal-length condition.
I'd earlier found the 2D rotation/reflection (rotoreflection) group elements: D(a) = {{cos(a), -s*sin(a)}, {sin(a), s*cos(a)}} -- s = +1 for rotations and -1 for reflections.
I'll now find all the finite 2D rotoreflection groups. Rotation first. Every element's generated subgroup must be finite, meaning that a = 2π*k/n for k and n relatively prime. Each a generates a cyclic group with order n, and all the a's thus generate a cyclic group with order gcd(all the n's). So we have C
with abstract group Z. Adding reflections means adding elements (one reflection) . (all the rotation elements). This gives us D with abstract group Dih, the dihedral group.-
Now consider crystal lattices. They have form x(n(k)'s) = sum over k of n(k)*b(k) where each b(k) is a lattice basis vector. The vectors ought not to be collinear, for obvious reasons. There can be fewer basis vectors than space dimensions, and the basis vectors are not unique. Consider:
b1*n1 + b2*n2 = (b1+b2)*n1 + b2*(n2-n1)
changing both the b's and the n's.
For getting the crystallographic restriction theorem, let us consider what maximal symmetry groups that lattices can have. These groups must contain two elements, the identity element (x->x giving n->n) and the inversion element (x->-x giving n->-n), with abstract group Z2.
A 1D lattice is easy: x
= n*b. Its MSG is {identity, inversion}, where the inversion is a reflection.A 2D lattice is where it gets interesting. x(n1,n2) = n1*b1 + n2*b2. Each lattice's MSG contains C2, the group of {identity, inversion}, where the inversion is a 180-d rotation. That makes the possible MSG's C(2n) and D(2n).
Let us consider the shortest lattice distance b0, and let us consider rotating by angle a. Consider triangle OAB, where sides OA and OB have length b0 and angle OAB has value a. How long will AB be? If its length b1 is shorter than b0, then that violates the shortest-length condition. It's simple trigonometry to calculate it:
b1 = 2*b0*sin(a/2)
So a >= 60d. This means that the MSG's are limited to C2, C4, C6 and D2, D4, D6. Counting all their subgroups, the possible symmetry groups are C1, C2, C3, C4, C6, and D1, D2, D3, D4, D6.
Note the gap at n = 5. C5 is not a possible MSG because it does not include inversion. C5 + inversion gives C10, which violates the lattice minimal-length condition.
lpetrich
Contributor
The most general 2D lattice has MSG C2, but do some lattices have larger MSG's?
Let's consider sixfold symmetry, C6. Consider a minimal-length lattice basis vector, a shortest one, b1 = {1,0} for convenience. Rotating by 60d gives {1/2,sqrt(3)/2}. It makes a good second basis vector b2. The distance to lattice point (n1,n2) is sqrt(n12 + n22 + n1*n2). Its minimum nonzero value is 1. Thus, this triangular lattice satisfies the minimal-length condition.
We can define alternate b2's like b1 - b2 = {1/2,-sqrt(3)/2} and b2 - b1 = {-1/2,sqrt(3)/2}. The first one is a second-axis inversion and the second one a first-axis inversion. Thus, the MSG of this lattice is not just C6, but D6.
Threefold symmetry with that first basis vector produces a second basis vector {-1/2,sqrt(3)/2}, but b1 + b2 = {1/2,sqrt(3)/2}, the sixfold one again.
Let's move on to fourfold symmetry, C4. Consider again a shortest basis vector, b1 = {1,0}. Rotating by 90d gives {0,1}, a good second basis vector. The distance to lattice point (n1,n2) is sqrt(n12 + n22) with minimum nonzero value 1. Thus, this square lattice satisfies the minimal-length condition.
Defining an alternate b2 with - b2 = {0,-1}, we find that it's a second-axis inversion. That makes this lattice's MSG not just C4, but D4.
In summary, C3 and C6 -> D6 and C4 -> D4.
-
Let us now consider C2 without higher rotational symmetries. For the most general lattice, one can show that C2 does not yield any reflections. That is easy to do for some suitable selection of basis vectors. So let us consider what happens when we add a reflection. C2 + one reflection gives D2 = C2 + two reflections in perpendicular directions.
Let us make the reflections inversions of each coordinate: {x,y} -> {-x,y} and {x,-y}. Note that the rotation is inversion of both: {-x,-y}.
Consider basis vector {a,b} where a and b are both > 0. Suppose it to be a shortest one. Then a/sqrt(3) < b < a*sqrt(3). There is another shortest one, {a,-b}, and the two together make a rhombic lattice, complete with MSG D2 in the general case. The square and triangular lattices are special cases of it.
Next suppose that {a,b} is the (m+1)th shortest one, with all the shorter ones being multiples of {0,c}. Then to avoid some shorter one being off-axis, {a,b} - {0,c} must equal {a,-b}. This gives us c = 2b. The length constraint for {a,b} gives us a2+b2 > c2 or a > b*sqrt((2m)2-1). That means that a can be arbitrarily large relative to b. Thus, we get the rhombic lattice again.
Finally, consider a lattice where {a,0} and {0,b} are shorter than any off-axis vectors. This gives us a rectangular lattice, complete with MSG D2 in the general case. The square lattice is a special case of it. So here are the 2D lattices and their symmetries:
General: C2
Rectangular, rhombic: D2
Square: D4
Triangular: D6
Subgroups:
C2 -- C1
D2 -- C2, D1, C1
D4 -- C4, D2, C2, D1, C1
D6 -- C6, D3, C3, D2, C2, D1, C1
The triangular is often called the hexagonal lattice.
Let's consider sixfold symmetry, C6. Consider a minimal-length lattice basis vector, a shortest one, b1 = {1,0} for convenience. Rotating by 60d gives {1/2,sqrt(3)/2}. It makes a good second basis vector b2. The distance to lattice point (n1,n2) is sqrt(n12 + n22 + n1*n2). Its minimum nonzero value is 1. Thus, this triangular lattice satisfies the minimal-length condition.
We can define alternate b2's like b1 - b2 = {1/2,-sqrt(3)/2} and b2 - b1 = {-1/2,sqrt(3)/2}. The first one is a second-axis inversion and the second one a first-axis inversion. Thus, the MSG of this lattice is not just C6, but D6.
Threefold symmetry with that first basis vector produces a second basis vector {-1/2,sqrt(3)/2}, but b1 + b2 = {1/2,sqrt(3)/2}, the sixfold one again.
Let's move on to fourfold symmetry, C4. Consider again a shortest basis vector, b1 = {1,0}. Rotating by 90d gives {0,1}, a good second basis vector. The distance to lattice point (n1,n2) is sqrt(n12 + n22) with minimum nonzero value 1. Thus, this square lattice satisfies the minimal-length condition.
Defining an alternate b2 with - b2 = {0,-1}, we find that it's a second-axis inversion. That makes this lattice's MSG not just C4, but D4.
In summary, C3 and C6 -> D6 and C4 -> D4.
-
Let us now consider C2 without higher rotational symmetries. For the most general lattice, one can show that C2 does not yield any reflections. That is easy to do for some suitable selection of basis vectors. So let us consider what happens when we add a reflection. C2 + one reflection gives D2 = C2 + two reflections in perpendicular directions.
Let us make the reflections inversions of each coordinate: {x,y} -> {-x,y} and {x,-y}. Note that the rotation is inversion of both: {-x,-y}.
Consider basis vector {a,b} where a and b are both > 0. Suppose it to be a shortest one. Then a/sqrt(3) < b < a*sqrt(3). There is another shortest one, {a,-b}, and the two together make a rhombic lattice, complete with MSG D2 in the general case. The square and triangular lattices are special cases of it.
Next suppose that {a,b} is the (m+1)th shortest one, with all the shorter ones being multiples of {0,c}. Then to avoid some shorter one being off-axis, {a,b} - {0,c} must equal {a,-b}. This gives us c = 2b. The length constraint for {a,b} gives us a2+b2 > c2 or a > b*sqrt((2m)2-1). That means that a can be arbitrarily large relative to b. Thus, we get the rhombic lattice again.
Finally, consider a lattice where {a,0} and {0,b} are shorter than any off-axis vectors. This gives us a rectangular lattice, complete with MSG D2 in the general case. The square lattice is a special case of it. So here are the 2D lattices and their symmetries:
General: C2
Rectangular, rhombic: D2
Square: D4
Triangular: D6
Subgroups:
C2 -- C1
D2 -- C2, D1, C1
D4 -- C4, D2, C2, D1, C1
D6 -- C6, D3, C3, D2, C2, D1, C1
The triangular is often called the hexagonal lattice.
lpetrich
Contributor
Let's now consider the 3D crystallographic groups. All the 2D rotation constraints apply to it -- rotations can only be by 0d, 180d, 120d, 90d, and 60d. However, 3D inversions (multiplying by -1) are also possible. Every element is either (rotation) or (reflection) = (inversion) * (rotation).
The rotation-reflection groups can be formed from the pure-rotation ones in either of two ways:
{ (group), (inversion)*(group) }
or with a subgroup that's half the group's order (index 2),
{ (subgroup), (inversion)*(coset) }
Needless to say, each of the second kind of group is a subgroup of one of the first kinds of group.
So our first step is to find the crystallographic pure-rotation groups.
The possible cyclic groups are C1, C2, C3, C4, and C6.
The 3D pure-rotation dihedral groups add 180d rotations around axes perpendicular to the main symmetry axis. Thus, the allowable ones are those with {allowable C group, perpendicular 180d rotations}, or
D1, D2, D3, D4, and D6.
The tetrahedral and octahedral groups T and O are allowable, but the icosahedral one I or Y isn't (no fivefold symmetry allowed).
Adding inversions, and continuing to use Schoenflies notation, we find all these allowable groups:
C1, C2, C3, C4, C6
C1h, C2h, C3h, C4h, C6h
S2, S4, S6 (or C1s, C2s, C3s in my variant notation)
C1v, C2v, C3v, C4v, C6v
D1, D2, D3, D4, D6
D1h, D2h, D3h, D4h, D6h
D1d, D2d, D3d
T, Th, Td, O, Oh
Seems like 36 groups. But some of them are degenerate.
C1h = C1v
C2 = D1
C2h = D1d
C2V = D1h
That leaves 32 groups.
I note that S2 is the pure-inversion group: {I,-I}
-
Now for the abstract groups of all these point groups:
1D
C - Z1 (identity group)
D - Z2 (reflection group)
2D
C - Z
D - Dih or D
3D
C - Z
C(n,h) - Z * Z2
S(2n) or C(n,s) - Z(2n)
C(n,v) - D
D - D
D(n,h) - D * Z2
D(n,d) - D(2n)
T - A4
Th - A4 * Z2
Td - S4
O - S4
Oh - S4 * Z2
I - A5
Ih - A5 * Z2
Here, abstract groups A = Alt and S = Sym
The rotation-reflection groups can be formed from the pure-rotation ones in either of two ways:
{ (group), (inversion)*(group) }
or with a subgroup that's half the group's order (index 2),
{ (subgroup), (inversion)*(coset) }
Needless to say, each of the second kind of group is a subgroup of one of the first kinds of group.
So our first step is to find the crystallographic pure-rotation groups.
The possible cyclic groups are C1, C2, C3, C4, and C6.
The 3D pure-rotation dihedral groups add 180d rotations around axes perpendicular to the main symmetry axis. Thus, the allowable ones are those with {allowable C group, perpendicular 180d rotations}, or
D1, D2, D3, D4, and D6.
The tetrahedral and octahedral groups T and O are allowable, but the icosahedral one I or Y isn't (no fivefold symmetry allowed).
Adding inversions, and continuing to use Schoenflies notation, we find all these allowable groups:
C1, C2, C3, C4, C6
C1h, C2h, C3h, C4h, C6h
S2, S4, S6 (or C1s, C2s, C3s in my variant notation)
C1v, C2v, C3v, C4v, C6v
D1, D2, D3, D4, D6
D1h, D2h, D3h, D4h, D6h
D1d, D2d, D3d
T, Th, Td, O, Oh
Seems like 36 groups. But some of them are degenerate.
C1h = C1v
C2 = D1
C2h = D1d
C2V = D1h
That leaves 32 groups.
I note that S2 is the pure-inversion group: {I,-I}
-
Now for the abstract groups of all these point groups:
1D
C - Z1 (identity group)
D - Z2 (reflection group)
2D
C
- ZD
- Dih or D3D
C
- ZC(n,h) - Z
* Z2S(2n) or C(n,s) - Z(2n)
C(n,v) - D
D
- DD(n,h) - D
* Z2D(n,d) - D(2n)
T - A4
Th - A4 * Z2
Td - S4
O - S4
Oh - S4 * Z2
I - A5
Ih - A5 * Z2
Here, abstract groups A
= Alt and S = Sym
lpetrich
Contributor
There are 14 kinds of 3D lattices, as opposed to 5 kinds of 2D ones, or one kind of 1D one: 
Bravais lattice.
Here they are with their maximal point groups:
Triclinic -- general lattice -- S2 (inversion group)
Monoclinic -- lattice with one vector perpendicular to the two others -- has plain and one-face-centered -- C2h
Orthorhombic -- lattice with all three vectors perpendicular -- has plain, body-centered, one-face-centered, three-face-centered -- D2h
Tetragonal -- lattice with two vectors square and the third one perpendicular -- has plain, body-centered -- D4h
Hexagonal -- lattice with two vectors making an equilateral triangle and the third one perpendicular -- D6h
Rhombohedral -- like hexagonal, but with two equally spaced interior points in the unit cell's main diagonal -- D3d
Cubic -- lattice with all three vectors equally long and orthogonal to each other -- has plain, body-centered, face-centered -- Oh
Subgroups:
S2 -- C1
C2h -- C1h, S2, C2, C1
D2h -- D2, C2v, S2, C2h, C1h, C2, C1
D4h -- D2h, D2d, D4, D2, C4v, C2v, S4, S2, C4h, C2h, C1h, C4, C2, C1
D3d -- D3, C3v, S6, S2, C2h, C1h, C3, C2, C1
D6h -- D3h, D2h, D3d, D6, D3, D2, C6v, C3v, C2v, S6, S2, C6h, C3h, C2h, C1h, C6, C3, C2, C1
Oh -- O, Td, Th, T, D3d, D2d, D4h, D2h, D4, D3, D2, C4v, C3v, C2v, S6, S4, S2, C4h, C2h, C1h, C4, C3, C2, C1
S2 = Ci (inversion)
C1h = C1v = Cs (one-axis inversion)
C2 = D1 (two-axis inversion)
C2h = D1d
C2v = D1h
Bravais lattice.Here they are with their maximal point groups:
Triclinic -- general lattice -- S2 (inversion group)
Monoclinic -- lattice with one vector perpendicular to the two others -- has plain and one-face-centered -- C2h
Orthorhombic -- lattice with all three vectors perpendicular -- has plain, body-centered, one-face-centered, three-face-centered -- D2h
Tetragonal -- lattice with two vectors square and the third one perpendicular -- has plain, body-centered -- D4h
Hexagonal -- lattice with two vectors making an equilateral triangle and the third one perpendicular -- D6h
Rhombohedral -- like hexagonal, but with two equally spaced interior points in the unit cell's main diagonal -- D3d
Cubic -- lattice with all three vectors equally long and orthogonal to each other -- has plain, body-centered, face-centered -- Oh
Subgroups:
S2 -- C1
C2h -- C1h, S2, C2, C1
D2h -- D2, C2v, S2, C2h, C1h, C2, C1
D4h -- D2h, D2d, D4, D2, C4v, C2v, S4, S2, C4h, C2h, C1h, C4, C2, C1
D3d -- D3, C3v, S6, S2, C2h, C1h, C3, C2, C1
D6h -- D3h, D2h, D3d, D6, D3, D2, C6v, C3v, C2v, S6, S2, C6h, C3h, C2h, C1h, C6, C3, C2, C1
Oh -- O, Td, Th, T, D3d, D2d, D4h, D2h, D4, D3, D2, C4v, C3v, C2v, S6, S4, S2, C4h, C2h, C1h, C4, C3, C2, C1
S2 = Ci (inversion)
C1h = C1v = Cs (one-axis inversion)
C2 = D1 (two-axis inversion)
C2h = D1d
C2v = D1h
lpetrich
Contributor
Over in EoG, I'd posted on how infinite sets cause trouble for omniscience -- if one has a set, one can always construct a bigger one from it.
But here, I'll prove some results for the theory of infinite sets. First, some definitions. The cardinality of a set is its number of elements. It can be written as card(A) or |A|. It is a nonnegative integer, with |{}| = 0. Two sets have the same cardinality if there is a bijection between them -- every element of one of them matches an element of the other one with none left over. Consider a function f from set A to set B:
f(A) = B
Sets may have subsets, sets whose elements are contained within them. The inverse relation is supersets. A proper subset lacks at least one element of the original set.
Let's now consider some cardinality arithmetic.
Now a step into infinite sets. Galileo recognized a paradox of them nearly 400 years ago. He considered the positive integers and their squares. There is a bijection between them, yet these squares become less and less dense in the original numbers as one continues in them.
It's a paradox because one expects |proper subset of A| < |A|, while here is a case of |proper subset of A| == |A|. This is a typical feature of infinite sets, and in general, for them,
|proper subset of A| <= |A|
while for finite sets,
|proper subset of A| < |A|
But here, I'll prove some results for the theory of infinite sets. First, some definitions. The cardinality of a set is its number of elements. It can be written as card(A) or |A|. It is a nonnegative integer, with |{}| = 0. Two sets have the same cardinality if there is a bijection between them -- every element of one of them matches an element of the other one with none left over. Consider a function f from set A to set B:
f(A) = B
- Injection -- one-to-one -- every element of A maps onto an element of B with different A elements mapping onto different B elements: for a and a' in A, f(a) == f(a') -> a == a' or a != a' -> f(a) != f(a')
- Surjection -- onto -- every element of B has at least one element of A mapped onto it: for every b in B, there is at least one a in A such that b == f(a).
- Bijection -- one-to-one correspondence -- both an injection and a surjection. An injection has |A| <= |B|, a surjection has |A| >= |B|, and a bijection has |A| == |B|.
Sets may have subsets, sets whose elements are contained within them. The inverse relation is supersets. A proper subset lacks at least one element of the original set.
Let's now consider some cardinality arithmetic.
- For two sets A and B that are disjoint, A intersect B = {}, the empty set, |A union B| = |A| + |B|.
- For two sets A and B, their Cartesian product AxB = {(a,b) for all a in A, b in B}. |AxB| = |A| * |B|
- Likewise for more sets for both of those two.
- For two sets A and B, the set F = {functions f(A) = B: f(a) = b for all a in A and some b in B} has |F| = |B||A|
Now a step into infinite sets. Galileo recognized a paradox of them nearly 400 years ago. He considered the positive integers and their squares. There is a bijection between them, yet these squares become less and less dense in the original numbers as one continues in them.
It's a paradox because one expects |proper subset of A| < |A|, while here is a case of |proper subset of A| == |A|. This is a typical feature of infinite sets, and in general, for them,
|proper subset of A| <= |A|
while for finite sets,
|proper subset of A| < |A|
lpetrich
Contributor
The modern theory of infinite sets was founded by a certain Georg Cantor in the late 19th cy. He showed that for every set, one could construct a larger set in a certain way, and that there is thus an infinite hierarchy of infinities. He called them aleph-0, aleph-1, aleph-2, ... The cardinality aleph-0 is the smallest infinite one, and it is the cardinality of countably infinite sets or just plain countable ones. These sets can be matched onto the positive integers in some way: |positive integers| = aleph-0.
Now consider nonnegative integers. Do the mapping 0 to 1, 1 to 2, 2 to 3, ... Or else
{0, 1, 2, 3, 4, ...} to {1, 2, 3, 4, 5, ...}
Thus, |nonnegative integers| = aleph-0.
Now the integers. One can arrange them in this fashion: {0, 1, -1, 2, -2, 3, -3, ...}. Thus |integers| = aleph-0.
Now to ordered pairs of positive integers. They can be done with zigzagging: {(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ...}. Thus |ordered pairs of positive integers| = aleph-0. This result also applies for all ordered n-tuples of positive integers for finite n.
Now for the positive rational numbers. There is a surjection between ordered pairs of positive integers and the positive rational numbers: (a,b) to a/b. It's a surjection because a and b need not be in lowest terms. But the positive integers are a subset of the positive rational numbers.
Thus, aleph-0 <= |positive rational numbers| <= aleph-0, or |positive rational numbers| = aleph-0.
It is easy to show that |rational numbers| also equals aleph-0.
For the algebraic numbers, one can take thee equations that they satisfy and zigzag over their possible polynomial degrees and coefficient values. This gives the complex algebraic numbers, which are a superset of the real ones. Thus |real algebraic numbers| = aleph-0 also.
For the computable numbers, those that can be approximated arbitrarily closely with a Turing machine, one can consider all possible Turing machines, since those for finding computable numbers are a subset of them. Turing machines have a finite alphabet of state-register symbols and a finite number of tape symbols, thus giving a finite number of transition-table entries:
state-register value, tape value) -> (new state-register value, new tape value, move left or right on the tape)
From zigzagging over their possible values, the number of possible Turing machines is thus countable: aleph-0. Thus, from
|integers| <= |computable numbers| < |Turing machines|
there are aleph-0 computable numbers.
Now consider nonnegative integers. Do the mapping 0 to 1, 1 to 2, 2 to 3, ... Or else
{0, 1, 2, 3, 4, ...} to {1, 2, 3, 4, 5, ...}
Thus, |nonnegative integers| = aleph-0.
Now the integers. One can arrange them in this fashion: {0, 1, -1, 2, -2, 3, -3, ...}. Thus |integers| = aleph-0.
Now to ordered pairs of positive integers. They can be done with zigzagging: {(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), ...}. Thus |ordered pairs of positive integers| = aleph-0. This result also applies for all ordered n-tuples of positive integers for finite n.
Now for the positive rational numbers. There is a surjection between ordered pairs of positive integers and the positive rational numbers: (a,b) to a/b. It's a surjection because a and b need not be in lowest terms. But the positive integers are a subset of the positive rational numbers.
Thus, aleph-0 <= |positive rational numbers| <= aleph-0, or |positive rational numbers| = aleph-0.
It is easy to show that |rational numbers| also equals aleph-0.
For the algebraic numbers, one can take thee equations that they satisfy and zigzag over their possible polynomial degrees and coefficient values. This gives the complex algebraic numbers, which are a superset of the real ones. Thus |real algebraic numbers| = aleph-0 also.
For the computable numbers, those that can be approximated arbitrarily closely with a Turing machine, one can consider all possible Turing machines, since those for finding computable numbers are a subset of them. Turing machines have a finite alphabet of state-register symbols and a finite number of tape symbols, thus giving a finite number of transition-table entries:
state-register value, tape value) -> (new state-register value, new tape value, move left or right on the tape)
From zigzagging over their possible values, the number of possible Turing machines is thus countable: aleph-0. Thus, from
|integers| <= |computable numbers| < |Turing machines|
there are aleph-0 computable numbers.
lpetrich
Contributor
Are the real numbers also countable? One of Georg Cantor's great discoveries is that they are not, and he used an ingenious diagonal argument. Let's confine ourselves to the 0-to-1 interval, and let's match up integers with real numbers in it represented in decimals or their equivalent in some other number base. Starting with the first number, change the first digit. Then change the second number's second digit, and so on down the line. This results in a new number that is different from the ones listed. So this matching up cannot be done, and there are thus more real numbers than integers:
|real numbers| = C > aleph-0
Try this with base 2, and you get 0's and 1's. Consider the position number of each digit. Construct a set of position numbers for 1's but not 0's. That's a subset of the positive integers. If one adds infinite trailing 1's to cases of infinite trailing 0's, one covers all those subsets. The set of all subsets of a set, including itself, is called that set's power set. Thus,
|Power set of the positive integers| >= |real numbers|
They turn out to be equal.
Georg Cantor also proved that the cardinality of set's power set is always greater than that of the original set. Let us suppose that it isn't, and that for every element a of set A, there is some f(a) that is some subset of A. Now consider the set S of all a where f(a) does not contain a. By this premise, there is some s such that f(s) = S. If s is contained in S, then s must be one of those a where f(a) does not contain a. Thus, s is not contained in S. But in that case, then s must be contained in S. A contradiction. Thus,
|power set of A| > |A|
Constructing the power set of A is equivalent to constructing all functions from A to {true,false}, where these functions are subset membership functions. Thus,
|power set of A| = 2|A|
Now consider the subset of all sequences of positive integers. This is equivalent to the set of all functions of positive integers to positive integers. One can get a subset of the real numbers from it by interpreting each sequence as a run length of alternately 1's and 0's. But, it contains all sequences of 1 and 2. Subtract 1 and one gets the trailing digits of all real numbers between 0 and 1. Thus,
|real numbers| <= |functions of positive integers to themselves| <= |real numbers|
or
|functions of positive integers to themselves| = C.
It turns out that the power set of the real numbers has the same cardinality as that of all functions from real numbers to real numbers. All continuous such functions, however, have cardinality C, that of the real numbers. This can be shown from how every real number is the limit of a Cauchy sequence of rational numbers. In fact, this is a definition of real numbers.
There is a nice shortcut proof of that theorem about continuous real functions of Cauchy sequences. Consider repeated exponentiation:
|{f(A) = X}| = |X||A|
|{g(B) = Y}| = |Y||B|
|{g(B) = f(A)| = (|X||A|)|B|
That is, all g such that g(b) = f(a). This makes g a function of a as well as of b, and it maps onto X: g(A,B) = X
The pair of arguments can be interpreted as a single argument with a Cartesian product: g(A,B) = h( (A,B) )
Thus we get
|{h( (A,B) ) = X| = |X||A|*|B|
yielding
(|X||A|)|B| = |X||A|*|B|
So this formula is correct for infinite exponentiation as well as for finite exponentiation.
Turning back to the case of continuous functions, there are |real numbers||rational numbers| of them, or Caleph-0 of them. But C = 2aleph-0, so the number of continuous functions is (2aleph-0)aleph-0 = 2aleph-0*aleph-0 = 2aleph-0 = C again, the real numbers.
This also means that the number of infinite sequences of real numbers is also equal to the number of real numbers.
Likewise, the number of real-number n-tuples is the same as the number of real numbers. One can use this power argument, or else interleaving the digits of real numbers between 0 and 1. If x = a1a2a3... and y = b1b2b3... then one constructs z = a1b1a2b2a3b3...
|real numbers| = C > aleph-0
Try this with base 2, and you get 0's and 1's. Consider the position number of each digit. Construct a set of position numbers for 1's but not 0's. That's a subset of the positive integers. If one adds infinite trailing 1's to cases of infinite trailing 0's, one covers all those subsets. The set of all subsets of a set, including itself, is called that set's power set. Thus,
|Power set of the positive integers| >= |real numbers|
They turn out to be equal.
Georg Cantor also proved that the cardinality of set's power set is always greater than that of the original set. Let us suppose that it isn't, and that for every element a of set A, there is some f(a) that is some subset of A. Now consider the set S of all a where f(a) does not contain a. By this premise, there is some s such that f(s) = S. If s is contained in S, then s must be one of those a where f(a) does not contain a. Thus, s is not contained in S. But in that case, then s must be contained in S. A contradiction. Thus,
|power set of A| > |A|
Constructing the power set of A is equivalent to constructing all functions from A to {true,false}, where these functions are subset membership functions. Thus,
|power set of A| = 2|A|
Now consider the subset of all sequences of positive integers. This is equivalent to the set of all functions of positive integers to positive integers. One can get a subset of the real numbers from it by interpreting each sequence as a run length of alternately 1's and 0's. But, it contains all sequences of 1 and 2. Subtract 1 and one gets the trailing digits of all real numbers between 0 and 1. Thus,
|real numbers| <= |functions of positive integers to themselves| <= |real numbers|
or
|functions of positive integers to themselves| = C.
It turns out that the power set of the real numbers has the same cardinality as that of all functions from real numbers to real numbers. All continuous such functions, however, have cardinality C, that of the real numbers. This can be shown from how every real number is the limit of a Cauchy sequence of rational numbers. In fact, this is a definition of real numbers.
There is a nice shortcut proof of that theorem about continuous real functions of Cauchy sequences. Consider repeated exponentiation:
|{f(A) = X}| = |X||A|
|{g(B) = Y}| = |Y||B|
|{g(B) = f(A)| = (|X||A|)|B|
That is, all g such that g(b) = f(a). This makes g a function of a as well as of b, and it maps onto X: g(A,B) = X
The pair of arguments can be interpreted as a single argument with a Cartesian product: g(A,B) = h( (A,B) )
Thus we get
|{h( (A,B) ) = X| = |X||A|*|B|
yielding
(|X||A|)|B| = |X||A|*|B|
So this formula is correct for infinite exponentiation as well as for finite exponentiation.
Turning back to the case of continuous functions, there are |real numbers||rational numbers| of them, or Caleph-0 of them. But C = 2aleph-0, so the number of continuous functions is (2aleph-0)aleph-0 = 2aleph-0*aleph-0 = 2aleph-0 = C again, the real numbers.
This also means that the number of infinite sequences of real numbers is also equal to the number of real numbers.
Likewise, the number of real-number n-tuples is the same as the number of real numbers. One can use this power argument, or else interleaving the digits of real numbers between 0 and 1. If x = a1a2a3... and y = b1b2b3... then one constructs z = a1b1a2b2a3b3...
lpetrich
Contributor
I will now introduce a relative of the aleph numbers called the beth numbers: beth-0, beth-1, beth-2, ...
beth-0 = aleph-0 = |positive integers| the countable infinity
beth-(n+1) = 2beth-n the cardinality of the power set of a set with cardinality beth-n.
Thus, beth-1 = C, the continuum cardinality, that of the real numbers, and beth-2 is the cardinality of all real-number-to-real-number functions. However, we cannot proceed any further with such identifications. So as Isaac Asimov once pointed out, in infinite sets, one can only count to 3.
How are the alephs and the beths related? Georg Cantor believed that aleph-1 == beth-1, something called the continuum hypothesis. This can be generalized to aleph-n == beth-n for all n.
But he was unable to prove that hypothesis -- or disprove it. Later mathematicians have found it to be independent of the usual axiomatic formulation of set theory, the Zermelo-Fraenkel axioms. It is also independent of an additional set-theory axiom, the Axiom of Choice. That axiom follows from the other ZF axioms for finite sets, but not for infinite ones.
beth-0 = aleph-0 = |positive integers| the countable infinity
beth-(n+1) = 2beth-n the cardinality of the power set of a set with cardinality beth-n.
Thus, beth-1 = C, the continuum cardinality, that of the real numbers, and beth-2 is the cardinality of all real-number-to-real-number functions. However, we cannot proceed any further with such identifications. So as Isaac Asimov once pointed out, in infinite sets, one can only count to 3.
How are the alephs and the beths related? Georg Cantor believed that aleph-1 == beth-1, something called the continuum hypothesis. This can be generalized to aleph-n == beth-n for all n.
But he was unable to prove that hypothesis -- or disprove it. Later mathematicians have found it to be independent of the usual axiomatic formulation of set theory, the Zermelo-Fraenkel axioms. It is also independent of an additional set-theory axiom, the Axiom of Choice. That axiom follows from the other ZF axioms for finite sets, but not for infinite ones.
lpetrich
Contributor
For an infinite sequence of real numbers x, y, z, ... one can push them to within 0-to-1 and one gets digits
x' = a1a2a3...
y' = b1b2b3...
z' = c1c2c3...
then one zigzags through them: a1a2b1a3b2c1... in the fashion of constructing pairs of positive integers. This gives a real number between 0 and 1.
Symbolically,
|Z+| = |Z0+| = |Z| = |Q| = |algebraic| = |computable| = aleph-0 = beth-0, the countable cardinality
For finite n and |S| = aleph-0, |all n-tuples of S = all functions of {1...n} to S: S^n| = aleph-0
|R| = |R(semi-infinite interval)| = |R(finite interval)| = C = beth-1 = 2^(aleph-0)
For finite or countable n and |S| = C, |all n-tuples of S = all functions of {1...n} to S: S^n| = C
For n >= 2 or n countable, |all functions of countable set S to {1...n}| = n^(aleph-0) = C
|all functions from R to R: R^R| = beth-2 = 2^(beth-1) = 2^C
I was reluctant to mention the natural numbers and the whole numbers. I've seen these definitions:
For finite-set cardinalities, one needs zero, so it's the nonnegative integers for them. In fact, one can define nonnegative integers in that fashion, complete with Peano's axioms. For those, one needs a successor function for set cardinalities. For that, one can define a sequence of successor sets, using
Successor of a set A = A union {A}
with the first set being the empty set.
Thus, one has
{}
{{}}
{{},{{}}}
{{},{{}},{{},{{}}}}
...
x' = a1a2a3...
y' = b1b2b3...
z' = c1c2c3...
then one zigzags through them: a1a2b1a3b2c1... in the fashion of constructing pairs of positive integers. This gives a real number between 0 and 1.
Symbolically,
|Z+| = |Z0+| = |Z| = |Q| = |algebraic| = |computable| = aleph-0 = beth-0, the countable cardinality
For finite n and |S| = aleph-0, |all n-tuples of S = all functions of {1...n} to S: S^n| = aleph-0
|R| = |R(semi-infinite interval)| = |R(finite interval)| = C = beth-1 = 2^(aleph-0)
For finite or countable n and |S| = C, |all n-tuples of S = all functions of {1...n} to S: S^n| = C
For n >= 2 or n countable, |all functions of countable set S to {1...n}| = n^(aleph-0) = C
|all functions from R to R: R^R| = beth-2 = 2^(beth-1) = 2^C
I was reluctant to mention the natural numbers and the whole numbers. I've seen these definitions:
- Natural numbers = positive integers (Z+)
- Natural numbers = nonnegative integers (Z0+)
- Whole numbers = nonnegative integers (Z0+)
For finite-set cardinalities, one needs zero, so it's the nonnegative integers for them. In fact, one can define nonnegative integers in that fashion, complete with Peano's axioms. For those, one needs a successor function for set cardinalities. For that, one can define a sequence of successor sets, using
Successor of a set A = A union {A}
with the first set being the empty set.
Thus, one has
{}
{{}}
{{},{{}}}
{{},{{}},{{},{{}}}}
...
lpetrich
Contributor
As to how one gets from an interval of real numbers to all the real numbers, functions for doing so work only on open intervals, intervals without the endpoints.
But one can turn a closed interval into an open one by pushing in the endpoints. Thus, for [0,1], one can do 0 -> 1/4, 1/4->3/8, 3/8->7/16, ..., making a sequence (1/2)(1 - 2-n). Likewise, one can do 1 -> 3/4, 3/4->5/8, 5/8->9/16, ..., with sequence (1/2)(1 + 2-n). One can also make endpoints in this fashion if they are initially absent, by pulling them out of the set. Thus, the closed interval, [0,1], the semiopen intervals [0,1) and (0,1], and the open interval (0,1) all have the same number of points, the same as for all the real numbers.
One such function from (0,1) to all the reals is f(x) = (2x-1)/( x*(1-x) ) = 1/(1-x) - 1/x. It is monotonically increasing, thus it is a bijection. Its inverse is
(x - 2 + sqrt(x^2+4))/(2x) = 2/(-x + 2 + sqrt(x^2+4))
Another such function is f(x) = tan(pi*(x-1/2)) with inverse 1/2+pi*arctan(x). It is also a bijection.
Still another one is (2x-1)/sqrt((2x-1)2-1) Its inverse is (1/2)*(1 + x/sqrt(1+x2)). Also a bijection.
Since continuous functions from real numbers to real numbers have cardinality C, that means that differentiable functions also do so, since they are a subset of the continuous ones. That also means that all analytic functions of the complex numbers also do so, along with the complex numbers themselves.
Now for permutations of positive integers, how many are there? In set-theoretic terms, a permutation is a self-bijection. For a finite set A,
|self-bijections of A| = |A|! = factorial(|A|)
Permutations of the positive integers are a subset of sequences of positive integers, thus
(aleph-0)! <= (aleph-0)(aleph-0) = C
But there is a surjection of the permutations of Z+ onto permutations of a countable number of two symbols A and B, like whether a number is even or odd. A subset of them has finite run lengths of A's and B's, so one gets an infinite sequence of positive integers. Thus, (aleph-0)! >= C. Combined,
|Permutations of positive integers: their self-bijections| = (aleph-0)! = C
But one can turn a closed interval into an open one by pushing in the endpoints. Thus, for [0,1], one can do 0 -> 1/4, 1/4->3/8, 3/8->7/16, ..., making a sequence (1/2)(1 - 2-n). Likewise, one can do 1 -> 3/4, 3/4->5/8, 5/8->9/16, ..., with sequence (1/2)(1 + 2-n). One can also make endpoints in this fashion if they are initially absent, by pulling them out of the set. Thus, the closed interval, [0,1], the semiopen intervals [0,1) and (0,1], and the open interval (0,1) all have the same number of points, the same as for all the real numbers.
One such function from (0,1) to all the reals is f(x) = (2x-1)/( x*(1-x) ) = 1/(1-x) - 1/x. It is monotonically increasing, thus it is a bijection. Its inverse is
(x - 2 + sqrt(x^2+4))/(2x) = 2/(-x + 2 + sqrt(x^2+4))
Another such function is f(x) = tan(pi*(x-1/2)) with inverse 1/2+pi*arctan(x). It is also a bijection.
Still another one is (2x-1)/sqrt((2x-1)2-1) Its inverse is (1/2)*(1 + x/sqrt(1+x2)). Also a bijection.
Since continuous functions from real numbers to real numbers have cardinality C, that means that differentiable functions also do so, since they are a subset of the continuous ones. That also means that all analytic functions of the complex numbers also do so, along with the complex numbers themselves.
Now for permutations of positive integers, how many are there? In set-theoretic terms, a permutation is a self-bijection. For a finite set A,
|self-bijections of A| = |A|! = factorial(|A|)
Permutations of the positive integers are a subset of sequences of positive integers, thus
(aleph-0)! <= (aleph-0)(aleph-0) = C
But there is a surjection of the permutations of Z+ onto permutations of a countable number of two symbols A and B, like whether a number is even or odd. A subset of them has finite run lengths of A's and B's, so one gets an infinite sequence of positive integers. Thus, (aleph-0)! >= C. Combined,
|Permutations of positive integers: their self-bijections| = (aleph-0)! = C
lpetrich
Contributor
I've found another interesting theorem about infinite sets: the set of all *finite* subsets of a countable set is also countable.
Let's take the positive integers for convenience. A finite set of them can be mapped onto a positive integer in this way:
{n1, n2, n3, ...} -> p1n1 * p2n2 * p3n3 * ...
for distinct prime numbers p1, p2, p3, ... like 2, 3, 5, ...
This is an injection from the set of finite subsets of positive integers FPSZ+ into the positive integers Z+.
There is also an injection from Z+ into FPSZ+: n -> {n}
Thus, there is a bijection for Z+ and FPSZ+, and thus, FPSZ+ is countable: |FPSZ+| = aleph-0.
-
Now for irrational numbers being uncountable. elementary set theory - Proof that the irrational numbers are uncountable - Mathematics Stack Exchange has a proof of it, working from Proof that e is irrational, where e is the base of the natural logarithms.
Start with BnSq, all the infinite binary sequences, sequences of 0 and 1. |BnSq| = C. Now omit those that have infinite trailing 0's, giving NTZBnSq. What is that set's cardinality? Take element {b1,b2,b3,...} of BnSq and construct {1,b1,1,b2,1,b3,...}. Thus, that set has cardinality |BnSq| = C. Thus, |BnSq| < |NTZBnSq| <= |BnSq| or |NTZBnSq| = C.
Now construct E(b) = sum of b(k)/k! for k from 0 to infinity where the sequence b is here counted from zero.
One can show that if b is in NTZBnSq, then E(b) will be irrational, parallel to a proof that e is irrational. Since |NTZBnSq| = C, we have
C <= |irrational numbers| <= C
thus
|irrational numbers| = C
-
This is a rather complicated proof, and it depends on proof of irrationality. It is also hard to generalize to the non-integer real numbers, the transcendental numbers, and the uncomputable numbers, among sets of real numbers without some countable subset of them.
But hw8ans.pdf has a rather simple proof that
|(real numbers) - (countable subset of them)| = |real numbers| = C
For the real numbers R, consider a countable subset of them, S, and find a countable subset T of (R - S), all elements of R not in S. Now define a bijection f between R and (R - S):
f(x in (R - (S union T))) = x
f(s) = t(2n)
f(t) = t(2n-1)
where n = 1, 2, 3, ..., all s are in S, and all t are in T. This bijection thus pushes the elements of S into (R - S), moving elements of T out of the way for them.
Thus, |R - S| = |R| = C
Thus, |non-integer real numbers| = |irrational numbers| = |transcendental numbers| = |uncomputable numbers| = C
Some countable subsets:
I note that this proof also works for any uncountably infinite set where one can find two disjoint countably-infinite subsets.
Let's take the positive integers for convenience. A finite set of them can be mapped onto a positive integer in this way:
{n1, n2, n3, ...} -> p1n1 * p2n2 * p3n3 * ...
for distinct prime numbers p1, p2, p3, ... like 2, 3, 5, ...
This is an injection from the set of finite subsets of positive integers FPSZ+ into the positive integers Z+.
There is also an injection from Z+ into FPSZ+: n -> {n}
Thus, there is a bijection for Z+ and FPSZ+, and thus, FPSZ+ is countable: |FPSZ+| = aleph-0.
-
Now for irrational numbers being uncountable. elementary set theory - Proof that the irrational numbers are uncountable - Mathematics Stack Exchange has a proof of it, working from
Proof that e is irrational, where e is the base of the natural logarithms.Start with BnSq, all the infinite binary sequences, sequences of 0 and 1. |BnSq| = C. Now omit those that have infinite trailing 0's, giving NTZBnSq. What is that set's cardinality? Take element {b1,b2,b3,...} of BnSq and construct {1,b1,1,b2,1,b3,...}. Thus, that set has cardinality |BnSq| = C. Thus, |BnSq| < |NTZBnSq| <= |BnSq| or |NTZBnSq| = C.
Now construct E(b) = sum of b(k)/k! for k from 0 to infinity where the sequence b is here counted from zero.
One can show that if b is in NTZBnSq, then E(b) will be irrational, parallel to a proof that e is irrational. Since |NTZBnSq| = C, we have
C <= |irrational numbers| <= C
thus
|irrational numbers| = C
-
This is a rather complicated proof, and it depends on proof of irrationality. It is also hard to generalize to the non-integer real numbers, the transcendental numbers, and the uncomputable numbers, among sets of real numbers without some countable subset of them.
But hw8ans.pdf has a rather simple proof that
|(real numbers) - (countable subset of them)| = |real numbers| = C
For the real numbers R, consider a countable subset of them, S, and find a countable subset T of (R - S), all elements of R not in S. Now define a bijection f between R and (R - S):
f(x in (R - (S union T))) = x
f(s
) = t(2n)f(t
) = t(2n-1)where n = 1, 2, 3, ..., all s
are in S, and all t are in T. This bijection thus pushes the elements of S into (R - S), moving elements of T out of the way for them.Thus, |R - S| = |R| = C
Thus, |non-integer real numbers| = |irrational numbers| = |transcendental numbers| = |uncomputable numbers| = C
Some countable subsets:
- Non-integer real numbers: all (n + 1/2) for n an integer
- Irrational numbers: all n*sqrt(2) for n a positive integer
- Transcendental numbers: all n*e for n a positive integer
- Uncomputable numbers: all n*(Chaitin's constant) for n a positive integer
I note that this proof also works for any uncountably infinite set where one can find two disjoint countably-infinite subsets.
lpetrich
Contributor
Oops, those are real numbers without various countable subsets (integers, rational numbers, algebraic numbers, computable numbers).
This discussion had brought up Turing machines. These are a theoretical abstraction for modeling computing. They have these parts:
S: alphabet of state symbols
T: alphabet of tape symbols
F: alphabet of final symbols, a subset of S
A state register. It contains a symbol from S.
A transition matrix: (S-F, T) -> (S for the state register, T for the tape, direction to move the tape)
If the state register's value is in F, then the Turing machine halts.
An infinite tape divided into cells, with a symbol from T in each one.
A read-write head that in each step moves the tape one cell in either direction.
Initial values of both the state register and the tape cells (usually a blank value for those). One may pass the Turing machine a value as its state register's initial value.
Since a Turing machine is specified with a finite set of parameters, there are countably many possible Turing machines: aleph-0.
A subset of Turing machines is pushdown-stack machines. Their memory is in the form of a stack with last-in-first-out access. One can add symbols from the top of the stack, and also remove symbols from there.
A further subset is finite-state machines. They have no tape or stack, and their only internal memory is the state register.
Even further is combinational-logic machines. They are FSM's that run for one step and then halt.
Alan Turing had proved a famous computability theorem with Turing machines. He proved that it is impossible to construct a Turing machine that can tell when any Turing machine will halt. He did this by showing that an attempt to construct one will run into a contradiction.
I will now show that there is a countable number of both halting and non-halting Turing machines. This can be done by considering finite state machines. One can set up a FSM that goes through N states and either halts or goes into an infinite loop. Since N can be made arbitrarily large, there is thus a countable number of both halting and non-halting FSM's, and thus Turing machines.
This discussion had brought up Turing machines. These are a theoretical abstraction for modeling computing. They have these parts:
S: alphabet of state symbols
T: alphabet of tape symbols
F: alphabet of final symbols, a subset of S
A state register. It contains a symbol from S.
A transition matrix: (S-F, T) -> (S for the state register, T for the tape, direction to move the tape)
If the state register's value is in F, then the Turing machine halts.
An infinite tape divided into cells, with a symbol from T in each one.
A read-write head that in each step moves the tape one cell in either direction.
Initial values of both the state register and the tape cells (usually a blank value for those). One may pass the Turing machine a value as its state register's initial value.
Since a Turing machine is specified with a finite set of parameters, there are countably many possible Turing machines: aleph-0.
A subset of Turing machines is pushdown-stack machines. Their memory is in the form of a stack with last-in-first-out access. One can add symbols from the top of the stack, and also remove symbols from there.
A further subset is finite-state machines. They have no tape or stack, and their only internal memory is the state register.
Even further is combinational-logic machines. They are FSM's that run for one step and then halt.
Alan Turing had proved a famous computability theorem with Turing machines. He proved that it is impossible to construct a Turing machine that can tell when any Turing machine will halt. He did this by showing that an attempt to construct one will run into a contradiction.
I will now show that there is a countable number of both halting and non-halting Turing machines. This can be done by considering finite state machines. One can set up a FSM that goes through N states and either halts or goes into an infinite loop. Since N can be made arbitrarily large, there is thus a countable number of both halting and non-halting FSM's, and thus Turing machines.
lpetrich
Contributor
Another model of computing is the lambda calculus, essentially doing everything with functions. Here, I'll use L instead of λ for typographical convenience. I'll use the usual lambda-calculus notation and then the more usual function notation.
The identity function:
identity = Lx.x ... identity(x) = x
Boolean values:
true = Lp.Lq.p ... true(p,q) = p
false = Lp.Lq.q ... false(p,q) = q
Note that those values are lambda-calculus functions
Boolean functions:
not = Lp.p false true ... not(p) = p(false,true)
and = Lp.Lq.p q p ... and(p,q) = p(q,p)
or = Lp.Lq.p p q ... or(p,q) = p(p,q)
Arithmetic is more complicated, but one can use Peano's axioms: functions that represent 0 and succession.
Like Turing machines, the lambda calculus has a classic undecidability problem: there is no function that can decide whether two general lambda-calculus expressions are equivalent (Dixin's Blog - Lambda Calculus via C# (8) Undecidability of Equivalence). In fact, these two problems are closely related.
-
Still another model is the primitive recursive and mu-recursive functions on natural numbers (nonnegative integers). From Primitive recursive function and μ-recursive function, these functions are built out of the following sorts of functions:
Many familiar algorithms are primitive recursive, but there are some algorithms that are computable without being primitive recursive, like the Ackermann function.
The identity function:
identity = Lx.x ... identity(x) = x
Boolean values:
true = Lp.Lq.p ... true(p,q) = p
false = Lp.Lq.q ... false(p,q) = q
Note that those values are lambda-calculus functions
Boolean functions:
not = Lp.p false true ... not(p) = p(false,true)
and = Lp.Lq.p q p ... and(p,q) = p(q,p)
or = Lp.Lq.p p q ... or(p,q) = p(p,q)
Arithmetic is more complicated, but one can use Peano's axioms: functions that represent 0 and succession.
Like Turing machines, the lambda calculus has a classic undecidability problem: there is no function that can decide whether two general lambda-calculus expressions are equivalent (Dixin's Blog - Lambda Calculus via C# (8) Undecidability of Equivalence). In fact, these two problems are closely related.
-
Still another model is the primitive recursive and mu-recursive functions on natural numbers (nonnegative integers). From
Primitive recursive function and μ-recursive function, these functions are built out of the following sorts of functions:- Constant: f(x1,x2,...,xk) = n
- Successor: S(x) = x + 1
- Projection: P(k,i)(x1,x2,...,xk) = xi
- Composition: for f with k args and g1...gk with m args, we have h(x1,x2,...,xm) = f(g1(x1,x2,...,xm),g2(x1,x2,...,xm),...,gk(x1,x2,...,xm))
- Primitive recursion: for f with k args and g with k+2 args, we have h(0,x1,x2,...,xk) = f(x1,x2,...,xk) and h(S,x1,x2,...,xk) = g(y,h(y,x1,x2,...,xk),x1,x2,...,xk)
- Minimization operator: mu(f)(x1,x2,...,xk) = z if f(z,x1,x2,...,xk) == 0 and f(i,x1,x2,...,xk) != 0 if 0 <= i < z
Many familiar algorithms are primitive recursive, but there are some algorithms that are computable without being primitive recursive, like the
Ackermann function.
lpetrich
Contributor
In his book "Gödel Escher Bach: an Eternal Golden Braid", Douglas Hofstadter described three toy programming languages that he invented to illustrate some aspects of computability: BlooP, FlooP, and GlooP ( BlooP and FlooP, Bloop Floop And Gloop)
BlooP is intended to calculate primitive recursive functions, thus those limitations. But one can do subtraction, factorials, and finding prime numbers with it, and likely many other computing tasks. A BlooP program is guaranteed to halt.
-
The next one up is FlooP. It is BlooP with the mu-loop construction, essentially while(true). A FlooP program is not guaranteed to halt. In fact, it is equivalent to Turing machines' capabilities and the lambda calculus, thus making it Turing-complete. BlooP, however, lacks Turing completelness, and it cannot emulate FlooP.
What is Turing-completeness?
A system is Turing-complete if it can have infinite-sized arrays and if it has conditional-branching control flow. Resource limitations force arrays to have finite sizes and data types to have finite ranges, but that's a secondary issue. Most computing hardware and programming languages are thus Turing-complete and equivalent to FlooP, with exceptions like FPGA's, HTML, CSS, and SQL.
-
GlooP is the next step up after FlooP, able to calculate what FlooP cannot calculate, but it does not seem to be possible. However, adding infinite-array function Pimc Pifl Pire will go at least part of the way.
Pimc = Parallel Infinite MapCar: applies a function to every value of a list
Pifl = Parallel Infinite Filter: uses a function to decide whether to return each value of a list
Pire = Parallel Infinite Reduce: reduces a list to a single value by repeatedly applying a two-arg function to the accumulated value and each list member. For the initial accumulated value, it can either use the first list value and then work on the rest of the list, or it can use an outside-supplied value and work on all of the list.
f(f(f(a1, a2), a3), a4) ...
or
f(f(f(f(init, a1), a2), a3), a4) ...
"MapCar" is the name of a Lisp function. Here are some corresponding functions elsewhere:
These functions are intended to operate on iterator functions as well as to lists. Since they are infinite, the only practical way to implement them is to do them symbolically, in computer-algebra fashion, and that may not always be feasible. One can also distinguish versions of them by the cardinality of the infinity of their operands. Like countable versions and continuum versions.
BlooP and FlooP, Bloop Floop And Gloop)BlooP is very limited. Its only datatype is nonnegative integers, though these can have arbitrary precision. Its only internal variable is an infinite array, "cell", with constant indexing. Its only operations on its data are assignment, addition, multiplication, <, >, and ==. Its only control-flow constructions are if-then, looping with a preset or previously-calculated number of repeats, and exiting code blocks and loops. A function cannot call itself, even indirectly.
BlooP is intended to calculate primitive recursive functions, thus those limitations. But one can do subtraction, factorials, and finding prime numbers with it, and likely many other computing tasks. A BlooP program is guaranteed to halt.
-
The next one up is FlooP. It is BlooP with the mu-loop construction, essentially while(true). A FlooP program is not guaranteed to halt. In fact, it is equivalent to Turing machines' capabilities and the lambda calculus, thus making it Turing-complete. BlooP, however, lacks Turing completelness, and it cannot emulate FlooP.
What is Turing-completeness?
A system is Turing-complete if it can have infinite-sized arrays and if it has conditional-branching control flow. Resource limitations force arrays to have finite sizes and data types to have finite ranges, but that's a secondary issue. Most computing hardware and programming languages are thus Turing-complete and equivalent to FlooP, with exceptions like FPGA's, HTML, CSS, and SQL.
-
GlooP is the next step up after FlooP, able to calculate what FlooP cannot calculate, but it does not seem to be possible. However, adding infinite-array function Pimc Pifl Pire will go at least part of the way.
Pimc = Parallel Infinite MapCar: applies a function to every value of a list
Pifl = Parallel Infinite Filter: uses a function to decide whether to return each value of a list
Pire = Parallel Infinite Reduce: reduces a list to a single value by repeatedly applying a two-arg function to the accumulated value and each list member. For the initial accumulated value, it can either use the first list value and then work on the rest of the list, or it can use an outside-supplied value and work on all of the list.
f(f(f(a1, a2), a3), a4) ...
or
f(f(f(f(init, a1), a2), a3), a4) ...
"MapCar" is the name of a Lisp function. Here are some corresponding functions elsewhere:
- pimc: Mathematica: Map, Python: map, C++ STL: transform
- pifl: Mathematica: Select, Python: filter, C++ STL: copy_if
- pire: Mathematica: Fold, Python: reduce, C++ STL: accumulate, reduce
These functions are intended to operate on iterator functions as well as to lists. Since they are infinite, the only practical way to implement them is to do them symbolically, in computer-algebra fashion, and that may not always be feasible. One can also distinguish versions of them by the cardinality of the infinity of their operands. Like countable versions and continuum versions.
lpetrich
Contributor
I'll sum up infinite-cardinal arithmetic. I'll use A0 for aleph-0 (and beth-0), C for the continuum (and beth-1), and B2 for beth-2.
Subtraction is poorly defined for infinities: {nonnegative integers} - {positive integers} = {0}, while {integers} - {even integers} = {odd integers}. Thus, A0 - A0 = either 1 or A0.
But addition, multiplication, and exponentiation are all well-defined.
Addition: union of two disjoint sets.
Multiplication: Cartesian product: ordered pair of (element of first set, element of second set)
Exponentiation: functions from (element of set for power) to (element of set for base)
Addition and multiplication are both associative, and multiplication is distributive over addition:
a+b = b+a, (a+b)+c = a+(b+c), a*b = b*a, (a*b)*c = a*(b*c), a*(b+c) = (a*b)+(a*c)
0 is the identity of addition and the annihilator of multiplication, while 1 is the identity of multiplication:
a+0 = a, a*0 = 0, a*1 = a
Exponentiation has these familiar identities:
ab+c = (ab)*(ac), ab*c = (ab)c, (a*b)c = (ac)*(bc)
A0 + A0 = A0 (even integers, odd integers)
C + A0 = C (push in a countable subset of the real numbers)
C + C = C (join two neighboring but disjoint line segments)
C - A0 = C (remove a countable subset)
A0 * A0 = A0 (zigzag over possible pairs)
A0 * C = C (A0*C is between 1*C and C*C)
C * C = C (interleave the digits)
A0n = A0 for finite n (all n-tuples)
Cn = C for finite n (all n-tuples)
(A0)! = C (all permutations or self-bijections)
|{all finite subsets of the positive integers}| = A0
2A0 = C (power set, binary representation)
nA0 = C (base-n representation)
A0A0 = C (infinite sequences of rational numbers)
CA0 = C (continuous functions from real numbers to real numbers, infinite sequences of real numbers)
2C = B2 (all functions from real numbers to real numbers)
Subtraction is poorly defined for infinities: {nonnegative integers} - {positive integers} = {0}, while {integers} - {even integers} = {odd integers}. Thus, A0 - A0 = either 1 or A0.
But addition, multiplication, and exponentiation are all well-defined.
Addition: union of two disjoint sets.
Multiplication: Cartesian product: ordered pair of (element of first set, element of second set)
Exponentiation: functions from (element of set for power) to (element of set for base)
Addition and multiplication are both associative, and multiplication is distributive over addition:
a+b = b+a, (a+b)+c = a+(b+c), a*b = b*a, (a*b)*c = a*(b*c), a*(b+c) = (a*b)+(a*c)
0 is the identity of addition and the annihilator of multiplication, while 1 is the identity of multiplication:
a+0 = a, a*0 = 0, a*1 = a
Exponentiation has these familiar identities:
ab+c = (ab)*(ac), ab*c = (ab)c, (a*b)c = (ac)*(bc)
A0 + A0 = A0 (even integers, odd integers)
C + A0 = C (push in a countable subset of the real numbers)
C + C = C (join two neighboring but disjoint line segments)
C - A0 = C (remove a countable subset)
A0 * A0 = A0 (zigzag over possible pairs)
A0 * C = C (A0*C is between 1*C and C*C)
C * C = C (interleave the digits)
A0n = A0 for finite n (all n-tuples)
Cn = C for finite n (all n-tuples)
(A0)! = C (all permutations or self-bijections)
|{all finite subsets of the positive integers}| = A0
2A0 = C (power set, binary representation)
nA0 = C (base-n representation)
A0A0 = C (infinite sequences of rational numbers)
CA0 = C (continuous functions from real numbers to real numbers, infinite sequences of real numbers)
2C = B2 (all functions from real numbers to real numbers)
lpetrich
Contributor
I'll now turn to regular polytopes. "Polytope" is a general term for what is called in two dimensions a polygon, in 3D a polyhedron, and in 4D a polychoron.
A regular polytope is one that is as symmetric as possible, with its subset parts looking alike. A regular polytope can be constructed from lower-dimension ones, and that gives us a clue as to which ones there can be. Regular polytopes can be described with a "Schläfli symbol", after 19th cy. Swiss mathematician Ludwig Schläfli.
A regular polygon is denoted with (p), where p is its number of sides.
A regular polyhedron is denoted with (p1,p2), where p2 of faces (p1) meet at each vertex. Two of them meet at each edge ().
A regular polychoron is denoted with (p1,p2,p3), where p3 of cells (p1,p2) meet at each edge (). Two of them meet at each face (p1).
So in general, a polytope (p1,p2,...p) has p of sub-polytopes (p1,p2,...,p(n-1)) meeting at each sub-polytope (p1,p2,...,p(n-3)). Two of them meet at each sub-polytope (p1,p2,...,p(n-2)).
One can find which ones are possible by using a recurrence relation involving the ratio of (half the edge length) / (radius of the circumscribed circle): s.
A new one is s' = sqrt(1 - (cos(pi/p)/s)2)
where s has Schläfli symbol (p1,p2,...,p) and s has that symbol but with p added at the beginning: (p,p1,p2,...,p).
If s = 0, then one gets a space tiling, while if s is imaginary or if s > 1, one gets a hyperbolic tiling. I will ignore hyperbolic ones.
A regular polytope is one that is as symmetric as possible, with its subset parts looking alike. A regular polytope can be constructed from lower-dimension ones, and that gives us a clue as to which ones there can be. Regular polytopes can be described with a "Schläfli symbol", after 19th cy. Swiss mathematician Ludwig Schläfli.
A regular polygon is denoted with (p), where p is its number of sides.
A regular polyhedron is denoted with (p1,p2), where p2 of faces (p1) meet at each vertex. Two of them meet at each edge ().
A regular polychoron is denoted with (p1,p2,p3), where p3 of cells (p1,p2) meet at each edge (). Two of them meet at each face (p1).
So in general, a polytope (p1,p2,...p
) has p of sub-polytopes (p1,p2,...,p(n-1)) meeting at each sub-polytope (p1,p2,...,p(n-3)). Two of them meet at each sub-polytope (p1,p2,...,p(n-2)).One can find which ones are possible by using a recurrence relation involving the ratio of (half the edge length) / (radius of the circumscribed circle): s.
A new one is s' = sqrt(1 - (cos(pi/p)/s)2)
where s has Schläfli symbol (p1,p2,...,p
) and s has that symbol but with p added at the beginning: (p,p1,p2,...,p).If s = 0, then one gets a space tiling, while if s is imaginary or if s > 1, one gets a hyperbolic tiling. I will ignore hyperbolic ones.
lpetrich
Contributor
Let's see what we have. A Schläfli symbol with length n is for a (n+1)-D polytope, or else for a n-D space tiling. I'll also consider only integer values of the symbols' values, and integer values >= 3. A value of 2 is a degenerate case. A polygon with it reduces to a line segment.
Length 0
s() = 1 -- line segments.
Length 1
The regular polygons, and one can easily show that s(p) = sin(pi/p)
One gets a line tiling as an infinite chain of line segments: p -> infinity.
The ones that can be continued are
s(3) = sqrt(3)/2 -- triangle (3-side)
s(4) = 1/sqrt(2) -- square (4-side)
s(5) = (1/4)*sqrt(10-2*sqrt(5)) -- pentagon (5-side)
s(6) = 1/2 -- hexagon (6-side)
Length 2
s(33) = sqrt(2/3) -- tetrahedron (4-face)
s(43) = 1/sqrt(3) -- cube (6-face)
s(53) = (sqrt(5)-1)/(2*sqrt(3)) -- dodecahedron (12-face)
s(63) = 0 -- hexagonal plane tiling
s(34) = 1/sqrt(2) -- octahedron (8-face)
s(44) = 0 -- square plane tiling
s(35) = sqrt(10-2*sqrt(5))/(2*sqrt(5)) -- icosahedron (20-face)
s(36) = 0 -- triangular plane tiling
So we get the 5 Platonic solids and 3 plane tilings
Length 3
s(333) = sqrt(5)/(2*sqrt(2)) -- simplex (5-cell)
s(433) = 1/2 -- tesseract or hypercube (8-cell)
s(533) = (3 - sqrt(5))/(4*sqrt(2)) -- 120-cell
s(343) = 1/2 -- 24-cell (halfway between an 8-cell and a 16-cell)
s(334) = 1/sqrt(2) -- cross-polytope (16-cell)
s(434) = 0 -- cubic space tiling
s(335) = (5-sqrt(5)/4 -- 600-cell
Length 4
s(3333) = sqrt(3/5) -- simplex
s(4333) = 1/sqrt(5) -- hypercube
s(3433) = 0 -- 24-cell space tiling
s(3343) = 0 -- 16-cell space-tiling
s(3334) = 1/sqrt(2) -- cross-polytope
s(4334) = 0 -- 8-cell (tesseract) space tiling
Length 5
s(33333) = (1/2)*sqrt(7/3) -- simplex
s(43333) = 1/sqrt(6) -- hypercube
s(33334) = 1/sqrt(2) -- cross-polytope
s(43334) = 0 -- hypercube space tiling
Length 6
s(333333) = 2/sqrt(7) -- simplex
s(433333) = 1/sqrt(7) -- hypercube
s(333334) = 1/sqrt(2) -- cross-polytope
s(433334) = 0 -- hypercube space tiling
Families
It ought to be evident that the polytopes settle down into a few families. In fact, these families are infinite. Their Schläfli symbols:
s(33...33) = sqrt((n+1)/(2n)) -- n-D simplex: triangle, tetrahedron, ...
s(43...33) = 1/sqrt -- n-D hypercube: square, cube, tesseract, ...
s(33...34) = 1/sqrt(2) -- n-D cross-polytope: square, octahedron, ...
s(43...34) = 0 -- hypercube space tiling
The extra ones are as follows:
2D: polygons with at least 5 sides, and two plane tilings, the triangular and hexagonal plane ones
3D: the regular dodecahedron and icosahedron
4D: the 24-cell, 120-cell, and 600-cell, and two space tilings, for the 16-cell and the 24-cell
Length 0
s() = 1 -- line segments.
Length 1
The regular polygons, and one can easily show that s(p) = sin(pi/p)
One gets a line tiling as an infinite chain of line segments: p -> infinity.
The ones that can be continued are
s(3) = sqrt(3)/2 -- triangle (3-side)
s(4) = 1/sqrt(2) -- square (4-side)
s(5) = (1/4)*sqrt(10-2*sqrt(5)) -- pentagon (5-side)
s(6) = 1/2 -- hexagon (6-side)
Length 2
s(33) = sqrt(2/3) -- tetrahedron (4-face)
s(43) = 1/sqrt(3) -- cube (6-face)
s(53) = (sqrt(5)-1)/(2*sqrt(3)) -- dodecahedron (12-face)
s(63) = 0 -- hexagonal plane tiling
s(34) = 1/sqrt(2) -- octahedron (8-face)
s(44) = 0 -- square plane tiling
s(35) = sqrt(10-2*sqrt(5))/(2*sqrt(5)) -- icosahedron (20-face)
s(36) = 0 -- triangular plane tiling
So we get the 5 Platonic solids and 3 plane tilings
Length 3
s(333) = sqrt(5)/(2*sqrt(2)) -- simplex (5-cell)
s(433) = 1/2 -- tesseract or hypercube (8-cell)
s(533) = (3 - sqrt(5))/(4*sqrt(2)) -- 120-cell
s(343) = 1/2 -- 24-cell (halfway between an 8-cell and a 16-cell)
s(334) = 1/sqrt(2) -- cross-polytope (16-cell)
s(434) = 0 -- cubic space tiling
s(335) = (5-sqrt(5)/4 -- 600-cell
Length 4
s(3333) = sqrt(3/5) -- simplex
s(4333) = 1/sqrt(5) -- hypercube
s(3433) = 0 -- 24-cell space tiling
s(3343) = 0 -- 16-cell space-tiling
s(3334) = 1/sqrt(2) -- cross-polytope
s(4334) = 0 -- 8-cell (tesseract) space tiling
Length 5
s(33333) = (1/2)*sqrt(7/3) -- simplex
s(43333) = 1/sqrt(6) -- hypercube
s(33334) = 1/sqrt(2) -- cross-polytope
s(43334) = 0 -- hypercube space tiling
Length 6
s(333333) = 2/sqrt(7) -- simplex
s(433333) = 1/sqrt(7) -- hypercube
s(333334) = 1/sqrt(2) -- cross-polytope
s(433334) = 0 -- hypercube space tiling
Families
It ought to be evident that the polytopes settle down into a few families. In fact, these families are infinite. Their Schläfli symbols:
s(33...33) = sqrt((n+1)/(2n)) -- n-D simplex: triangle, tetrahedron, ...
s(43...33) = 1/sqrt
-- n-D hypercube: square, cube, tesseract, ...s(33...34) = 1/sqrt(2) -- n-D cross-polytope: square, octahedron, ...
s(43...34) = 0 -- hypercube space tiling
The extra ones are as follows:
2D: polygons with at least 5 sides, and two plane tilings, the triangular and hexagonal plane ones
3D: the regular dodecahedron and icosahedron
4D: the 24-cell, 120-cell, and 600-cell, and two space tilings, for the 16-cell and the 24-cell