Translate

Saturday, October 20, 2007

Mathematical consistency

My prior thinking on logic and then the connection between logic and mathematics through equality finally lead me to realizing that consistency in mathematics is about identity.

So any valid mathematical statement must when numbers are used reduce to an identity, and mathematics is distinguished from the rest of logic only in that its valid statements reduce to numerical tautologies which are identities, like 1=1. That is, mathematics is just a subset of logic.

And mathematical truth can be defined as any mathematical statement where introducing any numbers valid under the conditions given will lead to an identity.

For example, with x=3, y=4 and z=5, it is true that x2 + y2 = z2 as introducing the numbers gives

9 + 16 = 25

which is

25 = 25.

Interestingly, by definition then any valid mathematical statement will give a tautology when numbers are introduced, so any statement that does not, is not a valid mathematical statement.

So by definition, relying merely on the equals being equal, every valid mathematical statement will lead to a tautology, and correct mathematics is consistent.

Extending to logic is straightforward but slightly outside of the scope of this post, though, easily enough I can note that in logic any valid logical statement will lead to a tautology.

And then truth is about tautology, and truth itself can be defined easily enough.

Truth is any unchanging object, concept or thing.

So truth is only about lack of change. Truths are absolutes.


James Harris

Saturday, October 13, 2007

Logic and equality

If you think globally about it EVERY mathematical statement reduces to an identity, like

x2 + y2 = z2, if x=3, y=4, and z=5, you have

9 + 16 = 25

25 = 25

and if that does not occur you do not have a valid mathematical statement.

Another way to say it is that if you plug in all the numbers and do all the mathematical operations then at the end you just get an identity, which in logic is a tautology as it is always true.

So every mathematical statement that is valid can be reduced to an identity.

And now it makes sense to move to logic and find a surprisingly easy way to connect mathematics and logic--through equality.

A few years ago I was pondering something or other (not sure what) and I realized that every logical statement just maps a truth to itself, or as I said to myself then, every logical statement connects a truth to itself.

Like with mathematics, for a logical statement, you must reduce to a tautology if it is a valid logical statement.

You must. There is no logical statement in existence that does not map a truth to itself.

When you have equals, you have equality, in logic, like in mathematics.

That may seem like a strange thing to emphasize, as if you have "=" then doesn't it just mean equal? Well, if it does then you can clear up some things considered big issues in modern logic so that must mean logicians do not necessarily know that equals means equal.

Once I realized that then I realized that anything else could NOT be a logical statement, just like 1=0 is not mathematically valid, as it breaks the equals I like to say.

So if you make sure the equals, as in the equals sign or a declaration of equality, actually mean equal, you must have a logical statement, and intriguingly you can then clean up ALL the supposed logical paradoxes.

I like the consideration of the set of all sets that exclude themselves, except itself, as that one is the easiest.

(Um, in case you didn't notice I resolved the supposed paradox with that "except".)

Harder I think for people to understand is considering a sentence that declares itself to be false.

e.g. This sentence is false.

It is trying to say that it is truthfully false, mapping truth to false, so it is an illogical statement like 1=0 is not a valid mathematical statement. So it doesn't make sense to then say, but if it is false, and is saying it's false, isn't it true? Because to be true it'd have to map a truth to itself, but no truth is false, so it cannot be true!

So it's like the sentence is saying, True = False. And that breaks the equals.

In what I call 3 logic I declare that sentence to be false as it's negatably true and then I continue as if it's not a big deal, but one way to look at that sentence is as a direct declaration that true equals false, which is not letting the equals be equal.

Now in allowing in a system of logic false statements I relied on the idea that a false statement is negatably true, like if you say 1 is 3 three, yeah that's false, but if you say 1 is NOT 3, that is true, so the previous is negatably true.

But I had to have a third type--something other than true or false--as what if you have sjdfkj jumps ships?

But what is a "sjdfkj"?

So if you negate that to get sjdfkj does not jump ships, you still have gobbledygook, so I call that the 0 type, neither true nor false, but still illogical, as the only logical statements are true ones.

Oh I'd like to emphasize that the set of all sets that exclude themselves, except itself, is a complete solution and gives you a single set, as there can be only one in all of infinity.

To see what logicians say on this see: "Russell's Paradox"

The use of the exception class also gives you the way to resolve the related so-called "Barber's Paradox", simply by using an exception.

The Barber shaves every man in the village who doesn't shave himself, except himself.

Now to me using exceptions is natural and rather neat as I have a background in computer programming.

Now then if a logical statement connects a truth to itself then a false statement is NOT a logical statement, nor is one with a truth value of 0, where I say false statement for the false one and for the 0 one I say malformed.

Just like if you have a supposedly valid mathematical equation and it reduces to

2=3

then you know it isn't valid!

I think that it's easier to get this in mathematics because mathematics has to be right to work practically, while the discipline of logic is often just about talking, so if people say one thing but do another--as exceptions are, I'm sure, not new to you--then you can say paradox when you simply ignore using equals in a consistent manner.

So no logical statement can contradict itself; therefore, there can be no logical paradox.

Notice that is true because a logical statement connects a truth to itself, like a mathematical statement connects a number to itself.

So an illogical statement cannot connect a truth to itself, and no logical statement can contradict itself, as it is like saying that 1=1 cannot contradict itself.

So fundamentally mathematics and logic are connected in this necessity that equals means equal!

And I think they should teach that in colleges and universities, so I suggest you go see if they do.


James Harris

Sunday, August 05, 2007

Wrapper theorem and ring of algebraic integers

The ring of algebraic integers has crucial properties which are unique to it involving the use of what I call wrapper values to allow certain factorizations to exist in that ring.

In an integral domain let

d1d2P(x) = (f1(x) + d1c1)(f2(x) + d2c2)

where the d's and c's are non-zero integers, where the d's are coprime to the c's and c1 is coprime to c2, P(x) is a non-monic primitive polynomial with integer coefficients, and where f1(0) = f2(0) = 0 so P(0) is coprime to d1 and d2, as then P(0) = c1c2.

If the ring is the ring of algebraic integers, with non-zero integer x, and d1 = p1 and d2 = p2 where p1 and p2 are differing prime numbers, and f1(x) and f2(x) are non-rational there cannot exist g1(x) and g2(x) such that

d1d2P(x) = (d1g1(x) + d1c1)(d2g2(x) + d2c2)

where

d1g1(x) = f1(x) and d2g2(x) = f2(x).

Proof:

Since P(x) is a polynomial with integer coefficients f1(x) and f2(x) must have values that are roots of the same polynomial. But if f1(x) has d1 as a factor and f2(x) does not, then you can find a non-monic primitive polynomial with integer coefficients irreducible over rationals, which contradicts a well established elementary theorem in number theory that none exists.

So then, how can you divide off d1 and d2?

One way is for the ring to employ what I call wrappers.

Consider w1 and w2, where

d1d2P(x) = ((w1d1)(w1(g1(x)+c1-d2) + (w1)2d1d2)((w2d2)(w2(g2(x)+c2-d1) + (w2)2d1d2)

where w1d1 and w2d2 are roots of a monic polynomial with integer coefficients, so those products are in the ring of algebraic integers while the factors are not.

In my ring of objects the wrappers are units and w1w2 = 1 or -1, while they are NOT units in the ring of algebraic integers.

So the ring of algebraic integers can multiply the factors (f1(x) + d1) and (f2(x) + d2) by numbers that are units in the object ring while also shifting them internally so that it is possible to divide off the d's.

What is left is then

P(x) = ((w1(g1(x)+c1-d2) + w1d2)((w2(g2(x)+c2-d1) + w2d1)

where that detail is available in the object ring as the individual elements are not all available in the ring of algebraic integers.


James Harris

Wednesday, June 20, 2007

Quadratic residue method for finding large primes

The idea is to get quadratic residues modulo some non-square and iterate up with them in the search for ever larger primes.

Start with, say 29 and let 17 be the non-square.

That gives

292 - 17 = 824 = 8*103

and 103 is prime, so now you use 1032 - 17 = 32*331, giving you 331, and now I'm wondering why I picked 17.

It's maybe quicker to just use n2 - 2, as then you get mostly primes at first though as you go farther out with bigger numbers you do tend to get composites.

The idea just shifts you to another distribution of primes--primes with a quadratic residue of 17 or 2 or whatever non-square you pick--so the probability is higher that you will get primes than just going with naturals.

Hmmm...let me do one more iteration, so 3312 - 17 = 8*13693, so it's starting to pick up a little steam. So I went from 29 to 103, to 331, to 13693, in three iterations.

Next would be 136932 - 17 = ( 23 )( 19 )( 43 )( 28687 ).

Then next is 286872 - 17 = ( 24 )( 1429 )( 35993 ).

So this thing is going slow, oh well, so maybe it's not so great an idea for that reason?

Here's another iteration:

359932 - 17 = ( 25 )( 179 )( 226169 )

and one more

2261692 - 17 = ( 25 )( 1598513017 )

and one last one:

15985130172 - 17 = ( 25 )( 229 )( 859 )( 1879 )( 216036409 )

Went backwards with that one. Oh well, just an idea...

One more to leave on a high note:

2160364092 - 17 = ( 25 )( 19 )( 76762713838183 )

Looks like you get about 5 bits added to the length per iteration.


James Harris

Sunday, January 21, 2007

Using prime counting formula

I've talked a lot in various formats across the web about a way to count prime numbers that I found back in 2002, but I don't see a lot of places where I go through a simple example, so I'll go through a basic example.

I am going to next give my prime counting function in its sieve form, where things might look a bit complicated but I'm going to break it all down simply to count the primes up to 100.

Sieve form of my prime counting function:

With natural numbers x and n, where p_i is the i_th prime:

P(x,n) = x - 1 - sum for i=1 to n of {P([x/p_i],i-1) - (i-1)}

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

The word "sieve" is used a lot like it is used in non-math areas to mean a way to block out certain things while getting just what you want. And to count the primes up to 100 the sieve part has to do with getting primes, as you first need to already know the primes up to the positive square root of 100, which is of course 10.

And those primes are 2, 3, 5, and 7, and there are 4 of them, so with

x=100, n = 4, and I can go back and expand out what I had before:

P(100,4) = 100 - 1 - (P([100/2], 0)-0) - (P([100/3], 1) - 1) - (P([100/5, 2) - 2 )- (P([100/7], 3) - 3 )

where I want to explain the part with the brackets, as, for instance,[100/3] = 33.

The brackets are called the floor function and mean to drop off any remainder when you do the division, which is a good thing, as it makes it easier to do the calculation without worry about any decimal places or fractions.

So, now I can go forward to get:

P(100,4) = 99 - P(50, 0) - P(33, 1) + 1 - P(20, 2) + 2 - P(14, 3) + 3

but with P(14,3) I need to do the reset mentioned in the definition as there are only 2 primes up to the positive of sqrt(14) as those are 2 and 3, so that needs to be changed to 2, and I can add all the integers together so I have:

P(100,4) = 105 - P(50, 0) - P(33, 1) - P(20, 2) - P(14, 2)

So now what? Well the function has called itself 4 times so you go through each time, and the first is easy enough as you now have

P(50, 0) = 50 - 1 = 49

as the 0 means no other iterations, because you go from 1, in the definition above. But,

P(33, 1) = 33 - 1 - P([33/2], 0) + 0 = 32 - P[16,0] = 32 - 15 = 17

I know that P[16,0] equals 15 from what I learned with the previous case as the 0 means not to iterate so you just subtract 1, so that's easy. Next is

P(20, 2) = 20 - 1 - (P([20/2], 0) - 0) - (P([20/3], 1) - 1)

so

P(20, 2) = 19 - P(10, 0) - P(6, 1) + 1

and the P(10,0) is easy to get as that is just 9. And there is a short-cut for P(6,1) though you can go the long way if you want, or you can notice that there is only one prime less than the positive square root of 6 as that prime is 2, so P(6,1) must be the count of primes up to 6, and those are 2, 3 and 5, so it is 3. Then

P(20, 2) = 20 - 9 - 3 = 8

and you may notice that is the count of primes up to 20. As 2 is equal to the number of primes less than the positive square root of 20.

So now only P(14, 2) is left and you may think now this is a long process but I am explaining a lot so you can have a clear idea of how it works. Once you get a feel for it though, it's a fast and easy way to count primes.

Now with P(14, 2) I can use the formula or I can just notice that it is the count of primes up to 14, which is 6, as those are 2, 3, 5, 7, 11 and 13. (As an exercise you can go ahead with the formula and verify you get 6.)

So now finally I can get the count of primes up to 100:

P(100,4) = 105 - 49 - 17 - 8 - 6 = 25

To verify your prime counts you can go on to web to various sources.

Ok, so that is a detailed explanation of how to use that formula which is the sieve form of my prime counting function.

Just for fun, I'll do a quick calculation for 120, as that's the last number before you need another prime, so n still equals 4, like before and

P(120,4) = 120 - 1 - (P([120/2], 0)-0) - (P([120/3], 1) - 1) - (P([120/5, 2) - 2 )- (P([120/7], 3) - 3 )

so

P(120,4) = 119 - 59 - P(40, 1) + 1 - P(24, 2) + 2 - P(17, 2) + 3

where P(17,3) goes to P(17,2) using the reset because there are only two primes up to the positive square root of 17. And now for some short-cuts, as P(24, 2) is the count of primes up to 24, and I'll just count those off on my fingers to get P(24, 2) = 9, and doing the same with P(17,2) gives

P(17,2) = 7

and hope you caught that one as I didn't at first as 17 is prime, so it gets counted.

And

P(40,1) = 40 - 1 - P(20,0) = 39 - 19 = 20

so I have

P(120,4) = 119 - 59 - 20 + 1 - 9 + 2 - 7 + 3 = 30.

So just like that you know there are 5 more primes after 100, before 120 and those are:

101, 103, 107, 109, and 113

And yes, if you just like playing with numbers you can easily keep doing prime counts where it's kind of a good idea to keep short-cut information handy.


James Harris (Edited to correct an error--P(14,2) instead of P(14,1)--8/30/09.)