Site index : Home : Me : Food : Lab : Links : Maths : More maths : Rants : Soekris
If we take a set A of order n and define U = A x A, then any relation on A is a subset of U, and any subset of U is a relation on A. P(U), the power set (set of all possible subsets) of U, is then the set of all possible relations on A and |P(U)| = 2|U|. But U = A x A, hence |U| = |A|2; and hence |P(U)| = 2|A|2.
If we define sets Q, R, S and T such that Q is the subset of all antisymmetric relations in P(U), R is the subset of all reflexive relations in P(U), S is the subset of all symmetric relations in P(U), and T is the subset of all transitive relations in P(U), then this defines sixteen classes to one of which every relation on A must belong. I have written a program in C, which for a given n generates every possible relation on a set A of order n, examines each relation, determines which of the properties (antisymmetry, reflexivity, symmetry and transitivity) it possesses, and increments the count for the appropriate class. The program returns results within a reasonable time frame for values of n up to 6 and uses negligible resources other than processor time.
The results so far are as follows (* denotes extrapolations according to my conjectured formulæ and/or sequences already existing in Neil Sloane's On-Line Encyclopedia of Integer Sequences, which I have not verified experimentally to match for sequence terms not shown here):
| n -> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | General formula (conjecture) |
|---|---|---|---|---|---|---|---|---|---|---|
| Orders of Q, R, S, T, U | ||||||||||
| |Q| | 1 | 2 | 12 | 216 | 11,664 | 1,899,568 | 918,330,048 | * 1,338,925,209,884 | * 5,856,458,868,470,016 | (2n)(3((n2-n)/2)) |
| |R| | 1 | 1 | 4 | 64 | 4,096 | 1,048,576 | 1,073,741,824 | 4,398,046,511,104 | 72,057,594,037,927,936 | A053763 = 2n2-n |
| |S| | 1 | 2 | 8 | 64 | 1,024 | 32,768 | 2,097,152 | 268,435,456 | 68,719,476,736 | A006125 = 2(n2+n)/2 |
| |T| | 1 | 2 | 13 | 171 | 3,994 | 154,303 | 9,415,189 | * 878,222,530 | * 122,207,703,623 | A006905 (Klaska) |
| |U| | 1 | 2 | 16 | 512 | 65,536 | 33,554,432 | 68,719,476,736 | 562,949,953,421,312 | 18,446,744,073,709,551,616 | A002416 = 2n2 |
| Partition of U defined by Q and R (antisymmetry and reflexivity) | ||||||||||
| |!Q!R| | 0 | 0 | 3 | 259 | 50,505 | 30,675,337 | 66,741,753,771 | |||
| |!QR| | 0 | 0 | 1 | 37 | 3,367 | 989,527 | 1,059,392,917 | |||
| |Q!R| | 0 | 1 | 9 | 189 | 10,935 | 1,830,519 | 903,981,141 | |||
| |QR| | 1 | 1 | 3 | 27 | 729 | 59,049 | 14,348,907 | A047656 = 3(n2-n)/2 | ||
| Partition of U defined by Q and S (antisymmetry and symmetry) | ||||||||||
| |!Q!S| | 0 | 0 | 0 | 240 | 52,864 | 31,632,128 | 67,799,049,600 | |||
| |!QS| | 0 | 0 | 4 | 56 | 1,008 | 32,736 | 2,097,088 | |||
| |Q!S| | 0 | 0 | 8 | 208 | 11,648 | 1,889,536 | 918,329,984 | |||
| |QS| | 1 | 2 | 4 | 8 | 16 | 32 | 64 | * 128 | * 256 | A000079 = 2n |
| Partition of U defined by Q and T (antisymmetry and transitivity) | ||||||||||
| |!Q!T| | 0 | 0 | 3 | 277 | 53,382 | 31,645,953 | 67,800,052,971 | |||
| |!QT| | 0 | 0 | 1 | 19 | 490 | 18,911 | 1,093,717 | |||
| |Q!T| | 0 | 0 | 0 | 64 | 8,160 | 1,754,176 | 910,008,576 | |||
| |QT| | 1 | 2 | 12 | 152 | 3,504 | 135,392 | 8,321,472 | |||
| Partition of U defined by R and S (reflexivity and symmetry) | ||||||||||
| |!R!S| | 0 | 0 | 6 | 292 | 60,480 | 32,474,112 | 67,643,670,528 | 558,551,660,571,904 | 18,374,686,411,220,582,400 | |U| - |RS| - |R!S| - |!RS| |
| |!RS| | 0 | 1 | 6 | 56 | 960 | 31,744 | 2,064,384 | 266,338,304 | 68,451,041,280 | |S| - |RS| (related to A006129?) |
| |R!S| | 0 | 0 | 2 | 56 | 4,032 | 1,047,552 | 1,073,709,056 | 4,398,034,413,952 | 72,057,593,769,492,480 | |R| - |RS| |
| |RS| | 1 | 1 | 2 | 8 | 64 | 1,024 | 32,768 | 2,097,152 | 268,435,456 | A006125 = 2(n2-n)/2 |
| Partition of U defined by R and T (reflexivity and transitivity) | ||||||||||
| |!R!T| | 0 | 0 | 3 | 306 | 57,801 | 32,358,495 | 67,636,529,250 | |U| - A006905 - |R| + A000798 | ||
| |!RT| | 0 | 1 | 9 | 142 | 3,639 | 147,361 | 9,205,662 | * 868,687,289 | * 11,577,994,269 | A006905 - A000798 |
| |R!T| | 0 | 0 | 0 | 35 | 3,741 | 1,041,634 | 1,073,532,297 | * 4,398,436,975,863 | * 72,057,593,395,148,582 | |R| - A000798 |
| |RT| | 1 | 1 | 4 | 29 | 355 | 6,942 | 209,527 | * 9,535,241 | * 642,779,354 | A000798 |
| Partition of U defined by S and T (symmetry and transitivity) | ||||||||||
| |!S!T| | 0 | 0 | 0 | 292 | 60,570 | 33,367,564 | 68,707,965,272 | |U| - A006905 - |S| + A000110(n+1) | ||
| |!ST| | 0 | 0 | 8 | 156 | 3,942 | 154,100 | 9,414,312 | * 878,218,390 | * 122,207,682,476 | A006905 - A000110(n+1) |
| |S!T| | 0 | 0 | 3 | 49 | 972 | 32,565 | 2,096,275 | 268,431,316 | 68,719,455,589 | |S| - A000110(n+1) |
| |ST| | 1 | 2 | 5 | 15 | 52 | 203 | 877 | 4,140 | 21,147 | A000110(n+1) = A000110(n) + A005493(n) |
| Partition of U defined by Q, R and S (antisymmetry, reflexivity, and symmetry) | ||||||||||
| |!Q!R!S| | 0 | 0 | 0 | 210 | 49,560 | 30,643,624 | 66,739,689,450 | |||
| |!Q!RS| | 0 | 0 | 3 | 49 | 945 | 31,713 | 2,064,321 | |||
| |!QR!S| | 0 | 0 | 0 | 30 | 3,304 | 988,504 | 1,059,360,150 | |||
| |!QRS| | 0 | 0 | 1 | 7 | 63 | 1,023 | 32,767 | * 2,097,151 | * 268,435,455 | 2(n2-n)/2-1 |
| |Q!R!S| | 0 | 0 | 6 | 182 | 10,920 | 1,830,488 | 903,981,078 | |||
| |Q!RS| | 0 | 1 | 3 | 7 | 15 | 31 | 63 | * 127 | * 255 | 2n-1 |
| |QR!S| | 0 | 0 | 2 | 26 | 728 | 59,048 | 14,348,906 | 3(n2-n)/2-1 | ||
| |QRS| | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Partition of U defined by Q, R and T (antisymmetry, reflexivity, and transitivity) | ||||||||||
| |!Q!R!T| | 0 | 0 | 3 | 250 | 50,151 | 30,659,137 | 66,740,739,558 | |||
| |!Q!RT| | 0 | 0 | 0 | 9 | 354 | 16,200 | 1,014,213 | |||
| |!QR!T| | 0 | 0 | 0 | 27 | 3,231 | 986,816 | 1,059,313,413 | |||
| |!QRT| | 0 | 0 | 1 | 10 | 136 | 2,711 | 79,504 | |||
| |Q!R!T| | 0 | 0 | 0 | 56 | 7,650 | 1,699,358 | 895,789,692 | |||
| |Q!RT| | 0 | 1 | 9 | 133 | 3,285 | 131,161 | 8,191,449 | |||
| |QR!T| | 0 | 0 | 0 | 8 | 510 | 54,818 | 14,218,884 | |||
| |QRT| | 1 | 1 | 3 | 19 | 219 | 4,231 | 130,023 | A001035 | ||
| Partition of U defined by Q, S and T (antisymmetry, symmetry, and transitivity) | ||||||||||
| |!Q!S!T| | 0 | 0 | 0 | 228 | 52,410 | 31,613,388 | 67,797,956,696 | |||
| |!Q!ST| | 0 | 0 | 0 | 12 | 454 | 18,740 | 1,092,904 | |||
| |!QS!T| | 0 | 0 | 3 | 49 | 972 | 32,565 | 2,096,275 | |||
| |!QST| | 0 | 0 | 1 | 7 | 36 | 171 | 813 | A058681 | ||
| |Q!S!T| | 0 | 0 | 0 | 64 | 8,160 | 1,754,176 | 910,008,576 | |||
| |Q!ST| | 0 | 0 | 8 | 144 | 3,488 | 135,360 | 8,321,408 | |||
| |QS!T| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | * 0 | * 0 | 0 |
| |QST| | 1 | 2 | 4 | 8 | 16 | 32 | 64 | * 128 | * 256 | 2n |
| Partition of U defined by R, S and T (reflexivity, symmetry, and transitivity) | ||||||||||
| |!R!S!T| | 0 | 0 | 0 | 260 | 56,878 | 32,326,902 | 67,634,465,540 | |!R!S| - |!R!ST| | ||
| |!R!ST| | 0 | 0 | 6 | 132 | 3,602 | 147,210 | 9,204,988 | A006905 - A000798 - A005493 | ||
| |!RS!T| | 0 | 0 | 3 | 46 | 923 | 31,593 | 2,063,710 | 266,335,041 | 68,451,024,273 | |!RS| - |!RST| |
| |!RST| | 0 | 1 | 3 | 10 | 37 | 151 | 674 | 3,263 | 17,007 | A005493 |
| |R!S!T| | 0 | 0 | 0 | 32 | 3,692 | 1,040,662 | 1,073,499,732 | 4,398,034,879,588 | |R!S| - |R!ST| | |
| |R!ST| | 0 | 0 | 2 | 24 | 340 | 6,890 | 209,324 | 9,534,364 | A000798 - A000110 | |
| |RS!T| | 0 | 0 | 0 | 3 | 49 | 972 | 32,565 | 2,096,275 | 268,431,316 | |RS| - |RST| |
| |RST| | 1 | 1 | 2 | 5 | 15 | 52 | 203 | 877 | 4,140 | A000110 (Bell) |
| Partition of U defined by Q, R, S and T (antisymmetry, reflexivity, symmetry, and transitivity) | ||||||||||
| |!Q!R!S!T| | 0 | 0 | 0 | 204 | 49,228 | 30,627,544 | 66,738,675,848 | |||
| |!Q!R!ST| | 0 | 0 | 0 | 6 | 332 | 16,080 | 1,013,602 | |||
| |!Q!RS!T| | 0 | 0 | 3 | 46 | 923 | 31,593 | 2,063,710 | |||
| |!Q!RST| | 0 | 0 | 0 | 3 | 22 | 120 | 611 | |||
| |!QR!S!T| | 0 | 0 | 0 | 24 | 3,182 | 985,844 | 1,059,280,848 | |||
| |!QR!ST| | 0 | 0 | 0 | 6 | 122 | 2,660 | 79,302 | |||
| |!QRS!T| | 0 | 0 | 0 | 3 | 49 | 972 | 32,565 | |||
| |!QRST| | 0 | 0 | 1 | 4 | 14 | 51 | 202 | A058692 | ||
| |Q!R!S!T| | 0 | 0 | 0 | 56 | 7,650 | 1,699,358 | 895,789,692 | |||
| |Q!R!ST| | 0 | 0 | 6 | 126 | 3,270 | 131,130 | 8,191,386 | |||
| |Q!RS!T| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| |Q!RST| | 0 | 1 | 3 | 7 | 15 | 31 | 63 | 127 | 255 | A000225 = 2n-1 |
| |QR!S!T| | 0 | 0 | 0 | 8 | 510 | 54,818 | 14,218,884 | |||
| |QR!ST| | 0 | 0 | 2 | 18 | 218 | 4,230 | 130,022 | A001035 - 1 | ||
| |QRS!T| | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| |QRST| | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| Approximate time for full analysis using single iP3-900 | ||||||||||
| Tcalc | 100ns | 300ns | 2us | 60us | 8ms | 4s | 2h | 2y | 60,000y | 2n2.100ns |
It is clear that the amount of time taken for the analysis grows very rapidly as n increases, and it is not feasible to perform the full analysis for n > 6 without the use of significant computing resources. I have, however, performed partial analyses for n = 7, 8, considering only symmetric relations, and a distributed analysis for n = 7, considering only reflexive relations, and in each case the results obtained match those predicted by the conjectured formulae.
Inductive proofs for the formulae for |Q|, |R|, |S|, |QR|, |QS|, |RS|, |QRS|, |QRST| can be shown easily with the aid of an incidence matrix.
Conjecture: |RST| for any n > 1 is equal to |ST| for n - 1. Also, |RS!T| for any n > 1 is equal to |S!T| for n - 1. Hence, |RS| for each n > 1 is equal to |S| for n - 1.
The above work is a result of a challenge by Professor Des MacHale to perform the order 3 analysis.
Site index : Home : Me : Food : Lab : Links : Maths : More maths : Rants : Soekris
This site was created with vi, and is best viewed with a HTML-capable browser. I welcome feedback on and links to this site. Any views expressed hereon are purely my own. Mail me with your comments! -- cjb at cjb dot ie (the old one is overwhelmed with spam)