Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-set-theory]

This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, differences and complements, De Morgan's laws, Venn diagrams, ...

0
votes
1answer
18 views

Order of Set Operations

A particular question states: Show if $A ⊆ B^c$ then $A ∩ B = ∅$. Being very new to set theory, I attempted to start some proof, which appears below, where $S =$ universe of discourse: $$ A \cap B = ...
1
vote
1answer
26 views

Proving Hausdorff maximality principle without Choice

I have heard that it is possible to prove a variant of the Hausdorff Maximality Principle without the axiom of choice. This is called "Hausdorff Maximality Principle for well-ordered partial orders" ...
0
votes
2answers
29 views

Elementary confusion about the universe of sets

Let ${V_0 = \varnothing}$, and recursively define the $\textit{universe of sets}$ by ${V_{n+1} = \mathscr P(V_n)}$. So for example: $${V_0 = \varnothing}$$ $${V_1 = \{\varnothing}\}$$ $${V_2 = \{ \...
-1
votes
2answers
17 views

Test binary relation on the set for reflexivity, symmetry, antisymmetry and transitivity

$$S = (-\infty,-1)$$ $$xRy, 27x^3+9xy^2 \leqslant 27x^2y+y^3$$ Can somebody help me with this, I am new in this field and I don't know how to start.
0
votes
2answers
20 views

for 2 sets, prove this without using venn diagrams or membership tables

How do I prove this without using venn diagrams or membership tables? I don't really understand. can someone help? I meant, I don't know how to solve it without venn diagrams: I can start with let x ...
3
votes
2answers
31 views

Is there an (efficient) algorithm to determine whether an equation of two terms in the language of elementary set theoretic operators is an identity?

By elementary set theoretic operations I refer to those which are usually imaged in Venn diagrams -- union, intersection, set difference, etc. In the formulation of my question I included the word ``...
3
votes
2answers
44 views

Prove a property of a bijective function $f$

Function $f: \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ is a bijection. ($0 \in \mathbb{N}$.) It has the following property: $f(x+y) = f(x) + f(y)$, where $(a,b)+(c,d) = (a+c, b+...
2
votes
3answers
37 views

Proving Equivalence Relations, Constructing and Defining Operations on Equivalence Classes

I think I have an intuitive sense of how ordered pairs can function to specify equivalence classes when used in the construction of integers and rationals, for example. I put the cart before the horse,...
0
votes
1answer
21 views

What does the notation $f[E]$ mean with $f:A\rightarrow B$ and $E \subseteq A$

Context: Show or disprove $f[\cap\chi]=\cap\{f[X]:X\in\chi\}$ for all $\chi\subseteq\mathcal{P}(A)$ with $\chi\neq\emptyset$ I don't know how to start because I don't know what the cornered brackets ...
0
votes
1answer
27 views

Distinct Uncountable Dense Subsets of R

I'm working on Question #5.v in chapter 3.1 of Sidney Morris's Toplogy without Tears. I'm supposed to prove that $\mathbb{R}$ has $2^{\mathfrak{c}}$ distinct uncountable dense subsets. I think my ...
0
votes
1answer
16 views

Set notation for a solution to a simple equation

Solve this equation below and express answer using set notation. $$|x+3|=9$$ My question really isn't about solving this inequality, it is more about the second part of the question, using set ...
0
votes
1answer
15 views

Reformulation of intersection of two unions

I want to prove a relation: $\left(\cup_{i \in I}A_i\right) \cap \left(\cup_{j \in J}B_j \right)= \cup_{i \in I, j\in J}\left(A_i \cap B_j\right)$. Would someone check if the following my attempt is ...
0
votes
1answer
37 views

Is this function $f$ defined uniquely?

Consider function $f: \mathbb{N}\times\mathbb{N} \to \mathbb{N}\times\mathbb{N}$. ($0 \in \mathbb{N}$.) We know that: $f$ is bijective $f((0,1)) = (1,0)$ $\forall x \forall y: x \leq y \implies f(x) \...
1
vote
2answers
27 views

Size of largest subset $F$ of $\mathcal{p}(X)$ such that any two subsets in $F$ intersect no trivially. [on hold]

Help with the following Putnam problem: let $S$ be a finite set, and suppose that a collection $\mathcal{F}$ of subsets of $S$ has the property that any two members of $\mathcal{F}$ have at least one ...
0
votes
1answer
23 views

How to prove by induction that n = m, |X| = n, |Y| = m [on hold]

We have two finite sets X and Y, where |X| = n, |Y| = m, n,m ∈ ℕ. I should show that n = m by induction. For that I should assume that f: X->Y is bijective. In this case it is clear that the ...
0
votes
1answer
33 views

A is a subset of B if and only if (C - B) is a subset of (C - A) (condition: for non-empty set C) [on hold]

How can I prove this phrase by starting from the left side? (start from A is a subset of B)
0
votes
1answer
50 views

Largest separated subset of a finite set

I can see the idea behind the following proof but I cannot express it in a mathematically elegant way...any help? Thanks in advance! Let X = {1, 2, 3, . . . , 2k}. Prove that the largest separated ...
0
votes
1answer
43 views

Proving - set theory

Is x∈ ((A\C) ∩ B) ∪ ((A\B) ∩ C) same as x∈ (AΔC)\B ? I need to prove that $(A\backslash (B \cup C))\cup (C\backslash (A\cup B))$ $=$ $(A\Delta C)\backslash B $ and using 'Let x∈... ...' method I get ...
0
votes
0answers
30 views

Existence of empty set

Empty set does not follow the definition of set, then why it is called a set,it does not contain well-defined collection of objects.
1
vote
2answers
46 views

Proof and problem solving - set theory

Prove that $(A\Delta C)\backslash B = (A\backslash (B \cup C))\cup (C\backslash (A\cup B))$. I tried with an $x$ that can be in $(A\Delta C)\backslash B$, so $x$ is in $A \Delta C$ but not in $B$. If ...
1
vote
1answer
29 views

Notation for countable union

I sometimes see the following notation for a countable union of sets: $\bigcup_{n\in\omega}E_n$ Is this notation strictly synonymous with the more standard $\bigcup_{n\in\mathbb{N}}E_n$?
-1
votes
3answers
21 views

Prove $A\ \triangle\ B = A^\prime\ \triangle\ B^\prime$, where $\triangle$ is the symmetric difference, and $X^\prime$ is the complement of $X$

Help prove that the symmetric difference of the sets is equal to the symmetric difference of the complements of these sets. That is, that $$A\ \triangle\ B = A^\prime\ \triangle\ B^\prime$$ Thank you ...
2
votes
1answer
33 views

Disjoint Events iff $P(A \cap B) = 0$

I found for example here that: $A$ and $B$ are disjoint iff $P(A\cap B) == 0$. I don't understand why. Take for example: $A = \{$"rolling a six-sided dice a 7 shows up"$\}$ $B = \{"$rolling a six-...
4
votes
4answers
62 views

Why is $\{-1,1\}^{\mathbb{Z}^2}$ not countable?

People at my class acted like it was obvious, but I am not that sure: Why is this set not countable? $$\{-1,1\}^{\mathbb{Z}^2}$$ So, this set contains all the functions from $$\mathbb{Z}^2\to\{-1,...
5
votes
1answer
57 views

How many $S\subseteq\mathcal{P}(A)$ contain each element of $A$ an even number of times?

Let $A=\{1,2,...,n\}$. Let the powerset of $A$ be $\mathcal{P}(A)$. We call $S\subseteq \mathcal{P}(A)$ a paired family of subsets if $\forall a\in A$, the number of elements of $S$ that contain $a$ ...
0
votes
1answer
12 views

Set Inverse Based on Mapping [on hold]

If I have a set R where R: A <-> B (i.e R is a set that relates the type A to the type B) and I have a set ...
-2
votes
0answers
57 views

I have question on my math homework for set [on hold]

How many pairs of subsets $A, B \subseteq [n]$ are there such that $A \cap B \not=\emptyset$.
0
votes
1answer
42 views

Intersection of infinite number of sets

Assume I have infinite number of sets such as $\left[1,\infty\right),\left[2,\infty\right),\left[3,\infty\right),...$.Any number in such set is natural. What is intersection of them: $S = \left[1,\...
2
votes
2answers
55 views

Why is $\bigcap_{x\in\mathbb{R}}\mathbb{N}=\mathbb{N}$?

$\bigcap_{x\in\mathbb{R}}\mathbb{N}=\mathbb{N}$ The generaldefinition of Intersection/Union is, that you have a indexset and an Array of sets $(A_i)$ that can be directly assigned to the index: Let $...
2
votes
1answer
68 views

Comparing enumerations on the same infinite set

Given two enumerations $A:S \to \mathbb{N}$, $B:S \to \mathbb{N}$ on the same countably infinite set $S$, are there infinitely many elements $s \in S$ with $A(s) \geq B(s)$? My feeling is that there ...
0
votes
0answers
28 views

C.Pinter A book of set theory, EX 3.3.11

Let G and H be equivalence relations in A. Prove that each equivalence class modulo G ∩ H is the intersection of an equivalence class modulo G with an equivalence class modulo H. More exactly, $$(G\...
0
votes
3answers
45 views

Proving Set Equality $A=B$

I have the following question: $$\text{Suppose $A,B,C$ are sets so that $A \cap C = B \cap C $ and $A \cup C=B \cup C$. Prove that $A=B$.}$$ My question is that the way I am doing it seems rather ...
0
votes
1answer
72 views

What is the point of defining relations in terms of other relations in mathematics?

I was reading the following set of notes on logic (page 84 of paper pdf) and came a across a rather simple definition but was unsure what it meant conceptually: I think I understand the proof (it ...
0
votes
2answers
33 views

Bijection between two infinite sets [duplicate]

I am trying to get right answer to question: Can you make bijection between set ℝ\{-3} and set ℝ? I know those two sets are not same size but I think I can still make bijection, but I need ...
1
vote
0answers
24 views

Showing that the class of finite subsets of a well-ordered class can be well-ordered

We know that if $(X, <)$ is a well-ordered class, then $\mathcal{P}(X)$ can be totally ordered by the following: $$A<^*B\ \text{iff min}(A\Delta B) \in A $$ where $\Delta$ is the symmetric ...
1
vote
1answer
42 views

Without the Axiom of Choice, is there a bijection between $\mathcal{P}(\aleph_\alpha)$ and $\mathcal{P}(\aleph_\alpha \times \aleph_\alpha)$?

My question is about finding a bijection between $\mathcal{P}(\aleph_\alpha)$ and $\mathcal{P}(\aleph_\alpha \times \aleph_\alpha)$ without the axiom of choice. This is an unproved statement in an ...
-3
votes
2answers
39 views

Define the relation $\sim$ on $A \times A$ by $(a, b) \sim (c, d) \iff abcd ≥ 0$. Show that $\sim$ is an equivalence relation.

Let $A = \mathbb Z \setminus \{0\}$ be the set of nonzero integers. Define the relation $\sim$ on $A \times A$ by $$(a, b) \sim (c, d) \iff abcd ≥ 0.$$ Show that $\sim$ is an equivalence relation. I ...
1
vote
1answer
23 views

Strange Notation for Collection of Sets

My professor used this notation for a collection of sets: $\{A_{\lambda} \}_{\lambda}$. What's the purpose of this extra subscript on the right curly bracket? I usually just go with $\{A_\lambda\}$ ...
1
vote
2answers
76 views

How shall I understand what the GNU utilities “comm” and “diff” do in terms of ordered sets?

I am looking for some help to understand two GNU utility programs in terms of ordered sets. If you happen to know their usages, you might be able to understand what I am asking here. In mathematics, ...
-2
votes
0answers
31 views

Brute Force AES and/ RSA with mathematical explanation, input from math guru?

Does a cryptography expert knowledgable with math have a explanation on: The amount of time it takes to brute force AES-$N$ bit with a password with combinations $A^N$, where $A$ is the number of ...
-2
votes
1answer
24 views

Proof that $((A\setminus B)\setminus (B\setminus C))^{c} = A^{c} \cup B$ [closed]

I'm lost in this question, how can I deal with multiple complements and differences?
0
votes
4answers
51 views

Bijective map between two finite sets is equivalent to the same cardinality

Let $X$ and $Y$ be two finite sets with cardinalities $|X| = n, |Y | = m$ respectively, where$ n,m \in \mathbb{N}$. Further assume $f : X \to Y$ to be bijective. Show that $n = m$. Hint: ...
1
vote
0answers
27 views

Applying Dilworth's theorem to 50 intervals in R

Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point. I think it is quite obvious I need to apply Dilworth's theorem to my ...
1
vote
0answers
57 views

$\text {dom}(R)$ and $\text {ran}(R)$ exists for any definition of order pair.

Suppose that we define, for any sets $x,y$, a set $(x,y)$ with the propertie that $$(x,y)=(x',y')\rightarrow x=x'\wedge y=y'(*)$$ Let $R$ be a set. I want to show that the classes $\{x:\exists y((x,y)...
0
votes
0answers
32 views

Can I bound universal set [closed]

Let Universe U={ A1,A2,A3, ... An} be a set of Facebook groups(i.e. A1, A2.... are representing a group), and E={e1,e2,e3} be a set of information. according to a "soft set theory," I am going to make ...
0
votes
1answer
48 views

Sheave of sets, what does $\{f_i \} \mapsto \{f_i \mid_{U_i \cap U_j}\}$ mean?

... for an open covering $U = \bigcup U_i$, an $I$-indexed family of functions $f_i : U_i \to \Bbb{R}, \ i \in I$, is an element of the product set $\prod_i CU_i$, while the assignments $\{f_i\} \...
-3
votes
1answer
33 views

When any function is applied to the output of any even function, is it odd or even? Explain [duplicate]

I only need a couple of sentences to explain, but I don't know how to word it, please help! I do not need an algebraic proof, just a sentence or two to explain why the output is always even.
2
votes
2answers
52 views

How do we formally define “j-th smallest element”?

Let $A$ be a nonempty finite subset of $\mathbb{R}$. Firstly, let me write down how to define the term "the smallest element of $A$" formally. Suppose 'for every $x\in A$, there exists $y \in A$ ...
-1
votes
0answers
39 views

A coherent general definition of an $n$-ary relation?

I know most people define a finitary relation as a subset of a Cartesian product of a finite number of sets: $$R\subseteq S_1\times S_2\times\cdots\times S_n$$ I used to do this too but I have ...
-1
votes
5answers
41 views

What does this set mean: $ \{ g \mid g : \{0,1\} \rightarrow \mathbb{N} \} $

I have an excercise and there is the set $ \{ g\mid g : \{0,1\} \rightarrow \mathbb{N} \} $. Now I wanted to know, that this set mean? What's the content of it? I know normal sets very well but in my ...