Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Formulation of recursive subset equality

  1. Oct 3, 2012 #1

    I'm currently trying to express the following:

    given a structured set of sets, of the form {1}, {1,{1,1}}, {{1,1},{1,1}}, or {1,{{1,1},1}} etc.

    I want to be able to test whether two sets are reductions of each other, where reduction means, that:
    {1,{1,1} is equal to {1}, or {1,1}, but not {{1,1},1}.

    The logic behind reduction is that I can reduce a subset to a subset of smaller cardinality, or singleton set (so {1,1} is a reduction of {1,{1,1}}. The relation is transitive, so given {1} is a reduction of {1,1} then {1} is a reduction of {1,{1,1}}.

    I think I have the right properties: given two ordered sets A and B, B is a reduction of A

    1) iff A and B contain the same number of subsets, and there is a bijection between the subsets of A and the subsets of B, where the corresponding subset in B is itself a reduction of the corresponding subset in A. (basically what I'm trying to say is that if you have {1,2,3} and {a,b,c} then 1 is linked to a, 2 to b, etc. also works for subsets, where you have {{1,2},3,4} and {a,b,c} where in that case {1,2} is linked with a, 3 with b, and 4 with c)
    2) iff there exists a set R such that B is a reduction of R, and R is a reduction of A.

    Does this definition make sense? And if yes, I'm really struggling to provide formal notation for 1. I'm not very familiar with set notation.

  2. jcsd
  3. Oct 3, 2012 #2
    The definition of a set is a collection with no repetitions and in which order doesn't matter. What you are dealing with are called "sequences." These "reductions" are subsequences of sequences.

    You may define words however you like, but nonstandard definitions are a pointless headache for the reader.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook