# Questions tagged [set-theory]

Set theory is the branch of mathematics that studies unordered collections of objects. Challenges with this tag will involve the manipulation or analysis of sets.

35 questions
Filter by
Sorted by
Tagged with
2k views

### N-Dimensional Cartesian Product

Introduction The Cartesian product of two lists is calculated by iterating over every element in the first and second list and outputting points. This is not a very good definition, so here are some ...
325 views

### Surreal Numbers

Surreal Numbers Surreal numbers are one way of describing numbers using sets. In this challenge you will determine the value of a surreal number. Intro A surreal number consists of two sets: a left ...
1k views

### Does this Set Represent a Natural Number?

In set theory, the natural numbers $\mathbb{N} = \{0, 1, 2, 3, ...\}$ are usually encoded as pure sets, that is sets which only contain the empty set or other sets that are pure. However, not all ...
729 views

### Compute the superset

Your task here is simple: Given a list of integer sets, find the set union. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no ...
808 views

### Number of surjections

Task Given 2 positive integers n and k, where n > k, output the number of surjections ...
1k views

### Verify Topology

Challenge Given a set T of subsets of a finite set S={1,2,3,...,n}, determine whether T is ...
913 views

### Golf a bijection within the natural numbers which map the primes to a proper subset of the primes

Definitions A bijection from a set S to a set T is a function from S to ...
2k views

### Cartesian product of two lists

Task Given two lists of characters, output their Cartesian product, i.e. the list of pairings of each letter from the first list with each letter from the second list. Example ...
169 views

### Find Subset Factors

Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example ...
698 views

### ASCII-Art Venn Diagram

Given two lists that contain no duplicate elements a and b, find the crossover between the two lists and output an ASCII-Art ...
679 views

### Venn Diagram Cells

Given multiple sets, e.g. s1={2,3,7}, s2={1,2,4,7,8} and s3={4,7}, a Venn diagram visualizes ...
5k views

### Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one

Write a program (or function) that exhibits four common big O time complexities depending on how it is run. In any form it takes in a positive integer N which you may assume is less than 231. When ...
1k views

### Uniquify Identifiers

Introduction By definition, unique identifiers should be unique. Having multiple identifiers that are the same causes one to retrieve unexpected data. But with data arriving concurrently from ...
286 views

### Greedily partition the list of combinations with repetition

First, a few definitions: Given n and k, consider the sorted list of multisets, where for each multiset we choose ...
2k views

### Construct the natural numbers with sets

This construction is a way of representing the Natural Numbers. In this representation, 0 is defined as the empty set and for all other numbers, n is the union of {0} and {n-1}. For example to ...
501 views

### Solve Math Problem Notation

Imagine I have an infinite number of homework problems (!) each given an integer number. Math Problem Notation is a notation for describing subsets of the problem using problem specifiers. An MPN ...
3k views

### As Easy As A-B-C

Input A string that contains at most one of each of the letters A, B, and C. They may be in ...
1k views

### Natural construction

The natural numbers including 0 are formally defined as sets, in the following way: Number 0 is defined as the empty set, {} For n ≥ 0, number n+1 is defined as n ∪ {n}. As a consequence, n = {0, 1, ...
3k views

### Is it a sum-free set?

A set is sum-free if no two (not necessarily distinct) elements when added together are part of the set itself. For example, {1, 5, 7} is sum-free, because all ...
316 views

Remember that a set is unordered without duplicates. Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, ...
808 views

### Laver table computations and an algorithm that is not known to terminate in ZFC

The Laver tables provide examples of programs which have not been shown to terminate in the standard axiomatic system of mathematics ZFC but which do terminate when one assumes very large cardinal ...
462 views

### Map a list of indefinite size to a number!

It is well known, in the field of Mathematics studying infinity, that the Cartesian product of any finite amount of countable sets is also countable. Your task is to write two programs to implement ...
900 views

### set intersection of two lists

Your goal is to compute the set intersection of two lists of integers. The intersection is defined as the unique un-ordered group of integers found at least once in both input list. Input The input ...
260 views

### Set Theoretic Arithmetic (+ and *) [closed]

Set Theoretic Arithmetic Premise There have been a couple challenges already that involve multiplying without the multiplication operator ( here and here ) and this challenge is in the same vein (...
107 views

### Pythy Finite Ordinals [duplicate]

Write a program in any language that takes a single natural number n as input and generates a Pyth program that, in turn, produces, using nested lists, the nested set given by S(n), where: S(0) = ∅ ...
260 views

### Maximally extend integer intervals

Suppose you are given a set of non-intersecting intervals of integers [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Where [a,b] is the ...
738 views

### Print the intersection of sequences

Sequences You are given four number sequences, numbered 1 through 4. OEIS The location of 0...
911 views

### ¿Yo Quiero jQuery?

The Setup You are given a simple web page with 11 elements: 10 input elements with IDs i1 thru ...
6k views

### Golf a Venn Diagram generator

Golf a Venn Diagram generator In order to properly celebrate John Venn's 180th birthday, today your task will be creating a program that outputs a Venn Diagram! Input: A positive integer ...
807 views

### Permutation Numbering

The Challenge For a given set of n integers, write a program which will output its lexicographic index. The Rules The input must only be a set of unique non-negative integers separated by spaces. ...
767 views

### Operations on Sets

Note: I have accepted an answer, but I'm willing to accept a better answer if it comes. Write a program that computes operations on sets. You may take input either from standard input or from command ...
2k views

### Length of String Using Set Theory

From Wikipedia Set-theoretic definition of natural numbers The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ ...
1k views

### Sum of Products of Subsets

Given an integer k and a list of integers A of size n, find the product of all subsets in A of size k and sum them together. For example, k = 2 n = 4 A = 1 2 3 4 ...