Idiomatic way to express set equality in XPath 2.0

An interesting and well-asked question! In my opinion, using every and satisfies to overcome the existential properties of sequence comparisons is a very valid and canonical enough method.

But since you are asking about another approach: How about sorting the sequences before comparing them with deep-equal()? Let us assume two sequences in the following stylesheet:

<?xml version="1.0" encoding="UTF-8" ?>
<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0">
    <xsl:output method="text"/>

    <xsl:variable name="A" select="('a','b','c')"/>
    <xsl:variable name="B" select="('a','c','b')"/>

    <xsl:template match="/">
      <xsl:choose>
          <xsl:when test="deep-equal($A,$B)">
              <xsl:text>DEEP-EQUAL!</xsl:text>
          </xsl:when>
          <xsl:otherwise>
              <xsl:text>NOT DEEP-EQUAL</xsl:text>
          </xsl:otherwise>
      </xsl:choose>
    </xsl:template>

</xsl:transform>

And of course, this transformation returns

NOT DEEP-EQUAL

But if you sort the sequences before comparing them, for instance with a custom function that makes use of xsl:perform-sort, see the relevant part of the specification:

<?xml version="1.0" encoding="UTF-8" ?>
<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="2.0"
    xmlns:local="www.local.com" extension-element-prefixes="local"
    xmlns:xs="http://www.w3.org/2001/XMLSchema">
    <xsl:output method="text"/>

    <xsl:variable name="A" select="('a','b','c')"/>
    <xsl:variable name="B" select="('a','c','b')"/>

    <xsl:template match="/">
      <xsl:choose>
          <xsl:when test="deep-equal(local:sort($A),local:sort($B))">
              <xsl:text>DEEP-EQUAL!</xsl:text>
          </xsl:when>
          <xsl:otherwise>
              <xsl:text>NOT DEEP-EQUAL</xsl:text>
          </xsl:otherwise>
      </xsl:choose>
    </xsl:template>

    <xsl:function name="local:sort" as="xs:anyAtomicType*">
        <xsl:param name="in" as="xs:anyAtomicType*"/>
        <xsl:perform-sort select="$in">
            <xsl:sort select="."/>
        </xsl:perform-sort>
    </xsl:function>

</xsl:transform>

then, the result will be

DEEP-EQUAL!

EDIT: In fact, set equality would entail that not only order is irrelevant, but also duplicates should not make a difference. Therefore, proper set equality would mean to also apply distinct-values() to the sequence variables:

<xsl:when test="deep-equal(local:sort(distinct-values($A)),local:sort(distinct-values($B)))">

Firstly, it depends on how you assess equality between items, for example do you compare two items using "=", "is", "eq", or "deep-equal"? Your own answer suggests that you're thinking of "=", which is almost the same as "eq" when applied to items, except that it has slightly different conversion rules. And as it happens, it's not a good operator to use with sets, because it's not transitive: untypedAtomic("4") = 4, untypedAtomic("4") = "4", but not(4 = "4"). So let's assume "eq", which is transitive except in corner cases involving numeric rounding of values that are "almost equal".

I'd then be inclined to suggest (as others have done)

deep-equal(sort($A), sort($B)) 

except that some data types (e.g. QNames) have an equality operator defined, but no ordering defined. So this will work for integers and strings, but not for QNames.

Obviously there's the O(n^2) method given in your "impulse" solution, but can one do better?

How about

let $A := count(distinct-values($a))
let $B := count(distinct-values($b))
let $AB := count(distinct-values(($a, $b))
return $A = $AB and $B = $AB

This should be O(n log n).