Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've edited this question to make it more understandable:


newly worded

See the following pairs of descriptions of sets.

'n mod 2 = 0', '2 * int(n)'

'sqrt(x^2+y^2) = 1', 'x = sin(n) y = cos(n)'

'?', 'Collatz algorithm starting from 27, returning the nth element'

The left of each pair can be queried for if a given number is part of the set, from the first example '4 mod 2 = 0' and the answer in this case is yes. This is usefull but it may take forever to find even one number from a set with only a few elements.

The right part represents the same set but can be queried for a number from the set in no particular order, so for example to get 5 numbers from the set is easy and fast but one can't ask if a given number is part of the set easily if at all for a set of infinite size.

Can I convert between thease two forms, if so then how?


old form of the question

'n mod 2 = 0' can be plotted to show a row of equally spaced peeks (where peak is a word I use to mean a value of true sorrounded by values of false), you can ask if a given position is a peek by replacing n with the value you want like this '2 mod 2 = 0', in this case yes, there is a peak at position 2. The equation can presumably be rearranged to get the position of the n'th peek, for example 2n would work.

These two different approaches can apparently be referred to as push and pull methods of getting the information.

Is there a way to convert between these two ideas?

'n mod 2 = 0' <-> '2n'

A less trivial example:

x = sin(n) y = cos(n) Wolfram Alpha

sqrt(x^2+y^2) = 1 Wolfram Alpha

Where the first version gives every part of the outside of the circle when run for every possible n and the second version gives if a position is on the outside of the circle.

goo.gl/wZ9Ox, goo.gl/2W6uU

Returning to the first example. Completing all peaks using '2n' to find out if any lay on a given position would take forever, however you may only have an algorithm that works by repeatedly placing a peak and moving forward two units and you may not know about the mod function or that 'n mod 2 = 0' is the reverse of your algorithm.

A more complicated but perhaps meaningfull example is a en.wikipedia.org/wiki/Collatz_conjecture starting from a given number might go on forever, or for a very long time, described algorithmically it is like 'n2' in the first example but if we want to know if a given number is part of the sequence then we need the 'n mod 2 = 0' version of the equation.

share|improve this question

closed as not a real question by Potato, Andres Caicedo, Asaf Karagila, t.b., Zev Chonoles Jun 22 '12 at 23:09

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

8  
I can't figure out what is being asked here. –  Ross Millikan Feb 12 '11 at 17:08
    
Do you understand how 'x = sin(n), y = cos(n)' and 'sqrt(x^2+y^2) = 1' can both result in a circle but how thease two forms have differnt properties regarding how they can be queried? –  alan2here Feb 12 '11 at 17:19
    
Yes, but talk of a row of peaks has me baffled, as does push and pull methods of getting information. Certainly you have parameterized a circle (though n is usually a whole number), but both versions should be on the circle. Presumably the goo.gl are intended as links to graphics, but they don't link. –  Ross Millikan Feb 12 '11 at 17:35
    
I think what is being alluded to here is going from an expression to a parametrisation of its set of zeroes, e.g. from "x mod 2 = 0" to "{2n | n in Z}" and from "x^2 + y^2 = 1" to "{(sin(t), cos(t)) | t in R}". And in the other direction. The question presumably is about whether there is a way to go from one form to the other in general, for some meaning of 'general'. –  ShreevatsaR Feb 12 '11 at 17:44
1  
Yes ShreevatsaR, thats right. How can one convert from an expression to a parametrisation of that expressions set of zeroes or from a parametrisation of a set of zeroes to an expression. I think that wording reads correctly, please tell me if not as there are words in that last sentance that I havn't used before. –  alan2here Feb 12 '11 at 18:24
show 2 more comments

2 Answers 2

You seem to be talking about implicit and explicit descriptions of sets. Implicit ones are descriptions of sets like $A = \{ n \in \mathbb{N} | n \equiv 0 (\mod 2) \}$ or $B = \{ (x,y) \in \mathbb{R}^2 | x^2 + y^2 = 1 \},$ while explicit (think: closed-form) ones are `parametrisations' $n \mapsto 2n$ or $z \mapsto (\cos z,\sin z).$ What I think you're trying to say with the 'reverse' algorithm, is that in general you don't have a way to generate a surjective parametrisation, i.e. one which covers the entire set (for example: if you just take natural numbers and take $n \mapsto (\cos n, \sin n)$, you'll almost get the circle (technically: a dense subset), but not the entire thing. With the mod 2-thing, you will get the entire set A, since the equation n = 0 (mod 2) just means that n is even, and every even integer can be written as n = 2k for some k. Hope this helps!

share|improve this answer
    
So how does one generate a surjective parametrisation like 'n mod 2 = 0' from an algorithm like 'start at 0, keep (add 2 and store) forever' or equation '2n'? –  alan2here Feb 12 '11 at 19:08
    
Can't find much on surjective parameterization. –  alan2here Feb 12 '11 at 20:17
add comment
up vote 0 down vote accepted

I got help elsewhere about this in the end. Here is the answer:

Decidable sets allow one to determine if a given element is in the set.

Enumerable sets have an effective procedure that will produce all elements in the set.

Some sets are both decidable and enumerable.

There are various relationships between decidability and enumerability such as that every decidable set is theoretically if not practically enumerable.

There are no general non brute force ways of converting between decidable and enumerable definitions of sets.

There are however lots of specific ways, for example there is a method for conic equations which could be used between "x^2 + y^2 = 1" and "x = sin(n), y = cos(n)".

share|improve this answer
1  
You must have found a psychic or something. As asked here, the question is unintelligible. \ –  The Chaz 2.0 Mar 6 '12 at 5:53
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.