Set Language

From Esolang
Jump to: navigation, search

It's recommended that you have at least a passing knowledge of set theory before reading this. You should also have significant knowledge of it before adding to it. My knowledge is lacking, so please help.

I got the idea when I read a mention of hypothetical real computation on Wikipedia, and thought about expanding it to functions, and then decided to go all the way and just use sets.

Constructions

There is only one data type: the set. The rest are constructions of the set.

If I mention a set later on, you probably shouldn't be using a construction, but it will still run. If any construction works, I'll call it a construction.

Sets

A set is composed of other sets, unless it's the null set, which is empty. A set can't contain itself. There can't be more than one of a given set in another set, and order doesn't matter.

Ordinal Numbers

This includes natural numbers, but also includes transfinite numbers, such as omega.

An ordinal number is expressed as the set of all lower ordinal numbers. 0 is the lowest, so it's the null set={}. 1 is {0}={{}}. 2 is {0,1}={{},{{}}}. Etc.

The compiler will automatically change them to the correct set when written normally.

Ordered Pairs

A pair of sets, in order. These are expressed {{a},{a,b}}, and can be written (a, b) as shorthand.

<<ordered pair> can be used to refer to the first element, and ><ordered pair> can be used to refer to the second.

Functions

These produce zero or one outputs for a given input. They need a better name. (Try "Predicates".) I'll call them functions for now.

They are formally defined as a set of two-element sequences in which the first element of each sequence is unique.

There is no special way to write them, but you can just use {(a, b), (c, d), ...}

Sequences

Like a set, but order matters and there can be repeat elements. They can only have countably infinite elements.

These are functions that map natural numbers (finite ordinal numbers) to something else.

These are written <a, b, c, ...>.

Types

This is just a bunch of constants used to represent what kind of construction something is. It includes NAT, ORD, INT, FRAC, REAL, SEQ, FUNC, PAIR, etc. for natural numbers, ordinal numbers, integers, fractions, real numbers, sequences, functions, etc.

Some of these are just natural numbers, but when possible, this uses the set of all possible members. For example, NAT is the set of all natural numbers. This can't be done for some, such as FUNC, since any set can be a member of a function, and you can't have a set with all the sets in it. It would contain itself.

Constants

TRUE = {{}}

FALSE = {}

NULL = {}

OMEGA = NAT = The set of all natural numbers

Methods

for

for(<variable>, <sequence>, <output sequence>, <local variables>) {
 <code>
}

First, it runs the code using the first element of the sequence as the variable and makes the resulting construct the first element of the output sequence. Next, it runs the code using the second element of the sequence as the input variable and makes the resulting construct the second element of the output sequence. This goes on with every element in the sequence. After that, the program continues normally. Using a finite sequence is not required. Elements omega and above aren't used. The code in the method may only change the local variables declared in the method.

seq

seq(<cardinal number>)

Returns a sequence of all the cardinal numbers up to that, in order. Useful in combination with for.

unseq

replace

replace(<variable>, <input set>, <output set>) {
 <code>
}

Runs the code with each element of the input set as the variable, and sets the output set to the union of all the results.

NOTICE: if you are attempting to make an implementation of this language, do not use the for operation for this. It only allows a countably infinite number of values, while replace has no such limit. Also, DO NOT underestimate the size a set can be. The number of moments in an eternity is not enough. Neither is the number of possible curves. Not all infinities are alike.

if

if(<boolean>){
 <code>
}

Runs <code> if <boolean> is anything except {}.

User-Defined Methods

These must be declared beforehand as so: method <method name>(<variables>) <code> end

They are run from the main method with <method name>(<constructions>, <natural number>, <construction>)

The code is run setting the variables to the corresponding constructions.

The natural number is the maximum number of times a method can recursively invoke itself. The construction is what the method returns if it runs out of layers. This is to insure that all programs halt. This doesn't hurt the effectiveness of this language nearly as much as it seems, due to the ability to find the limit as the natural number increases without limit.

Operations

belong

belong(<construction>, <set>) checks to see if the construction is an element of the set. Returns TRUE if it is, and FALSE if it isn't.

power

power(<set>) returns a set containing a set with each combination of elements in the input set.

evaluate

<function>[<construction>] inputs the construction into the function, and outputs the output. If there is no corresponding input, the output is undefined.

This can also be used to reference something from an ordered list.

boolean

<set>|<set> returns the union of the sets.

<set>&<set> returns the intersection of the sets.

<set>&!<set> returns the set containing the elements of the first set that are not in the second.

<set>^<set> returns the set containing the elements that are only in one set. A^B is the same as (A|B)&!(A&B).

The same commands can be repeated twice for boolean logic. For example, <boolean>||<boolean> returns TRUE if either boolean isn't {}.

Also, these can be used with one set, in which case it does it with all the subsets. For example |<set> returns all the set containing all the elements in each subset. ^<set> contains the elements that are in an odd number of the subsets.

arithmetic

+,-,*,/,%,==,>,<,>=,<=, etc. all work as expected on natural numbers, integers, rational numbers, real numbers, hyperreal numbers, functions, etc. as they're normally constructed, with the exception that / gives rational numbers when given integers, and gives unsigned rational numbers when given natural numbers. The language keeps track of what they're defined as. If you want to use it as if it's a different kind of number, use (<type>) to typecast.

assignment

<variable> = <construct> Assigns the construct to that variable. The variable does not need to be declared beforehand. You can think of it as every possible variable already having been declared. There's certainly enough memory.

is type

is(<construction>, <TYPE>) checks to see if construction is of type TYPE. It doesn't matter how it was declared. For example, is({{{}}}, PAIR) would return TRUE, because it could be interpreted as the pair ({},{}).

element

element(<set>) returns an element of the input set. If the input is the null set, so is the output. Which element is chosen is undefined, and may or may not be consistent on multiple runs of the program.

choice

choice(<set>) returns a set containing every function that contains an input for each element in the input set and an corresponding output that is an element of the set. Which elements are chosen is undefined, and may or may not be consistent on multiple runs of the program.

Libraries

Libraries are necessary for input and output. They are also useful for using constructions that don't come with the language.

Oracle

oracle.h contains useful oracles for the construction of oracle machines. They are functions. Notably, it has the sets of all the programs that halt in a large number of languages, such as Banana Scheme, and the very controversial oracle: FREE_WILL.

Random

random.h only exists on non-deterministic machines. If you have a deterministic one, you can download something from the random<size>.h series, which contains <size> random numbers. Unfortunately, it's impossible to have a set large enough to be guaranteed. Usually you can tell from the program how many you'll need.

Examples

Hello World

#include <stdout.h>
method main()
  replace(x, REAL, plane)
    replace(y, REAL, line)
    with (x, y)
  with line
  replace(point, plane, hello_world)
    output = NULL
    //H
    if((point[0]==0.)&(point[1]>=0.)&(point[1]<=2.))
      output = point
    end
    if((point[1]==1.)&(point[0]>=0.)&(point[0]<=1.))
      output = point
    end
    if((point[0]==1.)&(point[1]>=0.)&(point[1]<=2.))
      output = point
    end
    //e
    ...
  with(output)
  out_cartesian(plane)
return(0)

Find Limit

method find_limit(real sequence)
  replace(x, REAL, positive)				//Sets positive to the set of all positive real numbers
    if(x<0)
      x=NULL
    end
  with(x)
  replace(limit, REAL, answer)				//Checks every real number to see if it's the answer
    replace(epsilon, positive, output0)		//Checks every positive number to see if
      replace(a, NAT, output1)
        replace(x, NAT, output2)
        with(abs(sequence[x+a]-limit) > epsilon)) //If the limit is found, this is always FALSE. output2 will be FALSE.
      with(!output) //If the limit is found, output2 is at some point FALSE. output1 will be TRUE.
    with(!output) //If the limit is found, output1 is always TRUE. output0 will be FALSE.
    if(output0)
      output = NULL
    else
      output = limit
    end
  with(limit)
return(element(answer)) //REAL includes every way of writing every real number. I just need one way of writing it.

Find Bijections

method biject(set1, set2) {
  replace(x, set1, superfunction) {
    replace(y, set2, x) {
      y = (x, y)
    }
  }
  replace(function, power(superfunction), bijections) {
    replace(x, set1, output1) { //checks to make sure
      replace(pair, function, pair) { //returns all the input/output pairs for the input x
        if(<pair != x)
          pair=NULL
      }
      x = power(pair)!={pair, {}} && pair != NULL //only false if there is exactly one such pair
    }
    replace(y, set2, output2) { //checks to make sure
      replace(pair, function, pair) { //returns all the input/output pairs for the input x
        if(>pair != y)
          pair=NULL
      }
      y = power(pair)!={pair, {}} && pair != NULL //only false if there is exactly one such pair
    }
    if(!output1 && !output2)
      function = NULL
    end
  }
return(element(bijections))

Big Set

function embiggen(current)
  for(x, seq(NAT), NULL, current) {
    x = embiggen(current, OMEGA, embiggen2(current, x, NULL))
//embiggen2 looks exactly like this one, only with embiggen3, and so on.
//This can't continue forever, but it can be any arbitrarily high natural number.
//The last one has power(current) instead of embiggen(current).
  }
return(|current)

See Also